www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Using DList with capacity constraint (aka circular buffer)?

reply Seb <seb wilzba.ch> writes:
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
Feb 24 2016
next sibling parent bitwise <bitwise.pvt gmail.com> writes:
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
Feb 24 2016
prev sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
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
Feb 24 2016