///////////////////////////////////////////////////////////////
//
//	heap.cpp
//
//	Implementation of a heap of strings.  Interface in heap.h.
//
//	REVISION HISTORY
//		2/21/01  (Jeff Ondich) Wrote initial version.
//
///////////////////////////////////////////////////////////////

#include	"heap.h"

Heap::Heap( int size )
{
	mMaxSize = 0;
	mCurrentSize = 0;

	if( size > 0 )
	{
		mMaxSize = size;
		mHeap = new string[ size + 1 ];
		if( mHeap == NULL )
		{
			cerr << "Memory allocation error in Heap::Heap(int)" << endl;
			exit( 1 );
		}
	}
}


Heap::~Heap()
{
	delete [] mHeap;
}


int Heap::Size()
{
	return( mCurrentSize );
}


void Heap::AddItem( const string& newItem )
{
	if( mCurrentSize >= mMaxSize )
	{
		cerr << "Maximum heap size " << mMaxSize
			<< " exceeded while adding \"" << newItem << "\"" << endl;
		return;
	}

	// Find the location for the new item.
	mCurrentSize++;
	int i = mCurrentSize;
	while( i > 1  &&  mHeap[i/2] < newItem )
	{
		mHeap[i] = mHeap[i/2];
		i = i / 2;
	}
	
	// Insert the new item into its new home.
	mHeap[i] = newItem;
}


// Delete and return the root, fixing the heap before returning.

const string& Heap::RemoveItem()
{
	mHeap[0] = mHeap[1];

	int parent = 1;
	while( 2*parent < mCurrentSize )
	{
		int child = 2*parent;
		if( child + 1 < mCurrentSize  &&  mHeap[child+1] > mHeap[child] )
			child++;

		if( mHeap[child] > mHeap[mCurrentSize] )
			mHeap[parent] = mHeap[child];
		else
			break;
		
		parent = child;
	}

	mHeap[parent] = mHeap[mCurrentSize];
	mCurrentSize--;

	return( mHeap[0] );
}


void Heap::Print()
{
	for( int i=1; i <= mCurrentSize; i++ )
		cout << mHeap[i] << endl;
}