//-------------------------------------------------------
// Source file provided by Steve Ramage
// Email: sjr@sjrx.net
//
// Modified by Quinn Hsu
// Demonstrates how PbO can be used to expose optimization
//		parameters.  In this case ##ary
//
// Version 1.0
// Fixed bug in percolateDown
// Added tester main function similar to C version of program
//-------------------------------------------------------

#ifndef _DHEAPPQUEUE_CPP
#define _DHEAPPQUEUE_CPP
#include <cassert>
#include "DHeapPQueue.h"
#include <iostream>

##PARAM(int ary)
##PARAM(int maxSize)

template <class Object, class Compare>
bool DHeapPQueue<Object, Compare>::isEmpty() const
{
    if (size == 0) return true;
    return false;
}

template <class Object, class Compare>
const Object&  DHeapPQueue<Object, Compare>::findMin() const
{
   assert(size > 0);
   return dHeap[0];
}

template <class Object, class Compare>
void DHeapPQueue<Object, Compare>::insert(const Object& x)
{
	//cout << "Inserting: " << x << endl;
	
    if ((unsigned int)size == dHeap.size()) {
		dHeap.push_back(x);
    } else {
      	dHeap[size] = x;
    }
    
    size++;
    
    percolateUp(size - 1);
    
    //printHeap(size,0,0);
}


template <class Object, class Compare>
void DHeapPQueue<Object, Compare>::deleteMin()
{
  
    assert(size > 0);
    dHeap[0] = dHeap[size - 1];
    size--;
    percolateDown(0);
    
}

template <class Object, class Compare>
void DHeapPQueue<Object, Compare>::deleteMin(Object& minItem)
{     
    assert(size > 0);
    minItem = dHeap[0];
    deleteMin();
    
    //cout << "Deleting: " << minItem << endl;
    //printHeap(size, 0, 0);
}

template <class Object, class Compare>
void DHeapPQueue<Object, Compare>::makeEmpty() 
{
    //dHeap.resize(1);
    size = 0;
}

template <class Object, class Compare>
void DHeapPQueue<Object, Compare>::percolateDown(int index) 
{
    if (index >= size) return;
    
    if ((index*##ary + 1) > size) return;;
    
    
    int myMinChild = minChild(index);
    
    Compare comp;
    if (comp(dHeap[myMinChild], dHeap[index])) 
    {
      Object x = dHeap[index];
      dHeap[index] = dHeap[myMinChild];
      dHeap[myMinChild] = x;
      percolateDown(myMinChild);
    }
    
}


template <class Object, class Compare>
int DHeapPQueue<Object, Compare>::minChild(int index) const
{
    assert(index >= 0);
  
    int minIndex= ##ary*index + 1; 
    
    Object minObj = dHeap[##ary*index + 1];
    
    Compare comp;
    
    
    for(int i=##ary*index + 2; i <=  ##ary*index + ##ary; i++)
    {
      
		if (i >= size) break;
		
		if(comp(dHeap[i], minObj)) 
		{
			minObj = dHeap[i];
			minIndex = i;
		}
    }
    return minIndex;
}


template <class Object, class Compare>
void DHeapPQueue<Object, Compare>::percolateUp(int index)
{
  
    
    if (index > size) return;
    if (index == 0) return;
    
    Compare comp;
    int parentIndex = (index-1)/##ary;

    if (comp(dHeap[index], dHeap[parentIndex]))
    {
      Object x = dHeap[index];
      dHeap[index] = dHeap[parentIndex];
      dHeap[parentIndex] = x;
      //printHeap(size,0,0);
      percolateUp(parentIndex);
    }
    
}

template <class Object, class Compare>
void DHeapPQueue<Object, Compare>::printHeap(int size, int curr, int level)
{
	int i;
	for (i=0; i<size; i++) {
		cout << "[" << i << "] " << dHeap[i] << endl;
	}
}

struct less_int {
  bool operator() (const int & lint, const int & rint) const
    { return lint < rint; }
};

int main() {
	DHeapPQueue<int, less_int> H(4);
	
	int i, j;
	
	for (i=0, j=##maxSize/2; i<##maxSize; i++, j=(j+71)%##maxSize) {
		H.insert(j);
	}
	
	j=0;
	
	int min_value;
	
	for(j=0; j<maxSize; j++) {
		H.deleteMin(min_value);
		if (min_value != j) {
			cout << "Error in deleteMin: " << j << endl;
		}
	}
	
	cout << "Done.." << endl;
	return 0;

}
#endif