#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&lt;T&gt;"/> class.
        /// </summary>
        public BinaryPriorityQueue()
            : this(Comparer<T>.Default)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BinaryPriorityQueue&lt;T&gt;"/> 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&lt;T&gt;"/> 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&lt;T&gt;"/> 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
    }
}