pmunin
2/27/2017 - 11:42 PM

Simple .NET PriorityQueue based on SortedDictionary<TKey, Queue<TItem>> (BST) behind the scene

Simple .NET PriorityQueue based on SortedDictionary<TKey, Queue> (BST) behind the scene

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace PriorityQueueUtils
{
    public static class QueueWrappers
    {
        public static IQueue<T> AsQueue<T>(this Stack<T> lifo)
        {
            return new StackWrapper<T>(lifo);
        }

        public static IQueue<T> AsQueue<T>(this Queue<T> fifo)
        {
            return new QueueWrapper<T>(fifo);
        }
    }


    public class QueueWrapper<T> : IQueue<T>
    {
        public QueueWrapper(Queue<T> source)
        {
            this.source = source ?? new Queue<T>();
        }
        Queue<T> source;

        public bool IsEmpty => source.Count == 0;

        public T Dequeue()
        {
            return source.Dequeue();
        }

        public void Enqueue(T item)
        {
            source.Enqueue(item);
        }

        public IEnumerator<T> GetEnumerator()
        {
            return source.GetEnumerator();
        }

        public T Peek()
        {
            return source.Peek();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public bool Contains(T item)
        {
            return source.Contains(item);
        }

        public void EnqueueRange(IEnumerable<T> items)
        {
            foreach (var item in items)
            {
                source.Enqueue(item);
            }
        }
    }

    public class StackWrapper<T> : IQueue<T>
    {
        private Stack<T> source;

        public StackWrapper(Stack<T> source)
        {
            this.source = source ?? new Stack<T>();
        }

        public bool IsEmpty => source.Count == 0;

        public bool Contains(T item)
        {
            return source.Contains(item);
        }

        public T Dequeue()
        {
            return source.Pop();
        }

        public void Enqueue(T item)
        {
            source.Push(item);
        }

        public void EnqueueRange(IEnumerable<T> items)
        {
            foreach (var item in items)
            {
                Enqueue(item);
            }
        }

        public IEnumerator<T> GetEnumerator()
        {
            return source.GetEnumerator();
        }

        public T Peek()
        {
            return source.Peek();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Xunit;

namespace PriorityQueueUtils
{
    public class PriorityQueueTests
    {
        [Fact()]
        public void TestNullKey()
        {
            var items = new List<(MyPriority Priority, string name)>()
            {
                (new MyPriority(1),"adasd") ,
                (new MyPriority(3453),""),
                (null, "qweqwe")
            } ;

            var queue = PriorityQueue.Create(items, i => i.Priority, MyPriority.Comparer.Instance);
            while (!queue.IsEmpty)
            {
                var next = queue.Dequeue();
            }
        }

        class MyPriority
        {
            public MyPriority(int priority)
            {
                this.Priority = priority;
            }

            public int Priority { get; set; }
            public class Comparer : Comparer<MyPriority>
            {
                public static Comparer Instance { get; } = new Comparer(); 
                public override int Compare(MyPriority x, MyPriority y)
                {
                    //if (x == null) return 0;
                    //if (y == null) return 0;
                    return (x?.Priority??0) - (y?.Priority??0);
                }
            }
        }

    }
}
//Latest version is here: https://gist.github.com/affc23dd89950e67ece9ca3b19b9508a.git
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace PriorityQueueUtils
{
    /// <summary>
    /// Queue contract
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public interface IQueue<T>: IEnumerable<T>
    {
        /// <summary>
        /// Add item to queue
        /// </summary>
        /// <param name="item"></param>
        void Enqueue(T item);
        /// <summary>
        /// Add item to queue
        /// </summary>
        /// <param name="item"></param>
        void EnqueueRange(IEnumerable<T> items);
        /// <summary>
        /// Remove top item from queue
        /// </summary>
        /// <returns></returns>
        T Dequeue();
        /// <summary>
        /// Check if queue is empty
        /// </summary>
        bool IsEmpty { get; }

        /// <summary>
        /// Get item on the top of the queue, without removing it from the queue
        /// </summary>
        /// <returns></returns>
        T Peek();

        /// <summary>
        /// Check if the queue contains specified item
        /// </summary>
        /// <param name="item"></param>
        /// <returns></returns>
        bool Contains(T item);
    }

    /// <summary>
    /// Double ended queue, allowing to dequeue from top and bottom of the queue
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public interface IQueueDoubleEnded<T>: IQueue<T>
    {
        /// <summary>
        /// Dequeue from the bottom of the queue
        /// </summary>
        /// <returns></returns>
        T DequeueLast();

        /// <summary>
        /// Get the last item of the queue
        /// </summary>
        /// <returns></returns>
        T PeekLast();
    }

    /// <summary>
    /// Simple key value based Min Heap priority queue.
    /// Uses SortedDictionary and its BST behind the scene. Unlike SortedDictionary it Allow duplicate values.
    /// </summary>
    /// <typeparam name="TItem"></typeparam>
    /// <typeparam name="TPriority"></typeparam>
    public class PriorityQueue<TItem, TPriority> : IQueueDoubleEnded<TItem>, IEnumerable<TItem>
    {
        public PriorityQueue(Func<TItem, TPriority> getPriority, IEnumerable<TItem> items = null, IComparer<TPriority> comparer = null)
        {
            this.getPriority = getPriority;
            var tupleComparer = comparer != null ? new TupleComparer<TPriority>(comparer) : null;
            binaryTree = new SortedDictionary<Tuple<TPriority>, Queue<TItem>>(tupleComparer);
            AddRange(items);
        }

        /// <summary>
        /// Add multiple items to the queue
        /// </summary>
        /// <param name="items"></param>
        public void AddRange(IEnumerable<TItem> items)
        {
            foreach (var item in items ?? Enumerable.Empty<TItem>())
                Enqueue(item);
        }

        Func<TItem, TPriority> getPriority;

        /// <summary>
        /// Dictionary prohibit using Null as key, that's why we have to create Tuple
        /// </summary>
        SortedDictionary<Tuple<TPriority>, Queue<TItem>> binaryTree;
        public IEnumerable<TItem> GetItems()
        {
            foreach (var kvp in binaryTree)
                foreach (var item in kvp.Value)
                    yield return item;
        }

        public bool IsEmpty
        {
            get
            {
                return binaryTree.Count == 0;
            }
        }

        public TItem Dequeue()
        {
            var firstKvp = binaryTree.First();
            var res = firstKvp.Value.Dequeue();
            if (firstKvp.Value.Count == 0)
                if (!binaryTree.Remove(firstKvp.Key))
                {
                    //throw new InvalidOperationException();
                }
            return res;
        }

        Tuple<TPriority> T(TPriority priority)
        {
            //TODO: pooling to save memory
            return Tuple.Create(priority);
        }


        public void Enqueue(TItem item)
        {
            Queue<TItem> queue = null;
            var key = T(getPriority(item));
            if (!binaryTree.TryGetValue(key, out queue))
                binaryTree[key] = queue = new Queue<TItem>();
            queue.Enqueue(item);
        }

        IEnumerator<TItem> IEnumerable<TItem>.GetEnumerator()
        {
            return this.GetItems().GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetItems().GetEnumerator();
        }

        public TItem DequeueLast()
        {
            var kvp = binaryTree.Last();
            var res = kvp.Value.Dequeue();
            if (kvp.Value.Count == 0)
                binaryTree.Remove(kvp.Key);
            return res;
        }

        public TItem Peek()
        {
            var firstKvp = binaryTree.First();
            var res = firstKvp.Value.Peek();
            return res;
        }

        public TItem PeekLast()
        {
            var kvp = binaryTree.Last();
            var res = kvp.Value.Peek();
            return res;
        }

        public bool Contains(TItem item)
        {
            var itemPriority = T(getPriority(item));
            Queue<TItem> items = null;
            if (!binaryTree.TryGetValue(itemPriority, out items))
                return false;
            return items.Contains(item);
        }

        public void EnqueueRange(IEnumerable<TItem> items)
        {
            foreach (var item in items)
            {
                Enqueue(item);
            }
        }
    }

    /// <summary>
    /// Required to support adding Null as a Key to dictionaries (Nullable Priority to PriorityQueue)
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class TupleComparer<T> : IComparer<Tuple<T>>
    {
        public TupleComparer(IComparer<T> source)
        {
            this.Source = source??Comparer<T>.Default;
        }

        public IComparer<T> Source { get; private set; }

        public int Compare(Tuple<T> x, Tuple<T> y)
        {
            return Source.Compare(x.Item1, y.Item1);
        }
    }


    /// <summary>
    /// Simple Min Heap priority queue.
    /// Uses SortedDictionary and its BST behind the scene. Unlike SortedDictionary it Allow duplicate values.
    /// </summary>
    /// <typeparam name="TItem"></typeparam>
    public class PriorityQueue<TItem> : PriorityQueue<TItem, TItem>
    {
        public PriorityQueue(IEnumerable<TItem> items = null, IComparer<TItem> comparer = null) : base(i => i, items, comparer)
        {
        }
    }

    /// <summary>
    /// Helper class for creating PriorityQueues
    /// </summary>
    public static class PriorityQueue
    {
        /// <summary>
        /// Create priority queue, which will be sorted by comparer
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="items"></param>
        /// <param name="comparer"></param>
        /// <returns></returns>
        public static PriorityQueue<T> Create<T>(IEnumerable<T> items = null, IComparer<T> comparer = null)
        {
            return new PriorityQueue<T>(items, comparer);
        }

        /// <summary>
        /// Create priority queue, that will be sorted by priority extracted from item using specified delegate function
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <typeparam name="TPriority"></typeparam>
        /// <param name="items"></param>
        /// <param name="getPriority"></param>
        /// <param name="comparer"></param>
        /// <returns></returns>
        public static PriorityQueue<T, TPriority> Create<T, TPriority>(IEnumerable<T> items, Func<T, TPriority> getPriority, IComparer<TPriority> comparer = null)
        {
            return new PriorityQueue<T, TPriority>(getPriority, items, comparer);
        }
    }

}