8 Replies - 660 Views - Last Post: 15 April 2009 - 06:51 AM Rate Topic: -----

#1 bsmith11  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 15-January 09

Template function calls

Posted 14 April 2009 - 06:20 PM

Okay, here's my question. I have written this template class with type name Comparable, The only thing is I cannot figure out how to make the correct function declarations below the template. for example:
template<typename Comparable>
bool BinarySearchTree<comparable>::contains(...) const
{
.....
}


Is this right???
If so, I cannot figure the exact method to call the private member functions either.
#include <iostream>

using namespace std;

template <typename Comparable>
class BinarySearchTree
{
  public:
	BinarySearchTree( );
	BinarySearchTree( const BinarySearchTree & rhs );
	~BinarySearchTree( );

	const Comparable & findMin( ) const;
	const Comparable & findMax( ) const;
	bool contains( const Comparable & x ) const;
	bool isEmpty( ) const;
	void printTree( ) const;

	void makeEmpty( );
	void insert( const Comparable & x );
	void remove( const Comparable & x );

	const BinarySearchTree & operator=( const BinarySearchTree & rhs );

  private:
	struct BinaryNode
	{
	   Comparable element;
	   BinaryNode *left;
	   BinaryNode *right;

	   BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
		 : element( theElement ), left( lt ), right( rt ) { }
	};

	BinaryNode *root;
	
	void insert( const Comparable &x, BinaryNode * &t ) const;
	void remove( const Comparable &x, BinaryNode * &t ) const;
	BinaryNode *findMin( BinaryNode *t ) const;
	BinaryNode *findMax( BinaryNode *t ) const;
	bool contains( const Comparable &x, BinaryNode *t ) const;
	void makeEmpty( BinaryNode * &t );
	void printTree( BinaryNode *t ) const;
	BinaryNode * clone( BinaryNode *t ) const;
};



Here are the member functions in case a reference is needed.
void makeEmpty( BinaryNode * & t )
{
	if( t != NULL )
	{
		makeEmpty( t->left );
		makeEmpty( t->right );
		delete t;
	}
	t = NULL;
}


bool contains( const Comparable & x ) const
{
	return contains( x, root );
}


void insert( const Comparable & x )
{
	insert( x, root );
}

void remove( const Comparable & x )
{
	remove( x, root );
}

bool contains( const Comparable & x, BinaryNode *t ) const
{
	if( t == NULL )
		return false;
	else if( x < t->element )
		return contains( x, t->left );
	else if( t->element < x )
		return contains( x, t->right );
	else
		return true;	// Match
}
void insert( const Comparable &x, BinaryNode *&t ) const
{
	if( t == NULL )
		t = new BinaryNode( x, NULL, NULL );
	else if( x < t->element )
		insert( x, t->left );
	else if( t->element < x )
		insert( x, t->right );
	else
	;  // Duplicate; do nothing
}

BinaryNode *findMax( BinaryNode *t ) const
{
	if( t != NULL )
		while( t->right != NULL )
			t = t->right;
	return t;
}

void remove( const Comparable & x, BinaryNode * & t )
{
	if( t == NULL )
		return;   // Item not found; do nothing
	if( x < t->element )
		remove( x, t->left );
	else if( t->element < x )
		remove( x, t->right );
	else if( t->left != NULL && t->right != NULL ) // Two children
	{
		t->element = findMin( t->right )->element;
		remove( t->element, t->right );
	}
	else
	{
		BinaryNode *oldNode = t;
		t = ( t->left != NULL ) ? t->left : t->right;
		delete oldNode;
	}
}

const BinarySearchTree & operator=( const BinarySearchTree & rhs )
{
	if( this != &rhs )
	{
		makeEmpty( );
		root = clone( rhs.root );
	}
	return *this;
}

BinaryNode * clone( BinaryNode *t ) const
{
	if( t == NULL )
		return NULL;
	
	return new BinaryNode( t->element, clone( t->left ), clone( t->right ) );
}




I would appreciate just a nudge in the right direction...I want to do this myself as much as possible but I've just been fighting it for days and have exhausted my internet resources.

Is This A Good Question/Topic? 0
  • +

Replies To: Template function calls

#2 BlakeJustBlake  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 26
  • View blog
  • Posts: 441
  • Joined: 15-February 09

Re: Template function calls

Posted 14 April 2009 - 06:26 PM

You'd call them the same way as the public member functions. If you're saying what I think you're saying.
Was This Post Helpful? 0
  • +
  • -

#3 bsmith11  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 15-January 09

Re: Template function calls

Posted 14 April 2009 - 06:29 PM

I thought the same thing but when I do It comes back with tons of errors...unless im doing them all wrong.
Was This Post Helpful? 0
  • +
  • -

#4 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,137
  • Joined: 14-September 07

Re: Template function calls

Posted 14 April 2009 - 06:53 PM

