Priority Queue and Multi Value Sorted Dictionary in C#

• Download source code - 24.4 KB

Microsoft .NET Framework contains a rich set of collection types including generic, non-generic, and specialized, and almost every kind of requirement can be handled using these collections. The introduction of concurrent collections in .NET Framework 4.0 has even closed the gap for writing custom thread safe collections. Concurrent collections provide the thread safety where multiple threads can access the collections concurrently and work on.

In one of my projects, I required to use a Priority Queue where I could sort the items according to a certain priority and retrieve the item with the highest priority. Unfortunately, .NET Framework does not include a specific collection type that provides this particular functionality. Searching the web, I found multiple implementations of the data structure here on CodeProject, and a third party library PowerCollections that included a number of other collection types. Although I could use any of these, I wanted a wrapper over one of the .NET Framework collections.

Microsoft .NET Framework generic collections include the sorted dictionary that represents a collection of key/value pairs sorted on the key. A priority queue can be thought of as a sorted dictionary, but it includes multiple values for one key, whereas a sorted dictionary allows only one value per key. So the idea is to implement a multi value sorted dictionary and then wrap that collection to provide the interfaces for manipulating the queue functionality.

The MultiValueSortedDictionary is a wrapper over the SortedDictionary and implements the generic and non-generic versions of IDictionary, ICollection, and IEnumerable interfaces as are implemented by SortedDictionary. The class uses SortedDictionary in a composition relationship instead of inheriting to avoid tightly coupling it to the collection type and to encapsulate the multi value handling. The multiple values for a key are saved in a List collection and added to the dictionary.

public class MultiValueSortedDictionary<TKey, TValue> : 
                IDictionary<TKey, TValue>, 
                ICollection<KeyValuePair<TKey, TValue>>, 
                IEnumerable<KeyValuePair<TKey, TValue>>, 
                IDictionary, ICollection, IEnumerable
{
    private SortedDictionary<TKey, List<TValue>> _SortedDictionary;
    private int _Count;
    private bool _IsModified;

    ...
    ...
}

The class uses the IComparer implementation provided to sort the keys. In-case none is provided, then it uses the default IComparer implementation associated with the key. The class also accepts a generic dictionary list to copy the elements.

public MultiValueSortedDictionary()
{
    _SortedDictionary = new SortedDictionary<TKey, List<TValue>>();
}

public MultiValueSortedDictionary(IComparer<TKey> comparer)
{
    _SortedDictionary = new SortedDictionary<TKey, List<TValue>>(comparer);
}

public MultiValueSortedDictionary(IDictionary<TKey, TValue> dictionary)
    : this()
{
    if (dictionary == null) throw new ArgumentNullException("dictionary");

    foreach (KeyValuePair<TKey, TValue> pair in dictionary)
        this.Add(pair.Key, pair.Value);
    _IsModified = false;
}

public MultiValueSortedDictionary(IDictionary<TKey, TValue> dictionary, 
       IComparer<TKey> comparer) : this(comparer)
{
    if (dictionary == null) throw new ArgumentNullException("dictionary");

    foreach (KeyValuePair<TKey, TValue> pair in dictionary)
        this.Add(pair.Key, pair.Value);
    _IsModified = false;
}

While adding an item to the collection with a specified key and value, it first checks whether the specified key has already an associated list of values and adds the value to the list. Otherwise it creates a new instance of the List<T> collection type, adds the value to the list, and sets it as the value of the provided key in the sorted dictionary.

public void Add(TKey key, TValue value)
{
    if (key == null) throw new ArgumentNullException("key");
    
    List<TValue> values;

    if (!_SortedDictionary.TryGetValue(key, out values))
    {
        values = new List<TValue>();
        _SortedDictionary[key] = values;
    }

    values.Add(value);
    ++_Count;
    _IsModified = true;
}

The class implements the indexed property to access the values using an array like notation and the key as the index. It returns the first value in the associated list of values for the key when used as getter, and adds the value at the end of the list of values associated with the provided key when used as setter.

public TValue this[TKey key]
{
    get
    {
        if (key == null) throw new ArgumentNullException("key");

        List<TValue> values;
        if (!_SortedDictionary.TryGetValue(key, out values))
            throw new KeyNotFoundException();
        TValue value = default(TValue);
        if (values != null)
            value = values[0];
        return value;
    }
    set
    {
        if (key == null) throw new ArgumentNullException("key");

        Add(key, value);
    }
}

The class also implements two methods to remove a key and its associated values from the dictionary or a specific value associated with a key. The method to remove all the associated values of a key accepts the key as parameter and removes the associated list. The method to remove a key/value pair retrieves the list of values associated with the key and deletes the first instance of the value from the list. If the list contains no further values, then the key is also removed from the dictionary.

