// Andrew C. White, acwhite@charter.net
// 19 April 2002
// Templated Binary Tree

// THIS CODE MAY BE USED BY ANYONE FOR ANY PURPOSE. BY USING THIS CODE YOU
// AGREE TO TAKE FULL RESPNSIBILITY FOR ANY HARMFUL OR UNINTENDED CONSEQUENCES
// THAT IT MAY CAUSE.

// NOTE: This code was created for maximum readability, and therefore is probably
// not very efficient.

// NOTE: The use of templates allows for extreme flexibility. Currently, only
// in-order traversal is implemented, however adding more traversal types would 
// be simple to do.

// NOTE: Before you can add data to a new tree, you must first call the SetIsGreater
// function. This must only be done once for the tree. The function you pass in must
// return a pointer to a BinTreeNode and take two parameters of the data type.
// See the included example if this is unclear.

// NOTE: Before you can use the in-order transversal, you must first call the
// SetInOrder function. This must only be done once for the tree. The function
// you pass in must take a single parameter of the data type. See the included 
// example if this is unclear.


#ifndef _TBT_H_
#define _TBT_H_

///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
// TEMPLATED BINARY TREE NODE CLASS

template <class type> class BinTreeNode
{
public:
	BinTreeNode();
	~BinTreeNode();

	BinTreeNode<type>* Add(type newData, bool (*isGreater) (type data1, type data2));
	void InOrder(void (*inOrder) (type data));
	
private:
	BinTreeNode<type>* right;
	BinTreeNode<type>* left;
	type data;
	bool full;
};

// CONSTRUCTOR
template <class type> BinTreeNode<type>::BinTreeNode()
{
	right = 0;
	left = 0;
	full = false;
}

// DECONSTRUCTOR
template <class type> BinTreeNode<type>::~BinTreeNode()
{
	if(left)
	{
		delete left;
		left = 0;
	}

	if(right)
	{
		delete right;
		right = 0;
	}
}

// ADD
template <class type> BinTreeNode<type>* BinTreeNode<type>::Add(type newData, bool (*isGreater)(type data1, type data2))
{
	if(full)
	{
		if(isGreater(newData, data))
		{
			if(!right)
				right = new BinTreeNode<type>;
			
			return right->Add(newData, isGreater);
		}
		else
		{
			if(!left)
				left = new BinTreeNode<type>;

			return left->Add(newData, isGreater);
		}
	}
	else
	{
		data = newData;
		full = true;
		return this;
	}
}

// IN-ORDER TRAVERSAL
template <class type> void BinTreeNode<type>::InOrder(void (*inOrder) (type data))
{
	if(left)
		left->InOrder(inOrder);

	inOrder(this->data);

	if(right)
		right->InOrder(inOrder);
}

///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
// TEMPLATED BINARY TREE CLASS

template <class type> class BinTree
{
public:
	BinTree();
	~BinTree();

	BinTreeNode<type>* Add(type newData);
	void SetIsGreater(bool (*isGreater)(type data1, type data2));
	void InOrder();
	void SetInOrder(void (*inOrder) (type data));

private:
	BinTreeNode<type>* root;
	bool (*isGreater) (type data1, type data2);
	void (*inOrder) (type data);
};

// CONSTRUCTOR
template <class type> BinTree<type>::BinTree()
{
	root = 0;
	isGreater = 0;
}

// DECONSTRUCTOR
template <class type> BinTree<type>::~BinTree()
{
	if(root)
	{
		delete root;
		root = 0;
	}
	
	isGreater = 0;
	inOrder = 0;
}

// ADD
template <class type> BinTreeNode<type>* BinTree<type>::Add(type newData)
{
	if(!isGreater)
		return 0;
	
	if(!root)
		root = new BinTreeNode<type>;
	
    return root->Add(newData, isGreater);
}

// SET THE COMPARE FUNCTION
template <class type> void BinTree<type>::SetIsGreater(bool (*isGreater) (type data1, type data2))
{
	this->isGreater = isGreater;
}

// IN-ORDER TRAVERSAL
template <class type> void BinTree<type>::InOrder()
{
	if(root && inOrder)
		root->InOrder(inOrder);
}

// SET THE IN-ORDER TRAVERSAL FUNCTION
template <class type> void BinTree<type>::SetInOrder(void (*inOrder) (type data))
{
	this->inOrder = inOrder;
}

#endif 

// Andrew C. White, acwhite@charter.net
// 19 April 2002
// Templated Binary Tree

// THIS CODE MAY BE USED BY ANYONE FOR ANY PURPOSE. BY USING THIS CODE YOU
// AGREE TO TAKE FULL RESPNSIBILITY FOR ANY HARMFUL OR UNINTENDED CONSEQUENCES
// THAT IT MAY CAUSE.

#include <iostream>
#include "TBT.h"

bool test(int a, int b)
{
	if(a > b)
		return true;
		
	return false;
}

void output(int a)
{
	std::cout << ' ' << a << ' ';
}

void main()
{	
	BinTree<int> tree;
	tree.SetIsGreater(test);
	tree.SetInOrder(output);
	
	tree.Add(10);
	tree.Add(5);
	tree.Add(15);

	tree.InOrder();
}