You're missing class scope operators ::

void makeEmpty( BinaryNode * & t )
{
	if( t != NULL )
	{
		makeEmpty( t->left );
		makeEmpty( t->right );
		delete t;
	}
	t = NULL;
}

//should be

void BinarySearchTree::makeEmpty( BinaryNode * & t )
{
	if( t != NULL )
	{
		makeEmpty( t->left );
		makeEmpty( t->right );
		delete t;
	}
	t = NULL;
}


Was This Post Helpful? 0
  • +
  • -

#5 bsmith11  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 15-January 09

Re: Template function calls

Posted 14 April 2009 - 06:57 PM

The compiler says that it needs the template argument list.
Was This Post Helpful? 0
  • +
  • -

#6 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,137
  • Joined: 14-September 07

Re: Template function calls

Posted 14 April 2009 - 07:04 PM

I forgot a piece:

template <typename Comparable>
void BinarySearchTree<Comparable>::makeEmpty()
{
	//example
}



Sorry about that.
Was This Post Helpful? 0
  • +
  • -

#7 bsmith11  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 15-January 09

Re: Template function calls

Posted 14 April 2009 - 07:09 PM

ok, I have that much for a them...But here's where I run into trouble
BinaryNode *findMax( BinaryNode *t ) const
{
	if( t != NULL )
		while( t->right != NULL )
			t = t->right;
	return t;
}

const BinarySearchTree & operator=( const BinarySearchTree & rhs )
{
	if( this != &rhs )
	{
		makeEmpty( );
		root = clone( rhs.root );
	}
	return *this;
}



These definitions are beyond me. I've tried the template call and scope operators.
but it comes back saying there are problems before the '&' operator and before the '*'
Was This Post Helpful? 0
  • +
  • -

#8 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,137
  • Joined: 14-September 07

Re: Template function calls

Posted 14 April 2009 - 07:53 PM

Exact errors?


edit: You're missing the things already mentioned for those two functions.

This post has been edited by KYA: 14 April 2009 - 07:57 PM

Was This Post Helpful? 0
  • +
  • -

#9 bsmith11  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 15-January 09

Re: Template function calls

Posted 15 April 2009 - 06:51 AM

this is how I have them written

template<typename Comparable>
void BinarySearchTree<Comparable>::remove( const Comparable & x, BinaryNode * & t )
{
	if( t == NULL )
		return;   // Item not found; do nothing
	if( x < t->element )
		remove( x, t->left );
	else if( t->element < x )
		remove( x, t->right );
	else if( t->left != NULL && t->right != NULL ) // Two children
	{
		t->element = findMin( t->right )->element;
		remove( t->element, t->right );
	}
	else
	{
		BinaryNode *oldNode = t;
		t = ( t->left != NULL ) ? t->left : t->right;
		delete oldNode;
	}
}

template<typename Comparable>
 BinarySearchTree<Comparable>::BinaryNode *findMax( BinaryNode *t ) const
{
	if( t != NULL )
		while( t->right != NULL )
			t = t->right;
	return t;
}

template<typename Comparable>
const BinarySearchTree<Comparable>::BinarySearchTree & operator=( const BinarySearchTree & rhs )
{
	if( this != &rhs )
	{
		makeEmpty( );
		root = clone( rhs.root );
	}
	return *this;
}

template<typename Comparable>
 BinarySearchTree<Comparable>::BinaryNode * clone( BinaryNode *t ) const
{
	if( t == NULL )
		return NULL;
	
	return new BinaryNode( t->element, clone( t->left ), clone( t->right ) );
}


Here are the errors:
1>Compiling...
1>btree.cpp
1>e:\3200 extra credit\btree\btree.h(130) : error C2244: 'BinarySearchTree<Comparable>::remove' : unable to match function definition to an existing declaration
1> definition
1> 'void BinarySearchTree<Comparable>::remove(const Comparable &,BinarySearchTree<Comparable>::BinaryNode *&)'
1> existing declarations
1> 'void BinarySearchTree<Comparable>::remove(const Comparable &,BinarySearchTree<Comparable>::BinaryNode *&) const'
1> 'void BinarySearchTree<Comparable>::remove(const Comparable &)'
1>e:\3200 extra credit\btree\btree.h(133) : warning C4346: 'BinarySearchTree<Comparable>::BinaryNode' : dependent name is not a type
1> prefix with 'typename' to indicate a type
1>e:\3200 extra credit\btree\btree.h(133) : error C2143: syntax error : missing ';' before '*'
1>e:\3200 extra credit\btree\btree.h(133) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
1>e:\3200 extra credit\btree\btree.h(133) : fatal error C1903: unable to recover from previous error(s); stopping compilation
1>Build log was saved at "file://e:\3200Extra\3200Extra\Debug\BuildLog.htm"
1>3200Extra - 4 error(s), 1 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1