PriorityQueue<T> is a C# implementation of a generic priority queue based on a binary min-heap. This C# implementation provides O(log(n)) time for insertion methods; O(log(n)) time for removal methods; and constant time for retrieval methods. The implementation is derived from the List<T> class, therefore most List<T> methods can also be applied to a PriorityQueue<T>, however, List<T> methods that would destroy the heap condition of the priority queue will throw an InvalidOperationException, e.g. Reverse(). More...

Inheritance diagram for Com.Mission_Base.Pbl.PriorityQueue< T >:

Public Member Functions
void	EnsureHeapCondition (int index)
	Ensures the heap condition for an item in the PriorityQueue<T> at a given index. Call this method after you change the priority of an item in the PriorityQueue<T>.

void	EnsureHeapCondition ()
	Ensures the heap condition for the entire PriorityQueue<T>. Call this method after you change the priority of many items in the PriorityQueue<T>.

	PriorityQueue ()
	Initializes a new instance of the PriorityQueue<T> class that is empty and has the default initial capacity.

	PriorityQueue (IEnumerable< T > enumerable)
	Initializes a new instance of the PriorityQueue<T> class that contains elements copied from the specified collection and has sufficient capacity to accommodate the number of elements copied.

	PriorityQueue (Int32 capacity)
	Initializes a new instance of the PriorityQueue<T> class that is empty and has the specified initial capacity.

	PriorityQueue (IComparer< T > comparer)
	Initializes a new instance of the PriorityQueue<T> class that uses a specified comparer.

	PriorityQueue (IEnumerable< T > enumerable, IComparer< T > comparer)
	Initializes a new instance of the PriorityQueue<T> class that contains elements copied from a specified enumerable collection and that uses a specified comparer.

	PriorityQueue (Int32 capacity, IComparer< T > comparer)
	Initializes a new instance of the PriorityQueue<T> class that is empty, has the specified initial capacity and uses a specified comparer.

void	Enqueue (T item)
	Adds an object to the PriorityQueue<T>, maintaining the heap condition of the queue.

T	Dequeue ()
	Removes and returns the object at the beginning of the PriorityQueue<T>. I.e. an item with the lowest priority from the priority queue, maintaining the heap condition of the queue.

T	Peek ()
	Returns the object at the beginning of the PriorityQueue<T> without removing it. I.e. an item with the lowest priority.

new void	Add (T item)
	Adds an object to the PriorityQueue<T>, maintaining the heap condition of the queue.

new void	AddRange (IEnumerable< T > collection)
	Adds the elements of the specified collection to the PriorityQueue<T>, maintaining the heap condition of the queue.

new void	Insert (int index, T item)
	Inserts an object to the PriorityQueue<T>, maintaining the heap condition of the queue.

new void	InsertRange (int index, IEnumerable< T > collection)
	Inserts the elements of the specified collection to the PriorityQueue<T>, maintaining the heap condition of the queue.

new void	RemoveAt (int index)
	Removes the element at the specified index of PriorityQueue<T>, maintaining the heap condition of the queue.

new bool	Remove (T item)
	Removes the first occurrence of a specific object from the PriorityQueue<T>, maintaining the heap condition of the queue.

new int	RemoveAll (Predicate< T > match)
	Removes all the elements that match the conditions defined by the specified predicate, maintaining the heap condition of the queue.

new void	RemoveRange (int index, int count)
	Removes a range of elements from the PriorityQueue<T>, maintaining the heap condition of the queue.

new void	Reverse ()
	As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the queue is not empty.

new void	Reverse (int index, int count)
	As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the queue is not empty.

new void	Sort ()
	Sort the elements of the PriorityQueue<T>, maintaining the heap condition of the queue.

new void	Sort (IComparer< T > comparer)
	As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the comparer given is no the same specified in the constructor and the queue is not empty.

new void	Sort (int index, int count, IComparer< T > comparer)
	As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the comparer given is no the same specified in the constructor and the queue is not empty.

new void	Sort (Comparison< T > comparison)
	As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the queue is not empty.

Properties
new T	this[int index] `[get, set]`
	Gets or sets the element at the specified index.

object	SyncRoot `[get]`
	Gets an object that can be used to synchronize access to the priority queue.

bool	IsSynchronized `[get]`
	Gets a value indicating whether access to the PriorityQueue<T> is synchronized (thread safe).

