Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
PriorityDeque
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace us.lambdacalcul.collections
{
public class PriorityDeque<T, P>
{
private enum OperationType
{
Front,
Back
}
private InternalPriorityDeque<T, P> Root;
private IComparer<P> Comparer;
public PriorityDeque()
: this(Comparer<P>.Default)
{
}
public PriorityDeque(IComparer<P> comparer)
{
Comparer = comparer;
Root = null;
}
public void PushFront(T value, P priority)
{
EnsureRoot(priority);
Root.Push(OperationType.Front, value, priority);
}
public void PushBack(T value, P priority)
{
EnsureRoot(priority);
Root.Push(OperationType.Back, value, priority);
}
public T PopFront()
{
EnsureRoot();
T result = Root.Pop(OperationType.Front);
if (Root.InternalDeque.IsEmpty())
{
Root = Root.Left;
}
return result;
}
public T PopBack()
{
EnsureRoot();
T result = Root.Pop(OperationType.Back);
if (Root.InternalDeque.IsEmpty())
{
Root = Root.Left;
}
return result;
}
public T PeekFront()
{
EnsureRoot();
return Root.Peek(OperationType.Front);
}
public T PeekBack()
{
if (Root == null)
{
throw new InvalidOperationException("PeekBack operation is invalid because the PriorityDeque is empty.");
}
else
{
return Root.Peek(OperationType.Back);
}
}
public override string ToString()
{
if (Root != null)
{
return Root.ToString();
}
else
{
return "null";
}
}
private void EnsureRoot()
{
if(Root == null)
{
throw new InvalidOperationException("Operation is invalid because the collection is empty.");
}
}
private void EnsureRoot(P priority)
{
if(Root == null)
{
Root = new InternalPriorityDeque<T, P>(priority, Comparer);
}
}
private class InternalPriorityDeque<T, P>
{
public P DequePriority;
public LinkedList<T> InternalDeque;
public IComparer<P> Comparer;
public InternalPriorityDeque<T, P> Left;
public InternalPriorityDeque<T, P> Right;
public InternalPriorityDeque(P priority, IComparer<P> comparer)
{
DequePriority = priority;
Comparer = comparer;
InternalDeque = new LinkedList<T>();
Left = null;
Right = null;
}
public void Push(OperationType type, T value, P valuePriority)
{
int c = Comparer.Compare(valuePriority, DequePriority);
if (c < 0)
{
if (Left == null)
{
Left = new InternalPriorityDeque<T, P>(valuePriority, Comparer);
}
Left.Push(type, value, valuePriority);
}
else if (c > 0)
{
if (Right == null)
{
Right = new InternalPriorityDeque<T, P>(valuePriority, Comparer);
}
Right.Push(type, value, valuePriority);
}
else // c == 0
{
if (type == OperationType.Front)
{
InternalDeque.AddFirst(value);
}
else
{
InternalDeque.AddLast(value);
}
}
}
public T Pop(OperationType type)
{
if (Right != null)
{
T result = Right.Pop(type);
if (Right.InternalDeque.IsEmpty())
{
if (Right.Left == null)
{
Right = null;
}
else
{
Right = Right.Left;
}
}
return result;
}
else
{
if (type == OperationType.Front)
{
T result = InternalDeque.First.Value;
InternalDeque.RemoveFirst();
return result;
}
else
{
T result = InternalDeque.Last.Value;
InternalDeque.RemoveLast();
return result;
}
}
}
public T Peek(OperationType type)
{
if (Right != null)
{
return Right.Peek(type);
}
else
{
if (type == OperationType.Front)
{
return InternalDeque.First.Value;
}
else
{
return InternalDeque.Last.Value;
}
}
}
public override string ToString()
{
return string.Format("({0} <- Priority {1}: [{2}] -> {3})", Left != null ? Left.ToString() : "Null", DequePriority, string.Join(",", InternalDeque.Select(x => x.ToString()).ToArray()), Right != null ? Right.ToString() : "Null");
}
}
}
public class PriorityQueue<T, P> : PriorityDeque<T, P>
{
public PriorityQueue() : base()
{
}
public PriorityQueue(IComparer<P> comparer) : base(comparer)
{
}
public void Enqueue(T value, P priority)
{
PushFront(value, priority);
}
public T Dequeue()
{
return PopBack();
}
public T Peek()
{
return PeekBack();
}
}
public class PriorityStack<T, P> : PriorityDeque<T, P>
{
private PriorityDeque<T, P> InternalDeque;
public PriorityStack() : base()
{
}
public PriorityStack(IComparer<P> comparer) : base(comparer)
{
}
public void Push(T value, P priority)
{
PushFront(value, priority);
}
public T Pop()
{
return PopFront();
}
public T Peek()
{
return PeekFront();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment