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

namespace CarFire
{
    /// <summary>
    /// Why .NET doesn't already provide such a basic data structure
    /// as a priority queue is anybody's best guess.  This is an interface
    /// for a queue class which treats the items themselves as keys,
    /// the relative priorities being determined by a comparison between
    /// them.
    /// </summary>
    /// <typeparam name="T">The type of item to queue.  This must be a
    /// comparable class.</typeparam>
    public interface IPriorityQueue<T> where T : IComparable<T>
    {
        /// <summary>
        /// Add a new item to the priority queue.
        /// </summary>
        /// <param name="item">The item to add.</param>
        void Add(T item);

        /// <summary>
        /// Get the item with the highest priority, removing it
        /// from the priority queue.
        /// </summary>
        /// <returns>The highest priority item.</returns>
        T GetNext();

        /// <summary>
        /// Get the item with the highest priority, but keep it in
        /// the priority queue.
        /// </summary>
        /// <returns>The highest priority item.</returns>
        T Peek();

        /// <summary>
        /// Notify the priority queue that the priority of a certain item
        /// has improved.  If the items is not in the queue, it is added.
        /// Do not use this to demote items.  The internal structures will
        /// be reconfigured in order to ensure correct priority queueing.
        /// </summary>
        /// <param name="item">The item that improved.</param>
        void Promote(T item);

        /// <summary>
        /// Remove all the items from the priority queue.
        /// </summary>
        void Clear();

        /// <summary>
        /// Get the number of items in the priority queue.
        /// </summary>
        int Count { get; }
    }


    /// <summary>
    /// A minimum binary heap implementing a priority queue.
    /// </summary>
    /// <typeparam name="T">The type of items to load in the heap.</typeparam>
    public class BinaryHeap<T> : IPriorityQueue<T> where T : IComparable<T>
    {
        #region Public Properties

        /// <summary>
        /// Get the number of items in the binary heap.
        /// </summary>
        public int Count { get { return mSize; } }

        #endregion


        #region Public Methods

        /// <summary>
        /// Construct a binary heap.
        /// </summary>
        public BinaryHeap()
        {
            mList.Add(default(T));
        }

        /// <summary>
        /// Construct a binary heap with a predetermined capacity.
        /// The heap is dynamically-sized, but it will be more
        /// efficient if you set the capacity to the number of items
        /// you plan to add.
        /// </summary>
        /// <param name="capacity">The capacity of the heap.</param>
        public BinaryHeap(int capacity)
        {
            mList.Capacity = capacity;
            mList.Add(default(T));
        }


        /// <summary>
        /// Add a new item to the heap.
        /// </summary>
        /// <param name="item">The item to add.</param>
        public void Add(T item)
        {
            mList.Add(item);
            mSize++;
            PercolateUp(mSize);
        }


        /// <summary>
        /// Get the item with the lowest value, removing it from the heap.
        /// </summary>
        /// <returns>The highest priority item.</returns>
        public T GetNext()
        {
            Debug.Assert(mSize > 0);

            T next = mList[1];

            mList[1] = mList[mSize];
            PercolateDown(1);
            mList.RemoveAt(mSize);
            mSize--;

            return next;
        }

        /// <summary>
        /// Get the item with the lowest value, but keep it in the heap.
        /// </summary>
        /// <returns>The highest priority item.</returns>
        public T Peek()
        {
            Debug.Assert(mSize > 0);

            return mList[1];
        }


        /// <summary>
        /// Decrease the value of one of the items in the heap.  If the
        /// item is not already in the heap, it is added.
        /// </summary>
        /// <param name="item">The item to change.</param>
        public void Promote(T item)
        {
            for (int i = 1; i < mList.Count; i++)
            {
                if (item.Equals(mList[i]))
                {
                    mList[i] = item;
                    if (PercolateUp(i) == i) PercolateDown(i);
                    return;
                }
            }

            Add(item);
        }


        /// <summary>
        /// Remove all the items from the heap.
        /// </summary>
        public void Clear()
        {
            mList.Clear();
            mSize = 0;
        }

        #endregion


        #region Private Methods

        int PercolateUp(int index)
        {
            T temp = mList[index];

            for (int parent; index > 1; index = parent)
            {
                parent = index / 2;
                if (temp.CompareTo(mList[parent]) < 0) mList[index] = mList[parent];
                else break;
            }

            mList[index] = temp;
            return index;
        }

        int PercolateDown(int index)
        {
            T temp = mList[index];

            for (int child; index * 2 <= mSize; index = child)
            {
                child = index * 2;
                if (child != mSize && mList[child].CompareTo(mList[child + 1]) > 0) child++;
                if (temp.CompareTo(mList[child]) > 0) mList[index] = mList[child];
                else break;
            }

            mList[index] = temp;
            return index;
        }

        #endregion


        #region Private Variables

        List<T> mList = new List<T>();
        int mSize = 0;

        #endregion
    }


    /// <summary>
    /// The binary heap might be too slow for shortest path algorithms,
    /// so here is a fibonacci heap which should perform better.
    /// </summary>
    /// <typeparam name="T">The type of items to load in the heap.</typeparam>
    public class FibonacciHeap<T> : IPriorityQueue<T> where T : IComparable<T>
    {
        #region Public Properties

        /// <summary>
        /// Get the number of items in the fibonacci heap.
        /// </summary>
        public int Count { get { return mCount; } }

        #endregion


        #region Public Methods

