#region Arthea License /*********************************************************************** * Arthea MUD by R. Jennings (2007) http://arthea.googlecode.com/ * * By using this code you comply with the Artistic and GPLv2 Licenses. * ***********************************************************************/ #endregion // Taken from Suroden (http://sourceforge.net/projects/suroden) // - RJ, Aug'07 using System; using System.Collections; using System.Collections.Generic; namespace Arthea.Updates { /// <summary> /// Interface for a priority queue /// </summary> /// <typeparam name="T">The type to queue</typeparam> public interface IPriorityQueue<T> : IList<T> { /// <summary> /// Pushes the specified object. /// </summary> /// <param name="O">The object.</param> /// <returns></returns> int Push(T O); /// <summary> /// Pops this instance. /// </summary> /// <returns></returns> T Pop(); /// <summary> /// Peeks this instance. /// </summary> /// <returns></returns> T Peek(); /// <summary> /// Updates the specified i. /// </summary> /// <param name="i">The i.</param> void Update(int i); } /// <summary> /// Implementation of binary priority queue. /// </summary> /// <typeparam name="T"></typeparam> public class BinaryPriorityQueue<T> : IPriorityQueue<T> { #region [rgn] Fields (2) /// <summary> /// the comparer /// </summary> protected IComparer<T> Comparer; /// <summary> /// The inner list /// </summary> protected List<T> InnerList = new List<T>(); #endregion [rgn] #region [rgn] Methods (2) // [rgn] Protected Methods (2) /// <summary> /// Called when [compare]. /// </summary> /// <param name="i">The i.</param> /// <param name="j">The j.</param> /// <returns></returns> protected virtual int OnCompare(int i, int j) { return Comparer.Compare(InnerList[i], InnerList[j]); } /// <summary> /// Switches the elements. /// </summary> /// <param name="i">The i.</param> /// <param name="j">The j.</param> protected void SwitchElements(int i, int j) { T h = InnerList[i]; InnerList[i] = InnerList[j]; InnerList[j] = h; } #endregion [rgn] #region contructors /// <summary> /// Initializes a new instance of the <see cref="BinaryPriorityQueue<T>"/> class. /// </summary> public BinaryPriorityQueue() : this(Comparer<T>.Default) { } /// <summary> /// Initializes a new instance of the <see cref="BinaryPriorityQueue<T>"/> class. /// </summary> /// <param name="c">The c.</param> public BinaryPriorityQueue(IComparer<T> c) { Comparer = c; } /// <summary> /// Initializes a new instance of the <see cref="BinaryPriorityQueue<T>"/> class. /// </summary> /// <param name="C">The C.</param> public BinaryPriorityQueue(int C) : this(Comparer<T>.Default, C) { } /// <summary> /// Initializes a new instance of the <see cref="BinaryPriorityQueue<T>"/> class. /// </summary> /// <param name="c">The c.</param> /// <param name="Capacity">The capacity.</param> public BinaryPriorityQueue(IComparer<T> c, int Capacity) { Comparer = c; InnerList.Capacity = Capacity; } #endregion #region public methods /// <summary> /// Gets a value indicating whether this instance is synchronized. /// </summary> /// <value> /// <c>true</c> if this instance is synchronized; otherwise, <c>false</c>. /// </value> public bool IsSynchronized { get { return false; } } /// <summary> /// Gets the sync root. /// </summary> /// <value>The sync root.</value> public object SyncRoot { get { return this; } } /// <summary> /// Push an object onto the PQ /// </summary> /// <param name="O">The new object</param> /// <returns>The index in the list where the object is _now_. This will change when objects are taken from or put onto the PQ.</returns> public int Push(T O) { int p = InnerList.Count; InnerList.Add(O); // E[p] = O do { if (p == 0) break; int p2 = (p - 1)/2; if (OnCompare(p, p2) < 0) { SwitchElements(p, p2); p = p2; } else break; } while (true); return p; } /// <summary> /// Get the smallest object and remove it. /// </summary> /// <returns>The smallest object</returns> public T Pop() { T result = InnerList[0]; int p = 0; InnerList[0] = InnerList[InnerList.Count - 1]; InnerList.RemoveAt(InnerList.Count - 1); do { int pn = p; int p1 = 2*p + 1; int p2 = 2*p + 2; if (InnerList.Count > p1 && OnCompare(p, p1) > 0) // links kleiner p = p1; if (InnerList.Count > p2 && OnCompare(p, p2) > 0) // rechts noch kleiner p = p2; if (p == pn) break; SwitchElements(p, pn); } while (true); return result; } /// <summary> /// Notify the PQ that the object at position i has changed /// and the PQ needs to restore order. /// Since you dont have access to any indexes (except by using the /// explicit IList.this) you should not call this function without knowing exactly /// what you do. /// </summary> /// <param name="i">The index of the changed object.</param> public void Update(int i) { int p = i; int p2; do // aufsteigen { if (p == 0) break; p2 = (p - 1)/2; if (OnCompare(p, p2) < 0) { SwitchElements(p, p2); p = p2; } else break; } while (true); if (p < i) return; do // absteigen { int pn = p; int p1 = 2*p + 1; p2 = 2*p + 2; if (InnerList.Count > p1 && OnCompare(p, p1) > 0) // links kleiner p = p1; if (InnerList.Count > p2 && OnCompare(p, p2) > 0) // rechts noch kleiner p = p2; if (p == pn) break; SwitchElements(p, pn); } while (true); } /// <summary> /// Get the smallest object without removing it. /// </summary> /// <returns>The smallest object</returns> public T Peek() { if (InnerList.Count > 0) return InnerList[0]; else return default(T); } /// <summary> /// Determines whether [contains] [the specified value]. /// </summary> /// <param name="value">The value.</param> /// <returns> /// <c>true</c> if [contains] [the specified value]; otherwise, <c>false</c>. /// </returns> public bool Contains(T value) { return InnerList.Contains(value); } /// <summary> /// Removes all items from the <see cref="T:System.Collections.Generic.ICollection`1"></see>. /// </summary> /// <exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only. </exception> public void Clear() { InnerList.Clear(); } /// <summary> /// Gets the number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"></see>. /// </summary> /// <value></value> /// <returns>The number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</returns> public int Count { get { return InnerList.Count; } } /// <summary> /// Returns an enumerator that iterates through the collection. /// </summary> /// <returns> /// A <see cref="T:System.Collections.Generic.IEnumerator`1"></see> that can be used to iterate through the collection. /// </returns> public IEnumerator<T> GetEnumerator() { return InnerList.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return InnerList.GetEnumerator(); } /// <summary> /// Copies to. /// </summary> /// <param name="array">The array.</param> /// <param name="index">The index.</param> public void CopyTo(T[] array, int index) { InnerList.CopyTo(array, index); } #endregion #region explicit implementation /// <summary> /// Gets a value indicating whether this instance is fixed size. /// </summary> /// <value> /// <c>true</c> if this instance is fixed size; otherwise, <c>false</c>. /// </value> public bool IsFixedSize { get { return false; } } /// <summary> /// Gets a value indicating whether the <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only. /// </summary> /// <value></value> /// <returns>true if the <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only; otherwise, false.</returns> public bool IsReadOnly { get { return false; } } /// <summary> /// Gets or sets value at the specified index. /// </summary> /// <value></value> public T this[int index] { get { return InnerList[index]; } set { InnerList[index] = value; Update(index); } } /// <summary> /// Adds the specified o. /// </summary> /// <param name="o">The o.</param> public void Add(T o) { Push(o); } /// <summary> /// Removes the <see cref="T:System.Collections.Generic.IList`1"></see> item at the specified index. /// </summary> /// <param name="index">The zero-based index of the item to remove.</param> /// <exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.IList`1"></see> is read-only.</exception> /// <exception cref="T:System.ArgumentOutOfRangeException">index is not a valid index in the <see cref="T:System.Collections.Generic.IList`1"></see>.</exception> public void RemoveAt(int index) { throw new NotSupportedException(); } /// <summary> /// Inserts the specified index. /// </summary> /// <param name="index">The index.</param> /// <param name="value">The value.</param> public void Insert(int index, T value) { throw new NotSupportedException(); } /// <summary> /// Removes the specified value. /// </summary> /// <param name="value">The value.</param> /// <returns></returns> public bool Remove(T value) { throw new NotSupportedException(); } /// <summary> /// Indexes the of. /// </summary> /// <param name="value">The value.</param> /// <returns></returns> public int IndexOf(T value) { throw new NotSupportedException(); } #endregion } }