Skip to content

Instantly share code, notes, and snippets.

@lambdaknight

lambdaknight/gist:9061411

Created February 17, 2014 23:29
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save lambdaknight/9061411 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save lambdaknight/9061411 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. lambdaknight created this gist Feb 17, 2014.
    277 changes: 277 additions & 0 deletions gistfile1.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,277 @@
    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();
    }
    }
    }