/*
Name: Anne Dawson
Program: binaryHeap.cpp
Description: This is the implementation of the heap class.
*/


// Class Invariants:
// Min heap is implemented as an array based on the following rules:
// First node of the heap is in position "0" of the array. Then the node k has
// left child in 2*k+1 (array index)
// right child in 2*k+2 (array index)
// parent in int((k-1)/2) (array index)
// pointer m_array will point to the heap data
// default size of array is 50
// m_size is the current number of items in the heap
// m_capacity is the maximum size of the array (heap)

#include <iostream.h> 		//need it for the print function


template< typename type >
void reheapUp( type* heap, int root, int bottom );

template< typename type >
void reheapDown( type* heap, int top, int size );

template< typename type >
void copyData( type* thisData, type* otherData, int size );
// need to place the decleration of copyData before implementing and calling it

template< typename type >
CBinaryHeap< type >::CBinaryHeap( void )
// Post: binary heap has default capacity 50 and heap is empty
{
	m_array = new type[50];
	m_capacity=50;
	m_size = 0;
}

template< typename type >
CBinaryHeap< type >::CBinaryHeap( int maxCapacity )
// Post: maxCapacity is the capacity of the heap and the heap is empty
{
	m_array = new type[maxCapacity];
	m_capacity = maxCapacity;
	m_size = 0;
}

template< typename type >
CBinaryHeap< type >::CBinaryHeap( const CBinaryHeap<type>& otherHeap )
// Post: this heap is a copy of otherHeap
{
	m_array = new type[otherHeap.m_capacity];
	m_size=otherHeap.m_size;
	copyData(this->m_array, otherHeap.m_array, otherHeap.size());
}

template< typename type >
CBinaryHeap< type >::~CBinaryHeap( void )
// Post: memory allocated to heap has been released
{
    delete[] m_array;
}

template< typename type >
CBinaryHeap< type >& CBinaryHeap< type >::operator=( const CBinaryHeap< type >& otherHeap )
// Post: this heap has been assigned the value of otherHeap
{
	if(this!=&otherHeap)
	{
		delete [] this->m_array;
		this->m_array = new type[otherHeap.m_capacity];
	}

	copyData(this->m_array, otherHeap.m_array, otherHeap.size());

	this->m_size=otherHeap.m_size;
        return *this;
}

template< typename type >
void CBinaryHeap< type >::makeEmpty( void )
// Post: heap is empty
{
        while(m_size > 0)
        {
	  deleteTop();
        }
}

template< typename type >
void CBinaryHeap< type >::insert( const type& item )
// Pre: heap is not full
// Post: item has been inserted into heap
{
    m_array[ m_size++ ] = item;
    reheapUp( m_array, 0, m_size - 1 );
}

template< typename type >
void CBinaryHeap< type >::deleteTop( void )
// Pre: heap is not empty
// Post: item at top of heap has been removed
{
    m_array[ 0 ] = m_array[ --m_size ];
    reheapDown( m_array, 0, m_size );
}

template< typename type >
type& CBinaryHeap< type >::getTop( void )
// Pre: heap is not empty
// Post: reference to item at top of heap has been returned
{
	type* Top=m_array;
	return *Top;
}

template< typename type >
const type& CBinaryHeap< type >::getTop( void ) const
// Pre: heap is not empty
// Post: constant reference to item at top of heap has been returned
{
	type* Top=m_array;
	return *Top;
}

template< typename type >
int CBinaryHeap< type >::size( void ) const
// Post: number of elements in heap has been returned
{
        return m_size;
}

template< typename type >
bool CBinaryHeap< type >::isFull( void ) const
// Post: true if heap is full, false otherwise
{
       return(m_size==m_capacity);
}

template< typename type >
bool CBinaryHeap< type >::isEmpty( void ) const
// Post: true if heap is empty false otherwise
{
      return(m_size==0);
}


template< typename type >
void copyData( type* thisData, type* otherData, int size )
// Post: size elements pointed to by otherData have been
// copied to the area pointed to by thisData
{
	for(int a=0; a<size; a++)
	{
	  thisData[a]=otherData[a];
	}
}


template< typename type >
void reheapDown( type* heap, int top, int size )
// Post: data in heap at position >= top is a minimum binary heap
{
    int leftChild = 2 * top + 1;
    int rightChild = 2 * top + 2;
    int minChild;

    if( leftChild < size )  // root is not a leaf
    {
        // find index of smallest child
        if( heap[ leftChild ] < heap[ rightChild ] )
            minChild = leftChild;
        else
            minChild = rightChild;

        // if data at top is bigger than smallest child, swap and continue
        if( heap[ top ] > heap[ minChild ] )
        {
            type temp = heap[ top ];
            heap[ top ] = heap[ minChild ];
            heap[ minChild ] = temp;

            reheapDown( heap, minChild, size );
        }
    }
}


template< typename type >
void reheapUp( type* heap, int root, int bottom )
// Post: data in heap at position >= bottom is a minimum binary heap
{
	int pposition = (bottom-1)/2;
	type whatever;

	if(root!=bottom)
	{
	  if(heap[pposition] > heap[bottom])
	  {
	    whatever=heap[pposition];
	    heap[pposition]=heap[bottom];
	    heap[bottom]=whatever;

	    reheapUp(heap, root, pposition);
	  }
	}
}

template<typename type>
void CBinaryHeap< type >::print(void) const
//print for display and debugging purposes

{
	cout << "\n[ ";
	for (int b = 0; b<m_size; b++)
	{
		cout << m_array[b] << ", ";
	}
	cout << " ]" << endl;
}