using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Runtime.InteropServices;

namespace Brains.Framework
{
    /// <summary>
    /// Represents an item stored in a priority queue.
    /// </summary>
    /// <typeparam name="TValue">The type of object in the queue.</typeparam>
    /// <typeparam name="TPriority">The type of the priority field.</typeparam>
    [Serializable]
    internal struct PriorityQueueItem<TValue, TPriority>
    {
        private TValue value;
        private TPriority priority;

        public PriorityQueueItem(TValue val, TPriority pri)
        {
            this.value = val;
            this.priority = pri;
        }

        /// <summary>
        /// Gets the value of this PriorityQueueItem.
        /// </summary>
        public TValue Value
        {
            get { return value; }
        }

        /// <summary>
        /// Gets the priority associated with this PriorityQueueItem.
        /// </summary>
        public TPriority Priority
        {
            get { return priority; }
        }
    }


    /// <summary>
    /// Represents a binary heap priority queue.
    /// </summary>
    /// <typeparam name="TValue">The type of object in the queue.</typeparam>
    /// <typeparam name="TPriority">The type of the priority field.</typeparam>
    [Serializable]
    [ComVisible(false)]
    internal class PriorityQueue<TValue, TPriority> : ICollection, IEnumerable<PriorityQueueItem<TValue, TPriority>>
    {
        private PriorityQueueItem<TValue, TPriority>[] items;

        private const Int32 DefaultCapacity = 16;
        private Int32 capacity;
        private Int32 numItems;

        private Comparison<TPriority> compareFunc;

        /// <summary>
        /// Initializes a new instance of the PriorityQueue class that is empty,
        /// has the default initial capacity, and uses the default IComparer.
        /// </summary>
        public PriorityQueue() : this(DefaultCapacity, Comparer<TPriority>.Default)
        {
        }

        /// <summary>
        /// Initializes a new instance of the PriorityQueue class that is empty,
        /// has the specified initial capacity, and uses the default IComparer.
        /// </summary>
        /// <param name="initialCapacity">Desired initial capacity.</param>
        public PriorityQueue(Int32 initialCapacity) : this(initialCapacity, Comparer<TPriority>.Default)
        {
        }

        /// <summary>
        /// Initializes a new instance of the PriorityQueue class that is empty,
        /// has the default initial capacity, and uses the specified IComparer.
        /// </summary>
        /// <param name="comparer">An object that implements the IComparer interface
        /// for items of type TPriority.</param>
        public PriorityQueue(IComparer<TPriority> comparer) : this(DefaultCapacity, comparer)
        {
        }

        /// <summary>
        /// Initializes a new instance of the PriorityQueue class that is empty,
        /// has the specified initial capacity, and uses the specified IComparer.
        /// </summary>
        /// <param name="initialCapacity">Desired initial capacity.</param>
        /// <param name="comparer">An object that implements the IComparer interface
        /// for items of type TPriority.</param>
        public PriorityQueue(int initialCapacity, IComparer<TPriority> comparer)
        {
            Init(initialCapacity, new Comparison<TPriority>(comparer.Compare));
        }

        /// <summary>
        /// Initializes a new instance of the PriorityQueue class that is empty,
        /// has the default initial capacity, and uses the specified comparison
        /// function for comparing items of type TPriority.
        /// </summary>
        /// <param name="comparison">The comparison function.</param>
        public PriorityQueue(Comparison<TPriority> comparison)
            : this(DefaultCapacity, comparison)
        {
        }

        /// <summary>
        /// Initializes a new instance of the PriorityQueue class that is empty,
        /// has the specified initial capacity, and uses the specified comparison
        /// function for comparing items of type TPriority.
        /// </summary>
        /// <param name="initialCapacity">The desired initial capacity.</param>
        /// <param name="comparison">The comparison function.</param>
        public PriorityQueue(int initialCapacity, Comparison<TPriority> comparison)
        {
            Init(initialCapacity, comparison);
        }

        // Initializes the queue
        private void Init(int initialCapacity, Comparison<TPriority> comparison)
        {
            numItems = 0;
            compareFunc = comparison;
            SetCapacity(initialCapacity);
        }

        /// <summary>
        /// Gets the number of items that are currently in the queue.
        /// </summary>
        public int Count
        {
            get { return numItems; }
        }

        /// <summary>
        /// Gets or sets the queue's capacity.
        /// </summary>
        public int Capacity
        {
            get { return items.Length; }
            set { SetCapacity(value); }
        }

        // Set the queue's capacity.
        private void SetCapacity(int newCapacity)
        {
            int newCap = newCapacity;
            if (newCap < DefaultCapacity)
                newCap = DefaultCapacity;

            // throw exception if newCapacity < numItems
            if (newCap < numItems)
                throw new ArgumentOutOfRangeException("newCapacity", "New capacity is less than Count");

            this.capacity = newCap;
            if (items == null)
            {
                // Initial allocation.
                items = new PriorityQueueItem<TValue, TPriority>[newCap];
                return;
            }

            // Resize the array.
            Array.Resize(ref items, newCap);
        }

