C++ Method Definition and Implementation Error

[meddlepal]

I am having a problem with a class I am writing. I have defined a whole bunch of methods defined that the compiler is telling me in the implementation are different. The errors are:

1>------ Build started: Project: prog6a, Configuration: Debug Win32 ------
1>Compiling...
1>main.cpp
1>c:\users\philip\documents\visual studio 2005\projects\cs211\prog6a\prog6a\avltree.h(186) : error C2244: 'AVLTree<T>::levelorder' : unable to match function definition to an existing declaration
1> c:\users\philip\documents\visual studio 2005\projects\cs211\prog6a\prog6a\avltree.h(15) : see declaration of 'AVLTree<T>::levelorder'
1> definition
1> 'void AVLTree<T>::levelorder(AVLTree<T>::Node *&)'
1> existing declarations
1> 'void AVLTree<T>::levelorder(BinaryTree<T>::node *&)'
1>c:\users\philip\documents\visual studio 2005\projects\cs211\prog6a\prog6a\avltree.h(204) : error C2244: 'AVLTree<T>::LeftLeft' : unable to match function definition to an existing declaration
1> c:\users\philip\documents\visual studio 2005\projects\cs211\prog6a\prog6a\avltree.h(18) : see declaration of 'AVLTree<T>::LeftLeft'
1> definition
1> 'void AVLTree<T>::LeftLeft(AVLTree<T>::Node *&)'
1> existing declarations
1> 'void AVLTree<T>::LeftLeft(BinaryTree<T>::node *&)'
1>c:\users\philip\documents\visual studio 2005\projects\cs211\prog6a\prog6a\avltree.h(217) : error C2244: 'AVLTree<T>::RightRight' : unable to match function definition to an existing declaration
1> c:\users\philip\documents\visual studio 2005\projects\cs211\prog6a\prog6a\avltree.h(19) : see declaration of 'AVLTree<T>::RightRight'
1> definition
1> 'void AVLTree<T>::RightRight(AVLTree<T>::Node *&)'
1> existing declarations
1> 'void AVLTree<T>::RightRight(BinaryTree<T>::node *&)'
1>c:\users\philip\documents\visual studio 2005\projects\cs211\prog6a\prog6a\avltree.h(250) : error C2244: 'AVLTree<T>::LeftRight' : unable to match function definition to an existing declaration
1> c:\users\philip\documents\visual studio 2005\projects\cs211\prog6a\prog6a\avltree.h(20) : see declaration of 'AVLTree<T>::LeftRight'
1> definition
1> 'void AVLTree<T>::LeftRight(AVLTree<T>::Node *&)'
1> existing declarations
1> 'void AVLTree<T>::LeftRight(BinaryTree<T>::node *&)'
1>c:\users\philip\documents\visual studio 2005\projects\cs211\prog6a\prog6a\avltree.h(283) : error C2244: 'AVLTree<T>::RightLeft' : unable to match function definition to an existing declaration
1> c:\users\philip\documents\visual studio 2005\projects\cs211\prog6a\prog6a\avltree.h(21) : see declaration of 'AVLTree<T>::RightLeft'
1> definition
1> 'void AVLTree<T>::RightLeft(AVLTree<T>::Node *&)'
1> existing declarations
1> 'void AVLTree<T>::RightLeft(BinaryTree<T>::node *&)'
1>Build log was saved at "file://c:\Users\Philip\Documents\Visual Studio 2005\Projects\CS211\prog6a\prog6a\Debug\BuildLog.htm"
1>prog6a - 5 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

The class file is:

#include <iostream>
#include "BinaryTree.h"
#include "Queue.h"

using namespace std;

#ifndef _AVLTREE_H
#define _AVLTREE_H

template <class T>
class AVLTree : public BinaryTree<T>
{
public:
	void insert(const T& x);
	void levelorder(ptr& root);
	void printTree();

	void LeftLeft(ptr& pivot);
	void RightRight(ptr& pivot);
	void LeftRight(ptr& pivot);
	void RightLeft(ptr& pivot);

protected:
	struct Node
	{
		T data;
		int balance;
		Node* left;
		Node* right;
	};

	typedef Node* ptr;

	ptr root;
};

