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


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 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


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).


Good descision. Now, it's almost obvious what it does. :)


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


files

 but talk about a mess ;-)


I never understood, how the authors of the STL
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


 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).


 Good descision. Now, it's almost obvious what it does. :)


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


 files

 but talk about a mess ;-)


 I never understood, how the authors of the STL
 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