using System;
using System.Collections;

namespace Holo.Virtual.Rooms.Pathfinding
{
    /// <summary>
    /// The Heap allows to maintain a list sorted as long as needed.
    /// If no IComparer interface has been provided at construction, then the list expects the Objects to implement IComparer.
    /// If the list is not sorted it behaves like an ordinary list.
    /// When sorted, the list's "Add" method will put new objects at the right place.
    /// As well the "Contains" and "IndexOf" methods will perform a binary search.
    /// </summary>
    public class Heap : IList, ICloneable
    {
        #region Private Members

        private ArrayList FList;
        private IComparer FComparer = null;
        private bool FUseObjectsComparison;

        #endregion

        #region Constructors

        /// <summary>
        /// Default constructor.
        /// Since no IComparer is provided here, added objects must implement the IComparer interface.
        /// </summary>
        public Heap()
        {
            InitProperties(null, 0);
        }

        /// <summary>
        /// Constructor.
        /// Since no IComparer is provided, added objects must implement the IComparer interface.
        /// </summary>
        /// <param name="Capacity">Capacity of the list (<see cref="ArrayList.Capacity">ArrayList.Capacity</see>)</param>
        public Heap(int Capacity)
        {
            InitProperties(null, Capacity);
        }

        /// <summary>
        /// Constructor.
        /// </summary>
        /// <param name="Comparer">Will be used to compare added elements for sort and search operations.</param>
        public Heap(IComparer Comparer)
        {
            InitProperties(Comparer, 0);
        }

        /// <summary>
        /// Constructor.
        /// </summary>
        /// <param name="Comparer">Will be used to compare added elements for sort and search operations.</param>
        /// <param name="Capacity">Capacity of the list (<see cref="ArrayList.Capacity">ArrayList.Capacity</see>)</param>
        public Heap(IComparer Comparer, int Capacity)
        {
            InitProperties(Comparer, Capacity);
        }

        #endregion

        #region Properties

        /// <summary>
        /// If set to true, it will not be possible to add an object to the list if its value is already in the list.
        /// </summary>
        public bool AddDuplicates
        {
            set
            {
                FAddDuplicates = value;
            }
            get
            {
                return FAddDuplicates;
            }
        }
        private bool FAddDuplicates;

        /// <summary>
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        public int Capacity
        {
            get
            {
                return FList.Capacity;
            }
            set
            {
                FList.Capacity = value;
            }
        }

        #endregion

        #region IList Members

        /// <summary>
        /// IList implementation.
        /// Gets object's value at a specified index.
        /// The set operation is impossible on a Heap.
        /// </summary>
        /// <exception cref="ArgumentOutOfRangeException">Index is less than zero or Index is greater than Count.</exception>
        /// <exception cref="InvalidOperationException">[] operator cannot be used to set a value on a Heap.</exception>
        public object this[int Index]
        {
            get
            {
                if (Index >= FList.Count || Index < 0)
                    throw new ArgumentOutOfRangeException("Index is less than zero or Index is greater than Count.");
                return FList[Index];
            }
            set
            {
                throw new InvalidOperationException("[] operator cannot be used to set a value in a Heap.");
            }
        }

        /// <summary>
        /// IList implementation.
        /// Adds the object at the right place.
        /// </summary>
        /// <param name="O">The object to add.</param>
        /// <returns>The index where the object has been added.</returns>
        /// <exception cref="ArgumentException">The Heap is set to use object's IComparable interface, and the specifed object does not implement this interface.</exception>
        public int Add(object O)
        {
            int Return = -1;
            if (ObjectIsCompliant(O))
            {
                int Index = IndexOf(O);
                int NewIndex = Index >= 0 ? Index : -Index - 1;
                if (NewIndex >= Count) FList.Add(O);
                else FList.Insert(NewIndex, O);
                Return = NewIndex;
            }
            return Return;
        }

        /// <summary>
        /// IList implementation.
        /// Search for a specified object in the list.
        /// If the list is sorted, a <see cref="ArrayList.BinarySearch">BinarySearch</see> is performed using IComparer interface.
        /// Else the <see cref="Equals">Object.Equals</see> implementation is used.
        /// </summary>
        /// <param name="O">The object to look for</param>
        /// <returns>true if the object is in the list, otherwise false.</returns>
        public bool Contains(object O)
        {
            return FList.BinarySearch(O, FComparer) >= 0;
        }

        /// <summary>
        /// IList implementation.
        /// Returns the index of the specified object in the list.
        /// If the list is sorted, a <see cref="ArrayList.BinarySearch">BinarySearch</see> is performed using IComparer interface.
        /// Else the <see cref="Equals">Object.Equals</see> implementation of objects is used.
        /// </summary>
        /// <param name="O">The object to locate.</param>
        /// <returns>
        /// If the object has been found, a positive integer corresponding to its position.
        /// If the objects has not been found, a negative integer which is the bitwise complement of the index of the next element.
        /// </returns>
        public int IndexOf(object O)
        {
            int Result = -1;
            Result = FList.BinarySearch(O, FComparer);
            while (Result > 0 && FList[Result - 1].Equals(O))
                Result--;
            return Result;
        }