template <class T>
void AVLTree<T>::insert(const T& x)
{
	ptr p, q, qparent, piv, pivparent;
	p = new Node;
	p->data = x;
	p->left = NULL;
	p->right = NULL;
	p->balance = 0;

	if (root == NULL)
	{
		root = p;
		return;
	}

	q = root;
	qparent = NULL;

	piv = root;
	pivparent = NULL;

	do
	{
		if (q->balance != 0)
		{
			piv = q;
			pivparent = qparent;
		}

		qparent = q;
		
		if (x <= q->data)
		{
			q = q->left;
		}
		else
		{
			q = q->right;
		}
	} while(q != NULL);

	if (x <= qparent->data)
	{
		qparent->left = p;
	}
	else
	{
		qparent->right = p;
	}

	q = piv;

	do
	{
		if (x <= q->data)
		{
			q->balance++;
			q = q->left;
		}
		else
		{
			q->balance--;
			q = q->right;
		}
	} while (q != p);

	if (piv->balance == 0 ||
		piv->balance == 1 ||
		piv->balance == -1)
	{
		return;
	}
	else
	{
		if (x <= piv->data) && (x <= piv->left->data)
		{
			if(piv == root)
			{
				LeftLeft(root);
			}
			else if (piv == pivparent->left)
			{
				LeftLeft(pivparent->left);
			}
			else
			{
				LeftLeft(pivparent->right);
			}
			return;
		}

		if (x <= piv->data) && (x > piv->left->data)
		{
			if(piv == root)
			{
				LeftRight(root);
			}
			else if (piv == pivparent->left)
			{
				LeftRight(pivparent->left);
			}
			else
			{
				LeftRight(pivparent->right);
			}
			return;
		}

		if (x > piv->data) && (x > piv->left->data)
		{
			if(piv == root)
			{
				RightRight(root);
			}
			else if (piv == pivparent->left)
			{
				RightRight(pivparent->left);
			}
			else
			{
				RightRight(pivparent->right);
			}
			return;
		}

		if (x > piv->data) && (x <= piv->left->data)
		{
			if(piv == root)
			{
				RightLeft(root);
			}
			else if (piv == pivparent->left)
			{
				RightLeft(pivparent->left);
			}
			else
			{
				RightLeft(pivparent->right);
			}
			return;
		}
	}
}

template <class T>
void AVLTree<T>::levelorder(ptr& root)
{
	Queue<T> q;
}

template <class T>
void AVLTree<T>::printTree()
{
}

template <class T>
void AVLTree<T>::LeftLeft(ptr& pivot)
{
	ptr p;

	p = pivot->right;
	pivot->balance = 0;
	p->balance = 0;
	pivot->right = p->left;
	p->left = pivot;
	pivot = p;
}

template <class T>
void AVLTree<T>::RightRight(ptr& pivot)
{
	ptr p;

	p = pivot->left;
	pivot->balance = 0;
	p->balance = 0;
	pivot->left = p->right;
	p->right = pivot;
	pivot = p;
}

template <class T>
void AVLTree<T>::LeftRight(ptr& pivot)
{
	ptr p;
	ptr q;

	p = pivot->right;
	q = p->left;

	if (q->balance == -1)
	{
		pivot->balance = 0;
		p->balance = 1;  
	}
	else if (q->balance == 0)
	{
		pivot->balance = 0;
		p->balance = 0;
	}
	else
	{
		pivot->balance = -1;
		p->balance = 0;
	}

	q->balance = 0;
	p->left = q->right;
	q->right = p;
	pivot->right = q->left;
	q->left = pivot;
	pivot = q;
}

template <class T>
void AVLTree<T>::RightLeft(ptr& pivot)
{
	ptr p;
	ptr q;

	p = pivot->left;
	q = p->right;

	if (q->balance == 1)
	{
		pivot->balance = 0;
		p->balance = -1;  
	}
	else if (q->balance == 0)
	{
		pivot->balance = 0;
		p->balance = 0;
	}
	else
	{
		pivot->balance = 1;
		p->balance = 0;
	}

	q->balance = 0;
	p->right = q->left;
	q->left = p;
	pivot->left = q->right;
	q->right = pivot;
	pivot = q;
}

#endif

Does anybody know what is going wrong here? The definitions and implementations appear correct to me.

[mrboolf]

I'm fairly new to C++ in general and inheritance in particular so please someone correct me if I'm wrong: it seems to me like your methods definitions are conflicting with base class definitions of the same methods.

It's just a guess, I'm waiting for someone else (with more knowledge on the subject) to have a word about this.

[Ancient Dragon]

Node is defined within class AVLTree and only has scope within that class, so in order to use it as a parameter you need to declare its scope. Try this: void AVLTree<T>::levelorder(AVLTree::ptr& root)

[ArkM]

Where was defined the type ptr? Why Node and node typenames occured in err messages?
See also error C2244 description in MSDN...

[Ancient Dragon]

Where was defined the type ptr?

See line 32.

[meddlepal]

Hey guys thanks for the help. I came up with this solution. Replaced Line 32 with the following:

Original:

typedef node* ptr;

Fixed:

typedef BinaryTree<T>::node* ptr;

Why that works, I am not entirely sure. I'm sure it has to do with inheritance.