PriorityQueue<T> implementation

Question

I was hoping to get some general feedback and thoughts about my implementation of a generic priority queue. Please feel free to be as critical as you want or see fit.

Generic priority queue implementation (please note that the PriorityConvention can be None, HighestPriorityInFront, LowestPriorityInFront):

using System;
using System.Collections;
using System.Collections.Generic;
using Utilities.Enums.Generics;
using Utilities.Interfaces;
namespace Utilities.Classes.Generics
{
 /// <summary> A generic priority queue implementation. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <seealso> cref="T:System.Collections.Generic.IEnumerable{T}". </seealso>
 /// <seealso> cref="T:Utilities.Interfaces.IPriorityQueue{T}". </seealso>
 /// <typeparam name="T"> Generic type parameter, where T 
 /// must implement the IComparable interface. </typeparam>
 [Serializable]
 public class PriorityQueue<T> : IEnumerable<T>, IPriorityQueue<T>
 where T : IComparable<T>
 {
 #region Private Member Variables
 private readonly List<T> items; /* The items in the queue */
 #endregion
 #region Properties
 /// <summary> Gets the convention this priority queue uses to sort and insert items. </summary>
 /// <value> The ordering convention. </value>
 public PriorityConvention OrderingConvention { get; private set; }
 /// <summary> Gets the number of items that are in the priority queue. </summary>
 /// <value> The number of items in the priority queue. </value>
 public Int32 Count
 {
 get { return items.Count; }
 }
 #endregion
 #region Constructors
 /// <summary> Initializes a new instance of the PriorityQueue class. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <exception cref="ArgumentException"> Thrown when the convention is specified 
 /// as PriorityConvention.None. </exception>
 /// <param name="convention">
 /// (Optional) the convention to use when sorting and inserting items (this cannot be changed
 /// after the priority queue is created).
 /// </param>
 public PriorityQueue(PriorityConvention convention = PriorityConvention.HighestPriorityInFront)
 {
 if (convention == PriorityConvention.None)
 {
 throw new ArgumentException("No valid ordering convention was specified", "convention");
 }
 OrderingConvention = convention;
 items = new List<T>();
 }
 /// <summary> Initializes a new instance of the PriorityQueue class. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <exception cref="ArgumentException"> Thrown when the convention is specified
 /// as PriorityConvention.None. </exception>
 /// <param name="priorityItems"> The items to initialize the priority queue with. </param>
 /// <param name="convention">
 /// (Optional) the convention to use when sorting and inserting items (this cannot be changed
 /// after the priority queue is created).
 /// </param>
 public PriorityQueue(IEnumerable<T> priorityItems,
 PriorityConvention convention = PriorityConvention.HighestPriorityInFront)
 : this(convention)
 {
 if (convention == PriorityConvention.None)
 {
 throw new ArgumentException("No valid ordering convention was specified", "convention");
 }
 AddRange(priorityItems);
 }
 #endregion
 #region Public Methods
 /// <summary> Gets the enumerator for the priority queue. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <returns> The enumerator for the priority queue. </returns>
 public IEnumerator<T> GetEnumerator()
 {
 return items.GetEnumerator();
 }
 /// <summary> Gets the enumerator for the priority queue. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <returns> The enumerator for the priority queue. </returns>
 IEnumerator IEnumerable.GetEnumerator()
 {
 return GetEnumerator();
 }
 /// <summary> Adds an item to the priority queue. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <param name="item"> The item to add. </param>
 public void Add(T item)
 {
 Insert(item);
 }
 /// <summary>
 /// Adds the items to the priority queue. This method checks if the enumerable is null 
 /// and only iterates of the items once.
 /// </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <param name="itemsToAdd"> An IEnumerable&lt;T&gt; of items to add to the priority queue. </param>
 public void AddRange(IEnumerable<T> itemsToAdd)
 {
 if (itemsToAdd == null)
 {
 return;
 }
 foreach (T item in itemsToAdd)
 {
 Insert(item);
 }
 }
 /// <summary> Clears all the items from the priority queue. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 public void Clear()
 {
 items.Clear();
 }
 /// <summary> Clears all the items starting at the specified start index. </summary>
 /// <remarks> David Venegoni, Jan 03 2014. </remarks>
 /// <param name="startIndex"> The start index. </param>
 /// <returns> The number of items that were removed from the priority queue. </returns>
 public Int32 Clear(Int32 startIndex)
 {
 Int32 numberOfItems = items.Count - 1 - startIndex;
 items.RemoveRange(startIndex, numberOfItems);
 return numberOfItems;
 }
 /// <summary> Clears the number of items specified by count 
 /// from the priority queue starting at specified start index. </summary>
 /// <remarks> David Venegoni, Jan 03 2014. </remarks>
 /// <param name="startIndex"> The start index. </param>
 /// <param name="count"> Number of items to remove. </param>
 public void Clear(Int32 startIndex, Int32 count)
 {
 items.RemoveRange(startIndex, count);
 }
 /// <summary> Clears all the items that satisfy the specified predicate function. </summary>
 /// <remarks> David Venegoni, Jan 03 2014. </remarks>
 /// <param name="predicateFunction"> The predicate function to use in determining 
 /// which items should be removed. </param>
 /// <returns> The number of items that were removed from the priority queue. </returns>
 public Int32 ClearWhere(Func<T, Boolean> predicateFunction)
 {
 return items.RemoveAll(predicateFunction.Invoke);
 }
 /// <summary> Pops an item from the front of the queue. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <exception cref="InvalidOperationException"> Thrown when no items exist 
 /// in the priority queue. </exception>
 /// <returns> An item from the front of the queue. </returns>
 public T PopFront()
 {
 if (items.Count == 0)
 {
 throw new InvalidOperationException("No elements exist in the queue");
 }
 T item = items[0];
 items.RemoveAt(0);
 return item;
 }
 /// <summary> Pops an item from the back of the queue. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <exception cref="InvalidOperationException"> Thrown when no items exist
 /// in the priority queue. </exception>
 /// <returns> An item from the back of the queue. </returns>
 public T PopBack()
 {
 if (items.Count == 0)
 {
 throw new InvalidOperationException("No elements exist in the queue");
 }
 Int32 tail = items.Count - 1;
 T item = items[tail];
 items.RemoveAt(tail);
 return item;
 }
 /// <summary> Peeks at the item at the front queue without removing the item. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <exception cref="InvalidOperationException"> Thrown when no items exist 
 /// in the priority queue. </exception>
 /// <returns> The item at the front of the queue. </returns>
 public T PeekFront()
 {
 if (items.Count == 0)
 {
 throw new InvalidOperationException("No elements exist in the queue");
 }
 return items[0];
 }
 /// <summary> Peeks at the item at the back of the queue without removing the item. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <exception cref="InvalidOperationException"> Thrown when no items exist 
 /// in the priority queue. </exception>
 /// <returns> The item at the back of the queue. </returns>
 public T PeekBack()
 {
 if (items.Count == 0)
 {
 throw new InvalidOperationException("No elements exist in the queue");
 }
 return items[items.Count - 1];
 }
 /// <summary> Pops the specified number of items from the front of the queue. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <exception cref="ArgumentException">
 /// Thrown when the number of items to pop exceeds the number of items in the priority
 /// queue.
 /// </exception>
 /// <param name="numberToPop"> Number of items to pop from the front of the queue. </param>
 /// <returns> The items from the front of the queue. </returns>
 public IEnumerable<T> PopFront(Int32 numberToPop)
 {
 if (numberToPop > items.Count)
 {
 throw new ArgumentException(@"The numberToPop exceeds the number 
 of elements in the queue", "numberToPop");
 }
 var poppedItems = new List<T>();
 while (poppedItems.Count < numberToPop)
 {
 poppedItems.Add(PopFront());
 }
 return poppedItems;
 }
 /// <summary> Pops the specified number of items from the back of the queue. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <exception cref="ArgumentException">
 /// Thrown when the number of items to pop exceeds the number of items in the priority
 /// queue.
 /// </exception>
 /// <param name="numberToPop"> Number of items to pop from the back of the queue. </param>
 /// <returns> The items from the back of the queue. </returns>
 public IEnumerable<T> PopBack(Int32 numberToPop)
 {
 if (numberToPop > items.Count)
 {
 throw new ArgumentException(@"The numberToPop exceeds the number 
 of elements in the queue", "numberToPop");
 }
 var poppedItems = new List<T>();
 while (poppedItems.Count < numberToPop)
 {
 poppedItems.Add(PopBack());
 }
 return poppedItems;
 }
 /// <summary> Queries if the priority queue is empty. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <returns> true if the priority queue empty, false if not. </returns>
 public Boolean IsEmpty()
 {
 return items.Count == 0;
 }
 #endregion
 #region Private Methods
 /// <summary> Inserts the given item into the queue. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <param name="item"> The item to insert into the queue. </param>
 private void Insert(T item)
 {
 if (items.Count == 0)
 {
 items.Add(item);
 }
 else if (OrderingConvention == PriorityConvention.HighestPriorityInFront)
 {
 InsertAscending(item);
 }
 else
 {
 InsertDescending(item);
 }
 }
 /// <summary>
 /// Inserts the specified item into the priority queue 
 /// (using the PriorityConvention.HighestPriorityInFront convention).
 /// </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <param name="item"> The item to insert into the queue. </param>
 private void InsertAscending(T item)
 {
 T tail = items[items.Count - 1];
 Int32 comparedToTail = item.CompareTo(tail);
 if (comparedToTail <= 0) // Less or equal to the than the current minimum
 {
 items.Add(item);
 }
 else if (items.Count == 1)
 {
 /* 
 * Must assume that since there is only one item
 * in the list and that the function has reached 
 * this point, that the current item is greater 
 * than the item in the queue, so needs to be 
 * inserted in front 
 */
 items.Insert(0, item);
 }
 else
 {
 FindIndexAndInsertItemAscending(item);
 }
 }
 /// <summary>
 /// Inserts the specified item into the priority queue 
 /// (using the PriorityConvention.LowestPriorityInFront convention).
 /// </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <param name="item"> The item to insert into the queue. </param>
 private void InsertDescending(T item)
 {
 T tail = items[items.Count - 1];
 Int32 comparedToTail = item.CompareTo(tail);
 if (comparedToTail >= 0) // Greater than or equal to current maximum
 {
 items.Add(item);
 }
 else if (items.Count == 1) // See InsertAscending for explanation
 {
 items.Insert(0, item);
 }
 else
 {
 FindIndexAndInsertItemDescending(item);
 }
 }
 /// <summary>
 /// Searches for the index where the given item should be place in the queue and, 
 /// subsequently, inserts the item at the specified index.
 /// </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <param name="item"> The item to insert into the queue. </param>
 private void FindIndexAndInsertItemAscending(T item)
 {
 Int32 lowerBoundIndex = 0;
 Int32 upperBoundIndex = items.Count - 1;
 Int32 currentMedianIndex = upperBoundIndex / 2; // No need to floor, integers will always round towards 0
 /* 
 * Will determine which side of the median the current item should be placed, 
 * then updating the lower and upper bounds accordingly until the proper index 
 * is found, at which the point the item will be inserted.
 */
 while (true)
 {
 Int32 comparisonResult = item.CompareTo(items[currentMedianIndex]);
 switch (comparisonResult)
 {
 case 1:
 upperBoundIndex = currentMedianIndex;
 break;
 case -1:
 lowerBoundIndex = currentMedianIndex;
 break;
 default:
 FindIndexAndInsertItem(item,
 currentMedianIndex,
 PriorityConvention.HighestPriorityInFront);
 return;
 }
 if (AreEndConditionsMet(item, lowerBoundIndex, upperBoundIndex, ref currentMedianIndex))
 {
 break;
 }
 }
 }
 /// <summary>
 /// Searches for the index where the given item should be place in the queue and, 
 /// subsequently, inserts the item at the specified index.
 /// </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <param name="item"> The item to insert into the queue. </param>
 private void FindIndexAndInsertItemDescending(T item)
 {
 // See FindIndexAndInsertItemAscending for explanation
 Int32 lowerBoundIndex = 0;
 Int32 upperBoundIndex = items.Count - 1;
 Int32 currentMedianIndex = upperBoundIndex / 2;
 while (true)
 {
 Int32 comparisonResult = item.CompareTo(items[currentMedianIndex]);
 switch (comparisonResult)
 {
 case 1:
 lowerBoundIndex = currentMedianIndex;
 break;
 case -1:
 upperBoundIndex = currentMedianIndex;
 break;
 default:
 FindIndexAndInsertItem(item,
 currentMedianIndex,
 PriorityConvention.LowestPriorityInFront);
 return;
 }
 if (AreEndConditionsMet(item, lowerBoundIndex, upperBoundIndex, ref currentMedianIndex))
 {
 break;
 }
 }
 }
 /// <summary>
 /// Searches for the index where the given item should be place in the queue and,
 /// subsequently, inserts the item at the specified index.
 /// </summary>
 /// <remarks>
 /// This method will be called when the specified item equals 
 /// another item (can be more than one) within the queue.
 /// David Venegoni, Jan 02 2014.
 /// </remarks>
 /// <param name="item"> The item to insert into the queue. </param>
 /// <param name="currentIndex"> The index in which to start at. </param>
 /// <param name="priorityConvention"> The priority convention to use when finding the index. </param>
 private void FindIndexAndInsertItem(T item, Int32 currentIndex, PriorityConvention priorityConvention)
 {
 Int32 currentPosition = currentIndex;
 Int32 condition = priorityConvention == PriorityConvention.HighestPriorityInFront ? 1 : -1;
 Boolean isLastElement = false;
 while (item.CompareTo(items[currentPosition]) != condition)
 {
 ++currentPosition;
 if (currentPosition < items.Count) // Make sure the index does not go out of range
 {
 continue;
 }
 isLastElement = true;
 break;
 }
 if (isLastElement)
 {
 items.Add(item);
 }
 else
 {
 items.Insert(currentPosition, item);
 }
 }
 /// <summary>
 /// Determines if the current lower bound, upper bound, and median index are 
 /// at the end conditions, if not, the current median index is updated 
 /// using the lower and upper bound indices.
 /// </summary>
 /// <remarks>
 /// The end conditions are: 
 /// 1) Is the upper bound index 0? 
 /// 2) Is the lower bound index the last index in the queue? 
 /// 3) Is the new median index (calculated using lower and 
 /// upper bound indices) the same as the current median index?
 /// David Venegoni, Jan 02 2014.
 /// </remarks>
 /// <param name="item"> The item to insert if the end conditions are met. </param>
 /// <param name="lowerBoundIndex"> Zero-based index of the lower bound. </param>
 /// <param name="upperBoundIndex"> Zero-based index of the upper bound. </param>
 /// <param name="currentMedianIndex"> [in,out] The current median index. </param>
 /// <returns> true if end conditions met, false if not. </returns>
 private Boolean AreEndConditionsMet(T item, Int32 lowerBoundIndex,
 Int32 upperBoundIndex, ref Int32 currentMedianIndex)
 {
 if (upperBoundIndex == 0)
 {
 items.Insert(0, item);
 return true;
 }
 if (lowerBoundIndex == items.Count - 1)
 {
 items.Add(item);
 return true;
 }
 /* 
 * If the new median is the same as the old median, 
 * then this item's priority will always be +1 from 
 * the median's priority, not to mention that continuing 
 * to use that median will result in an infinite loop 
 */
 Int32 newMedianIndex = (upperBoundIndex + lowerBoundIndex) / 2;
 if (currentMedianIndex == newMedianIndex)
 {
 items.Insert(currentMedianIndex + 1, item);
 return true;
 }
 currentMedianIndex = newMedianIndex;
 return false;
 }
 #endregion
 }
}

Interface (IPriorityQueue<T>):

using System;
using System.Collections.Generic;
namespace Utilities.Interfaces
{
 /// <summary> Generic priority queue interface. </summary>
 /// <remarks> David Venegoni, Jan 02 2014. </remarks>
 /// <typeparam name="T"> Generic type parameter. Must implement the IComparable interface. </typeparam>
 public interface IPriorityQueue<T>
 where T : IComparable<T>
 {
 /// <summary> Gets the number of items in the priority queue. </summary>
 /// <value> The number of items in the priority queue. </value>
 Int32 Count { get; }
 /// <summary> Adds an item to the priority queue, inserting it with respect to its priority. </summary>
 /// <param name="item"> The item to add. </param>
 void Add(T item);
 /// <summary> Adds a range of items to the priority queue, inserting them with respect to their priority. </summary>
 /// <param name="itemsToAdd"> An IEnumerable&lt;T&gt; of items to add to the priority queue. </param>
 void AddRange(IEnumerable<T> itemsToAdd);
 /// <summary> Clears all the items from the priority queue. </summary>
 void Clear();
 /// <summary> Clears all the items starting at the specified start index. </summary>
 /// <param name="startIndex"> The start index. </param>
 /// <returns> The number of items that were removed from the priority queue. </returns>
 Int32 Clear(Int32 startIndex);
 /// <summary> Clears the number of items specified by count from the priority queue starting at specified start index. </summary>
 /// <param name="startIndex"> The start index. </param>
 /// <param name="count"> Number of items to remove. </param>
 void Clear(Int32 startIndex, Int32 count);
 /// <summary> Clears all the items that satisfy the specified predicate function. </summary>
 /// <param name="predicateFunction"> The predicate function to use in determining which items should be removed. </param>
 /// <returns> The number of items that were removed from the priority queue. </returns>
 Int32 ClearWhere(Func<T, Boolean> predicateFunction);
 /// <summary> Pops an item from the front of the queue. </summary>
 /// <returns> An item from the front of the queue. </returns>
 T PopFront();
 /// <summary> Pops an item from the back of the queue. </summary>
 /// <returns> An item from the back of the queue. </returns>
 T PopBack();
 /// <summary> Peeks at the item at the front of the queue, but does not remove it from the queue. </summary>
 /// <returns> The item that is at the front of the queue. </returns>
 T PeekFront();
 /// <summary> Peek at the item at the back of the queue, but does not remove it from the queue. </summary>
 /// <returns> The item that is at the back of the queue. </returns>
 T PeekBack();
 /// <summary> Pops the specified number of items from the front of the queue. </summary>
 /// <param name="numberToPop"> Number of items to pop from the front of the queue. </param>
 /// <returns> The items that were popped from the front of the queue. </returns>
 IEnumerable<T> PopFront(Int32 numberToPop);
 /// <summary> Pops the specified number of items from the back of the queue. </summary>
 /// <param name="numberToPop"> Number of items to pop from the back of the queue. </param>
 /// <returns> The items that were popped from the back of the queue. </returns>
 IEnumerable<T> PopBack(Int32 numberToPop);
 /// <summary> Queries if the priority queue is empty. </summary>
 /// <returns> true if the priority queue is empty, false if not. </returns>
 Boolean IsEmpty();
 }
}

Answer 1

General

Priority queues in general keep a queue per priority. While your implementation achieves that, it is associated with a lot of copying when inserting and removing data due to the array backing structure of List. Using a SortedList with the priority as key and Queue<T> as values would probably be faster and less code.

This question on SO shows a basic implementation based on a SortedDictionary.

Technical

1. For consistency I would consider implementing all three Clear methods with the same interface (returning the number of elements removed) and all go through one method. Something like this:

   public int Clear()
   {
    return Clear(0);
   }
   public int Clear(int startIndex)
   {
    return Clear(startIndex, Count - 1 - startIndex);
   }
   public int Clear(int startIndex, int count)
   {
    // Note: RemoveRange will throw if index and count are not a valid range within the list
    list.RemoveRange(startIndex, count);
    return count;
   }
   

2. Consider changing PopFront to use an enumerator which avoids creating a temporary copy:

   public IEnumerable<T> PopFront(Int32 numberToPop)
   {
    if (numberToPop > items.Count)
    {
    throw new ArgumentException(@"The numberToPop exceeds the number 
    of elements in the queue", "numberToPop");
    }
    while (numberToPop-- > 0)
    {
    yield return PopFront();
    }
   }
   

   Same for PopBack

3. FindIndexAndInsertItemAscending and FindIndexAndInsertItemDescending are almost exactly the same except for the PriorityConvention passed to FindIndexAndInsertItem so they should be refactored into one method.

   Also List defines a BinarySearch method which should simplify your code somewhat. No need to reinvent the wheel.

• David Venegoni: Thanks Chris for your feedback, especially #2, it never occurred to me to use yield. It is interesting that you mentioned #1 because originally I did return an int for the Clear(), but later changed it to void because I was using three lines of code for Clear() as I used a local variable to store items.Count, then cleared the items, and returned the local variable, it just was not very clean and/or elegant. Your implementation however, is very clean, and probably would not have thought of it had you not mentioned it.
• David Venegoni: I do have a few questions in regards to using a SortedList<K, V>. The way I am reading it, it seems like you are suggesting that I should implement it with the key (K) = the priority, and the value (V) = Queue<T>, is this correct? Additionally, if the key is the priority, then it would seem that I would need to change the generic type parameters to PriorityQueue<TKey, TValue> much like it is seen here codeproject.com/Articles/126751/….
• David Venegoni: The main motivation behind having the single type parameter is to make the class act as much like a queue as possible, I will do some benchmarking tests and post the results, interesting to see which is faster.
• ChrisWue: @DavidVenegoni: Yes the idea is that you have a key which is the priority and the value which is your entity. Right now it is expected that the entity knows it's own priority value through the IComparable which can be problematic because now the entity is comparing itself solely on priority and not other attributes. You effectively intermingle two properties of the entities (what it represents and it's priority).