public bool Remove(TKey key)
{
    if (key == null) throw new ArgumentNullException();

    bool removed = false;
    List<TValue> values;
    if (_SortedDictionary.TryGetValue(key, out values) &&
        _SortedDictionary.Remove(key))
    {
        _Count -= values.Count;
        _IsModified = removed = true;
    }
    return removed;
}

public bool Remove(KeyValuePair<TKey, TValue> item)
{
    if (item.Key == null ||
        item.Key == null)
        throw new ArgumentException();

    bool removed = false;
    List<TValue> values;
    if (_SortedDictionary.TryGetValue(item.Key, out values) &&
        values.Remove(item.Value))
    {
        --_Count;
        if (values.Count == 0)
            _SortedDictionary.Remove(item.Key);
        removed = true;
        _IsModified = true;
    }
    return removed;
}

Similarly, it provides interfaces to safely retrieve a single value or the list of values associated with a key. The two overloads of the TryGetValue method are used for this purpose.

public bool TryGetValue(TKey key, out TValue value)
{
    if (key == null) throw new ArgumentNullException();

    value = default(TValue);
    bool found = false;
    List<TValue> values;
    if (_SortedDictionary.TryGetValue(key, out values))
    {
        value = values[0];
        found = true;
    }
    return found;
}

public bool TryGetValue(TKey key, out IEnumerable<TValue> values)
{
    if (key == null) throw new ArgumentNullException();

    values = null;
    bool found = false;
    List<TValue> valuesList;
    if (_SortedDictionary.TryGetValue(key, out valuesList))
    {
        values = valuesList;
        found = true;
    }
    return found;
}

Further, the class defines an inner structure that implements the enumeration interfaces. The enumerator is basically a wrapper over the SortedDictionary and the List enumerators. The MoveNext method iterates recursively over both the enumerators to retrieve the next available key/value pair.

public struct Enumerator : 
    IEnumerator<KeyValuePair<TKey, TValue>>, 
    IDisposable, IDictionaryEnumerator, IEnumerator
{
    private readonly KeyValuePair<TKey, TValue> DefaultCurrent;
    private MultiValueSortedDictionary<TKey, TValue> _Dictionary;
    private IEnumerator<KeyValuePair<TKey, List<TValue>>> _Enumerator1;
    private IEnumerator<TValue> _Enumerator2;
    private KeyValuePair<TKey, TValue> _Current;

    public bool MoveNext()
    {
        //if (_Disposed)
        //    throw new InvalidOperationException(
        //         "The enumerator has already been disposed.");

        if (_Dictionary._IsModified)
            throw new InvalidOperationException("The collection was " + 
                      "modified after the enumerator was created.");

        if (!_Valid) return false;
        TKey key = default(TKey);
        TValue value = default(TValue);
        if (_Enumerator2 == null)
        {
            if (_Enumerator1.MoveNext())
            {
                if (_Enumerator1.Current.Value != null)
                    _Enumerator2 = _Enumerator1.Current.Value.GetEnumerator();
            }
            else
                _Valid = false;
        }

        if (!_Valid) return false;

        key = _Enumerator1.Current.Key;
        if (_Enumerator2 != null)
        {
            if (_Enumerator2.MoveNext())
                value = _Enumerator2.Current;
            else
            {
                _Enumerator2 = null;
                return MoveNext();
            }
        }
        _Current = new KeyValuePair<TKey, TValue>(key, value);
        return true;
    }
}

Once the MultiValueSortedDictionary is implemented, it can be used directly as a priority queue, or a wrapper class can be defined that provides the interface for using the collection as a queue.

public class PriorityQueue<TPriority, TItem> : 
        IDictionary<TPriority, TItem>, 
        IEnumerable<KeyValuePair<TPriority, TItem>>, 
        IDictionary, ICollection, IEnumerable
{
    MultiValueSortedDictionary<TPriority, TItem> _Dictionary;

    ...
    ...

    public void Enqueue(TPriority priority, TItem item)
    {
        if (priority == null)
            throw new ArgumentNullException("priority");
        _Dictionary.Add(priority, item);
    }

    public TItem Dequeue()
    {
        if (Count == 0)
            throw new InvalidOperationException("The KoderHack.Collections." + 
                      "PriorityQueue<TPriority, TItem> is empty.");

        KeyValuePair<TPriority, TItem> pair = _Dictionary.First();
        _Dictionary.Remove(pair);
        return pair.Value;
    }

    public TItem Peek()
    {
        if (Count == 0)
            throw new InvalidOperationException("The KoderHack.Collections." + 
                      "PriorityQueue<TPriority, TItem> is empty.");

        return _Dictionary.First().Value;
    }
}

That is all implementing a priority queue. I hope this helps!