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);
}
}
}