A generic PriorityQueue implementation based on Wintellect PowerCollections

I’ve recently started using Wintellect PowerCollections for my .NET 2.0 work. In case you don’t know it yet, that’s a very nice generic implementation of collection classes, similar in purpose to what the C++ standard template library has to offer. Peter Golde is the lead developer on this project and there’s the PowerCollections blog for those who want to follow development closely.

In a recent blog post, Peter outlined where the project was going, with steps that will be done and also two steps that won’t be done. One of these not-to-be-done steps was about the priority queue functionality that had originally been planned in the PowerCollection specs. In the newer posting, Peter suggested that the OrderedBag and OrderedSet classes, which are already available, could be used for priority queue functionality, so a special class for the same purpose wouldn’t be needed.

Why OrderedSet and OrderedBag don’t fit for me

Being in need of a priority queue implementation and based on this information, I tried to make the OrderedSet and/or OrderedBag classes work for me, which wasn’t very successful. I posted about some of my original confusion on the support forum on the Wintellect website before I finally understood that there seems to be a fundamental difference between Peter’s and my own understanding of what exactly a priority queue should provide.

Peter’s point of view is this, apparently: A priority queue is a collection class which sorts all its items by a “priority” criteria. By accessing all the items in the sorted order, I can effectively access them in the priority order. So any kind of sorted collection can do the job, really, as long as I can adapt the ordering method to use the “priority” criteria.

My point of view is this: A priority queue is an ordinary collection, like a Set or a Bag, depending on its use. I want to put objects in it and have uniqueness maintained if I’m using a Set. The priority is an additional dimension applied to each item and I want to be able to access the data in the collection in the order given by the priority. Each item’s priority may possibly be a complicated calculated value depending on other criteria. The notion of the priority must not interfere with “normal” usage of the collection.

The PowerCollections OrderedSet and OrderedBag classes aren’t fit for my purpose of a priority queue because they can only sort the data in them by one single comparer. If that comparer renders an order defined by the items’ priorities, the collection classes use that same comparer not only to determine the order, but also for all other comparisons that must be done. For example, it’s impossible to find out (using the normal Contains method) whether a given object is in the collection because only the priority level will be used for the comparison (in case it’s a Bag). If a Set is used, it’s not even possible to insert more than one item on the same priority level because items with the same priority level are considered equal and therefor forbidden in a Set.

So, two points of criticism here:

  1. The fact that the ICollection<T>.Contains() method is overridden in the OrderedSet and OrderedBag classes to use the provided comparer is completely correct as far as MS docs are concerned. But in the context of a priority queue it still robs me of important functionality. I have recently found another post on the PowerCollections blog about a utility method GetIdentityComparer. It’s possible that this can be used in conjunction with another utility function to find a specific object in the collection, I haven’t tried this. (Of course this is just my personal opinion, but I also don’t like the definition in MS docs very much, because as a developer using that method somewhere in code, I don’t really expect it to do anything else than finding out if the object I pass in is part of the collection. Having that method use some other comparer seems to me to be very counter-intuitive.)
  2. It’s practically impossible to use the OrderedSet in the context of a priority queue, unless I can be sure that each item in the collection will have it’s own unique priority level. It’s completely impossible to create a priority queue on this basis that will also check its items for uniqueness (not based on the comparer).

My own implementation

Using the PowerCollections Set and OrderedDictionary, I went on to create my own priority queue class that would behave the way I think it should. While it’s quite a flexible generic class, it may of course be slanted towards the purpose I had in mind at the time of writing, it wasn’t meant to be an all-round, all purpose class. Still, I thought there may be others who’d like to have a similar functionality, so I’m publishing my code here.

The class uses a delegate, that must be passed to its constructor, to calculate the priority level of each object, so the implementation of that calculation can be externalised. This is the declaration of the delegate:

public delegate L GetPriorityLevelDelegate<L, V> (V value);

The class restricts the type for the priority level to those that implement IComparable. This is done so the OrderedDictionary can use the IComparable interface to perform the ordering of the levels. This is sufficient in my case, of course a more complicated implementation would be possible where the other options for the OrderedDictionary (delegate or IComparer<T>) could be used. That said, here’s the code:

  public class PriorityQueue<L, V> : CollectionBase<V> 
    where L: IComparable {
    public PriorityQueue(GetPriorityLevelDelegate<L, V> getPriorityLevelDelegate, 
      bool iterateReverse) {
      this.getPriorityLevel = getPriorityLevelDelegate;
      this.iterateReverse = iterateReverse;
      
      Clear();
    }

    public PriorityQueue(GetPriorityLevelDelegate<L, V> getPriorityLevelDelegate) : 
      this (getPriorityLevelDelegate, false) { }

    private GetPriorityLevelDelegate<L, V> getPriorityLevel;

    private OrderedDictionary<L, Set<V>> levels;

    private Set<V> GetSetForItem(V item) {
      L level = getPriorityLevel(item);
      Set<V> set;
      if (!levels.ContainsKey(level)) {
        set = new Set<V>( );
        levels[level] = set;
      }
      else
        set = levels[level];
      return set;
    }

    public override void Add(V item) {
      Set<V> set = GetSetForItem(item);
      set.Add(item);
    }

    public override void Clear( ) {
      levels = new OrderedDictionary<L, Set<V>>();
    }

    public override bool Contains(V item) {
      Set<V> set = GetSetForItem(item);
      return set.Contains(item);
    }

    public override bool Remove(V item) {
      Set<V> set = GetSetForItem(item);
      return set.Remove(item);
    }

    public override int Count {
      get { 
        int count = 0;
        foreach (L level in levels.Keys)
          count += levels[level].Count;
        return count;
      }
    }

    public override V[] ToArray( ) {
      V[] result = new V[Count];
      int index = 0;
      foreach (V value in this)
        result[index++] = value;
      return result;
    }

    private bool iterateReverse;
    public bool IterateReverse {
      get { return iterateReverse; }
      set { iterateReverse = value; }
    }

    public override IEnumerator<V> GetEnumerator( ) {
      return Iterate().GetEnumerator();
    }

    public IEnumerable<V> Iterate(bool backwards) {
      ICollection<L> list = backwards ^ iterateReverse ? 
        levels.Reversed( ).Keys : levels.Keys;
      foreach (L level in list)
        foreach (V value in levels[level])
          yield return value;
    }

    public IEnumerable<V> Iterate( ) {
      return Iterate(iterateReverse);
    }

    public IEnumerable<V> IterateBackwards( ) {
      return Iterate(true);
    }
  }

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s