using System;
using System.Collections.Generic;

namespace Microscopic_Traffic_Simulator___Model.Utilities
{
    /// <summary>
    /// Heap data structure where values of items are ordered by their keys.
    /// </summary>
    /// <typeparam name="TKey">Key type of items.</typeparam>
    /// <typeparam name="TValue">Value type of items.</typeparam>
    class Heap<TKey, TValue> where TKey : IComparable
    {
        /// <summary>
        /// List of items which is heap implemented on.
        /// </summary>
        List<KeyValuePair<TKey, TValue>> list = new List<KeyValuePair<TKey, TValue>>();


        /// <summary>
        /// Get current top item of heap.
        /// </summary>        
        internal KeyValuePair<TKey, TValue> Top { get { return list[0]; } }

        /// <summary>
        /// Items count in heap.
        /// </summary>
        internal int Count { get { return list.Count; } }

        /// <summary>
        /// Push new item to heap. The item is placed on the end of list and then it bubbles up.
        /// </summary>
        /// <param name="key">Key of heap.</param>
        /// <param name="value">Value of heap.</param>
        internal void Push(TKey key, TValue value)
        {
            list.Add(new KeyValuePair<TKey, TValue>(key, value));
            int index = list.Count - 1;
            while (index > 0 && list[index].Key.CompareTo(list[(index - 1) >> 1].Key) < 0)
            {
                Swap(index, (index - 1) >> 1);
                index = (index - 1) >> 1;
            }
        }

        /// <summary>
        /// Pop top item of heap. Popped item is replaced by the last list item which bubbles down.
        /// </summary>
        /// <returns>Top item.</returns>
        internal KeyValuePair<TKey, TValue> Pop()
        {
            KeyValuePair<TKey, TValue> toReturn =
                new KeyValuePair<TKey, TValue>(list[0].Key, list[0].Value);
            list[0] = list[list.Count - 1];
            list.RemoveAt(list.Count - 1);
            int index = 0;
            bool end;
            do
            {
                end = true;
                int son1 = (index << 1) + 1;
                int son2 = (index << 1) + 2;
                if (son2 < list.Count)
                {
                    int lessSon = list[son1].Key.CompareTo(list[son2].Key) > 0 ? son2 : son1;
                    if (list[index].Key.CompareTo(list[lessSon].Key) >= 0)
                    {
                        Swap(index, lessSon);
                        index = lessSon;
                        end = false;
                    }
                }
                else if (son1 < list.Count)
                {
                    if (list[index].Key.CompareTo(list[son1].Key) >= 0)
                    {
                        Swap(index, son1);
                        index = son1;
                        end = false;
                    }
                }
            } while (!end);
            return toReturn;
        }

        /// <summary>
        /// Clear heap.
        /// </summary>
        internal void Clear()
        {
            list.Clear();
        }

        /// <summary>
        /// Swap two items in heap list.
        /// </summary>
        /// <param name="index1">Index of the first item.</param>
        /// <param name="index2">Index of another item.</param>
        private void Swap(int index1, int index2)
        {
            KeyValuePair<TKey, TValue> pom = list[index1];
            list[index1] = list[index2];
            list[index2] = pom;
        }
    }
}
