mavltree.cpp

AVL Tree implementation: I also included a test function to compare the AVL Tree performance with S

#include "mavltree.hpp"
#include "comparer.hpp"
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include "time.h"

using namespace std;

int doCustAVLTest(int records, char type, AVLTree< float, ByDivision<float> >& avlTree);
int doMapTest(int records, char type, map<const int, float>& m);
int doSetTest(int records, char type, set<float>& s);
const int NUMBER_OF_RECORDS = 20;

int main()
{
	map<const int, float> m;
	set<float> s;
	AVLTree< float, ByDivision<float> > avlTree;

	char input[100];
	char type[100];

	cout << "*********************************************" << endl;
	cout << "AVL tree and STL container test program" << endl;
	cout << "type \"q\" to quit!" << endl;
	cout << "*********************************************" << endl;

	cout << "Please enter test options: " << endl;
	cout << " * \"1\" for AVL " << endl;
	cout << " * \"2\" for Map " << endl;
	cout << " * \"3\" for Set " << endl;
	cin >> input;

	if (input && strcmp(input, "q") != 0)
	{
		cout << "Please enter the operation: " << endl;
		cout << " * \"i\" for Insert " << endl;
		cout << " * \"g\" for Get " << endl;
		//cout << " * \"m\" for Modify " << endl;
		//cout << " * \"d\" for Delete " << endl;
		//cout << " * \"p\" for Print Content " << endl;
		cout << " * \"c\" for Check whether the AVL tree is valid, only for AVL(1)" << endl;
		cin >> type;
	}

	while (type && strcmp(type, "q") != 0 && 
			input && strcmp(input, "q") != 0)
	{
		if (strcmp(input, "1") == 0)
			doCustAVLTest(NUMBER_OF_RECORDS, type[0], avlTree);
		else if (strcmp(input, "2") == 0)
			doMapTest(NUMBER_OF_RECORDS, type[0], m);
		else if (strcmp(input, "3") == 0)
			doSetTest(NUMBER_OF_RECORDS, type[0], s);

		cout << "Please enter test options: " << endl;
		cout << " * \"1\" for AVL " << endl;
		cout << " * \"2\" for Map " << endl;
		cout << " * \"3\" for Set " << endl;
		cin >> input;

		if (input && strcmp(input, "q") != 0)
		{
			cout << "Please enter the operation: " << endl;
			cout << " * \"i\" for Insert " << endl;
			cout << " * \"g\" for Get " << endl;
			//cout << " * \"m\" for Modify " << endl;
			//cout << " * \"d\" for Delete " << endl;
			//cout << " * \"p\" for Print Content " << endl;
			cout << " * \"c\" for Check whether the AVL tree is valid, only for AVL(1)" << endl;
			cin >> type;
		}
		else 
			break;
	}

	return 0;
}

