As part of getting my blog back up and running I’ve been trying out some code formatters. After trying out the formatter at http://www.manoli.net/csharpformat/ and being a bit disappointed, I found a good stackoverflow response suggesting Windows Liver Writer with Paste From Visual Studio plugin. This seems to work far better than I had expected and it isn’t specific to C#!
The rest of this post is just showing off the code formatting on a generic priority queue I wrote this weekend for a Traveling Salesman demo.
Start by adding the relevant namespaces.
using System;
using System.Linq;
using System.Collections.Generic;
In order to make our priority queue completely generic, we create a generic queue node type to associate each data item with its priority score.
/// <summary>
/// A basic generic priority queue node.
/// </summary>
/// <typeparam name="T">The data type to be wrapped by associated instances.</typeparam>
internal class PriorityQueueNode<T>
{
/// <summary>
/// Gets or sets the item associated with this instance.
/// </summary>
public T Item { get; set; }
/// <summary>
/// Gets or sets the integer priority associated with this instance.
/// </summary>
public int Priority { get; set; }
/// <summary>
/// Creates a string representation of this PriorityQueueNode instance.
/// </summary>
/// <returns>A string representation of this PriorityQueueNode instance.</returns>
public override string ToString()
{
return String.Format("[{0}:{1}]", Item, Priority);
}
}
Next, we build the priority queue class itself. Note that we are using the new SortedSet<> class from .NET 4.0. I’ll have to get into that in a future post. (For the impatient, here’s a pretty good Code Project article on it.) Essentially, all this code is doing is setting up the queue around the SortedSet<> instance and associating an IComparer instance with it.
/// <summary>
/// Represents a simple generic priority queue.
/// </summary>
/// <typeparam name="T">The data type to use with the associated instances.</typeparam>
internal class PriorityQueue<T>
{
private SortedSet<PriorityQueueNode<T>> mItems;
private IComparer<PriorityQueueNode<T>> mComparer;
/// <summary>
/// Initializes a new instance of the PriorityQueue class.
/// </summary>
public PriorityQueue()
{
mComparer = new PriorityComparer<T>();
mItems = new SortedSet<PriorityQueueNode<T>>(mComparer);
}
Next, we implement the basic queue operations. For this queue we are defining the three most common queue operations:
- Enqueue() – Add a node with its priority.
- Dequeue() – Remove the first node.
- Peek() – Get the first node without removing it.
/// <summary>
/// Enqueues the given item with the given priority.
/// </summary>
/// <param name="item">The item to enqueue.</param>
/// <param name="priority">The priority to associate with the given item.</param>
public void Enqueue(T item, int priority)
{
PriorityQueueNode<T> node = new PriorityQueueNode<T>()
{
Item = item,
Priority = priority
};
mItems.Add(node);
}
/// <summary>
/// Removes the lowest priority valued item and returns it.
/// </summary>
/// <returns>The lowest ranked item from the queue.</returns>
/// <exception cref="InvalidOperationException">
/// An InvalidOperationException is thrown if the queue is empty.
/// </exception>
public T Dequeue()
{
if (mItems.Count == 0)
{
throw new InvalidOperationException("Queue is empty.");
}
//Grab the first node, remove it, and return it.
PriorityQueueNode<T> node = mItems.First<PriorityQueueNode<T>>();
mItems.Remove(node);
return node.Item;
}
/// <summary>
/// Returns the lowest priority valued item without removing it from the queue.
/// </summary>
/// <returns>The lowest ranked item from the queue.</returns>
/// <exception cref="InvalidOperationException">
/// An InvalidOperationException is thrown if the queue is empty.
/// </exception>
public T Peek()
{
if (mItems.Count == 0)
{
throw new InvalidOperationException("Queue is empty.");
}
//Grab the first node and return it.
return (mItems.First<PriorityQueueNode<T>>()).Item;
}
Really, there isn’t too much interesting going on here except for the use of LINQ to grab the first item. SortedList<> doesn’t implement indexers the way that other collection classes do so this was an easy way to grab the first item.
With the queue implemented, the last thing you need is just to implement an IComparer that can be used to compare two priority queue nodes when the SortedSet<> rebalances itself internally. Depending on how you implement the comparer, you can dramatically change the way the queue operates. (For example having it dequeue higher ranked items rather than lower ranked items as I implemented it.) For my implementation, I use the default CompareTo() methods to compare the integer priorities and then check on an equal priority to see if the items are actually the same item. This sorts the queue so that the lowest ranked elements are returned first –exactly what I needed for my Traveling Salesman demo.
/// <summary>
/// Compares two PriorityQueueNodes.
/// </summary>
/// <param name="x">The first node to compare.</param>
/// <param name="y">The second node to compare.</param>
/// <returns>An integer indicating the relative position of x to y.</returns>
public int Compare(PriorityQueueNode<T> x, PriorityQueueNode<T> y)
{
int compareValue = x.Priority.CompareTo(y.Priority);
return ((compareValue == 0) && (x.Item.Equals(y.Item) == false)) ? (-1) : compareValue;
}
Just a few footnotes…
- If you feel so inclined, you can implement multiple IComparer classes and implement your queue to choose one at runtime. This is probably a better way to do it if you’re looking for reuse.
- This particular implementation is certainly not thread-safe. Something to keep in mind.
- Also, if you throw away thread safety, you can probably make the IComparer instance in the PriorityQueue<> class static to avoid having a new instance of the comparer for each priority queue instance. I didn’t bother for my demo because I was going to have exactly one instance of the queue, but it crossed my mind.
Filter by APML
Subscribe