IComparer< T >	Comparer `[get]`
	Gets the IComparer<T> object that is used to order the values in the PriorityQueue<T>.

Detailed Description

PriorityQueue<T> is a C# implementation of a generic priority queue based on a binary min-heap. This C# implementation provides O(log(n)) time for insertion methods; O(log(n)) time for removal methods; and constant time for retrieval methods. The implementation is derived from the List<T> class, therefore most List<T> methods can also be applied to a PriorityQueue<T>, however, List<T> methods that would destroy the heap condition of the priority queue will throw an InvalidOperationException, e.g. Reverse().

Template Parameters

T	The type of values in the priority queue. The type must implement the IComparable<T> interface.

Type Constraints

T

:

IComparable<T>

Definition at line 57 of file PriorityQueue.cs.

Constructor & Destructor Documentation

Com.Mission_Base.Pbl.PriorityQueue< T >.PriorityQueue ( )

Initializes a new instance of the PriorityQueue<T> class that is empty and has the default initial capacity.

Definition at line 248 of file PriorityQueue.cs.

Com.Mission_Base.Pbl.PriorityQueue< T >.PriorityQueue ( IEnumerable< T > enumerable )

Initializes a new instance of the PriorityQueue<T> class that contains elements copied from the specified collection and has sufficient capacity to accommodate the number of elements copied.

Definition at line 256 of file PriorityQueue.cs.

Com.Mission_Base.Pbl.PriorityQueue< T >.PriorityQueue ( Int32 capacity )

Initializes a new instance of the PriorityQueue<T> class that is empty and has the specified initial capacity.

Definition at line 266 of file PriorityQueue.cs.

Com.Mission_Base.Pbl.PriorityQueue< T >.PriorityQueue ( IComparer< T > comparer )

Initializes a new instance of the PriorityQueue<T> class that uses a specified comparer.

Definition at line 275 of file PriorityQueue.cs.

Com.Mission_Base.Pbl.PriorityQueue< T >.PriorityQueue	(	IEnumerable< T >	enumerable,
		IComparer< T >	comparer
	)

Initializes a new instance of the PriorityQueue<T> class that contains elements copied from a specified enumerable collection and that uses a specified comparer.

Definition at line 284 of file PriorityQueue.cs.

Com.Mission_Base.Pbl.PriorityQueue< T >.PriorityQueue	(	Int32	capacity,
		IComparer< T >	comparer
	)

Initializes a new instance of the PriorityQueue<T> class that is empty, has the specified initial capacity and uses a specified comparer.

Definition at line 295 of file PriorityQueue.cs.

Member Function Documentation

new void Com.Mission_Base.Pbl.PriorityQueue< T >.Add ( T item )

Adds an object to the PriorityQueue<T>, maintaining the heap condition of the queue.

Parameters

item	The object to add to the PriorityQueue<T>.

PriorityQueue<T> accepts null as a valid value for reference types and allows duplicate elements.

If the number of items in the queue is less than Capacity, this method is an O(Log(N)) operation, where N is the number of items in the queue. If the capacity needs to be increased to accommodate the new element, this method becomes an O(N) operation, where N is the number of items in the queue.

Definition at line 402 of file PriorityQueue.cs.

new void Com.Mission_Base.Pbl.PriorityQueue< T >.AddRange ( IEnumerable< T > collection )

Adds the elements of the specified collection to the PriorityQueue<T>, maintaining the heap condition of the queue.

Parameters

collection The collection whose elements should be added the PriorityQueue<T>. The collection itself cannot be null, but it can contain elements that are null, if type T is a reference type.

This method is an O(N) operation, where N is the number of items in the queue after the operation.

Definition at line 416 of file PriorityQueue.cs.

T Com.Mission_Base.Pbl.PriorityQueue< T >.Dequeue ( )

Removes and returns the object at the beginning of the PriorityQueue<T>. I.e. an item with the lowest priority from the priority queue, maintaining the heap condition of the queue.

Returns: The object that is removed from the beginning of the PriorityQueue<T>.

This method is similar to the Peek method, but Peek does not modify the PriorityQueue<T>

This method is an O(Log(N)) operation, where N is the number of items in the queue.

Definition at line 333 of file PriorityQueue.cs.

void Com.Mission_Base.Pbl.PriorityQueue< T >.Enqueue ( T item )

