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 recieved 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:
/// <summary>
/// Helper class that implements a priority queue
/// </summary>
/// <typeparam name="T">The type of the values placed in the queue</typeparam>
public class PriorityQueue<T>:ListMapping<int,T>
{
#region Constructor
/// <summary>
/// Constructor
/// </summary>
public PriorityQueue()
: base()
{
}
#endregion
#region Public Functions
/// <summary>
/// Peek at the next thing in the queue
/// </summary>
/// <returns></returns>
public virtual T Peek()
{
if (Items.ContainsKey(HighestKey))
{
return Items[HighestKey][0];
}
return default(T);
}
public override void Add(int Priority, T Value)
{
if (Priority > HighestKey)
HighestKey = Priority;
base.Add(Priority, Value);
}
/// <summary>
/// Removes an item from the queue and returns it
/// </summary>
/// <returns>The next item in the queue</returns>
public T Remove()
{
T ReturnValue=default(T);
if (Items.ContainsKey(HighestKey)&&Items[HighestKey].Count >= 1)
{
ReturnValue = Items[HighestKey][0];
Items[HighestKey].Remove(ReturnValue);
if (Items[HighestKey].Count == 0)
{
Items.Remove(HighestKey);
HighestKey = int.MinValue;
foreach (int Key in Items.Keys)
{
if (Key > HighestKey)
HighestKey = Key;
}
}
}
return ReturnValue;
}
#endregion
#region Protected Variables
protected int HighestKey = int.MinValue;
#endregion
}
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:
/// <summary>
/// Maps a key to a list of data
/// </summary>
/// <typeparam name="T1">Key value</typeparam>
/// <typeparam name="T2">Type that the list should contain</typeparam>
public class ListMapping<T1,T2>
{
#region Constructors
/// <summary>
/// Constructor
/// </summary>
public ListMapping()
{
}
#endregion
#region Private Variables
protected Dictionary<T1, List<T2>> Items = new Dictionary<T1, List<T2>>();
#endregion
#region Public Functions
/// <summary>
/// Adds an item to the mapping
/// </summary>
/// <param name="Key">Key value</param>
/// <param name="Value">The value to add</param>
public virtual void Add(T1 Key, T2 Value)
{
try
{
if (Items.ContainsKey(Key))
{
Items[Key].Add(Value);
}
else
{
Items.Add(Key, new List<T2>());
Items[Key].Add(Value);
}
}
catch { throw; }
}
/// <summary>
/// Determines if a key exists
/// </summary>
/// <param name="key">Key to check on</param>
/// <returns>True if it exists, false otherwise</returns>
public virtual bool ContainsKey(T1 key)
{
try
{
return Items.ContainsKey(key);
}
catch { throw; }
}
/// <summary>
/// The list of keys within the mapping
/// </summary>
public virtual ICollection<T1> Keys
{
get { try { return Items.Keys; } catch { throw; } }
}
/// <summary>
/// Remove a list of items associated with a key
/// </summary>
/// <param name="key">Key to use</param>
/// <returns>True if the key is found, false otherwise</returns>
public virtual bool Remove(T1 key)
{
try
{
return Items.Remove(key);
}
catch { throw; }
}
/// <summary>
/// Gets a list of values associated with a key
/// </summary>
/// <param name="key">Key to look for</param>
/// <returns>The list of values</returns>
public virtual List<T2> this[T1 key]
{
get
{
return Items[key];
}
set
{
Items[key] = value;
}
}
/// <summary>
/// Clears all items from the listing
/// </summary>
public virtual void Clear()
{
Items.Clear();
}
/// <summary>
/// The number of items in the listing
/// </summary>
public virtual int Count
{
get { return Items.Count; }
}
#endregion
}
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.
cb9b6530-ae61-4bb0-82c8-f25d4b214529|0|.0