int doCustAVLTest(int records, char type, AVLTree< float, ByDivision<float> >& avlTree)
{
	clock_t start, finish;
	double duration;
	const char* operation;
	if (type == 'i')
	{
		operation = "INSERT";
		//Do clear first
		if (!avlTree.empty())
		{
			avlTree.clear(avlTree.begin().getIterPtr());
			cout << "AVL tree cleared! Type any key + \"ENTER\" to continue ..." << endl;

			char b[1];
			cin >> b;
		}

		//Prepare the preset data instead of totally depending on random numbers
		int inserted[NUMBER_OF_RECORDS];
		for (int i = 0; i < NUMBER_OF_RECORDS; i++)
			inserted[i] = i;

		//suffle the array
		int randSuff = (int)((rand() / 1000000) % NUMBER_OF_RECORDS + NUMBER_OF_RECORDS / 2);
		for (int i = 0; i < randSuff; i++)
		{
			int randFrom = (rand() / 1000000) % NUMBER_OF_RECORDS;
			int randTo = (rand() / 1000000) % NUMBER_OF_RECORDS;

			if (randFrom != randTo)
			{
				int temp = inserted[randFrom];
				inserted[randFrom] = inserted[randTo];
				inserted[randTo] = temp;
			}
		}

	    start = clock();
		for (int i = 0; i < NUMBER_OF_RECORDS; i++)
		{
			/*float random = floor(rand() / 1000000);
			avlTree.insert(random);
			cout << "Successfully insert the number: " << random << endl;*/

			avlTree.insert(inserted[i]);
			cout << "Successfully insert the number: " << inserted[i] << endl;
		}

		finish = clock();
	}
	else if (type == 'g')
	{
		operation = "GET";
		//if empty, insert first
		if (avlTree.empty())
			doCustAVLTest(records, 'i', avlTree);

	    start = clock();
		for (int i = 0; i < records; i++)
		{
			//find random numbers
			float random = (rand() / 1000000) % (NUMBER_OF_RECORDS * 2);
			cout << "Finding number " << random << " ..."; 
			if (avlTree.find(random) != avlTree.end())
				cout << "Found :-)";
			cout << endl;
		}
		finish = clock();
	}
	/*else if (type == 'd')
	{
		operation = "DELETE";
		//if empty, insert first
		if (avlTree.empty())
			doCustAVLTest(records, 'i', avlTree);

	    start = clock();
		for (int i = 0; i < records; i++)
		{
			//find random numbers
			float random = (rand() / 1000000) % (NUMBER_OF_RECORDS * 2);
			cout << "Deleting number " << random << " ..."; 

			//if (avlTree.find(random) != avlTree.end())
			//{
				if (avlTree.erase(random).getIterPtr() != NULL
					&& (avlTree.erase(random) != avlTree.begin()))
				   cout << " Deleted :-) ";
			//}
			cout << endl;
		}
		finish = clock();
	}
	else if  (type == 'm')
	{
		operation = "MODIFY";
		//if empty, insert first
		if (avlTree.empty())
			doCustAVLTest(records, 'i', avlTree);

	    start = clock();
		for (int i = 0; i < records; i++)
		{
			//change numbers
			float random = floor(rand() / 1000000);
			float to = floor(rand() / 1000000) + floor(rand() / 1000000) + floor(rand() / 1000000);
			cout << i << ") " << "Changing number " << random << " to " << to << " ..."; 
			if (avlTree.change(random, to) != avlTree.end())
				cout << "Changed :-)";

			cout << endl;
		}
		finish = clock();
	}*/
	else if  (type == 'p')
	{
		operation = "PRINT";

	    start = clock();

		/*int count = 0;
		for (AVLTree< float, ByDivision<float> >::iterator iter(avlTree.leftmost());
			iter != avlTree.end(); ++iter)
		{
			cout << "Visit node: " << *iter << endl;
			count++;
		}
		
		//print the last element
		cout << "Visit node: " << *avlTree.end() << endl;
		count++;

		cout << "START NODE: " << *avlTree.begin() << endl;
		cout << "END NODE: " << *avlTree.end() << endl;
		cout << "Node count: " << count << endl;

		cout << "********************************************** " << endl << endl;*/
		avlTree.print();
		finish = clock();
	}
	else if  (type == 'c')
	{
		operation = "CHECK VALIDATION";

	    start = clock();
		if (avlTree.isAVLTree())
			 cout << "VALID!" << endl;
		else
			cout << "NOT valid!" << endl;
		finish = clock();
	}
	else
	{
		cout << "Invalid operation, please choose from the menu" << endl;
		return -1;
	}

	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("/\\ Test AVL tree (%s) (%d Records): \n/\\ Time elapsed: %lf seconds.\n", operation, records, duration);
	return 1;
}

int doMapTest(int records, char type, map<const int, float>& m)
{
	clock_t start, finish;
	double duration;
	const char* operation;

	if (type == 'i')
	{
		operation = "INSERT";
		//do clear first
		if (!m.empty())
		{
			m.clear();
			cout << "map cleared! Type any key + \"ENTER\" to continue ..." << endl;

			char b[1];
			cin >> b;
		}

		start = clock();
		for (int i = 0; i < records; i++)
		{
			int key = i;
			float value = (rand() / 1000000) % NUMBER_OF_RECORDS;
			m.insert(make_pair(key, value));
			cout << "Successfully inserting " << key << " => " << value << endl;
		}

		finish = clock();
	}
	else if (type == 'g')
	{
		operation = "GET";
		//do insert first
		if (m.empty())
			doMapTest(records, 'i', m);

		start = clock();
		for (int i = 0; i < records; i++)
		{
			int key = i;

			map<const int, float>::iterator iter = m.find(i);
			if (iter != m.end())
				cout << "Found " << i << " : " << iter->first << " => " << iter->second << " :-) " << endl;
		}
		finish = clock();
	}
	else
	{
		cout << "Invalid operation, please choose from the menu" << endl;
		return -1;
	}

	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("/\\ Test Map (%s) (%d Records): \n/\\ Time elapsed: %lf seconds.\n", operation, records, duration);
	return 1;
}

int doSetTest(int records, char type, set<float>& m)
{
	clock_t start, finish;
	double duration;
	const char* operation;

	if (type == 'i')
	{
		operation = "INSERT";
		//do clear first
		if (!m.empty())
		{
			m.clear();
			cout << "set cleared! Type any key + \"ENTER\" to continue ..." << endl;

			char b[1];
			cin >> b;
		}

		start = clock();
		for (int i = 0; i < records; i++)
		{
			float value = (rand() / 1000000) % NUMBER_OF_RECORDS;
			m.insert(value);
			cout << "Successfully inserting " << value << endl;
		}

		finish = clock();
	}
	else if (type == 'g')
	{
		operation = "GET";
		//do insert first
		if (m.empty())
			doSetTest(records, 'i', m);

		start = clock();
		for (int i = 0; i < records; i++)
		{
			float value = (rand() / 1000000) % (NUMBER_OF_RECORDS * 2);
			set<float>::iterator iter = m.find(value);
			if (iter != m.end())
				cout << "Found " << *iter << ":-)" << endl;
		}
		finish = clock();
	}
	else
	{
		cout << "Invalid operation, please choose from the menu" << endl;
		return -1;
	}

	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("/\\ Test Set (%s) (%d Records): \n/\\ Time elapsed: %f seconds.\n", operation, records, duration);
	return 1;
}

