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

using Demo.Arithmetic.Sort;

namespace Demo.Arithmetic.DS
{
    /// <summary>
    /// Represents a heap.
    /// </summary>
    /// <typeparam name="T">A comparable data structure.</typeparam>
    public class Heap<T> where T : IComparable
    {
        /// <summary>
        /// Heap type, either big root a small root.
        /// </summary>
        HeapType _heapType = HeapType.BigRoot;

        /// <summary>
        /// An array contains the heap's data.
        /// </summary>
        T[] _rawData;

        /// <summary>
        /// Constructor.
        /// </summary>
        /// <param name="capability">The heap's capability.</param>
        /// <param name="heapType">The heap type.</param>
        public Heap(int capability, HeapType heapType)
        {
            // Initializes the array.
            _rawData = new T[capability];

            _heapType = heapType;
        }

        #region Public methods

        /// <summary>
        /// Sorts the array.
        /// </summary>
        /// <param name="sortOrder">Sort order.</param>
        public void Sort(SortOrder sortOrder)
        {
            if (sortOrder == SortOrder.None) return;
            if (_rawData == null || _rawData.Length <= 1) return;

            HeapType formerHeapType = _heapType;

            // If the order is ascending, then use big root, otherwise use small root.
            _heapType = sortOrder == SortOrder.Ascending ? HeapType.BigRoot : HeapType.SmallRoot;

            // Build the heap up.
            BuildHeap();

            for (int i = _rawData.Length - 1; i > 0; i--)
            {
                Exchange(0, i);
                Heapify(0, i - 1);
            }

            _heapType = formerHeapType;
        }

        /// <summary>
        /// Build the heap up.
        /// </summary>
        public void BuildHeap()
        {
            for (int i = _rawData.Length / 2 - 1; i >= 0; i--)
            {
                Heapify(i, _rawData.Length - 1);
            }
        }

        public void Heapify(int rootIndex, int lastIndex)
        {
            // If the root node is a leaf, then it is a heap already.
            if (IsLeaf(rootIndex, lastIndex)) return;

            int nextRootIndex = GetRootIndex(rootIndex, lastIndex);

            if (nextRootIndex == rootIndex)
            {
                return;
            }
            else
            {
                // Exchange.
                Exchange(rootIndex, nextRootIndex);

                // Verify the heap.
                Heapify(nextRootIndex, lastIndex);
            }
        }

        #endregion

        #region Private methods

        /// <summary>
        /// Returns the root's index by compare the parent node and children nodes according to the heap's type.
        /// </summary>
        /// <param name="rootIndex">The parent's node index.</param>
        /// <param name="lastIndex">The heap's last index.</param>
        /// <returns>The root's index.</returns>
        private int GetRootIndex(int rootIndex, int lastIndex)
        {
            int tLeftIndex = rootIndex + rootIndex + 1;
            if (tLeftIndex > lastIndex) return rootIndex;

            int nextRootIndex = ((_heapType == HeapType.BigRoot && _rawData[rootIndex].CompareTo(_rawData[tLeftIndex]) > 0) ||
                (_heapType == HeapType.SmallRoot && _rawData[rootIndex].CompareTo(_rawData[tLeftIndex]) < 0)) ?
                rootIndex : tLeftIndex;

            int tRightIndex = rootIndex + rootIndex + 2;
            if (tRightIndex > lastIndex) return nextRootIndex;

            nextRootIndex = ((_heapType == HeapType.BigRoot && _rawData[nextRootIndex].CompareTo(_rawData[tRightIndex]) > 0) ||
                (_heapType == HeapType.SmallRoot && _rawData[nextRootIndex].CompareTo(_rawData[tRightIndex]) < 0)) ?
                nextRootIndex : tRightIndex;

            return nextRootIndex;
        }

        /// <summary>
        /// Exchanges the nodes.
        /// </summary>
        /// <param name="firstIndex">The first node's index.</param>
        /// <param name="secondIndex">The second node's index.</param>
        private void Exchange(int firstIndex, int secondIndex)
        {
            T temp = _rawData[firstIndex];
            _rawData[firstIndex] = _rawData[secondIndex];
            _rawData[secondIndex] = temp;
        }

        #endregion

        #region Static methods

        /// <summary>
        /// Checks if the node is a leaf.
        /// </summary>
        /// <param name="nodeIndex">The node's index.</param>
        /// <param name="lastIndex">The last index of the heap.</param>
        /// <returns>Returns true if the node is a leaf.</returns>
        private static bool IsLeaf(int nodeIndex, int lastIndex)
        {
            return nodeIndex + nodeIndex + 1 > lastIndex;
        }

        #endregion

        #region Properties

        public T this[int i]
        {
            get
            {
                return _rawData[i];
            }

            set
            {
                _rawData[i] = value;
            }
        }

        /// <summary>
        /// The capability.
        /// </summary>
        public int Capability
        {
            get
            {
                return _rawData.Length;
            }
        }

        #endregion
    }

    /// <summary>
    /// Heap type.
    /// </summary>
    public enum HeapType
    { 
        BigRoot = 0x00,
        SmallRoot = 0x01
    }
}
//csharp/7235