For a formal test, you can get some inspiration from the unit test of Java's ArrayDeque: https://github.com/openjdk/jdk/blob/master/test/jdk/java/util/concurrent/tck/ArrayDequeTest.java

Thanks for your feedback.

I've been experimenting with A* path finding in Python. That's where I first came across deque. But I want it finally in Delphi and of course, my Delphi doesn't have deque in the library so I had to do a bit of digging. It's a brilliant idea and quite strange that there aren't many more examples online. Luckily for me, your code is clear and logical even without a knowledge of Java.

I made my Move code even smaller by only creating a temp array to hold the items after the right index.

// temp array only needs to store nRight items
nRight := Capacity - RightIndex;
SetLength(temp, nRight);
Move(Items[RightIndex], temp[0], nRight*ItemSize);
Move(Items[0], Items[nRight], RightIndex*ItemSize);
Move(temp[0], Items[0], nRight*ItemSize);
temp := nil;

I tried to crash the code but it seems to hold out. Have you seen some sort of formal test of a deque?

I came up with this...

// test deque
for i := 1 to 128 do begin
for j := 1 to 2+Random(7) do begin
que.Push(500+i);
end;
for j := 1 to 2+Random(5) do begin
que.PushLeft(300+i);
end;
end;
while not que.isEmpty do
write(que.Pop, ',');
writeln(sLineBreak);

So, the output is expected to a 500 series followed by a 300 series.

Hi Bruce,

no I am not *copying* the new array back to "elements". I am merely *assigning* the "elements" variable to point to the new array.

In Java there's no way to change the length of an array, so I have to create a new, bigger one.

In Pascal, the SetLength() method actually does the same: it creates a new array and copies the existing elements into that new array.

Best wishes
Sven

This is what I did...

procedure TDeque.Grow;
{- auto-grow the queue }
var
newCap: integer; // new capacity
nRight: integer; // number of items after Right
delta: integer;
temp: array of integer;
begin
// calculate suitable delta
if Capacity > 64 then Delta := Capacity div 4
else if Capacity > 8 then Delta := 16 else Delta := 4;
newCap := Capacity + delta;

if newCap >= MaxSize then
raise Exception.Create('TDeque: Capacity exceeds size limit!');

// if Right > 0 then
if Right > 0 then begin
nRight := Capacity - Right;
SetLength(temp, nRight);
Move(Items[Right], temp[0], nRight*DataSize);
Move(Items[0], Items[nRight], Right*DataSize);
Move(temp[0], Items[0], nRight*DataSize);
temp := nil;
end;

// adjust Left, Right and Capacity
Left := 0;
Right := Size;
Capacity := newCap;
SetLength(Items, Capacity);
end;