        /// <summary>
        /// Adds an object to the queue, in order by priority.
        /// </summary>
        /// <param name="value">The object to be added.</param>
        /// <param name="priority">Priority of the object to be added.</param>
        public void Enqueue(TValue value, TPriority priority)
        {
            if (numItems == capacity)
            {
                // need to increase capacity
                // grow by 50 percent
                //SetCapacity((3 * Capacity) / 2);
                SetCapacity((int)(Capacity * 1.5));
            }

            // Create the new item
            PriorityQueueItem<TValue, TPriority> newItem =
                new PriorityQueueItem<TValue, TPriority>(value, priority);
            int i = numItems;
            ++numItems;

            // and insert it into the heap.
            while ((i > 0) && (compareFunc(items[i / 2].Priority, newItem.Priority) > 0))
            {
                items[i] = items[i / 2];
                i /= 2;
            }
            items[i] = newItem;
        }

        // Remove a node at a particular position in the queue.
        private PriorityQueueItem<TValue, TPriority> RemoveAt(Int32 index)
        {
            // remove an item from the heap
            PriorityQueueItem<TValue, TPriority> o = items[index];
            PriorityQueueItem<TValue, TPriority> tmp = items[numItems - 1];
            items[--numItems] = default(PriorityQueueItem<TValue, TPriority>);
            if (numItems > 0)
            {
                int i = index;
                int j = i + 1;
                while (i < Count / 2)
                {
                    if ((j < Count - 1) && (compareFunc(items[j].Priority, items[j + 1].Priority) > 0))
                    {
                        j++;
                    }
                    if (compareFunc(items[j].Priority, tmp.Priority) >= 0)
                    {
                        break;
                    }
                    items[i] = items[j];
                    i = j;
                    j *= 2;
                }
                items[i] = tmp;
            }
            return o;
        }

        /// <summary>
        /// Removes and returns the item with the highest priority from the queue.
        /// </summary>
        /// <returns>The object that is removed from the beginning of the queue.</returns>
        public PriorityQueueItem<TValue, TPriority> Dequeue()
        {
            if (Count == 0)
                throw new InvalidOperationException("The queue is empty");
            return RemoveAt(0);
        }

        /// <summary>
        /// Removes the item with the specified value from the queue.
        /// The passed equality comparison is used.
        /// </summary>
        /// <param name="item">The item to be removed.</param>
        /// <param name="comp">An object that implements the IEqualityComparer interface
        /// for the type of item in the collection.</param>
        public void Remove(TValue item, IEqualityComparer comparer)
        {
            // need to find the PriorityQueueItem that has the Data value of o
            for (int index = 0; index < numItems; ++index)
            {
                if (comparer.Equals(item, items[index].Value))
                {
                    RemoveAt(index);
                    return;
                }
            }
            throw new ApplicationException("The specified itemm is not in the queue.");
        }

        /// <summary>
        /// Removes the item with the specified value from the queue.
        /// The default type comparison function is used.
        /// </summary>
        /// <param name="item">The item to be removed.</param>
        public void Remove(TValue item)
        {
            Remove(item, EqualityComparer<TValue>.Default);
        }

        /// <summary>
        /// Returns the object at the beginning of the priority queue without removing it.
        /// </summary>
        /// <returns>The object at the beginning of the queue.</returns>
        public PriorityQueueItem<TValue, TPriority> Peek()
        {
            if (Count == 0)
                throw new InvalidOperationException("The queue is empty");
            return items[0];
        }

        /// <summary>
        /// Removes all objects from the queue.
        /// </summary>
        public void Clear()
        {
            numItems = 0;
            TrimExcess();
        }

        /// <summary>
        /// Sets the capacity to the actual number of elements in the Queue,
        /// if that number is less than 90 percent of current capacity. 
        /// </summary>
        public void TrimExcess()
        {
            if (numItems < (0.9 * capacity))
                SetCapacity(numItems);
        }

        /// <summary>
        /// Determines whether an element is in the queue.
        /// </summary>
        /// <param name="o">The object to locate in the queue.</param>
        /// <returns>True if item found in the queue.  False otherwise.</returns>
        public bool Contains(TValue item)
        {
            foreach (PriorityQueueItem<TValue, TPriority> qItem in items)
            {
                if (qItem.Value.Equals(item))
                    return true;
            }
            return false;
        }

