Deque impl.

[Dmitry Olshansky]

29-Jan-2013 23:44, Robert Schadek пишет:
> Hi,
>
> I have a Deque implementation that I really like. I would like to get
> some comments on it.
> http://dpaste.1azy.net/4bf119e7 dpaste does not run the unittests
> successfully. I don't
> know why. I tested on a x32 as well as x64 machine and it works on both.
>

I skimmed through it what caught my eye instantly: this deque exposes 
too much of operations that are not required of any deque. The end 
result is that it's pretty much always have to be an array (all these 
indexed inserts, removals etc.). To put it plainly it *is* an array.

To be honest deque can be implemented far better if random access as in 
indexing, removal and such is dropped. Canonical interface is:

front
insertFront
removeFront
back
insertBack
removeBack
length (and even this could be dropped sometimes)
empty

That is all. The only extra sugar to add is a bidirectional range over 
it via opSlice() (the one with no args). Then cool stuff like foreach works:
Deque!T deque = ...;
foreach(value; deque)  //calls deque[] -> deque.opSlice() implicitly
{ ...}

What about that better representation I spoke of? Simpler interface 
unties your hands, and in particular you can layout data
as a list (or array) of arrays (pages/block you name it) thus killing 
the need to move data around on insert{Front,Back}.

Calling a type an Iterator and then describing it as a range is bound to 
baffle your users ;)
Another nit is that it's common to just house such types inside of a 
container and call them simply Range i.e. Deque!T.Range.

-- 
Dmitry Olshansky