Blog Series RSS FeedFollow gutgames on TwitterTwitter Feed



Other Posts in Data Types

  1. Replacing List
  2. Factory Pattern using Generics in C#
  3. Vector Class and Events in .Net
  4. Binary Trees in C# using Generics
  5. Priority Queue in C#
  6. Cheap Trick for Fluent Interfaces
  7. Building an DI Container

Priority Queue in C#

10/27/2009

This is simply one of my many data type posts. Not the most interesting of subjects, but hey it might help someone out. Anyway, I created a sort of distributed message based event system for a project that I was working on. Some messages/events were a bit more important than others and they were coming in faster than the system could handle so I figured that what was needed was a priority queue. A priority queue is basically a queue, first in first out, data type but items are prioritized. So an item with a lower priority will be returned after something of a higher priority but will be returned in the order it was received when compared to items of the same priority... Really you can think of this as a set of queues, one for each priority level. We start the highest priority and work our way down. And if none of that made sense (since I'm writing it, I give it a 50/50 chance that it didn't), you can read about them a bit more here. Anyway, I went ahead and implemented my own version since .Net only has your basic queue: 

   1: /// <summary>
   2: /// Helper class that implements a priority queue
   3: /// </summary>
   4: /// <typeparam name="T">The type of the values placed in the queue</typeparam>
   5: public class PriorityQueue<T>:ListMapping<int,T>
   6: {
   7:     #region Constructor
   8:  
   9:     /// <summary>
  10:     /// Constructor
  11:     /// </summary>
  12:     public PriorityQueue()
  13:         : base()
  14:     {
  15:     }
  16:  
  17:     #endregion
  18:  
  19:     #region Public Functions
  20:  
  21:     /// <summary>
  22:     /// Peek at the next thing in the queue
  23:     /// </summary>
  24:     /// <returns></returns>
  25:     public virtual T Peek()
  26:     {
  27:         if (Items.ContainsKey(HighestKey))
  28:         {
  29:             return Items[HighestKey][0];
  30:         }
  31:         return default(T);
  32:     }
  33:  
  34:     public override void Add(int Priority, T Value)
  35:     {
  36:         if (Priority > HighestKey)
  37:             HighestKey = Priority;
  38:         base.Add(Priority, Value);
  39:     }
  40:  
  41:     /// <summary>
  42:     /// Removes an item from the queue and returns it
  43:     /// </summary>
  44:     /// <returns>The next item in the queue</returns>
  45:     public T Remove()
  46:     {
  47:         T ReturnValue=default(T);
  48:         if (Items.ContainsKey(HighestKey)&&Items[HighestKey].Count >= 1)
  49:         {
  50:             ReturnValue = Items[HighestKey][0];
  51:             Items[HighestKey].Remove(ReturnValue);
  52:             if (Items[HighestKey].Count == 0)
  53:             {
  54:                 Items.Remove(HighestKey);
  55:                 HighestKey = int.MinValue;
  56:                 foreach (int Key in Items.Keys)
  57:                 {
  58:                     if (Key > HighestKey)
  59:                         HighestKey = Key;
  60:                 }
  61:             }
  62:         }
  63:         return ReturnValue;
  64:     }
  65:  
  66:     #endregion
  67:  
  68:     #region Protected Variables
  69:  
  70:     protected int HighestKey = int.MinValue;
  71:  
  72:     #endregion
  73: }

