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

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

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

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

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

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

"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