        /// <summary>
        /// IList implementation.
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        public bool IsFixedSize
        {
            get
            {
                return FList.IsFixedSize;
            }
        }

        /// <summary>
        /// IList implementation.
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        public bool IsReadOnly
        {
            get
            {
                return FList.IsReadOnly;
            }
        }

        /// <summary>
        /// IList implementation.
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        public void Clear()
        {
            FList.Clear();
        }

        /// <summary>
        /// IList implementation.
        /// Cannot be used on a Heap.
        /// </summary>
        /// <param name="Index">The index before which the object must be added.</param>
        /// <param name="O">The object to add.</param>
        /// <exception cref="InvalidOperationException">Insert method cannot be called on a Heap.</exception>
        public void Insert(int Index, object O)
        {
            throw new InvalidOperationException("Insert method cannot be called on a Heap.");
        }

        /// <summary>
        /// IList implementation.
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        /// <param name="Value">The object whose value must be removed if found in the list.</param>
        public void Remove(object Value)
        {
            FList.Remove(Value);
        }

        /// <summary>
        /// IList implementation.
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        /// <param name="Index">Index of object to remove.</param>
        public void RemoveAt(int Index)
        {
            FList.RemoveAt(Index);
        }

        #endregion

        #region IList.ICollection Members

        /// <summary>
        /// IList.ICollection implementation.
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        /// <param name="array"></param>
        /// <param name="arrayIndex"></param>
        public void CopyTo(Array array, int arrayIndex) { FList.CopyTo(array, arrayIndex); }

        /// <summary>
        /// IList.ICollection implementation.
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        public int Count { get { return FList.Count; } }

        /// <summary>
        /// IList.ICollection implementation.
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        public bool IsSynchronized { get { return FList.IsSynchronized; } }

        /// <summary>
        /// IList.ICollection implementation.
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        public object SyncRoot { get { return FList.SyncRoot; } }

        #endregion

        #region IList.IEnumerable Members

        /// <summary>
        /// IList.IEnumerable implementation.
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        /// <returns>Enumerator on the list.</returns>
        public IEnumerator GetEnumerator()
        {
            return FList.GetEnumerator();
        }

        #endregion

        #region IClonable Members

        /// <summary>
        /// ICloneable implementation.
        /// Idem <see cref="ArrayList">ArrayList</see>
        /// </summary>
        /// <returns>Cloned object.</returns>
        public object Clone()
        {
            Heap Clone = new Heap(FComparer, FList.Capacity);
            Clone.FList = (ArrayList)FList.Clone();
            Clone.FAddDuplicates = FAddDuplicates;
            return Clone;
        }

        #endregion

        #region Delegate Members

        /// <summary>
        /// Defines an equality for two objects
        /// </summary>
        public delegate bool Equality(object Object1, object Object2);

        #endregion

        #region Overridden Members

        /// <summary>
        /// Object.ToString() override.
        /// Build a string to represent the list.
        /// </summary>
        /// <returns>The string refecting the list.</returns>
        public override string ToString()
        {
            string OutString = "{";
            for (int i = 0; i < FList.Count; i++)
                OutString += FList[i].ToString() + (i != FList.Count - 1 ? "; " : "}");
            return OutString;
        }

        /// <summary>
        /// Object.Equals() override.
        /// </summary>
        /// <returns>true if object is equal to this, otherwise false.</returns>
        public override bool Equals(object Object)
        {
            Heap SL = (Heap)Object;
            if (SL.Count != Count)
                return false;
            for (int i = 0; i < Count; i++)
                if (!SL[i].Equals(this[i]))
                    return false;
            return true;
        }

        /// <summary>
        /// Object.GetHashCode() override.
        /// </summary>
        /// <returns>Hash code for this.</returns>
        public override int GetHashCode()
        {
            return FList.GetHashCode();
        }

        #endregion

        #region Public Members

        /// <summary>
        /// Idem IndexOf(object), but starting at a specified position in the list
        /// </summary>
        /// <param name="Object">The object to locate.</param>
        /// <param name="Start">The index for start position.</param>
        /// <returns></returns>
        public int IndexOf(object Object, int Start)
        {
            int Result = -1;
            Result = FList.BinarySearch(Start, FList.Count - Start, Object, FComparer);
            while (Result > Start && FList[Result - 1].Equals(Object))
                Result--;
            return Result;
        }

        /// <summary>
        /// Idem IndexOf(object), but with a specified equality function
        /// </summary>
        /// <param name="Object">The object to locate.</param>
        /// <param name="AreEqual">Equality function to use for the search.</param>
        /// <returns></returns>
        public int IndexOf(object Object, Equality AreEqual)
        {
            for (int i = 0; i < FList.Count; i++)
                if (AreEqual(FList[i], Object)) return i;
            return -1;
        }

