using System;
using System.Collections.Generic;
using System.Text;

namespace SokobanResultSearch.BusinessEntities
{
    class BinaryHeap
    {
        #region Private fields

        private State[] _heap;

        private int     _lastIndex;

        #endregion

        #region Constructor

        public BinaryHeap() { _heap = new State[10000000]; }

        #endregion

        #region Public members

        public int Count
        {
            get { return _lastIndex; }
        }
        
        public void Push(State state)
        {
            int current = _lastIndex++;
            int value   = state.HeuristicsValue;
            for (int parent = current - 1 >> 1; parent > -1 && value < _heap[parent].HeuristicsValue; parent = current - 1 >> 1)
            {
                _heap[current] = _heap[parent];
                current = parent;
            }
            _heap[current] = state;
        }


        public State Pop()
        {
            int current         = 0;
            State result        = _heap[current];
            State movedState    = _heap[--_lastIndex];
            int value           = movedState.HeuristicsValue;

            for (int selectedIndex = (current << 1) + 1; selectedIndex < _lastIndex; selectedIndex = (current << 1) + 1)
            {
                int nextIndex = selectedIndex + 1;
                if (value > _heap[selectedIndex].HeuristicsValue && _heap[selectedIndex].HeuristicsValue < _heap[nextIndex].HeuristicsValue)
                {
                    _heap[current]  = _heap[selectedIndex];
                    current         = selectedIndex;
                }
                else if (value > _heap[nextIndex].HeuristicsValue)
                {
                    _heap[current] = _heap[nextIndex];
                    current = nextIndex;
                }
                else break;
            }
            _heap[current] = movedState;

            return result;
        }

        #endregion
    }
}