/*
 * AVLTree Methods declaration
 */
template<class T, class Compare>
AVLTree<T, Compare>::AVLTree()
{
	header = new AVLNode<T>;
	header->isHeader = true;
	header->parent = NULL;
	header->left = header->right = header;
	header->balanceFactor = '=';
	node_count = 0;
	cout << "/// I've done the init process!" << endl;
}

template<class T, class Compare>
AVLTree<T, Compare>::~AVLTree()
{
	cout << "Releasing memory ... " << endl;
	clear(header->parent);
	cout << "Release success !!!" << endl;
}

template<class T, class Compare>
void AVLTree<T, Compare>::clear(Link link)
{
	if (link != NULL)
	{
		clear(link->left);
		clear(link->right);
		delete link;
	}
	else
	{
		delete header;
		header = new AVLNode<T>;
		header->isHeader = true;
		header->parent = NULL;
		header->left = header->right = header;
		header->balanceFactor = '=';
		node_count = 0;
	}
}

/*template<class T, class Compare>
void AVLTree<T, Compare>::erase(iterator itr)
{
	//itr positioned at root node
	if ((itr.getIterPtr())->parent->parent == (itr.getIterPtr()))
		deleteLink((itr.getIterPtr())->parent->parent);
	//itr positioned at a left child
	else if ((itr.getIterPtr())->parent->left == (itr.getIterPtr()))
		deleteLink((itr.getIterPtr())->parent->left);
	else
		deleteLink((itr.getIterPtr())->parent->right);
}

template<class T, class Compare>
void AVLTree<T, Compare>::deleteLink(Link& link)
{
	if (link->left == NULL || link->right == NULL)
		prune(link);
	else if (link->right->left == NULL)
	{
		link->item = link->right->item;
		prune(link->right);
	}//empty left subtree of right subtree of link
	else
	{
		Link temp = link->right->left;

		while(temp->left != NULL)
			temp = temp->left;

		link->item = temp->item;
		prune(temp->parent->left);
	}//nonempty left subtree of right subtree of link
}

template<class T, class Compare>
void AVLTree<T, Compare>::prune(Link& link)
{
	Link linkCopy = link, newLink;
	node_count--;

	if ((link->left == NULL) && (link->right == NULL))
	{
		if (link == header->left)
			header->left = link->parent; //new leftmost
		if (link == header->right)
			header->right = link->parent; //new rightmost

		link = NULL;
	}
	else if (link->left == NULL)
	{
		link = link->right;
		link->parent = linkCopy->parent;
		if (linkCopy == header->left)
		{
			newLink = link;

			while((newLink->left) != NULL)
				newLink = newLink->left;

			header->left = newLink; //new leftmost
		}//recalculate leftmost
	}//link -> left nonempty
	else
	{
		link = link->left;
		link->parent = linkCopy->parent;
		if (linkCopy == header->right)
		{
			newLink = link;

			while ((newLink->right) != NULL)
				newLink = newLink->right;

			header->right = newLink; //new rightmost
		}//recalculate rightmost
	}//root->right nonempty

	delete linkCopy;
}//prune*/

template<class T, class Compare>
bool AVLTree<T, Compare>::empty()
{
	if (header->parent == NULL 
		&& node_count == 0)
		return true;
	else
		return false;
}

template<class T, class Compare>
AVLIterator<T> AVLTree<T, Compare>::begin()
{
	return iterator(header->parent);
}

template<class T, class Compare>
AVLIterator<T> AVLTree<T, Compare>::end()
{
	return iterator(header->right);
}

template<class T, class Compare>
AVLIterator<T> AVLTree<T, Compare>::leftmost()
{
	return iterator(header->left);
}

template<class T, class Compare>
AVLIterator<T> AVLTree<T, Compare>::rightmost()
{
	return iterator(header->right);
}

template<class T, class Compare>
bool AVLTree<T, Compare>::checkAVLTree(Link root)
{
	int maxHeight = 0;

	if (root == NULL)
		return true;
	else
		if ((abs(getHeight(root->left, 0, maxHeight) - getHeight(root->right, 0, maxHeight)) <= 1)
					&& (checkAVLTree(root->left))
					&& (checkAVLTree(root->right)))
			return true;

	return false;
}

template<class T, class Compare>
int AVLTree<T, Compare>::getHeight(Link root, int height, int& maxHeight)