PriorityQueue.cs

using System;
using System.Collections.Generic;

/// <summary>
/// Priority queue. All methods are O(1) but Contains() which is O(n).
/// The queue is thread safe.
///
/// Usage:
///   int nbPriority = 3;
///   var queue = PriorityQueue<string>(nbPriority);
///
///   queue.Enqueue("Paris", 2);
///   queue.Enqueue("New York", 2);
///   queue.Enqueue("San Francisco", 1);
///
///   queue.Dequeue(); // result will be: "San Francisco"
///   queue.Dequeue(); // result will be: "Paris"
///   queue.Dequeue(); // result will be: "New York"
/// </summary>
public class PriorityQueue<T> {

	readonly Queue<T>[] queues;
	readonly Object lockObj = new Object();

	public PriorityQueue(int nbPriority) {
		queues = new Queue<T>[nbPriority];

		for (int i = 0; i < queues.Length; i++) {
			queues[i] = new Queue<T>();
		}
	}

	/// <summary>
	/// Returns the number of nodes in the queue.
	/// O(1)
	/// </summary>
	public int Count {
		get	{
			int count = 0;

			lock(lockObj) {
				for (int i = 0; i < queues.Length; i++) {
					count += queues[i].Count;
				}
			}

			return count;
		}
	}

	/// <summary>
	/// Returns the head of the queue, without removing it (use Dequeue() for that).
	/// Throws an exception when the queue is empty.
	/// O(1)
	/// </summary>
	public T Peek() {
		lock(lockObj)
		{
			for (int i = 0; i < queues.Length; i++) {
				if (queues[i].Count > 0) {
					return queues[i].Peek();
				}
			}
		}

		throw new InvalidOperationException("Cannot call Peek() on an empty queue");
	}

	/// <summary>
	/// Removes every node from the queue.
	/// O(n)
	/// </summary>
	public void Clear()
	{
		lock(lockObj)
		{
			for (int i = 0; i < queues.Length; i++) {
				queues[i].Clear();
			}
		}
	}

	/// <summary>
	/// Returns whether the given item is in the queue.
	/// O(n)
	/// </summary>
	public bool Contains(T item)
	{
		lock(lockObj)
		{
			for (int i = 0; i < queues.Length; i++) {
				if (queues[i].Contains(item)) {
					return true;
				}
			}

			return false;
		}
	}

	/// <summary>
	/// Removes and returns the object at the beginning of the queue
	/// If queue is empty, throws an exception.
	/// O(1)
	/// </summary>
	public T Dequeue()
	{
		lock(lockObj)
		{
			for (int i = 0; i < queues.Length; i++) {
				if (queues[i].Count > 0) {
					return queues[i].Dequeue();
				}
			}
		}

		throw new InvalidOperationException("Cannot call Dequeue() on an empty queue");
	}

	/// <summary>
	/// Adds an object to the end of the
	/// If queue is empty, throws an exception.
	/// O(1)
	/// </summary>
	public void Enqueue(T item, int priority)
	{
		if (priority > queues.Length) {
			throw new InvalidOperationException("Out of range priority");
		}

		lock(lockObj)
		{
			queues[priority - 1].Enqueue(item);
		}
	}

}