www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - double-ended queue (deque)

reply Ben Hinkle <bhinkle4 juno.com> writes:
For those who can't wait for DTL, or for those who just need a simple
double-ended queue, I've put a deque.d at

 http://home.comcast.net/~benhinkle/deque.d

It is implemented as a single dynamic array so slicing and manipulating it
like an array is very easy and "D-like". I figured no iterator is needed
for it. The resizing algorithm is the messiest part but right now it is
pretty simple. I looked around on the web a little before making it so
apologies someone already wrote a deque and I missed it. Feedback welcome.

-Ben
May 03 2004
parent reply "Jan-Eric Duden" <jeduden whisset.com> writes:
Shouldn't the capacity of the deque grow exponentially?

Right now, complexity of adding elements is O(n) where n is the size of the
deque. (because of the copying)
If the capacity of deque grows exponentially it is only O(log n).
AFAIK the STL does the same.
-- 
Jan-Eric Duden

"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:c770lv$1cbm$1 digitaldaemon.com...
 For those who can't wait for DTL, or for those who just need a simple
 double-ended queue, I've put a deque.d at

  http://home.comcast.net/~benhinkle/deque.d

 It is implemented as a single dynamic array so slicing and manipulating it
 like an array is very easy and "D-like". I figured no iterator is needed
 for it. The resizing algorithm is the messiest part but right now it is
 pretty simple. I looked around on the web a little before making it so
 apologies someone already wrote a deque and I missed it. Feedback welcome.

 -Ben

May 04 2004
parent reply "Jan-Eric Duden" <jeduden whisset.com> writes:
Never mind... the code actually does it...
The ensure_size function is really messy. ;)
-- 
Jan-Eric Duden
"Jan-Eric Duden" <jeduden whisset.com> wrote in message
news:c77hm4$26dd$1 digitaldaemon.com...
 Shouldn't the capacity of the deque grow exponentially?

 Right now, complexity of adding elements is O(n) where n is the size of

 deque. (because of the copying)
 If the capacity of deque grows exponentially it is only O(log n).
 AFAIK the STL does the same.
 -- 
 Jan-Eric Duden

 "Ben Hinkle" <bhinkle4 juno.com> wrote in message
 news:c770lv$1cbm$1 digitaldaemon.com...
 For those who can't wait for DTL, or for those who just need a simple
 double-ended queue, I've put a deque.d at

  http://home.comcast.net/~benhinkle/deque.d

 It is implemented as a single dynamic array so slicing and manipulating


 like an array is very easy and "D-like". I figured no iterator is needed
 for it. The resizing algorithm is the messiest part but right now it is
 pretty simple. I looked around on the web a little before making it so
 apologies someone already wrote a deque and I missed it. Feedback


 -Ben


May 04 2004
parent reply Ben Hinkle <bhinkle4 juno.com> writes:
Jan-Eric Duden wrote:

 Never mind... the code actually does it...
 The ensure_size function is really messy. ;)

The scary part is I had a version that was a lot messier and decided to go with the "simple" version. It checks if there is already enough space and slop if there is it centers the data without reallocating and otherwise it reallocates. Plus whenever it reallocates it recenters the data when copying the data to the new array. The scary version was the one that tries to copy the data more to one side or the other depending on which end is growing faster and by how much (assuming past trends predict future trends). I've never looked at what STL impls do - well, ok, I've opened up the files but talk about a mess ;-)
May 04 2004
next sibling parent reply "Jan-Eric Duden" <jeduden whisset.com> writes:
"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:c781a6$2t5j$1 digitaldaemon.com...
 Jan-Eric Duden wrote:

 Never mind... the code actually does it...
 The ensure_size function is really messy. ;)

The scary part is I had a version that was a lot messier and decided to go with the "simple" version. It checks if there is already enough space and slop if there is it centers the data without reallocating and otherwise it reallocates. Plus whenever it reallocates it recenters the data when copying the data to the new array. The scary version was the one that

 to copy the data more to one side or the other depending on which end is
 growing faster and by how much (assuming past trends predict future
 trends).

 I've never looked at what STL impls do - well, ok, I've opened up the

 but talk about a mess ;-)

can actually understand their code and keep it bug free. I hope the authors of the DTL will produce nice code. :)
May 04 2004
parent "Matthew" <matthew.hat stlsoft.dot.org> writes:
"Jan-Eric Duden" <jeduden whisset.com> wrote in message
news:c78cnc$cro$1 digitaldaemon.com...
 "Ben Hinkle" <bhinkle4 juno.com> wrote in message
 news:c781a6$2t5j$1 digitaldaemon.com...
 Jan-Eric Duden wrote:

 Never mind... the code actually does it...
 The ensure_size function is really messy. ;)

The scary part is I had a version that was a lot messier and decided to go with the "simple" version. It checks if there is already enough space and slop if there is it centers the data without reallocating and otherwise it reallocates. Plus whenever it reallocates it recenters the data when copying the data to the new array. The scary version was the one that

 to copy the data more to one side or the other depending on which end is
 growing faster and by how much (assuming past trends predict future
 trends).

 I've never looked at what STL impls do - well, ok, I've opened up the

 but talk about a mess ;-)

can actually understand their code and keep it bug free. I hope the authors of the DTL will produce nice code. :)

You need have no worries there. I've been fighting "flavours" of STL for years. I don't intend to inflict the same degree of pain on DTL users/maintainers/enhancers
May 04 2004
prev sibling parent Eric Anderton <Eric_member pathlink.com> writes:
I've never looked at what STL impls do - well, ok, I've opened up the files
but talk about a mess ;-)

This is a bit off topic, but I once found myself chasing a compile error through hundreds of lines of STL code. I was somwhere between pulling my hair out in frustration and going blind from the unmaintainable mess it was when I found out what was wrong: the Visual Studio 6 compiler has the world's most hoplessly broken template implementation. Thank goodness for D with built in arrays and gc.
May 04 2004