Queue
Trass3r
un at known.com
Tue Aug 10 16:26:02 PDT 2010
> Is there a Queue in Phobos? I can only see a SList on the online
> documentation.
Is this really a coincidence? ^^
I recently opened the very same thread in D.learn.
There seems to be none yet.
---
I found some very old queue code with doubling strategy. Improvements
welcome :D
module queue;
class Queue(T)
{
private:
T[] data;
uint head=0;
uint tail=0;
public:
this(uint size)
{
data.length=size;
}
this()
{
data.length=16;
}
void enqueue(T elem)
{
uint tt = (tail+1) % data.length;
if (tt != head) // free
{
data[tail]=elem;
tail=tt;
}
else // double it
{
uint m = data.length;
T[] newdata;
newdata.length=m * 2;
for(uint i=0; i<m-2; i++)
newdata[i] = data[(head+i)%m]; // copy entries
data=newdata;
head=0;
tail=m-1;
data[tail]=elem;
tail++;
}
}
T first()
in
{
assert(hasElements());
}
body
{
return data[head];
}
T dequeue()
in
{
assert(hasElements());
}
body
{
T tmp = data[head];
head = (head+1)%data.length;
return tmp;
}
bool hasElements() {return head!=tail;} // hasElements property
}
More information about the Digitalmars-d
mailing list