Garlands Blog

/*
 Copyright (c) 2008, André Ahrens
 All rights reserved.

 Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
 - Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
 - Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
 - Neither the name of embalon.de nor the name of the author may be used to endorse or promote products derived from this software without specific prior written permission.

 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */


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

namespace Embalon
{
     /// <summary>
     /// Generic PriorityQueue with ability to change priority after an
     /// element was added
     /// </summary>
     /// <typeparam name="TPriority">Type of priority of elements
     /// </typeparam>
     /// <typeparam name="TElement">Type of elements</typeparam>
     public class PriorityQueue<TPriority, TElement>
         where TPriority: IComparable
     {
         List<ElementContainer> Heap = new List<ElementContainer>();
         PriorityMode Mode = PriorityMode.MaxFirst;

         public PriorityQueue()
         {

         }

         /// <summary>
         ///
         /// </summary>
         /// <param name="Mode">Should the PriorityQueue consider a higher
         /// or alower value as a higher priority</param>
         public PriorityQueue(PriorityMode Mode)
         {
             this.Mode = Mode;
         }

         bool HasHigherPriority(TPriority a, TPriority b)
         {
             return (Mode == PriorityMode.MaxFirst) ?
                 a.CompareTo(b) > 0 : a.CompareTo(b) < 0;
         }

         /// <summary>
         /// The same as Enqueue: Add an element to the PriorityQueue
         /// </summary>
         /// <param name="Priority">Priority of the element</param>
         /// <param name="Element">The element</param>
         public void Add(TPriority Priority, TElement Element)
         {
             Heap.Add(new ElementContainer(Priority, Element));
             ChangePriority(Element, Priority);
         }

         /// <summary>
         /// The same as Add: Add an element to the PriorityQueue
         /// </summary>
         /// <param name="Priority">Priority of the element</param>
         /// <param name="Element">The element</param>
         public void Enqueue(TPriority Priority, TElement Element)
         {
             Add(Priority, Element);
         }

         /// <summary>
         /// Returns the topmost element of the PriorityQueue and
         /// removes it from the queue
         /// </summary>
         /// <returns>The element in the queue with the
         //// highest priority</returns>
         public TElement Dequeue()
         {
             if (Heap.Count == 0)
                 throw new Exception("Queue is empty");
             TElement Result = Heap[0].Element;
             Remove(0);
             return Result;
         }

         /// <summary>
         /// Returns the topmost element of the PriorityQueue
         /// </summary>
         /// <returns>The element in the queue with the highest
         /// priority</returns>
         public TElement Peek()
         {
             if (Heap.Count == 0)
                 throw new Exception("Queue is empty");
             return Heap[0].Element;
         }

         /// <summary>
         /// Removes an element from the queue, identified by
         /// comparing it to the given element
         /// </summary>
         /// <param name="Element">The element which should
         /// be removed</param>
         public void Remove(TElement Element)
         {
             Remove(GetElementIndex(Element));
         }

         /// <summary>
         /// Removes an element from the queue, identified by index.
         /// </summary>
         /// <param name="ElementIndex">The index of the element
         /// which should be removed</param>
         public void Remove(int ElementIndex)
         {
             if (ElementIndex >= Heap.Count || ElementIndex < 0)
                 throw new Exception("Index is out of allowed range");

             Heap[ElementIndex] = Heap[Heap.Count - 1];
             Heap.RemoveAt(Heap.Count - 1);
             Reheap(ElementIndex);
         }

         /// <summary>
         /// Change the priority of an element
         /// </summary>
         /// <param name="Element">The element whose priority
         /// should be changed</param>
         /// <param name="NewPriority">The new priority</param>
         public void ChangePriority(TElement Element, TPriority NewPriority)
         {
             ChangePriority(GetElementIndex(Element), NewPriority);
         }

         int GetElementIndex(TElement Element)
         {
             for (int i = 0; i < Heap.Count; i++)
             {
                 if (Heap[i].Element.Equals(Element))
                 {
                     return i;
                 }
             }
             throw new Exception("Element not found");
         }

         /// <summary>
         /// Change the priority of an element
         /// </summary>
         /// <param name="ElementIndex">The index of the element
         /// whose priority should be changed</param>
         /// <param name="NewPriority">The new priority</param>
         public void ChangePriority(int ElementIndex, TPriority NewPriority)
         {
             if (ElementIndex >= Heap.Count || ElementIndex < 0)
                 throw new Exception("Index is out of allowed range");

             if (HasHigherPriority(Heap[ElementIndex].Priority,
                 NewPriority))
             {
                 Heap[ElementIndex].Priority = NewPriority;
                 Reheap(ElementIndex);
             }
             else
             {
                 Heap[ElementIndex].Priority = NewPriority;
                 while (((ElementIndex - 1) / 2) >= 0 &&
                     HasHigherPriority(NewPriority,
                     Heap[(ElementIndex - 1) / 2].Priority))
                 {
                     ElementContainer Temp = Heap[(ElementIndex - 1) / 2];
                     Heap[(ElementIndex - 1) / 2] = Heap[ElementIndex];
                     Heap[ElementIndex] = Temp;
                     ElementIndex = (ElementIndex - 1) / 2;
                 }
             }
         }

         void Reheap(int Index)
         {
             if (2 * Index + 2 > Heap.Count)
                 return;
             else if (2 * Index + 2 == Heap.Count)
             {
                 if (HasHigherPriority(Heap[2 * Index + 1].Priority,
                     Heap[Index].Priority))
                 {
                     ElementContainer Temp = Heap[2 * Index + 1];
                     Heap[2 * Index + 1] = Heap[Index];
                     Heap[Index] = Temp;
                     Reheap(2 * Index + 1);
                 }
             }
             else
             {
                 int MaxChildIndex = (HasHigherPriority(
                     Heap[2 * Index + 1].Priority,
                     Heap[2 * Index + 2].Priority)) ?
                     (2 * Index + 1) : (2 * Index + 2);
                 if (HasHigherPriority(Heap[MaxChildIndex].Priority,
                     Heap[Index].Priority))
                 {
                     ElementContainer Temp = Heap[MaxChildIndex];
                     Heap[MaxChildIndex] = Heap[Index];
                     Heap[Index] = Temp;
                     Reheap(MaxChildIndex);
                 }
             }
         }

         public int Count
         {
             get
             {
                 return Heap.Count;
             }
         }

         /// <summary>
         /// Removes all elements from the queue
         /// </summary>
         public void Clear()
         {
             Heap.Clear();
         }

         /// <summary>
         /// Detects if a given element is part of the queue
         /// </summary>
         /// <param name="Element">Element that should be searched</param>
         /// <returns>True if given element is in the queue</returns>
         public bool Contains(TElement Element)
         {
             if (Element is IComparable)
             {
                 foreach (ElementContainer E in Heap)
                 {
                     if (E.Element.Equals(Element))
                         return true;
                 }
                 return false;
             }
             else throw new Exception("Element is not comparable");
         }

         class ElementContainer
         {
             public TPriority Priority;
             public TElement Element;

             public ElementContainer(TPriority Priority, TElement Element)
             {
                 this.Priority = Priority;
                 this.Element = Element;
             }
         }

     }

     public enum PriorityMode
     {
         MaxFirst, MinFirst
     }
}