PriorityDeque

gistfile1.cs

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