        /// <summary>
        /// Copies the elements of the ICollection to an Array, starting at a particular Array index. 
        /// </summary>
        /// <param name="array">The one-dimensional Array that is the destination of the elements copied from ICollection.
        /// The Array must have zero-based indexing.</param>
        /// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
        public void CopyTo(PriorityQueueItem<TValue, TPriority>[] array, int arrayIndex)
        {
            if (array == null)
                throw new ArgumentNullException("array");
            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException("arrayIndex", "arrayIndex is less than 0.");
            if (array.Rank > 1)
                throw new ArgumentException("array is multidimensional.");
            if (arrayIndex >= array.Length)
                throw new ArgumentException("arrayIndex is equal to or greater than the length of the array.");
            if (numItems > (array.Length - arrayIndex))
                throw new ArgumentException("The number of elements in the source ICollection is greater than the available space from arrayIndex to the end of the destination array.");

            Array.Copy(items, 0, array, arrayIndex, numItems);
        }

        /// <summary>
        /// Copies the queue elements to a new array. 
        /// </summary>
        /// <returns>A new array containing elements copied from the Queue.</returns>
        public PriorityQueueItem<TValue, TPriority>[] ToArray()
        {
            PriorityQueueItem<TValue, TPriority>[] newItems =
                new PriorityQueueItem<TValue, TPriority>[numItems];
            Array.Copy(items, newItems, numItems);
            return newItems;
        }

        #region ICollection Members

        /// <summary>
        /// Copies the elements of the ICollection to an Array, starting at a particular Array index. 
        /// </summary>
        /// <param name="array">The one-dimensional Array that is the destination of the elements copied from ICollection.
        /// The Array must have zero-based indexing.</param>
        /// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
        void ICollection.CopyTo(Array array, int index)
        {
            this.CopyTo((PriorityQueueItem<TValue, TPriority>[])array, index);
        }

        /// <summary>
        /// Gets a value indicating whether access to the ICollection is synchronized (thread safe). 
        /// </summary>
        bool ICollection.IsSynchronized
        {
            get { return false; }
        }

        /// <summary>
        /// Gets an object that can be used to synchronize access to the ICollection. 
        /// </summary>
        object ICollection.SyncRoot
        {
            get { return items.SyncRoot; }
        }

        #endregion

        #region IEnumerable<PriorityQueueItem<TValue,TPriority>> Members

        /// <summary>
        /// Returns an enumerator that iterates through a collection. 
        /// </summary>
        /// <returns>An IEnumerator that can be used to iterate through the collection.</returns>
        public IEnumerator<PriorityQueueItem<TValue, TPriority>> GetEnumerator()
        {
            for (int i = 0; i < numItems; i++)
            {
                yield return items[i];
            }
        }

        #endregion

        #region IEnumerable Members

        /// <summary>
        /// Returns an enumerator that iterates through a collection.
        /// </summary>
        /// <returns>An IEnumerator that can be used to iterate through the collection.</returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion
    }

    #region Interfaces
    public interface IPriorityQueue<T>
    {
        #region Methods
        int Push(T item);
        T Pop();
        T Peek();
        void Update(int i);
        #endregion
    }
    #endregion

    internal class PriorityQueueB<T> : IPriorityQueue<T>
    {
        #region Variables Declaration
        protected List<T> InnerList = new List<T>();
        protected IComparer<T> mComparer;
        #endregion

        #region Contructors
        public PriorityQueueB()
        {
            mComparer = Comparer<T>.Default;
        }

        public PriorityQueueB(IComparer<T> comparer)
        {
            mComparer = comparer;
        }

        public PriorityQueueB(IComparer<T> comparer, int capacity)
        {
            mComparer = comparer;
            InnerList.Capacity = capacity;
        }
        #endregion

        #region Methods
        protected void SwitchElements(int i, int j)
        {
            T h = InnerList[i];
            InnerList[i] = InnerList[j];
            InnerList[j] = h;
        }

        protected virtual int OnCompare(int i, int j)
        {
            return mComparer.Compare(InnerList[i], InnerList[j]);
        }

        /// <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 item)
        {
            int p = InnerList.Count, p2;
            InnerList.Add(item); // E[p] = O
            do
            {
                if (p == 0)
                    break;
                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, p1, p2, pn;
            InnerList[0] = InnerList[InnerList.Count - 1];
            InnerList.RemoveAt(InnerList.Count - 1);
            do
            {
                pn = p;
                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);

            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, pn;
            int p1, 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
            {
                pn = p;
                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];
            return default(T);
        }

        public void Clear()
        {
            InnerList.Clear();
        }

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

        public void RemoveLocation(T item)
        {
            int index = -1;
            for (int i = 0; i < InnerList.Count; i++)
            {

                if (mComparer.Compare(InnerList[i], item) == 0)
                    index = i;
            }

            if (index != -1)
                InnerList.RemoveAt(index);
        }

        public T this[int index]
        {
            get { return InnerList[index]; }
            set
            {
                InnerList[index] = value;
                Update(index);
            }
        }
        #endregion
    }
}