Thread: Compiler Error
View Single Post
Old 06-10-2004, 06:34 PM   #6 (permalink)
saiz66
Registered User
 
Join Date: May 2004
Posts: 11
saiz66 is on a distinguished road
I haven't used the < operator in my code yet. But what goes wrong is in the implementation file in my professor's code. I am happy to add it for you:

Code:
#include "pqueuebh.h"
#include <iostream.h>

// Priority Queue:  Implementation File ( Dynamic binary heap )

// Note: Delete and new functions are assumed to take constant time


// Initial size of Priority Queue
static const int InitPQSize = 10;


// DoubleArray
//
// Time complexity: O(n)

template <class Etype>
void
PQueue<Etype>::DoubleArray ( )
{
	Etype *OldArray = Array;
	Array = new Etype [2*MaxSize+1];
	for ( int i=1; i<=CurrentSize; i++ )
		Array[i] = OldArray[i];
	MaxSize *= 2;
	delete [] OldArray;
}


// FixHeap
//
// Time complexity: O(n)

template <class Etype>
void
PQueue<Etype>::FixHeap ( )
{
	for ( int i=CurrentSize/2; i>0; i-- )
		PercolateDown ( i );
	OrderOK = 1;
}


// PercolateDown
//
// Time complexity: O(log n)

template <class Etype>
void
PQueue<Etype>::PercolateDown ( int Parent )
{
	int Child = 2*Parent;
	Etype Temp = Array[Parent];
	while ( Child <= CurrentSize )
	{
		
		if (    Child != CurrentSize            // Right child exists
			&& Array[Child+1] < Array[Child] )
			Child++;
		
		if ( Array[Child] < Temp )
		{
			Array [Parent] = Array[Child];
			Parent = Child;
			Child = 2*Parent;
		}
		else
			break;
	}
	Array[Parent] = Temp;
}


// PercolateUp
//
// Time complexity: O(log n)

template <class Etype>
void
PQueue<Etype>::PercolateUp ( int Child )
{
	int Parent = Child/2;
	Etype Temp = Array[Child];
	while ( Parent > 0 )
	{
		if ( Temp < Array[Parent] )
		{
			Array[Child] = Array[Parent];
			Child = Parent;
			Parent = Child/2;
		}
		else
			break;
	}
	Array[Child] = Temp;
}


// Constructor
//
// Time complexity: O(1)

template <class Etype>
PQueue<Etype>:: PQueue ( ) : MaxSize ( InitPQSize ),
CurrentSize ( 0 ),
OrderOK ( 1 )
{
	// Root is defined at position 1 (and NOT 0)
	Array = new Etype [MaxSize+1];
}


// Copy constructor
//
// Time complexity: O(n)

template <class Etype>
PQueue<Etype>::PQueue ( const PQueue<Etype> & Rhs )
{
	Array = NULL;
	*this = Rhs;
}


// Destructor
//
// Time complexity: O(1)

template <class Etype>
PQueue<Etype>::~PQueue ( )
{
	delete [ ] Array;
}


// Copy assignment
//
// Time complexity: O(n)

template <class Etype>
const PQueue<Etype> &
PQueue<Etype>::operator= ( const PQueue<Etype> & Rhs )
{
	if ( this != &Rhs )
	{
		delete [ ] Array;
		Array = new Etype [Rhs.MaxSize+1];
		MaxSize = Rhs.MaxSize;
		CurrentSize = Rhs.CurrentSize;
		OrderOK = Rhs.OrderOK;
		for ( int i=1; i<=CurrentSize; i++ )
			Array[i] = Rhs.Array[i];
	}
	return *this;
}


// Insert
//
// Amortized time complexity:
//
//           O(1)     if prioritization is NOT maintained
//           O(log n) if prioritization is maintained for a
//                       Priority Queue that was already prioritized
//           O(n)     if prioritization is restored for a
//                       Priority Queue that was NOT prioritized

template <class Etype>
int
PQueue<Etype>::Insert ( const Etype & Element, int i )
{
	i=1;
	if ( CurrentSize == MaxSize )
		DoubleArray ( );
	Array[++CurrentSize] = Element;  // Place Element at the end
	if ( OrderOK )
		if ( i != 1 )
		{
			if ( CurrentSize>1 && Element<Array[CurrentSize/2] ) 
				OrderOK = 0;  // Heap-order property is violated
		}
		else
			PercolateUp ( CurrentSize ); // Maintain heap-order property
		else
            if ( i == 1 )
				FixHeap ( );     // Restore heap-order property
			return 1;
}


// DeleteMin
//
// Time complexity:
//
//           O(log n)   if the Priority Queue was already prioritized
//           O(n)       otherwise

template <class Etype>
int
PQueue<Etype>::DeleteMin ( Etype & Element )
{
	if ( Empty ( ) )
	{
		return 0;
	}
	
	// Prioritize the binary heap if necessary
	if ( !OrderOK )
		FixHeap ( );
	
	Element = Array[1];
	Array[1] = Array[CurrentSize--];
	PercolateDown ( 1 );   // Maintain heap-order property
	return 1;
}


// Length
//
// Time complexity: O(1)

template <class Etype>
int
PQueue<Etype>::Length ( ) const
{
	return CurrentSize;
}


// Empty
//
// Time complexity: O(1)

template <class Etype>
int
PQueue<Etype>::Empty ( ) const
{
	return CurrentSize == 0;
}


// Clear
//
// Time complexity: O(1)

template <class Etype>
void
PQueue<Etype>::Clear ( )
{
	CurrentSize = 0;
	OrderOK = 1;
}
I highlited the part where it shows the compiler error. Thanks for the help.
saiz66 is offline   Reply With Quote