Monday, November 13, 2006

A Prioritized Queue in C#

Mark Paint asked me on my CyclicQueue CodeProject article to publish my PrioritizedQueue. I don't have the time to wrap it nicely and write an article, so I'm just putting it here for anyone who might need it.

Basically it's like a priority queue, except that here items with the same priority are guaranteed to be extracted in the order they were entered (FIFO). Important: If you don't need this feature then what you need is a simple priority queue which can be implemented in a more effective way (especially memory-wise) using a heap structure. Also, for my personal needs I've used a fixed number of 5 priorities - which may not be the best solution for all problems.

Goodies:
* You can make it automatically shrink the queues when there is a lot of free space (make sure to change the maxCount member variable).
* Support for thread-safe wrapper (Synchronized), enumeration, etc.

Things to modify:
* More flexible priorities
* Generics support

(Note: I'm posting this with Windows Live Writer. For some reason, there is a limit on size of the post - so I can't post it completely in one post. I'll post the synchronization class and the enumerator in  few minutes)

using System;
using System.Collections;
using System.Diagnostics;

namespace DataStructures
{
   
/// <summary>
   /// A queue which allows the items to have priorities. Items with the same
   /// priority are returned in FIFO order (that's why it's a prioritiIZED queue and not a prioritY Q)
   /// TODO: Make the priorities (names and number) more flexible
   /// </summary>
    [Serializable]
   
public class PrioritizedQueue :Queue
    {
       
private int count = 0; // Counts the number of items in the PrioritizedQueue
       // Our idea was to trim (i.e. shrink) the internal queues once they got a too large empty portion.
       // The problem is that we don't know the internal size of the queues (only the number of items in them).
       // The best approximation we can have is to constantly keep track of the largest number of items in the
       // queues, since the last call the TrimToSize().
       // When this value becomes significantly larger than Count, there is a good chance that the queues
       // can be shrinked.
       // To avoid shrinking needlessly, we shrink the queues only when maxCount has exceeded a certain threshold.
       // It is important to note that this feature (i.e. automatically shrinking of the queues) provides a very
       // important and significant improvement on the memory usage of this class.
       private int maxCount = 0;
       
private Queue[] queues;
       
private readonly int defaultQueueIndex = 2;
       
private int version = 0;
       
public const QueuePriority DEFAULT_PRIORITY =QueuePriority.Normal;
       
public PrioritizedQueue()
        {
            queues =
new Queue[5];
           
for (int i = 0; i < 5; i++)
            {
                queues[i] =
new Queue();
            }
        }

       
public PrioritizedQueue(ICollection collection) :this()
        {
            queues[defaultQueueIndex] =
new Queue(collection);
        }

       
public override void Clear()
        {
            version++;
           
foreach (Queue queuein queues)
            {
                queue.Clear();
            }
            count = 0;
        }

       
public override bool Contains(object obj)
        {
           
foreach (Queue queuein queues)
            {
               
if (queue.Contains(obj))
                {
                   
return true;
                }
            }
           
return false;
        }

       
public override object Dequeue()
        {
           
if (count == 0)
            {
               
throw new InvalidOperationException("Cannot dequeue empty queue");
            }

           
object obj =null;
           
foreach (Queue queuein queues)
            {
               
if (queue.Count > 0)
                {
                    obj = dequeueImpl(queue);
                   
break;
                }
            }           

           
return obj;
        }

       
public virtual object Dequeue(QueuePriority priority)
        {
           
return dequeueImpl(queues[(int)priority]);
        }

       
public override void Enqueue(object obj)
        {
            version++;
            queues[defaultQueueIndex].Enqueue(obj);           
            count++;
           
if (count > maxCount)
            {
                maxCount = count;
            }
        }

       
public virtual void Enqueue(object obj,QueuePriority priority)
        {
            version++;
            queues[(
int)priority].Enqueue(obj);
            count++;
           
if (count > maxCount)
            {
                maxCount = count;
            }
        }

       
public override object Peek()
        {
           
if (count == 0)
            {
               
throw new InvalidOperationException("Cannot peek empty queue");
            }

           
object obj =null;
           
foreach (Queue queuein queues)
            {
               
if (queue.Count > 0)
                {
                    obj = queue.Peek();
                   
break;
                }
            }
           
return obj;
        }

       
public virtual object Peek(QueuePriority priority)
        {
           
Queue queue = queues[(int)priority];
           
if (queue.Count == 0)
            {
               
throw new InvalidOperationException("Cannot peek empty queue");
            }
           
return queue.Peek();
        }

       
public static PrioritizedQueue Synchronized(PrioritizedQueue prioritizedQueue)
        {
           
if (prioritizedQueue ==null)
            {
               
throw new ArgumentNullException("prioritizedQueue");
            }
           
return new PrioritizedQueue.SynchronizedPrioritizedQueue(prioritizedQueue);
        }

       
public override object[] ToArray()
        {
           
object[] objs =new object[count];
           
if (count > 0)
            {
               
this.CopyTo(objs, 0);
            }
           
return objs;
        }

       
public override void TrimToSize()
        {
            version++;
           
foreach (Queue queuein queues)
            {
                queue.TrimToSize();
            }
            maxCount = count;
        }

        #region ICollection Members

       
public override bool IsSynchronized
        {
           
get
            {
               
return false;
            }
        }

       
public override int Count
        {
           
get {return count; }
        }

       
public override void CopyTo(Array array,int index)
        {
           
if (array ==null)
            {
               
throw new ArgumentNullException("array");
            }
           
if (array.Rank != 1)
            {
               
throw new ArgumentException("Array rank must be 1","array");
            }
           
if (index < 0)
            {
               
throw new ArgumentOutOfRangeException("index","Array index out of range");
            }
           
if ((array.Length - index) < count)
            {
               
throw new ArgumentException("Array is too small","array");
            }

           
foreach (Queue queuein queues)
            {
                queue.CopyTo(array, index);
                index += queue.Count;
            }
        }

       
public override object SyncRoot
        {
           
get
            {
               
return this;
            }
        }

        #endregion

        #region
IEnumerable Members

       
public override IEnumerator GetEnumerator()
        {           
           
return new PrioritizedQueue.PrioritizedQueueEnumerator(this);
        }

        #endregion

        #region
ICloneable Members

       
public override object Clone()
        {
           
PrioritizedQueue newPrioritizedQueue =new PrioritizedQueue();
           
for (int i = 0; i < queues.Length; i++)
            {
                newPrioritizedQueue.queues[i] =
new Queue(queues[i]);
            }
            newPrioritizedQueue.version =
this.version;

           
return newPrioritizedQueue;
        }

        #endregion

       /// <summary>
       /// The actual implementation of Dequeue.
       /// This method removes the next item from the given queue and updates the internal counter.
       /// In addition, it shrinks the queues if there is too much space left in the internal queues.
       /// Finally, it returns the object that was extracted from the queue.
       /// </summary>
       private int trimCounter = 0;
       
private object dequeueImpl(Queue queue)
        {           
            version++;
           
if ((count * 4 < maxCount) && (maxCount > 100))
            {
               
// If the available space is significantly larger than necessary (i.e. larger than
               // 4 times the number of items in the Q and larger than a predefined threshold of 100)
               // then we trim the Q to its actual size.
               this.TrimToSize();
                trimCounter++;
            }
           
object obj = queue.Dequeue();
            count--;
           
return obj;
        }

    }

    public enum QueuePriority
    {
        High = 0,
        AboveNormal = 1,
        Normal = 2,
        BelowNormal = 3,
        Low = 4
    }

}

No comments: