/* PriorityQueue.cs - C# implementation of a binary min-heap based generic priority queue. Copyright (C) 2012 Peter Graf This file is part of PBL - The Program Base Library. PBL is free software. This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA For more information on the Program Base Library or Peter Graf, please see: http://www.mission-base.com/. $Log: PriorityQueue.cs,v $ Revision 1.3 2012/12/11 00:44:32 peter Added documentation comments. Revision 1.2 2012/12/09 02:40:28 peter Better exception handling Revision 1.1 2012/12/09 01:19:23 peter Initial Version */ using System; using System.Collections.Generic; using System.Runtime.InteropServices; using System.Diagnostics; namespace Com.Mission_Base.Pbl { /// /// 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(). /// /// /// The type of values in the priority queue. The type must implement the IComparable<T> interface. /// [Serializable] [ComVisible(false)] [DebuggerDisplay("Count = {Count}")] public class PriorityQueue : List, IList where T : IComparable { private readonly object _lock; private readonly IComparer _comparer; #region Heap handling private int CompareItems(T left, T right) { if (_comparer == null) { if (left == null) { if (right == null) { return 0; } return -1; } return left.CompareTo(right); } return _comparer.Compare(left, right); } private int LastParentIndex { // For zero based arrays all elements with an index bigger // than 'Count / 2 - 1' do not have any children get { return Count / 2 - 1; } } private void EnsureHeapConditionDownward(int index) { int lastParentIndex = LastParentIndex; if (index <= lastParentIndex) { var entry = base[index]; // As long as the entry has at least one child // while (index <= lastParentIndex) { // For zero based arrays the left child is at '2 * index + 1' // int childIndex = 2 * index + 1; var child = base[childIndex]; // If the entry also has a right child, the smaller child // needs to be considered for the swap // if (childIndex < Count - 1) { // The right child is next to the left child in the array // int rightChildIndex = childIndex + 1; var rightChild = base[rightChildIndex]; if (CompareItems(rightChild, child) < 0) { // Use the right child for the swap // child = rightChild; childIndex = rightChildIndex; } } if (CompareItems(entry, child) <= 0) { // The heap condition is fulfilled for the entry // return; } // Do the swap with the child // base[childIndex] = entry; base[index] = child; index = childIndex; } } // The entry does not have any children, therefore // the heap condition is fulfilled for the entry } private int EnsureHeapConditionUpward(int index) { if (index > 0) { var entry = base[index]; // As long as the entry is not the top of the heap // while (index > 0) { // For zero based arrays the parent index is '( index - 1 ) / 2' // int parentIndex = (index - 1) / 2; var parent = this[parentIndex]; if (CompareItems(entry, parent) >= 0) { // The heap condition is fulfilled for the entry // return index; } // Do the swap with the parent // base[parentIndex] = entry; base[index] = parent; index = parentIndex; } } // The entry is the top of the heap // return 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. /// public void EnsureHeapCondition(int index) { int rc = EnsureHeapConditionUpward(index); if (rc == index) { EnsureHeapConditionDownward(index); } } /// /// 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. /// public void EnsureHeapCondition() { // The heap condition is always fulfilled for entries without children, // therefore 'bottom-up heap construction' only needs to look // at elements that do have children // for (int index = LastParentIndex; index >= 0; index--) { EnsureHeapConditionDownward(index); } } private void HeapRemoveAt(int index) { if (index < 0 || index >= Count) { throw new ArgumentOutOfRangeException(string.Format("Index {0} is less than 0, or index is equal to or greater than priority queue count {1}.", index, Count)); } else if (index == Count - 1) { base.RemoveAt(index); return; } // Remove the last entry in the list // base[index] = base[Count - 1]; base.RemoveAt(Count - 1); if (Count > 1) { // Copying the values might have violated the heap condition // at position index, it needs to ensured // EnsureHeapCondition(index); } } #endregion #region Constructors /// /// Initializes a new instance of the PriorityQueue<T> class that is empty and has the default initial capacity. /// public PriorityQueue() { _lock = new object(); } /// /// 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. /// public PriorityQueue(IEnumerable enumerable) : base(enumerable) { _lock = new object(); EnsureHeapCondition(); } /// /// Initializes a new instance of the PriorityQueue<T> class that is empty and has the specified initial capacity. /// public PriorityQueue(Int32 capacity) : base(capacity) { _lock = new object(); } /// /// Initializes a new instance of the PriorityQueue<T> class that uses a specified comparer. /// public PriorityQueue(IComparer comparer) { _comparer = comparer; _lock = new object(); } /// /// Initializes a new instance of the PriorityQueue<T> class that contains elements copied from a specified enumerable collection and that uses a specified comparer. /// public PriorityQueue(IEnumerable enumerable, IComparer comparer) : base(enumerable) { _comparer = comparer; _lock = new object(); EnsureHeapCondition(); } /// /// Initializes a new instance of the PriorityQueue<T> class that is empty, has the specified initial capacity and uses a specified comparer. /// public PriorityQueue(Int32 capacity, IComparer comparer) : base(capacity) { _comparer = comparer; _lock = new object(); } #endregion #region Queue methods /// /// Adds an object to the PriorityQueue<T>, maintaining the heap condition of the queue. /// /// /// 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. /// public void Enqueue(T item) { base.Add(item); EnsureHeapConditionUpward(Count - 1); } /// /// 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. /// /// /// 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. /// public T Dequeue() { if (Count == 0) { throw new InvalidOperationException("The priority queue is empty."); } var result = base[0]; HeapRemoveAt(0); return result; } /// /// Returns the object at the beginning of the PriorityQueue<T> without removing it. I.e. an item with the lowest priority. /// /// /// 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. /// public T Peek() { if (Count == 0) { throw new InvalidOperationException("The priority queue is empty."); } return base[0]; } #endregion #region List methods /// /// Gets or sets the element at the specified 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. /// public new T this[int index] { get { return base[index]; } set { base[index] = value; EnsureHeapCondition(index); } } /// /// Adds an object to the PriorityQueue<T>, maintaining the heap condition of the queue. /// /// /// 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. /// public new void Add(T item) { Enqueue(item); } /// /// Adds the elements of the specified collection to the PriorityQueue<T>, maintaining the heap condition of the queue. /// /// /// 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. /// public new void AddRange(IEnumerable collection) { base.AddRange(collection); EnsureHeapCondition(); } /// /// Inserts an object to the PriorityQueue<T>, maintaining the heap condition of the queue. /// /// /// The zero-based index of the element to get or set. /// /// /// 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. /// public new void Insert(int index, T item) { Enqueue(item); } /// /// Inserts the elements of the specified collection to the PriorityQueue<T>, maintaining the heap condition of the queue. /// /// /// The zero-based index of the element to get or set. /// /// /// 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. /// public new void InsertRange(int index, IEnumerable collection) { base.InsertRange(index, collection); EnsureHeapCondition(); } /// /// Removes the element at the specified index of PriorityQueue<T>, maintaining the heap condition of the queue. /// /// /// 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. /// public new void RemoveAt(int index) { HeapRemoveAt(index); } /// /// Removes the first occurrence of a specific object from the PriorityQueue<T>, maintaining the heap condition of the queue. /// /// /// The object to remove from the PriorityQueue<T>. The value can be null for reference types. /// /// /// 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. /// public new bool Remove(T item) { int index = IndexOf(item); if (index < 0) { return false; } HeapRemoveAt(index); return true; } /// /// Removes all the elements that match the conditions defined by the specified predicate, maintaining the heap condition of the queue. /// /// /// The Predicate<T> delegate that defines the conditions of the elements to remove. /// /// /// 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. /// public new int RemoveAll(Predicate match) { var result = base.RemoveAll(match); if (result > 0) { EnsureHeapCondition(); } return result; } /// /// Removes a range of elements from the PriorityQueue<T>, maintaining the heap condition of the queue. /// /// /// The zero-based starting index of the range of elements to remove. /// /// /// The number of elements to remove. /// /// /// This method is an O(N) operation, where N is the number of items in the queue. /// public new void RemoveRange(int index, int count) { base.RemoveRange(index, count); if (index > LastParentIndex) { EnsureHeapCondition(); } } /// /// As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the queue is not empty. /// /// /// This method will throw an InvalidOperationException, if the queue is not empty. /// public new void Reverse() { if (Count > 1) { throw new InvalidOperationException("A priority queue cannot be reversed."); } } /// /// As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the queue is not empty. /// /// /// This method will throw an InvalidOperationException, if the queue is not empty. /// public new void Reverse(int index, int count) { if (index > LastParentIndex) { throw new InvalidOperationException("A priority queue cannot be partially reversed."); } base.Reverse(index, count); } /// /// 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. /// public new void Sort() { if (Count > 1) { if (_comparer != null) { base.Sort(_comparer); } else { base.Sort(); } } } /// /// 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. /// /// /// This method will throw an InvalidOperationException, if the comparer given is no the same specified in the constructor and the queue is not empty. /// public new void Sort(IComparer comparer) { if (Count > 1) { if (!ReferenceEquals(comparer, _comparer)) { throw new InvalidOperationException("A priority queue cannot be sorted with a comparer other than the one specified for the priority queue."); } base.Sort(_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. /// /// /// This method will throw an InvalidOperationException, if the comparer given is no the same specified in the constructor and the queue is not empty. /// public new void Sort(int index, int count, IComparer comparer) { if (Count > 1) { if (!ReferenceEquals(comparer, _comparer) || index != 0 || count != Count) { throw new InvalidOperationException("A priority queue cannot be partially sorted."); } base.Sort(index, count, _comparer); } } /// /// As the heap condition of the queue needs to be maintained, this method will throw an InvalidOperationException, if the queue is not empty. /// /// /// This method will throw an InvalidOperationException, if the queue is not empty. /// public new void Sort(Comparison comparison) { if (Count > 1) { throw new InvalidOperationException("A priority queue cannot be sorted with a comparison."); } } #endregion #region Misc /// /// Gets an object that can be used to synchronize access to the priority queue. /// /// /// An object that can be used to synchronize access to the priority queue. /// public object SyncRoot { get { return _lock; } } /// /// Gets a value indicating whether access to the PriorityQueue<T> is synchronized (thread safe). /// /// /// false. /// public bool IsSynchronized { get { return false; } } /// /// Gets the IComparer<T> object that is used to order the values in the PriorityQueue<T>. /// /// /// The comparer that is used to order the values in the PriorityQueue<T> or null if no comparer has be specified. /// public IComparer Comparer { get { return _comparer; } } #endregion } }