#ifndef INTERVALHEAP_C
#define INTERVALHEAP_C

#include <math.h>
#include "IntervalHeap.h"
using namespace std;

/**
 * Construct the interval heap.
 * capacity is the capacity of the interval heap.
 */
template <class Comparable>
IntervalHeap<Comparable>::IntervalHeap( int cap )
   : currentSize( 0 ), capacity( cap )
{
  // calculate number of nodes needed
  int i = capacity / 2 + capacity % 2 + 1; 	
  array = new IntervalHeapNode <Comparable> [ i ];
}

/**
 * Insert item x into the priority queue, maintaining heap order.
 * Duplicates are allowed.
 * Throw Overflow if container is full.
 */
template <class Comparable>
void IntervalHeap<Comparable>::insert( const Comparable & x )
{
   // test for full heap
   if( capacity == currentSize )
      throw Overflow( );

   // test for empty heap
   if ( currentSize == 0 ){
      // this trick is for findMin and findMax on a 1 element heap
      array[0].left = x;
      array[0].right = x;

      currentSize++;
      return;
   } else if ( currentSize == 1 ){
      // 2 elements so figure out where to put it
      if ( x < array[0].left )
	 array[0].left = x;
      else
	 array[0].right = x;

      currentSize++;
      return;
   }
   
   int lNode = currentSize / 2 + currentSize % 2 - 1;

   // if odd number of elements....
   if ( currentSize % 2 )
      // lnode contains a single key
      if ( x <= array[lNode].left ){
	 array[lNode].right = array[lNode].left;
	 array[lNode].left = x;
      } else 
	 array[lNode].right = x;
      
   else { // even number of elements
     lNode++;
     array[lNode].left = x;
   }
   currentSize++;

   // setup some node indexes
   int vNode = lNode; // visited node
   int pNode;// parent node
   if ( lNode % 2 )
      pNode = lNode / 2; 
   else 
      pNode = lNode / 2 - 1;
   
   // perculate up
   while ( ( vNode != 0 ) && ( ( ( array[pNode].left < x ) || ( x < array[pNode].right ) ) ) ){
      if ( x < array[pNode].left ){
	 array[vNode].left = array[pNode].left;
	 array[pNode].left = x;
      } else if ( array[pNode].right < x ) {
	 if ( ( currentSize % 2 ) && ( vNode == lNode ) )
	    array[vNode].left = array[pNode].right;
	 else
	    array[vNode].right = array[pNode].right;
	    
	 array[pNode].right = x;
      }
      vNode = pNode;
      if ( vNode % 2 )
         pNode = vNode / 2; // parent node
      else 
         pNode = vNode  / 2 - 1;
   }
   return;
}

/**
 * print heap
 */
template <class Comparable>
void IntervalHeap<Comparable>::print( ) const
{
   if ( isEmpty ( ) ){
      cout << "     The heap is empty" << endl;
      return;
   }

   cout << "     The current heap content:" << endl;

   // get last node
   int lNode = currentSize / 2 + currentSize % 2 - 1 ;

   // handle special case where lnode is root node
   if ( currentSize < 3 )
      lNode = 0;
   else
         cout << "     [" << array[0].left << ", " << array[0].right << "] " << endl;

   int i = 1; // node index
   int x; // 
   int level = 1;
   cout << "     ";
   // print heap
   while ( i < lNode ){
      int num = (int) pow ( 2, (double) level );
      for ( x = i ; x <= num && (x*2) < (currentSize-2) ; x++, i++ ){
         cout << "[" << array[x].left << ", " << array[x].right << "] ";

         // check for newline conditions
         if ( (x != 0 ) && (!( x % 8 )) )
 	    cout << endl << "     ";
      }
      if ( ( (x*2) < (currentSize - 2) ) || ( x > num) ) 
         cout << endl << "     ";
      level++;
   }
   
   // for the last element we might only have 1 so print 1
   // if odd we have 1
   if ( currentSize % 2)
      cout << "[" << array[lNode].left << "]" << endl;
   else
      cout << "[" << array[lNode].left << ", " << array[lNode].right << "]" << endl;

   return;
}

/**
 * Find the smallest item in the priority queue.
 * Return the smallest item, or throw Underflow if empty.
 */
template <class Comparable>
const Comparable & IntervalHeap<Comparable>::findMin( ) const
{
   if( currentSize == 0 )
      throw Underflow( );
   return array[ 0 ].left;
}
/**
 * Find the largest item in the priority queue.
 * Return the largest item, or throw Underflow if empty.
 */
