#include <string.h>
#include "PairHeap.h"


#define MAX_SIZE_INC  10000


PairHeap::PairHeap(int initial_size)
{
  _size = initial_size;
  _heap = new Pair *[_size + 1];
  _heap[0] = new Pair;		// Place a fake sentinel Pair in position 0
  _heap[0]->numOccurrences = MAX_PAIR_OCCURRENCES;
  _numElts = 0;
}


PairHeap::~PairHeap()
{
  delete _heap[0];		// Don't forget to kill the sentinel ...
  delete [] _heap;
}


void 
PairHeap::insert(Pair *pair)
{
  // If we're already at capacity, resize.
  if (_numElts == _size)
    _resize();
  
  _heap[++_numElts] = pair;
  _percolate(_numElts);
}


Pair *
PairHeap::removeMax(void)
{
  Pair *result = _heap[1];
  _heap[1] = _heap[_numElts--];
  _sift(1);

  return result;
}


void
PairHeap::updatePair(Pair *pair)
{
  _percolate(pair->heapIndex);
}


void 
PairHeap::_sift(int index)
{
  Pair *cur = _heap[index];
  int max, lc, rc;

  lc = _lchild(index);
  rc = _rchild(index);
  if ((rc == -1) || (_heap[lc]->numOccurrences >= _heap[rc]->numOccurrences))
    max = lc;
  else
    max = rc;

  while ((max != -1) && (cur->numOccurrences < _heap[max]->numOccurrences)) {
    _heap[index] = _heap[max];
    _heap[index]->heapIndex = index;
    index = max;
    lc = _lchild(index);
    rc = _rchild(index);
    if ((rc == -1) || 
	(_heap[lc]->numOccurrences >= _heap[rc]->numOccurrences))
      max = lc;
    else
      max = rc;
  }

  _heap[index] = cur;
  _heap[index]->heapIndex = index;
}


void 
PairHeap::_percolate(int index)
{
  Pair *cur = _heap[index];
  int parent = _parent(index);

  while (_heap[parent]->numOccurrences < cur->numOccurrences) {
    _heap[index] = _heap[parent];
    _heap[index]->heapIndex = index;
    index = parent;
    parent = _parent(index);
  }

  _heap[index] = cur;
  _heap[index]->heapIndex = index;
}


int 
PairHeap::_parent(int index)
{
  return (index >> 1);
}


int 
PairHeap::_lchild(int index)
{
  int result = (index << 1);

  if (result > _numElts)
    return -1;

  return result;
}


int 
PairHeap::_rchild(int index)
{
  int result = (index << 1) + 1;

  if (result > _numElts)
    return -1;

  return result;
}


void
PairHeap::_resize(void)
{
  int new_size = (_size > MAX_SIZE_INC) ? (_size + MAX_SIZE_INC) : (_size<<1);
  Pair **new_heap = new Pair *[new_size];

  memcpy(new_heap, _heap, _size);
  delete [] _heap;
  _heap = new_heap;
  _size = new_size;
}