///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//  Copyright (C) 1995-2002 by the Board of Trustees of Leland Stanford      //
//  Junior University.  See LICENSE for details.                             //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////

#ifndef _heap_h_
#define _heap_h_

#include <iostream.h>
#include "misc.h"

const int DEFAULT_HEAP_SIZE=4;

template <class _Data>
class Heap {
private:
  // Data
  int _size;
  int _numItems;
  _Data *_array;
  Bool (*_leqFunc)(_Data,_Data);

  // Private functions
  void Copy(const Heap&);
  void Destroy() { delete [] _array; }
  void Resize();
  void Heapify(int);

  IF_DEBUG(
    void CheckHeapRec(int, int);
  )

  // Static functions
  static int Left(int index) { return 2*index+1; }
  static int Right(int index) { return 2*index+2; }
  static int Parent(int index) { return (index-1)/2; }

public:
  // Constructors and Destructor
  Heap(Bool (*p)(_Data,_Data), int size=DEFAULT_HEAP_SIZE) :
    _size(size), _numItems(0), _array(new _Data[size]), _leqFunc(p) {}
  Heap(const Heap &a) { Copy(a); }
  ~Heap() { Destroy(); }

  // Operator=
  Heap& operator=(const Heap&);

  // Access functions
  _Data GetMin() const { ASSERT(!Empty()); return _array[0]; }
  Bool Empty() const { return _numItems == 0; }
  int NumItems() const { return _numItems; }

  // Data manipulation functions
  void Reset() { _numItems = 0; }
  void Insert(_Data);
  void DeleteMin()
  { ASSERT(!Empty());
    if (--_numItems > 0) { _array[0] = _array[_numItems]; Heapify(0); } }
  void ReplaceMin(_Data d) { ASSERT(!Empty()); _array[0] = d; Heapify(0); }
  _Data ExtractMin() { _Data result = GetMin(); DeleteMin(); return result; }

  // Debug
  IF_DEBUG(
    void CheckHeap();
  )

  // Friend functions
  ostream& Print(ostream&);
};

template <class _Data>
void Heap<_Data>::Copy(const Heap<_Data> &a) 
{
  _size = a._size;
  _numItems = a._numItems;
  _array = new _Data[_size];

  for (int i=0; i<_numItems; i++)
    _array[i] = a._array[i];
}

template <class _Data>
void Heap<_Data>::Resize()
{
  _size *= 2;
  _Data *tmp = new _Data[_size];
  for (int i=0; i<_numItems; i++)
    tmp[i] = _array[i];
  delete [] _array;
  _array = tmp;
}

template <class _Data>
void Heap<_Data>::Heapify(int index)
{
  ASSERT_MSG(index >=0 && index < _numItems,("Illegal parameter in Heapify"));
  int l = Left(index);
  if (l >= _numItems) {
    return;
  }
  int r = Right(index);
  int minindex;
  if (_leqFunc(_array[l],_array[index])) {
    minindex = l;
  } else {
    minindex = index;
  }
  if (r < _numItems && _leqFunc(_array[r],_array[minindex])) {
    minindex = r;
  }
  if (minindex != index) {
    _Data tmp = _array[index];
    _array[index] = _array[minindex];
    _array[minindex] = tmp;
    Heapify(minindex);
  }
//   IF_DEBUG(
//     if (index == 0) {
//       CheckHeap();
//     }
//   )
}

template <class _Data>
Heap<_Data>& Heap<_Data>::operator=(const Heap<_Data> &a)
{
  if (&a!=this) {
    Destroy();
    Copy(a);
  }
  return *this;
}

template <class _Data>
void Heap<_Data>::Insert(_Data d)
{
  if (_size==_numItems) Resize();
  _array[_numItems] = d;
  int index = _numItems++;
  int parent = Parent(index);
  while (index > 0 && _leqFunc(_array[index],_array[parent])) {
    _Data tmp = _array[index];
    _array[index] = _array[parent];
    _array[parent] = tmp;
    index = parent;
    parent = Parent(index);
  }
//   IF_DEBUG(
//     CheckHeap();
//   )
}

IF_DEBUG(

template <class _Data>
void Heap<_Data>::CheckHeapRec(int index1, int index2)
{
  if (index1 >= _numItems || index2 >= _numItems) {
    return;
  }
  if (!_leqFunc(_array[index1],_array[index2])) {
    ASSERT_MSG(FALSE,("Ordering problem in heap"));
  }
  CheckHeapRec(index1,Left(index2));
  CheckHeapRec(index1,Right(index2));
}

template <class _Data>
void Heap<_Data>::CheckHeap()
{
  for (int i = 0; i < _numItems; i++) {
    CheckHeapRec(i,i);
  }
}

)

template <class _Data>
ostream& Heap<_Data>::Print(ostream &os)
{
  for (int i=0; i<_numItems; i++)
    os << _array[i] << ' ';
  return os;
}

#endif