/*
Thor Server 2.0 Project - Codenamed "Stockholm"
Copyright 2008 - 2009 Joe Hegarty


This file is part of The Thor Server 2.0 Project - Codenamed "Stockholm".

The Thor Server 2.0 Project - Codenamed "Stockholm" is free software: you can 
redistribute it and/or modify it under the terms of the Microsoft Public License

The Thor Server Project is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
Microsoft Public License for more details.

You should have received a copy of the Microsoft Public License
along with The Thor Server Project.  If not, see 
http://www.opensource.org/licenses/ms-pl.html
*/

using System;
using System.Collections.Generic;

namespace StockholmLibrary.Util
{
    //------------------------------------
    public class PriorityQueue<T>
    {

        protected List<T> _innerList = new List<T>();
        protected IComparer<T> _comparer;


        //**********************************************
        public PriorityQueue()
        {
            _comparer = Comparer<T>.Default;
        }

        //**********************************************
        public PriorityQueue(IComparer<T> comparer)
        {
            _comparer = comparer;
        }

        //**********************************************
        public PriorityQueue(IComparer<T> comparer, int capacity)
        {
            _comparer = comparer;
            _innerList.Capacity = capacity;
        }


        //**********************************************
        protected void SwitchElements(int i, int j)
        {
            T h = _innerList[i];
            _innerList[i] = _innerList[j];
            _innerList[j] = h;
        }

        //**********************************************
        protected virtual int OnCompare(int i, int j)
        {
            return _comparer.Compare(_innerList[i], _innerList[j]);
        }

        //**********************************************
        public int Push(T item)
        {
            int p = _innerList.Count, p2;
            _innerList.Add(item);
            do
            {
                if (p == 0)
                    break;
                p2 = (p - 1) / 2;
                if (OnCompare(p, p2) < 0)
                {
                    SwitchElements(p, p2);
                    p = p2;
                }
                else
                    break;
            } while (true);
            return p;
        }

        //**********************************************
        public T Pop()
        {
            T result = _innerList[0];
            int p = 0, p1, p2, pn;
            _innerList[0] = _innerList[_innerList.Count - 1];
            _innerList.RemoveAt(_innerList.Count - 1);
            do
            {
                pn = p;
                p1 = 2 * p + 1;
                p2 = 2 * p + 2;
                if (_innerList.Count > p1 && OnCompare(p, p1) > 0)
                    p = p1;
                if (_innerList.Count > p2 && OnCompare(p, p2) > 0)
                    p = p2;

                if (p == pn)
                    break;
                SwitchElements(p, pn);
            } while (true);

            return result;
        }

        //**********************************************
        public void Update(int i)
        {
            int p = i, pn;
            int p1, p2;
            do
            {
                if (p == 0)
                    break;
                p2 = (p - 1) / 2;
                if (OnCompare(p, p2) < 0)
                {
                    SwitchElements(p, p2);
                    p = p2;
                }
                else
                    break;
            } while (true);
            if (p < i)
                return;
            do
            {
                pn = p;
                p1 = 2 * p + 1;
                p2 = 2 * p + 2;
                if (_innerList.Count > p1 && OnCompare(p, p1) > 0)
                    p = p1;
                if (_innerList.Count > p2 && OnCompare(p, p2) > 0)
                    p = p2;

                if (p == pn)
                    break;
                SwitchElements(p, pn);
            } while (true);
        }

        //**********************************************
        public T Peek()
        {
            if (_innerList.Count > 0)
                return _innerList[0];
            return default(T);
        }

        //**********************************************
        public void Clear()
        {
            _innerList.Clear();
        }

        //**********************************************
        public int Count
        {
            get { return _innerList.Count; }
        }

        //**********************************************
        public void RemoveLocation(T item)
        {
            int index = -1;
            for (int i = 0; i < _innerList.Count; i++)
            {

                if (_comparer.Compare(_innerList[i], item) == 0)
                    index = i;
            }

            if (index != -1)
                _innerList.RemoveAt(index);
        }

        //**********************************************
        public T this[int index]
        {
            get { return _innerList[index]; }
            set
            {
                _innerList[index] = value;
                Update(index);
            }
        }

    }
}