The code above is not the fastest out there but it gets the job done. It should be fairly straight forward but just know that the priority goes up, so 9 is a higher priority than 1. Also you may be wondering what the hell the ListMapping class is. It's another one of my classes from the utility library.  But the code for it can be found below: 

   1: /// <summary>
   2: /// Maps a key to a list of data
   3: /// </summary>
   4: /// <typeparam name="T1">Key value</typeparam>
   5: /// <typeparam name="T2">Type that the list should contain</typeparam>
   6: public class ListMapping<T1,T2>
   7: {
   8:     #region Constructors
   9:  
  10:     /// <summary>
  11:     /// Constructor
  12:     /// </summary>
  13:     public ListMapping()
  14:     {
  15:     }
  16:  
  17:     #endregion
  18:  
  19:     #region Private Variables
  20:  
  21:     protected Dictionary<T1, List<T2>> Items = new Dictionary<T1, List<T2>>();
  22:  
  23:     #endregion
  24:  
  25:     #region Public Functions
  26:  
  27:     /// <summary>
  28:     /// Adds an item to the mapping
  29:     /// </summary>
  30:     /// <param name="Key">Key value</param>
  31:     /// <param name="Value">The value to add</param>
  32:     public virtual void Add(T1 Key, T2 Value)
  33:     {
  34:         try
  35:         {
  36:             if (Items.ContainsKey(Key))
  37:             {
  38:                 Items[Key].Add(Value);
  39:             }
  40:             else
  41:             {
  42:                 Items.Add(Key, new List<T2>());
  43:                 Items[Key].Add(Value);
  44:             }
  45:         }
  46:         catch { throw; }
  47:     }
  48:  
  49:     /// <summary>
  50:     /// Determines if a key exists
  51:     /// </summary>
  52:     /// <param name="key">Key to check on</param>
  53:     /// <returns>True if it exists, false otherwise</returns>
  54:     public virtual bool ContainsKey(T1 key)
  55:     {
  56:         try
  57:         {
  58:             return Items.ContainsKey(key);
  59:         }
  60:         catch { throw; }
  61:     }
  62:  
  63:     /// <summary>
  64:     /// The list of keys within the mapping
  65:     /// </summary>
  66:     public virtual ICollection<T1> Keys
  67:     {
  68:         get { try { return Items.Keys; } catch { throw; } }
  69:     }
  70:  
  71:     /// <summary>
  72:     /// Remove a list of items associated with a key
  73:     /// </summary>
  74:     /// <param name="key">Key to use</param>
  75:     /// <returns>True if the key is found, false otherwise</returns>
  76:     public virtual bool Remove(T1 key)
  77:     {
  78:         try
  79:         {
  80:             return Items.Remove(key);
  81:         }
  82:         catch { throw; }
  83:     }
  84:  
  85:     /// <summary>
  86:     /// Gets a list of values associated with a key
  87:     /// </summary>
  88:     /// <param name="key">Key to look for</param>
  89:     /// <returns>The list of values</returns>
  90:     public virtual List<T2> this[T1 key]
  91:     {
  92:         get
  93:         {
  94:             return Items[key];
  95:         }
  96:         set
  97:         {
  98:             Items[key] = value;
  99:         }
 100:     }
 101:  
 102:     /// <summary>
 103:     /// Clears all items from the listing
 104:     /// </summary>
 105:     public virtual void Clear()
 106:     {
 107:         Items.Clear();
 108:     }
 109:  
 110:     /// <summary>
 111:     /// The number of items in the listing
 112:     /// </summary>
 113:     public virtual int Count
 114:     {
 115:         get { return Items.Count; }
 116:     }
 117:  
 118:  
 119:     #endregion
 120: }

Basically all the code does, is map a key (in this case an integer/priority) to a list of items. It's sort of like a dictionary object but allows you to add the same key multiple times and it simply adds it to the list. That being said, it shouldn't be too difficult to figure them out. So try them out, leave feedback, and happy coding.

Comments

 





 


Recent Posts

Craig’s Utility Library 3.2 Released
Version 3.2 of Craig's Utility Library has been released.
Craig’s Framework
This post talks about Craig's Framework, a set of core classes that will be used in most of my MVC based projects going forward and how I plan to open source it.
Personal Data Management
Start of a project that I will be working on that will attempt to put the vast majority of my personal online life into one location.
Craig’s Utility Library 3.1 Released
New version of Craig's Utility Library has been released.
Small Changes, Big Speed Ups
This post talks about a basic change that I did to the bitmap extensions that gave me a large increase in speed.

Recent Comments

Adjusting Contrast of an Image in C#
Roey - It is better to use ColorMatri...
Enabling JSONP in WCF
BLop - Just to inform :"Cross doma...
Viewstate Compression When Using AJAX
Tahri Akram - I'm using compressing/decompre...
Creating a Zip File in C#
Nicholas Carey - Why not use DotNetZip from htt...
Major Rework Happening
mark foley - Hi!Your site is amazing. ...
DISCLAIMER

The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.

© Copyright 2010