| [ Team LiB ] |
|
Recipe 10.2 Creating a Priority QueueProblemYou 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. SolutionCreate a priority queue that orders items as they are added to the queue and return items based on their priority. The PriorityQueue class shows how this is accomplished: using System;
using System.Collections;
public class PriorityQueue : IEnumerable, ICloneable
{
public PriorityQueue( ) {}
public PriorityQueue(IComparer icomparer)
{
specialComparer = icomparer;
}
protected ArrayList internalQueue = new ArrayList( );
protected IComparer 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 newPQ = new PriorityQueue(specialComparer);
newPQ.CopyTo(internalQueue.ToArray( ),0);
return newPQ;
}
public int IndexOf(string str)
{
return (internalQueue.BinarySearch(str));
}
public bool Contains(string str)
{
if (internalQueue.BinarySearch(str) >= 0)
{
return (true);
}
else
{
return (false);
}
}
public int BinarySearch(string str)
{
return (internalQueue.BinarySearch(str, specialComparer));
}
public bool Contains(string str, IComparer specialComparer)
{
if (internalQueue.BinarySearch(str, specialComparer) >= 0)
{
return (true);
}
else
{
return (false);
}
}
public void CopyTo(Array array, int index)
{
internalQueue.CopyTo(array, index);
}
public virtual object[] ToArray( )
{
return (internalQueue.ToArray( ));
}
public virtual void TrimToSize( )
{
internalQueue.TrimToSize( );
}
public void Enqueue(string str)
{
internalQueue.Add(str);
internalQueue.Sort(specialComparer);
}
public string DequeueSmallest( )
{
string s = (string)internalQueue[0];
internalQueue.RemoveAt(0);
return (s);
}
public string DequeueLargest( )
{
string s = (string)internalQueue[internalQueue.Count - 1];
internalQueue.RemoveAt(internalQueue.Count - 1);
return (s);
}
public string PeekSmallest( )
{
return ((string)internalQueue[0]);
}
public string PeekLargest( )
{
return ((string)internalQueue[internalQueue.Count - 1]);
}
public IEnumerator 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 items—in this case, string values—may 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 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 ArrayList. This was the simplest way to construct this type of queue, since an ArrayList 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, TrimToSize, and many others. Some of the more important methods to examine are Enqueue, DequeueSmallest, DequeueLargest, PeekSmallest, and PeekLargest. The Enqueue method accepts a string as an argument and adds it to the end of the internalQueue. Next, this ArrayList 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 ArrayList after each item is added, we 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 ArrayList 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.Length), 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 ContainsString and Contains methods. The only real difference between these two methods is that the Contains method uses the IComparer interface of the string object, whereas the Contains method uses the specialComparer interface to use when searching for a string in the internalQueue, if one is provided. The PriorityQueue class members are listed in Table 10-1.
The PriorityQueue can be created and filled with strings using code like the following: class CTest
{
static void Main( )
{
// Create ArrayList of messages
ArrayList msgs = new ArrayList( );
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
CompareStrLen comparer = new CompareStrLen( );
PriorityQueue pqueue = new PriorityQueue(comparer);
// Add all messages from the ArrayList 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);
}
// 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( ));
}
}
}
An ArrayList of string messages is created that will be used to fill the queue. A new CompareStrLen IComparer type object is created and passed in to the constructor of the PriorityQueue. If we did not pass in this IComparer object, the output would be much different; instead of retrieving items from the queue based on length, they would be retrieved based on their alphabetical order. (The IComparer interface is covered in detail in the Discussion section.) Finally, a foreach loop is used to enqueue all messages into the PriorityQueue object. At this point, the PriorityQueue object can be used in a manner similar to the Queue class contained in the FCL, except for the ability to remove items from both the head and tail of the queue. DiscussionYou can instantiate the PriorityQueue class with or without a special comparer object. In the case of our example, this special comparer object is defined as follows: public class CompareStrLen : IComparer
{
public int Compare(object obj1, object obj2)
{
int result = 0;
if ((obj1 is string) && (obj2 is string))
{
result = Compare((string)obj1, (string)obj2);
}
else
{
throw (new ArgumentException("Arguments are not both strings"));
}
return (result);
}
public int Compare(string str1, string str2)
{
if (str1.Length == str2.Length)
{
return (0);
}
else if (str1.Length > str2.Length)
{
return (1);
}
else
{
return (-1);
}
}
}
This special comparer is required because we want to prioritize the elements in the queue by size. The default string IComparer interface compares strings alphabetically. Implementing the IComparer interface requires that we implement a single method, Compare, with the following signature: int Compare(object x, object 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 implementation is used. It attempts to convert its two object arguments to strings and, in turn, calls a second overload of the Compare method that accepts two string type arguments. This second Compare method simply returns a 0 if both strings are of the same length, a 1 if the first string argument is larger than the second, and a -1 if the reverse is true. If we wanted to compare objects other than strings, the previous IComparer interface could be modified as follows: public class CompareObjs : IComparer
{
public int Compare(object obj1, object obj2)
{
int result = 0;
IComparable comparableObj1 = obj1 as IComparable;
IComparable comparableObj2 = obj2 as IComparable;
if(comparableObj1 != null && comparableObj2 != null)
{
result = comparableObj1.CompareTo(comparableObj2);
}
else
{
throw (new ArgumentException(
"Arguments do not both implement IComparable"));
}
return (result);
}
public int Compare(string str1, string str2)
{
if (str1.Length == str2.Length)
{
return (0);
}
else if (str1.Length > str2.Length)
{
return (1);
}
else
{
return (-1);
}
}
}
This CompareObjs method requires that both objects implement the IComparable interface. If they do not, you will need to modify the type to implement this interface. This interface requires the CompareTo method to be implemented in the type. The definition of this method is as follows: int CompareTo(object obj) This method accepts an object to compare with this instance. The return value is calculated as follows:
It is up to you to decide how the CompareTo method is implemented and to define what makes two of these objects equal, greater than, or less than one another. See AlsoSee the "ArrayList Class," "IEnumerable Interface," "ICloneable Interface," "IComparer Interface," and "IComparable Interface" topics in the MSDN documentation. |
| [ Team LiB ] |
|