Recipe 11.2. Creating a Priority Queue Problem You need a data structure that operates similarly to a Queue but that returns objects based on a specific order. When objects are added to this queue, they are located in the queue according to their priority. When objects are retrieved from the queue, the queue simply returns the highest or lowest priority element based on which one you ask for. Solution Create a generic priority queue that orders items as they are added to the queue and returns items based on their priority. The PriorityQueue<T> class of Example 11-1 shows how this can be accomplished. Example 11-1. Generic PriorityQueue class using System; using System.Collections; using System.Collections.Generic; public class PriorityQueue<T> : IEnumerable<T>, ICloneable { public PriorityQueue(){} public PriorityQueue(IComparer<T> icomparer) { specialComparer = icomparer; } protected List<T> internalQueue = new List<T>(); protected IComparer<T> specialComparer = null; public int Count { get {return (internalQueue.Count);} } public void Clear() { internalQueue.Clear(); } public object Clone() { // Make a new PQ and give it the same comparer. PriorityQueue<T> newPQ = new PriorityQueue<T>(specialComparer); newPQ.CopyTo(internalQueue.ToArray(),0); return newPQ; } public int IndexOf(T item) { return (internalQueue.IndexOf(item)); } public bool Contains(T item) { return (internalQueue.Contains(item)); } public int BinarySearch(T item) { return (internalQueue.BinarySearch(item, specialComparer)); } public bool Contains(T item, IComparer<T> specialComparer) { return (internalQueue.BinarySearch(item, specialComparer) >= 0); } public void CopyTo(T[] array, int index) { internalQueue.CopyTo(array, index); } public virtual T[] ToArray() { return (internalQueue.ToArray()); } public virtual void TrimToSizeTrimExcess() { internalQueue.TrimExcess(); } public void Enqueue(T item) { internalQueue.Add(item); internalQueue.Sort(specialComparer); } public T DequeueSmallest() { T item = internalQueue[0]; internalQueue.RemoveAt(0); return (item); } public T DequeueLargest() { T item = internalQueue[internalQueue.Count - 1]; internalQueue.RemoveAt(internalQueue.Count - 1); return (item); } public T PeekSmallest() { return (internalQueue[0]); } public T PeekLargest() { return (internalQueue[internalQueue.Count - 1]); } public IEnumerator GetEnumerator() { return (internalQueue.GetEnumerator()); } IEnumerator<T> System.Collections.Generic.IEnumerable<T>.GetEnumerator() { return (internalQueue.GetEnumerator()); } }
|
For example, perhaps your application or component needs to send packets of data of differing sizes across a network. The algorithm for sending these packets of data states that the smallest (or perhaps the largest) packets will be sent before the larger (or smaller) ones. An analogous programming problem involves queuing up specific jobs to be run. Each job could be run based on its type, order, or size. This priority queue is designed so that itemsin this case, string valuesmay be added in any order; but when they are removed from the head or tail of the queue, they are dequeued in a specific order. The IComparer<T> type object, a specialComparer that is passed in through the constructor of this object, determines this order. The queued string objects are stored internally in a field called internalQueue of type List<T>. This was the simplest way to construct this type of queue, since a List<T> has most of the functionality built into it that we wanted to implement for this type of queue. Many of the methods of this class delegate to the internalQueue in order to perform their duties. These types of methods include Count, Clear, TrimExcess, and many others. Some of the more important methods of the PriorityQueue<T> class are Enqueue, DequeueSmallest, DequeueLargest, PeekSmallest, and PeekLargest. The Enqueue method accepts a type T as an argument and adds it to the end of the internalQueue. Next, this List<T> is sorted according to the specialComparer object. If the specialComparer object is null, the comparison defaults to the IComparer of the string object. By sorting the List<T> after each item is added, you do not have to perform a sort before every search, dequeue, and peek method. A small performance hit will occur when an item is added, but this is a one-time-only penalty. Keep in mind that when items are removed from the head or tail of this queue, the internal List<T> does not have to be resorted. There are two dequeue methods: DequeueSmallest and DequeueLargest. These methods remove items from the head (index equals 0) of the internalQueue and from the tail (index equals internalQueue.Count -1), respectively. Before returning the string, these methods will remove that string from the queue. The PeekSmallest and PeekLargest methods work in a similar manner, except that they do not remove the string from the queue. Two other methods of interest are the overloaded Contains methods. The only real difference between these two methods is that one of the Contains methods uses the IComparer interface of the string object, whereas the other overloaded Contains method uses the specialComparer interface when searching for a string in the internalQueue, if one is provided. The PriorityQueue<T> class members are listed in Table 11-1. Table 11-1. PriorityQueue class membersMember | Description |
|---|
Count property | Returns an int indicating the number of items in the queue. Calls the internalQueue. Count method. | Clear method | Removes all items from the queue. Calls the internalQueue method. | Clone method | Returns a copy of the PriorityQueue<T> object. | IndexOf method | Returns the zero-based index of the queue item that contains a particular search string. Its syntax is: IndexOf(T item)
where item is the string to be found in the queue. Calls the internalQueue method. | Contains method | Returns a bool indicating whether a particular search string is found in the queue. Its syntax is: Contains(T item)
where item is the string to be found in the queue. Calls theinternalQueue method. | BinarySearch method | Returns the zero-based index of the queue item that contains a particular search type T. Its syntax is: BinarySearch(T item)
where item is the type T to be found in the queue. The comparison of item with the type T found in the queue is handled by the IComparer<T> implementation, if one was passed as an argument to one of the overloads of the PriorityQueue<T> class constructor. Calls the internalQueue method. | Contains method | Returns a bool indicating whether a particular search type T is found in the queue. Its syntax is: Contains(T item, IComparer<T> specialComparer)
where item is the string to be found in the queue. The comparison of item with the strings found in the queue is handled by the IComparer<T> implementation, if one was passed as an argument to one of the overloads of the PriorityQueue<T> class constructor. Calls the internalQueue method. | CopyTo method | Copies the queue items to a one-dimensional array starting at a particular position in the queue. Its syntax is: CopyTo(T[] array, int arrayIndex)
where array is the array to receive the copy of the queue items and arrayIndex is the position in the queue from which to begin copying items. Calls the internalQueue method. | ToArray method | Copies the items in the queue to an object array. Calls the internalQueue method. | trimExcess method | Sets the capacity of the queue to the current count of its items. If the trimExcess method is called when no items are in the queue, its capacity is set to a default value. Calls the internalQueue method. | Enqueue method | Adds an item to the queue. It then sorts the queue based on either the default sort behavior of each item or the IComparer<T> implementation passed as an argument to one of the PriorityQueue<T> class constructors. Its syntax is: Enqueue(T item)
where item is the type T to be added to the queue. | DequeueLargest method | Returns and removes the item at the tail of the queue (i.e., the last item in the queue). | DequeueSmallest method | Returns and removes the item at the head of the queue (i.e., the first item in the queue). | PeekSmallest method | Returns the item at the head of the queue (i.e., the first item in the queue). | PeekLargest method | Returns the item at the tail of the queue (i.e., the last item in the queue). | GetEnumerator method | Returns an enumerator that allows iteration of the items in the queue. Calls the internalQueue method. |
The PriorityQueue<T> can be instantiated and filled with strings using code like the Test class shown in Example 11-2. Example 11-2. Testing the PriorityQueue class class Test { static void Main() { // Create ArrayList of messages. List<string> msgs = new List<string>(); msgs.Add("foo"); msgs.Add("This is a longer message."); msgs.Add("bar"); msgs.Add(@"Message with odd characters !@#$%^&*()_+=-0987654321~|}{[]\\;:?/>.<,"); msgs.Add(@"< >"); msgs.Add("<text>one</text><text>two</text><text>three</text>" + "<text>four</text>"); msgs.Add(""); msgs.Add("1234567890"); // Create a Priority Queue with the appropriate comparer. // The comparer is created from the CompareLen type // defined in the Discussion section. CompareLen<string> comparer = new CompareLen<string>(); PriorityQueue<string> pqueue = new PriorityQueue<string>(comparer); // Add all messages from the List to the priority queue. foreach (string msg in msgs) { pqueue.Enqueue(msg); } // Display messages in the queue in order of priority. foreach (string msg in pqueue) { Console.WriteLine("Msg: " + msg); } Console.WriteLine("pqueue.IndexOf('bar') == " + pqueue.IndexOf("bar")); Console.WriteLine("pqueue.IndexOf('_bar_') == " + pqueue.IndexOf("_bar_")); Console.WriteLine("pqueue.Contains('bar') == " + pqueue.Contains("bar")); Console.WriteLine("pqueue.Contains('_bar_') == " + pqueue.Contains("_bar_")); Console.WriteLine("pqueue.BinarySearch('bar') == " + pqueue.BinarySearch("bar")); Console.WriteLine("pqueue.BinarySearch('_bar_') == " + pqueue.BinarySearch("_bar_")); // Dequeue messages starting with the smallest. int currCount = pqueue.Count; for (int index = 0; index < currCount; index++) { // In order to dequeue messages starting with the largest, uncomment // the following line and comment the following lines that // dequeue starting with the smallest message. //Console.WriteLine("pqueue.DequeueLargest(): " + // pqueue.DequeueLargest().ToString()); Console.WriteLine("pqueue.DequeueSmallest(): " + pqueue.DequeueSmallest().ToString()); } } }
|
The output of this method is shown here: Msg: Msg: foo Msg: bar Msg: 1234567890 Msg: This is a longer message. Msg: <text>one</text><text>two</text><text>three</text><text>four</text> Msg: Message with odd characters !@#$%^&*()_+=-0987654321~|}{[]\\;:?/>.<, Msg: < > pqueue.IndexOf('bar') == 2 pqueue.IndexOf('_bar_') == -1 pqueue.Contains('bar') == True pqueue.Contains('_bar_') == False pqueue.BinarySearch('bar') == 1 pqueue.BinarySearch('_bar_') == -4 pqueue.DequeueSmallest(): pqueue.DequeueSmallest(): foo pqueue.DequeueSmallest(): bar pqueue.DequeueSmallest(): 1234567890 pqueue.DequeueSmallest(): This is a longer message. pqueue.DequeueSmallest(): <text>one</text><text>two</text><text>three </text><text>four</text> pqueue.DequeueSmallest(): Message with odd characters !@#$%^&*()_+=-0987654321~|}{[]\\;:?/>.<, pqueue.DequeueSmallest(): < >
A List<T> of string messages is created that will be used to fill the queue. A new CompareLen IComparer<T> type object is created and passed in to the constructor of the PriorityQueue<T>. If you did not pass in this IComparer<T> object, the output would be much different: instead of items being retrieved from the queue based on length, they would be retrieved based on their alphabetical order. (The IComparer<T> interface is covered in detail in the Discussion section.) Finally, a foreach loop is used to enqueue all messages into the PriorityQueue<T> object. At this point, the PriorityQueue<T> object can be used in a manner similar to the Queue<T> class contained in the FCL, except for the ability to remove items from both the head and tail of the queue. Discussion You can instantiate the PriorityQueue<T> class with or without a special comparer object. The special comparer object used in this recipe is defined in Example 11-3. Example 11-3. Special CompareLen comparer class public class CompareLen<T> : IComparer<T> where T: IComparable<T> { public int Compare(T obj1, T obj2) { int result = 0; if (typeof(T) == typeof(string)) { result = CompareStrings(obj1 as string, obj2 as string); } else { // Default to the object type's comparison algorithm. result = Comparer<T>.Default.Compare(obj1, obj2); } return (result); } private int CompareStrings(string str1, string str2) { if (str1 == null || str2 == null) { throw(new ArgumentNullException( "The strings being compared may not be null.")); } if (str1.Length == str2.Length) { return (0); } else if (str1.Length > str2.Length) { return (1); } else { return (-1); } } public bool Equals(T item1, T item2) { if (item1 == null || item2 == null) { throw(new ArgumentNullException( "The objects being compared may not be null.")); } return (item1.Equals(item2)); } public int GetHashCode(T obj) { if (obj == null) { throw(new ArgumentNullException( "The obj parameter may not be null.")); } return (obj.GetHashCode()); } }
|
This special comparer is required because you want to prioritize the elements in the queue by size. The default string IComparer<string> interface compares strings alphabetically. Implementing the IComparer<T> interface requires that you implement a single method, Compare, with the following signature: int Compare(T x, T y);
where x and y are the objects being compared. When implementing custom Compare methods, the method is to return 0 if x equals y, less than 0 if x is less than y, and greater than 0 if x is greater than y. This method is called automatically by the .NET runtime whenever the custom IComparer<T> implementation is used. See Also See the "List<T> Class," "IEnumerable Interface," "ICloneable Interface," "IComparer<T> Interface," and "IComparable<T> Interface" topics in the MSDN documentation. |
