using System;
using PriorityQueue.Interfaces;

namespace PriorityQueue
{
    public class PriorityQueue<T, U> : Heap<T, U> where T : INode<U> where U : IComparable<U>
    {
        // workaround for due to inablitly to call MaxValue/MinValue on generics 
        static readonly U _maxValue = (U)typeof(U).GetField("MaxValue").GetValue(null);
        static readonly U _minValue = (U)typeof(U).GetField("MinValue").GetValue(null);
        public U LeastSignificant { get => IsMin ? _maxValue : _minValue; }
        
        public int[] Location { get; set; }
        
        // indexer - returns null if attempting to access outside heap
        public T this[int i] { get => Location[i] > HeapSize ? default(T) : Array[Location[i]]; }

        public PriorityQueue(int size, bool isMin = false)
            : this(new T[size], isMin) { }

        public PriorityQueue(T[] array, bool isMin = false)
            : base(array, isMin)
        {
            Location = new int[Array.Length];
        }

        // swap two indexies
        protected override void Swap(int first, int second)
        {
            // swap in heap
            base.Swap(first, second);

            // swap in location table
            Location[Array[first].Id] = first;
            Location[Array[second].Id] = second;
        }

        // insert a new node and bubble up
        public void Insert(T node)
        {
            int index = ++HeapSize;
            U key = node.Key;

            node.Key = LeastSignificant;
            Array[index] = node;
            Location[node.Id] = index;
            ChangeKey(index, key);
        }

        // return most significant
        public T Peek() =>
            Array[0];

        // check if heap is empty
        public bool IsEmpty() =>
            HeapSize < 0;

        // remove and return top node
        public T Extract()
        {
            if (HeapSize < 0)
                throw new System.OverflowException("Heap Underflow");

            T sig = Peek();

            Swap(0, HeapSize--);
            Heapify(0);

            return sig;
        }

        protected bool LessSignificant(U that, U other) =>
            that.CompareTo(other) * (IsMin ? -1 : 1) > 0;

        public void ChangeKey(int id, U key)
        {
            int index = Location[id];

            // key < Array[index].Key
            if (LessSignificant(key, Array[index].Key))
                throw new System.ArgumentException($"New key ({key}) is less significant than node {id}'s current key ({Array[index].Key}).");

            Array[index].Key = key;

            while (index > 0 && MoreSignificant(Array[index], Array[Parent(index)]))
            {
                Swap(index, Parent(index));
                index = Parent(index);
            }
        }
    }
}