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