Hey all,

this is yet another post about phobos (missing) data structures ;-)
I know this has been discussed quite a bit - [1,2,3] to name a few.

While it would be nice to have those "trivially to implement" wrappers for some common use cases (map, unordered map, set, multiset, ...) [1], this question focuses solely on dequeues.

It is great that we have DList, so having a circular buffer (aka constrained queue) should be easy.

I do understand that baking this into DList  (as e.g. Python does) might (a) make things more complex or (b) add overhead that isn't needed for every user.

However my question is: why is there not a neat wrapper around DList with a capacity constraint?

Unfortunately we don't have inheritance for structs, but proxying most methods should work too (see e.g [4]).

1) Has anyone else missed deque with capacity constraints?
2) Would such a wrapper fit into phobos?
3) Would you prefer (a) a wrapper around DList [4], (b) around arrays [5] or (c) a "vanilla" circular queue?
(b is slower, but allows indexing)

Best wishes,

[1] https://stackoverflow.com/questions/7162274/why-is-d-missing-container-classes
[2] http://forum.dlang.org/thread/mailman.852.1359488662.22503.digitalmars-d@puremagic.com
[3] http://forum.dlang.org/post/mailman.394.1358112013.22503.digitalmars-d@puremagic.com
[4] http://dpaste.dzfl.pl/d8de9325e9a3
[5] http://rosettacode.org/wiki/Queue/Usage#Faster_Version

On Wednesday, 24 February 2016 at 14:46:12 UTC, Seb wrote:
> Hey all,
>
> this is yet another post about phobos (missing) data structures ;-)
> I know this has been discussed quite a bit - [1,2,3] to name a few.
>
> While it would be nice to have those "trivially to implement" wrappers for some common use cases (map, unordered map, set, multiset, ...) [1], this question focuses solely on dequeues.
>
> It is great that we have DList, so having a circular buffer (aka constrained queue) should be easy.
>
> I do understand that baking this into DList  (as e.g. Python does) might (a) make things more complex or (b) add overhead that isn't needed for every user.
>
> However my question is: why is there not a neat wrapper around DList with a capacity constraint?
>
> Unfortunately we don't have inheritance for structs, but proxying most methods should work too (see e.g [4]).
>
> 1) Has anyone else missed deque with capacity constraints?
> 2) Would such a wrapper fit into phobos?
> 3) Would you prefer (a) a wrapper around DList [4], (b) around arrays [5] or (c) a "vanilla" circular queue?
> (b is slower, but allows indexing)
>
> Best wishes,
>
> [1] https://stackoverflow.com/questions/7162274/why-is-d-missing-container-classes
> [2] http://forum.dlang.org/thread/mailman.852.1359488662.22503.digitalmars-d@puremagic.com
> [3] http://forum.dlang.org/post/mailman.394.1358112013.22503.digitalmars-d@puremagic.com
> [4] http://dpaste.dzfl.pl/d8de9325e9a3
> [5] http://rosettacode.org/wiki/Queue/Usage#Faster_Version

Andrei is working on containers, but struggling with trying to make them @safe without comprimising efficiency or utility, AFAIK. Getting the containers done to his liking may require the work on lifetimes(language supported ref counting) to be complete. IIRC, there was a circular buffer on code.dlang.org somewhere. I've been planning on adding one to my container set(not on code.dlang.org yet) which would be implemented on a contiguous array, with the contents wrapping around as items are added/removed. I believe it's the most efficient approach.

   Bit

On 2/24/16 9:46 AM, Seb wrote:
> Hey all,
>
> this is yet another post about phobos (missing) data structures ;-)
> I know this has been discussed quite a bit - [1,2,3] to name a few.
>
> While it would be nice to have those "trivially to implement" wrappers
> for some common use cases (map, unordered map, set, multiset, ...) [1],
> this question focuses solely on dequeues.

FYI, dcollections has a deque that is based on 2 arrays:

https://github.com/schveiguy/dcollections/blob/master/dcollections/Deque.d

-Steve