        /// <summary>
        /// Construct an empty fibonacci heap.
        /// </summary>
        public FibonacciHeap()
        {
            mList = new LinkedList<NodeInfo>();
            mLookup = new Dictionary<T, LinkedListNode<NodeInfo>>();
        }


        /// <summary>
        /// Add a new item to the heap.
        /// </summary>
        /// <param name="item">The item to add.</param>
        public void Add(T item)
        {
            LinkedListNode<NodeInfo> node = mList.AddLast(new NodeInfo(item));
            if (mMin == null || item.CompareTo(mMin.Value.Item) < 0) mMin = node;

            mLookup[item] = node;
            mCount++;
        }


        /// <summary>
        /// Get the item with the lowest value, removing it from the heap.
        /// </summary>
        /// <returns>The highest priority item.</returns>
        public T GetNext()
        {
            LinkedListNode<NodeInfo> temp = mMin;
            mList.Remove(mMin);
            mMin = null;

            LinkedListNode<NodeInfo> node = temp.Value.Children.First;
            while (node != null)
            {
                Cut(node);
                node = temp.Value.Children.First;
            }
            Consolidate();

            mLookup.Remove(temp.Value.Item);
            mCount--;
            return temp.Value.Item;
        }

        /// <summary>
        /// Get the item with the lowest value, but keep it in the heap.
        /// </summary>
        /// <returns>The highest priority item.</returns>
        public T Peek()
        {
            return mMin.Value.Item;
        }


        /// <summary>
        /// Decrease the value of one of the items in the heap.  If the
        /// item is not already in the heap, it is added.
        /// </summary>
        /// <param name="item">The item to change.</param>
        public void Promote(T item)
        {
            LinkedListNode<NodeInfo> node;
            if (mLookup.TryGetValue(item, out node))
            {
                LinkedListNode<NodeInfo> parent = node.Value.Parent;
                if (parent != null)
                {
                    if (node.Value.Item.CompareTo(parent.Value.Item) < 0)
                    {
                        Cut(node);
                        CascadingCut(parent);
                        if (node.Value.Item.CompareTo(mMin.Value.Item) < 0) mMin = node;
                    }
                }
                else if (node.Value.Item.CompareTo(mMin.Value.Item) < 0) mMin = node;
            }
            else
            {
                Add(item);
            }
        }


        /// <summary>
        /// Remove all the items from the heap.
        /// </summary>
        public void Clear()
        {
            mList.Clear();
            mMin = null;
            mCount = 0;
            mLookup.Clear();
        }

        #endregion


        #region Private Methods

        // Builds up the binomial trees.  More importantly, it sets the min
        // pointer and ensures that no root binomial tree has the same degree.
        void Consolidate()
        {
            LinkedListNode<NodeInfo>[] degree = new LinkedListNode<NodeInfo>[64];

            for (LinkedListNode<NodeInfo> node = mList.First; node != null;)
            {
                LinkedListNode<NodeInfo> match = degree[node.Value.Degree];
                if (match == null)
                {
                    if (mMin == null || node.Value.Item.CompareTo(mMin.Value.Item) <= 0) mMin = node;
                    degree[node.Value.Degree] = node;
                    
                    node = node.Next;
                }
                else
                {
                    degree[node.Value.Degree] = null;

                    if (node.Value.Item.CompareTo(match.Value.Item) < 0)
                    {
                        Link(match, node);
                    }
                    else
                    {
                        mList.Remove(match);
                        mList.AddAfter(node, match);
                        Link(node, match);
                        node = match;
                    }
                }
            }
        }

        // Removes child from whatever list it is in and makes it a child
        // of parent.  This is for building up the binomial trees.
        void Link(LinkedListNode<NodeInfo> child, LinkedListNode<NodeInfo> parent)
        {
            child.List.Remove(child);
            parent.Value.Children.AddLast(child);
            child.Value.Parent = parent;
            child.Value.IsMarked = false;
        }

        // Removes node from whatever list it is in and makes it a root binomial
        // tree.
        void Cut(LinkedListNode<NodeInfo> node)
        {
            node.List.Remove(node);
            mList.AddLast(node);
            node.Value.Parent = null;
            node.Value.IsMarked = false;
        }

        // Cuts each node that is marked, following the ancestry until it finds
        // an unmarked ancestor (in which case it marks it) or a root node.
        void CascadingCut(LinkedListNode<NodeInfo> node)
        {
            while (node.Value.Parent != null)
            {
                if (node.Value.IsMarked)
                {
                    Cut(node);
                    node = node.Value.Parent;
                }
                else
                {
                    node.Value.IsMarked = true;
                    break;
                }
            }
        }

        #endregion


        #region Private Types

        // This container class has the information we need to form
        // a tree out of linked lists.
        class NodeInfo
        {
            public LinkedListNode<NodeInfo> Parent;
            public LinkedList<NodeInfo> Children = new LinkedList<NodeInfo>();
            public bool IsMarked = false;

            public int Degree { get { return Children.Count; } }

            public T Item { get { return mItem; } }

            public NodeInfo(T item)
            {
                mItem = item;
            }

            T mItem;
        }

        #endregion


        #region Private Variables

        LinkedList<NodeInfo> mList;
        LinkedListNode<NodeInfo> mMin;
        int mCount;

        // To speed up promotions, we need a fast lookup for nodes.
        Dictionary<T, LinkedListNode<NodeInfo>> mLookup;

        #endregion
    }
}