Adds an object to the PriorityQueue<T>, maintaining the heap condition of the queue.

Parameters

item	The object to add to the PriorityQueue<T>.

PriorityQueue<T> accepts null as a valid value for reference types and allows duplicate elements.

If the number of items in the queue is less than Capacity, this method is an O(Log(N)) operation, where N is the number of items in the queue. If the capacity needs to be increased to accommodate the new element, this method becomes an O(N) operation, where N is the number of items in the queue.

Definition at line 316 of file PriorityQueue.cs.

void Com.Mission_Base.Pbl.PriorityQueue< T >.EnsureHeapCondition ( int index )

Ensures the heap condition for an item in the PriorityQueue<T> at a given index. Call this method after you change the priority of an item in the PriorityQueue<T>.

Ensuring the heap condition for a single item is an O(Log(N)) operation, where N is the number of items in the queue.

Definition at line 189 of file PriorityQueue.cs.

void Com.Mission_Base.Pbl.PriorityQueue< T >.EnsureHeapCondition ( )

Ensures the heap condition for the entire PriorityQueue<T>. Call this method after you change the priority of many items in the PriorityQueue<T>.

Ensuring the heap condition for the entire priority queue is an O(N) operation, where N is the number of items in the queue.

Definition at line 204 of file PriorityQueue.cs.

new void Com.Mission_Base.Pbl.PriorityQueue< T >.Insert	(	int	index,
		T	item
	)

Inserts an object to the PriorityQueue<T>, maintaining the heap condition of the queue.

Parameters

index	The zero-based index of the element to get or set.
item	The object to add to the PriorityQueue<T>.

As this method maintains the heap condition of the queue, the item inserted might actually be moved to an index different to the one specified.

PriorityQueue<T> accepts null as a valid value for reference types and allows duplicate elements.

If the number of items in the queue is less than Capacity, this method is an O(Log(N)) operation, where N is the number of items in the queue. If the capacity needs to be increased to accommodate the new element, this method becomes an O(N) operation, where N is the number of items in the queue.

Definition at line 438 of file PriorityQueue.cs.

new void Com.Mission_Base.Pbl.PriorityQueue< T >.InsertRange	(	int	index,
		IEnumerable< T >	collection
	)

Inserts the elements of the specified collection to the PriorityQueue<T>, maintaining the heap condition of the queue.

Parameters

index	The zero-based index of the element to get or set.
collection	The collection whose elements should be added the PriorityQueue<T>. The collection itself cannot be null, but it can contain elements that are null, if type T is a reference type.

As this method maintains the heap condition of the queue, the items inserted might actually be moved to indices different to the ones specified.

This method is an O(N) operation, where N is the number of items in the queue after the operation.

Definition at line 457 of file PriorityQueue.cs.

T Com.Mission_Base.Pbl.PriorityQueue< T >.Peek ( )

Returns the object at the beginning of the PriorityQueue<T> without removing it. I.e. an item with the lowest priority.

Returns: The object at the beginning of the PriorityQueue<T>.

This method is similar to the Dequeue method, but Peek does not modify the PriorityQueue<T>

This method is an O(1) operation.

Definition at line 355 of file PriorityQueue.cs.

new bool Com.Mission_Base.Pbl.PriorityQueue< T >.Remove ( T item )

Removes the first occurrence of a specific object from the PriorityQueue<T>, maintaining the heap condition of the queue.

Parameters

item	The object to remove from the PriorityQueue<T>. The value can be null for reference types.

Returns: true if item is successfully removed; otherwise, false. This method also returns false if item was not found in the PriorityQueue<T>.

This method performs a linear search; therefore, this method is an O(N) operation, where N is the number of items in the queue.

Definition at line 489 of file PriorityQueue.cs.

new int Com.Mission_Base.Pbl.PriorityQueue< T >.RemoveAll ( Predicate< T > match )

Removes all the elements that match the conditions defined by the specified predicate, maintaining the heap condition of the queue.

Parameters

match The Predicate<T> delegate that defines the conditions of the elements to remove.

Returns: The number of elements removed from the PriorityQueue<T>.

This method performs a linear search; therefore, this method is an O(N) operation, where N is the number of items in the queue.

Definition at line 512 of file PriorityQueue.cs.

new void Com.Mission_Base.Pbl.PriorityQueue< T >.RemoveAt ( int index )

