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.
Create 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.
Table 10-1. PriorityQueue class members
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.
You 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(objectx
, objecty
);
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:
A negative number less than zero is returned if the current instance
is less than obj
.
A zero is returned if the current instance is equal to
obj
.
A positive number greater than zero is returned if the current
instance is greater than obj
.
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.