// File: Heap_ADT.cpp
// Array Heap ADT implementation

#include <queue> 
#include "Heap_ADT.h"

template <class heapEltType> 
	HeapADT<heapEltType>::HeapADT() : eltsInHeap(0)
{eltsInHeap=0;}

 // Get for printing
 template <class heapEltType> 
	vector<heapEltType>  HeapADT<heapEltType>::getData() const
 { return(heap);}
 

template <class heapEltType>
	void HeapADT<heapEltType>::insertToHeap(heapEltType elt)
{//heap[eltsInHeap++]=elt;
 heap.push_back(elt);
 eltsInHeap++;
 if (eltsInHeap>1)
   reheapUp();
}

template <class heapEltType>
 void HeapADT<heapEltType>::removeFromHeap(heapEltType &elt)
{elt=heap[0];
 heap[0]=heap[--eltsInHeap];
 // Keep heap fully used
 heap.pop_back();
 reheapDown();
}

template <class heapEltType>
	int HeapADT<heapEltType>::isHeapEmpty()
{return((eltsInHeap==0));
}

template <class heapEltType>
 void HeapADT<heapEltType>::reheapUp()
{int eltIndex=eltsInHeap-1;
 while(eltIndex>0 && heap[eltIndex]>heap[parentOfNode(eltIndex)]) {
  swap(heap[eltIndex],heap[parentOfNode(eltIndex)]);
  eltIndex=parentOfNode(eltIndex);
 }
}


template <class heapEltType>
 void HeapADT<heapEltType>::reheapDown()
{int eltIndex=0,MaxIndex,Done=0;
 do {
  MaxIndex=maxChild(eltIndex);
  if (MaxIndex>0 && heap[eltIndex]<heap[MaxIndex])  {
   swap(heap[eltIndex],heap[MaxIndex]);
   eltIndex=MaxIndex;
  }
  else Done=1;
 } while (!Done);
}


template <class heapEltType>
 int HeapADT<heapEltType>::parentOfNode(int Index)
{if (Index>0)
  return((Index-1)/2);
 return(-1);
}

template <class heapEltType>
 int HeapADT<heapEltType>::leftChild(int Index) const
{if (Index*2+1<eltsInHeap)
  return(Index*2+1);
 return(-1);
}

template <class heapEltType>
 int HeapADT<heapEltType>::rightChild(int Index) const
{if (Index*2+2<eltsInHeap)
  return(Index*2+2);
 return(-1);
}

template <class heapEltType>
 int HeapADT<heapEltType>::maxChild(int Index)
{if (leftChild(Index)>0 && rightChild(Index)>0) {
  if (heap[leftChild(Index)]>heap[rightChild(Index)])
   return(leftChild(Index));
  return(rightChild(Index));
 }
 if (leftChild(Index)>0) return(leftChild(Index));
 if (rightChild(Index)>0) return(rightChild(Index));
 return(-1);
}

template <class heapEltType>
 void HeapADT<heapEltType>::swap(heapEltType &x,heapEltType &y)
{heapEltType temp;
 temp=x;
 x=y;
 y=temp;
}

template <class heapEltType> ostream &operator << (ostream &out,const HeapADT<heapEltType> &TheHeap)
{ vector<heapEltType> TheHeapVector=TheHeap.getData();
  typename vector<heapEltType>::iterator it;
  for (it=TheHeapVector.begin(); it != TheHeapVector.end(); it++)
	out << *it << " ";
  out << endl;
  return(out);
}  

template <typename heapEltType> void HeapADT<heapEltType>::heapPrint() const
{ // A queue to hold indices. An entry of -1 indicates end of level.
  queue<int> nodeList;
  // Process Root
  if (heap.size()>0) {
    // print root
    cout << heap[0];
    // and an end of level marker
    nodeList.push(0);
    // Insert its children
    nodeList.push(leftChild(0));	// left child
    nodeList.push(rightChild(0));	// right child
  }
  int index=nodeList.front();
  while (index<heap.size()) {
    nodeList.pop();
    if (index==0) {
      cout << endl;
      nodeList.push(0);  	// eoln marker
    }
    else {
      cout << heap[index] << " ";
      nodeList.push(leftChild(index));	// left child
      nodeList.push(rightChild(index));	// right child
    }  
    index=nodeList.front();
  }
  cout << endl;
}


template class HeapADT<int>;
template ostream &operator << (ostream &out,const HeapADT<int> &TheHeap);