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
}
}
1 comment:
Grateful for sharing thiss
Post a Comment