Implements a PriorityQueue collection in D.

priorityqueue.d

module priorityqueue;

private import std.array : front, popFront;

public class PriorityQueue( _ElemType )
{
	public alias _ElemType ElementType;
	
	public enum SortMode : ubyte
	{
		/+
			The queue will not be sorted by priority,
			forcing it to behave like a standard FIFO
			(first-in, first-out) collection.
		+/
		None,
		
		/+
			OnDemand sorting will ensure the queue is
			sorted by priority only when attempting to
			dequeue an item. Useful if you need to
			rapidly enqueue a large number of items
		+/
		OnDemand,
		
		/+
			Immediate sorting will ensure the queue is
			sorted by priority immediately after an
			item is added. Useful if you need to
			rapidly dequeue a large number of items.
		+/
		Immediate
	}
	
	protected struct PriorityElement( T )
	{
		public T Item;
		public int Priority;
	}
	
	protected alias PriorityElement!_ElemType Element;
	
	protected Element[] elements;
	protected SortMode pMode;
	
	public SortMode Mode() @property
	{
		return this.pMode;
	}
	
	public void Mode( SortMode mode ) @property
	{
		if( mode == SortMode.Immediate )
			this.Sort();
		
		this.pMode = mode;
	}
	
	public int Count() @property
	{
		return this.elements.length;
	}
	
	public this( SortMode mode = SortMode.OnDemand )
	{
		this.pMode = mode;
	}
	
	public void Enqueue( _ElemType item, int priority )
	{
		this.elements ~= Element( item, priority );
		
		if( this.Mode == SortMode.Immediate )
			this.Sort();
	}
	
	public _ElemType Dequeue()
	{
		if( this.Mode == SortMode.OnDemand )
			this.Sort();
			
		_ElemType item = this.elements.front.Item;
		this.elements.popFront();
		
		return item;
	}
	
	public bool TryDequeue( ref _ElemType item )
	{
		if( this.Count == 0 )
			return false;
		
		item = this.Dequeue();
		return true;
	}
	
	public int GetPriority( _ElemType item )
	{
		foreach( Element element; this.elements )
			if( element.Item == item )
				return element.Priority;
		
		throw new Exception( "The queue does not contain a matching element." );
	}
	
	public alias Enqueue Push;
	public alias Dequeue Pop;
	public alias TryDequeue TryPop;
	
	protected void Sort()
	{
		this.elements = this.Sort( this.elements );
	}
	
	protected Element[] Sort( Element[] unsorted )
	{
		//Custom implementation of the QuickSort algorithm.
		if( unsorted.length < 2 )
			return unsorted;
		
		Element pivot = unsorted[0];
		Element[] first, second;
		
		foreach( Element item; unsorted[1 .. $] )
			if( item.Priority <= pivot.Priority )
				first ~= item;
			else
				second ~= item;
		
		return this.Sort( first ) ~ pivot ~ this.Sort( second );
	}
}