template <class Comparable>
const Comparable & IntervalHeap<Comparable>::findMax( ) const
{
   if( isEmpty( ) )
      throw Underflow( );

   // special case if we have 1 element
   if ( currentSize == 1 )
      return array[ 0 ].left;

   return array[ 0 ].right;
}

/**
 * Remove the smallest item from the priority queue.
 * Throw Underflow if empty.
 */
template <class Comparable>
void IntervalHeap<Comparable>::deleteMin( )
{
   if( isEmpty( ) )
      throw Underflow( );

   if ( currentSize < 3 ){
      if ( currentSize == 1 ){
	 // calculate number of nodes needed
         int i = capacity / 2 + capacity % 2 + 1;
	 array = new IntervalHeapNode <Comparable> [ i ];
	 currentSize = 0;
      } else {
	 array[0].right = array[0].left;
	 currentSize--;
      }
   }
   
   int hNode = 0; // node with hole
   int c1Node, c2Node; // child nodes
   
   // get last node
   int lNode = currentSize / 2 + currentSize % 2 - 1 ;
   
   
   // percolate down
   // while the hole node has children (ie it's not a leaf)
   while ( (hNode * 2 + 1) < lNode ) {
      c1Node = hNode * 2 + 1;
      c2Node = hNode * 2 + 2; 

      // if we have 2 valid children nodes
      if ( c2Node <= lNode ) {
	 if ( array[c2Node].left < array[c1Node].left ) {
	    array[hNode].left = array[c2Node].left;
	    hNode = c2Node;
	 } else {
	    array[hNode].left = array[c1Node].left;
	    hNode = c1Node;
	 }
      } else{
	 array[hNode].left = array[c1Node].left;
	 hNode = c1Node;
      }
   }

   if ( hNode != lNode ){
      
      array[hNode].left = array[lNode].left;
      if ( array[hNode].left < array[hNode].right )
         ;
      else {
         Comparable temp = array[hNode].left;
         array[hNode].left = array[hNode].right;
         array[hNode].right = temp;
      }
   }
   currentSize--;

   // if we now have an odd number we have to fix the lNode so the right is the left
   if ( currentSize % 2 )
      array[lNode].left = array[lNode].right;
}

/**
 * Remove the largest item from the priority queue.
 * Throw Underflow if empty.
 */
template <class Comparable>
void IntervalHeap<Comparable>::deleteMax( )
{
   if( isEmpty( ) )
      throw Underflow( );

   if ( currentSize < 3 ){
      if ( currentSize == 1 ){
	 // calculate number of nodes needed
         int i = capacity / 2 + capacity % 2 + 1;
	 array = new IntervalHeapNode <Comparable> [ i ];
	 currentSize = 0;
      } else {
	 array[0].left = array[0].right;
	 currentSize--;
      }
   }
   
   int hNode = 0; // node with hole
   int c1Node, c2Node; // child nodes
   
   // get last node
   int lNode = currentSize / 2 + currentSize % 2 - 1 ;
   
   
   // percolate down
   // while the hole node has children (ie it's not a leaf)
   while ( (hNode * 2 + 1) < lNode ) {
      c1Node = hNode * 2 + 1;
      c2Node = hNode * 2 + 2; 

      // if we have 2 valid children nodes
      if ( c2Node <= lNode ) {
	 if ( array[c2Node].right < array[c1Node].right ) {
	    array[hNode].right = array[c1Node].right;
	    hNode = c1Node;
	 } else {
	    array[hNode].right = array[c2Node].right;
	    hNode = c2Node;
	 }
      } else{
	 array[hNode].right = array[c1Node].right;
	 hNode = c1Node;
      }
   }

   if ( hNode != lNode ){
      
      array[hNode].right = array[lNode].right;
      if ( array[hNode].left < array[hNode].right )
         ;
      else {
         Comparable temp = array[hNode].left;
         array[hNode].left = array[hNode].right;
         array[hNode].right = temp;
      }
   }
   currentSize--;

   // if we now have an odd number we have to fix the lNode so the right is the left
   if ( currentSize % 2 )
      array[lNode].left = array[lNode].right;
}

/**
 * Make the priority queue logically empty.
 */
template <class Comparable>
void IntervalHeap<Comparable>::makeEmpty( )
{
   currentSize = 0;
}

#endif