Removes the element at the specified index of PriorityQueue<T>, maintaining the heap condition of the queue.

Parameters

index The zero-based index of the element to remove.

This method is an O(Log(N)) operation, where N is the number of items in the queue.

Definition at line 472 of file PriorityQueue.cs.

new void Com.Mission_Base.Pbl.PriorityQueue< T >.RemoveRange	(	int	index,
		int	count
	)

Removes a range of elements from the PriorityQueue<T>, maintaining the heap condition of the queue.

Parameters

index	The zero-based starting index of the range of elements to remove.
count	The number of elements to remove.

This method is an O(N) operation, where N is the number of items in the queue.

Definition at line 534 of file PriorityQueue.cs.

new void Com.Mission_Base.Pbl.PriorityQueue< T >.Reverse ( )

As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the queue is not empty.

Exceptions

InvalidOperationException This method will throw an InvalidOperationException, if the queue is not empty.

Definition at line 549 of file PriorityQueue.cs.

new void Com.Mission_Base.Pbl.PriorityQueue< T >.Reverse	(	int	index,
		int	count
	)

As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the queue is not empty.

Exceptions

InvalidOperationException This method will throw an InvalidOperationException, if the queue is not empty.

Definition at line 563 of file PriorityQueue.cs.

new void Com.Mission_Base.Pbl.PriorityQueue< T >.Sort ( )

Sort the elements of the PriorityQueue<T>, maintaining the heap condition of the queue.

This method uses Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

On average, this method is an O(N log(N)) operation, where N is the number of items in the queue; in the worst case it is an O(N ^ 2) operation.

Definition at line 580 of file PriorityQueue.cs.

new void Com.Mission_Base.Pbl.PriorityQueue< T >.Sort ( IComparer< T > comparer )

As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the comparer given is no the same specified in the constructor and the queue is not empty.

Exceptions

InvalidOperationException This method will throw an InvalidOperationException, if the comparer given is no the same specified in the constructor and the queue is not empty.

Definition at line 601 of file PriorityQueue.cs.

new void Com.Mission_Base.Pbl.PriorityQueue< T >.Sort	(	int	index,
		int	count,
		IComparer< T >	comparer
	)

As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the comparer given is no the same specified in the constructor and the queue is not empty.

Exceptions

InvalidOperationException This method will throw an InvalidOperationException, if the comparer given is no the same specified in the constructor and the queue is not empty.

Definition at line 619 of file PriorityQueue.cs.

new void Com.Mission_Base.Pbl.PriorityQueue< T >.Sort ( Comparison< T > comparison )

As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the queue is not empty.

Exceptions

InvalidOperationException This method will throw an InvalidOperationException, if the queue is not empty.

Definition at line 637 of file PriorityQueue.cs.

Property Documentation

IComparer<T> Com.Mission_Base.Pbl.PriorityQueue< T >.Comparer

get

Gets the IComparer<T> object that is used to order the values in the PriorityQueue<T>.

Returns: The comparer that is used to order the values in the PriorityQueue<T> or null if no comparer has be specified.

Definition at line 676 of file PriorityQueue.cs.

bool Com.Mission_Base.Pbl.PriorityQueue< T >.IsSynchronized

get

Gets a value indicating whether access to the PriorityQueue<T> is synchronized (thread safe).

Returns: false.

Definition at line 666 of file PriorityQueue.cs.

object Com.Mission_Base.Pbl.PriorityQueue< T >.SyncRoot

get

Gets an object that can be used to synchronize access to the priority queue.

Returns: An object that can be used to synchronize access to the priority queue.

Definition at line 655 of file PriorityQueue.cs.

new T Com.Mission_Base.Pbl.PriorityQueue< T >.this[int index]

getset

Gets or sets the element at the specified index.

Parameters

index The zero-based index of the element to get or set.

PriorityQueue<T> accepts null as a valid value for reference types and allows duplicate elements.

This property provides the ability to access a specific element in the collection by using the following syntax: myCollection[index].

Retrieving the value of this property is an O(1) operation; setting the property is an O(Log(N)) operation, where N is the number of items in the queue.

Definition at line 382 of file PriorityQueue.cs.

The documentation for this class was generated from the following file:

projects/com/mission_base/pbl/PriorityQueue.cs

Public Member Functions

Properties

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Property Documentation