        /// <summary>
        /// Idem IndexOf(object), but with a start index and a specified equality function
        /// </summary>
        /// <param name="Object">The object to locate.</param>
        /// <param name="Start">The index for start position.</param>
        /// <param name="AreEqual">Equality function to use for the search.</param>
        /// <returns></returns>
        public int IndexOf(object Object, int Start, Equality AreEqual)
        {
            if (Start < 0 || Start >= FList.Count) throw new ArgumentException("Start index must belong to [0; Count-1].");
            for (int i = Start; i < FList.Count; i++)
                if (AreEqual(FList[i], Object)) return i;
            return -1;
        }

        /// <summary>
        /// The objects will be added at the right place.
        /// </summary>
        /// <param name="C">The object to add.</param>
        /// <returns>The index where the object has been added.</returns>
        /// <exception cref="ArgumentException">The Heap is set to use object's IComparable interface, and the specifed object does not implement this interface.</exception>
        public void AddRange(ICollection C)
        {
            foreach (object Object in C)
                Add(Object);
        }

        /// <summary>
        /// Cannot be called on a Heap.
        /// </summary>
        /// <param name="Index">The index before which the objects must be added.</param>
        /// <param name="C">The object to add.</param>
        /// <exception cref="InvalidOperationException">Insert cannot be called on a Heap.</exception>
        public void InsertRange(int Index, ICollection C)
        {
            throw new InvalidOperationException("Insert cannot be called on a Heap.");
        }

        /// <summary>
        /// Limits the number of occurrences of a specified value.
        /// Same values are equals according to the Equals() method of objects in the list.
        /// The first occurrences encountered are kept.
        /// </summary>
        /// <param name="Value">Value whose occurrences number must be limited.</param>
        /// <param name="NumberToKeep">Number of occurrences to keep</param>
        public void LimitOccurrences(object Value, int NumberToKeep)
        {
            if (Value == null)
                throw new ArgumentNullException("Value");
            int Pos = 0;
            while ((Pos = IndexOf(Value, Pos)) >= 0)
            {
                if (NumberToKeep <= 0)
                    FList.RemoveAt(Pos);
                else
                {
                    Pos++;
                    NumberToKeep--;
                }
                if (FComparer.Compare(FList[Pos], Value) > 0)
                    break;
            }
        }

        /// <summary>
        /// Removes all duplicates in the list.
        /// Each value encountered will have only one representant.
        /// </summary>
        public void RemoveDuplicates()
        {
            int PosIt;
            PosIt = 0;
            while (PosIt < Count - 1)
            {
                if (FComparer.Compare(this[PosIt], this[PosIt + 1]) == 0)
                    RemoveAt(PosIt);
                else
                    PosIt++;
            }
        }

        /// <summary>
        /// Returns the object of the list whose value is minimum
        /// </summary>
        /// <returns>The minimum object in the list</returns>
        public int IndexOfMin()
        {
            int RetInt = -1;
            if (FList.Count > 0)
            {
                RetInt = 0;
                object RetObj = FList[0];
            }
            return RetInt;
        }

        /// <summary>
        /// Returns the object of the list whose value is maximum
        /// </summary>
        /// <returns>The maximum object in the list</returns>
        public int IndexOfMax()
        {
            int RetInt = -1;
            if (FList.Count > 0)
            {
                RetInt = FList.Count - 1;
                object RetObj = FList[FList.Count - 1];
            }
            return RetInt;
        }

        /// <summary>
        /// Returns the topmost object on the list and removes it from the list
        /// </summary>
        /// <returns>Returns the topmost object on the list</returns>
        public object Pop()
        {
            if (FList.Count == 0)
                throw new InvalidOperationException("The heap is empty.");
            object Object = FList[Count - 1];
            FList.RemoveAt(Count - 1);
            return (Object);
        }

        /// <summary>
        /// Pushes an object on list. It will be inserted at the right spot.
        /// </summary>
        /// <param name="Object">Object to add to the list</param>
        /// <returns></returns>
        public int Push(object Object)
        {
            return (Add(Object));
        }

        #endregion

        #region Private Members

        private bool ObjectIsCompliant(object Object)
        {
            if (FUseObjectsComparison && !(Object is IComparable))
                throw new ArgumentException("The Heap is set to use the IComparable interface of objects, and the object to add does not implement the IComparable interface.");
            if (!FAddDuplicates && Contains(Object))
                return false;
            return true;
        }

        private class Comparison : IComparer
        {
            public int Compare(object Object1, object Object2)
            {
                IComparable C = Object1 as IComparable;
                return C.CompareTo(Object2);
            }
        }

        private void InitProperties(IComparer Comparer, int Capacity)
        {
            if (Comparer != null)
            {
                FComparer = Comparer;
                FUseObjectsComparison = false;
            }
            else
            {
                FComparer = new Comparison();
                FUseObjectsComparison = true;
            }
            FList = Capacity > 0 ? new ArrayList(Capacity) : new ArrayList();
            FAddDuplicates = true;
        }

        #endregion
    }
}