/*
 * Copyright (c) 2005-2006 Erik Tigerholm <eriktigerholm@gmail.com>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
using System;
using System.Collections.Generic;
using System.Text;

namespace OpenTraffic.Collections
{
    [Serializable]
    public class TrafficHeap<TK, TT> : IPriorityQueue<TK, TT> where TK : IComparable<TK>
    {
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures")]
        protected List<KeyValuePair<TK, TT>> data { get; private set; }

        public int Count { get { return data.Count; } }

        protected int last { get { return data.Count; } }

        public virtual KeyValuePair<TK, TT> Peek()
        {
            return data[0];
        }

        public TrafficHeap(int size)
        {
            data = new List<KeyValuePair<TK, TT>>(size);

        }

        protected virtual void SwitchElement(int i1, int i2)
        {
            KeyValuePair<TK, TT> tmp = data[i1];
            data[i1] = data[i2];
            data[i2] = tmp;
        }

        private static int GetParentIndex(int i)
        {
            return (i - 1) >> 1;
        }

        private void BubbleUp()
        {
            BubbleUp(last - 1);
        }

        protected void BubbleUp(int i)
        {
            int nextI = GetParentIndex(i);
            while ((i != 0) && (data[i].Key.CompareTo(data[nextI].Key) > 0))
            {
                SwitchElement(i, nextI);
                i = nextI;
                nextI = GetParentIndex(i);
            };
        }

        private static int GetFirstChild(int i)
        {
            return (i << 1) + 1;
        }

        protected void BubbleDown(int i)
        {
            bool b = false;
            do
            {
                b = false;
                int child = GetFirstChild(i);
                if ((child + 1 < last))
                {
                    if (data[child + 1].Key.CompareTo(data[child].Key) > 0)
                    {
                        child++;
                    }
                }
                if ((child < last) && (data[child].Key.CompareTo(data[i].Key)) > 0)
                {
                    SwitchElement(child, i);
                    i = child;
                    b = true;
                }


            }
            while (b == true);

        }
        public virtual void Clear()
        {
            data.Clear();
        }
        public void Add(TK key, TT d)
        {
            Add(new KeyValuePair<TK, TT>(key, d));

        }

        public virtual void Add(KeyValuePair<TK, TT> kv)
        {
            data.Add(kv);
            BubbleUp();
        }


        public void RemoveFirst()
        {
            data[0] = data[last - 1];
            data.RemoveAt(last - 1);
            BubbleDown(0);

        }
        public virtual KeyValuePair<TK, TT> Pop()
        {
            if (last == 0) throw new IndexOutOfRangeException();
            KeyValuePair<TK, TT> tmp = data[0];
            RemoveFirst();
            return tmp;
        }

        public override string ToString()
        {
            string str = "----------------" + System.Environment.NewLine;
            int nextStop = 0;
            for (int i = 0; i < last; i++)
            {

                str += data[i].Key.ToString().Substring(0, 4) + "\t";
                if (i == nextStop)
                {
                    nextStop = GetFirstChild(i) + 1;
                    str += System.Environment.NewLine;
                }
            }
            str += "----------------" + System.Environment.NewLine;
            return str;
        }

        public virtual bool ControlInnerState()
        {
            for (int i = 0; i < last; i++)
            {
                int child = GetFirstChild(i);
                for (int j = 0; j < 1; j++)
                {
                    if (child < last)
                    {
                        if (data[child].Key.CompareTo(data[i].Key) > 0)
                        {
                            return false;
                        }
                    }
                    child++;
                }
            }
            return true;
        }
    }
}