#ifndef __BINARYTREE_AMV
	#define __BINARYTREE_AMV

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

namespace amv	{

template <class type>
class binaryTree	{

	class node	{
		type object;
		unsigned repetitions;
		node *father, *leftChild, *rightChild;
		public:
			node(const type &sourceObject, node *pFatherNode=(node *)0):
			object(sourceObject), repetitions(1),
			father(pFatherNode), leftChild(0), rightChild(0)
				{
				}
			node(const node &n, node *pFatherNode=(node *)0): object(n.object),
			repetitions(n.repetitions), father(pFatherNode), leftChild(0), rightChild(0)
				{
				if(n.leftChild)
					leftChild=new node(*(n.leftChild),this);
				if(n.rightChild)
					rightChild=new node(*(n.rightChild),this);
				}

			~node()
				{
				delete leftChild;
				delete rightChild;
				if(father)
					{
					if(father->leftChild==this)
						father->leftChild=0;
					else
						father->rightChild=0;
					}
				}

			const type *insert(const type &sourceObject)
				{

				if(object==sourceObject)
					{
					++repetitions;
					return 0;
					}
				else
					{
					if(object<sourceObject)
						{
						if(rightChild)
							return (rightChild->insert(sourceObject));
						else
							{
							rightChild=new node(sourceObject,this);
							return &(rightChild->object);
							}
						}
					else
						{
						if(leftChild)
							return (leftChild->insert(sourceObject));
						else
							{
							leftChild=new node(sourceObject,this);
							return &(leftChild->object);
							}
						}
					}
				}

			type *find(const type &searchedObject)
				{
				if(object==searchedObject)
					return &object;
				else
					{
					if(object<searchedObject)
						{
						if(rightChild)
							return (rightChild->find(searchedObject));
						}
					else
						{
						if(leftChild)
							return (leftChild->find(searchedObject));
						}
					}

				return 0;
				}

			const type *find(const type &searchedObject) const
				{
				if(object==searchedObject)
					return &object;
				else
					{
					if(object<searchedObject)
						{
						if(rightChild)
							return (rightChild->find(searchedObject));
						}
					else
						{
						if(leftChild)
							return (leftChild->find(searchedObject));
						}
					}

				return 0;
				}

			friend ostream &operator<<(ostream &os, const node &Node)
				{

				if(Node.leftChild)
					os<<*(Node.leftChild);

				os<<Node.object<<','<<Node.repetitions<<';';

				if(Node.rightChild)
					os<<*(Node.rightChild);

				return os;
				}

			friend class binaryTree<type>;

	};

	node *pRootNode;
	public:
		binaryTree();
		binaryTree(const binaryTree &t);
		template<class it>
		binaryTree(it begin, it end)
			{
			while(begin!=end)
				{
				if(pRootNode)
					pRootNode->insert(*begin);
				else
					pRootNode=new node(*begin);
				++begin;
				}
			}
		~binaryTree();
		binaryTree &operator=(const binaryTree &t);
		const type *insert(const type &sourceObject);
		type *find(const type &sourceObject);
		const type *find(const type &sourceObject) const;
		operator bool() const;
		friend ostream &operator<<(ostream &os, const binaryTree<type> &btree);
};

template <class type>
inline binaryTree<type>::binaryTree(): pRootNode(0)
{
}

template <class type>
inline binaryTree<type>::binaryTree(const binaryTree &t): pRootNode(new node(*(t.pRootNode)))
{
}

template <class type>
inline binaryTree<type>::~binaryTree()
{
delete pRootNode;
}

template <class type>
binaryTree<type> &binaryTree<type>::operator=(const binaryTree &t)
{
delete pRootNode;
if(t.pRootNode)
	pRootNode=new node(*(t.pRootNode));
else
	pRootNode=0;

return *this;
}

template <class type>
inline const type *binaryTree<type>::insert(const type &sourceObject)
{
if(pRootNode)
	return (pRootNode->insert(sourceObject));
else
	{
	pRootNode=new node(sourceObject);
	return (&(pRootNode->object));
	}
}

template <class type>
inline type *binaryTree<type>::find(const type &sourceObject)
{
if(pRootNode)
	return (pRootNode->find(sourceObject));
else
	return 0;
}

template <class type>
inline const type *binaryTree<type>::find(const type &sourceObject) const
{
if(pRootNode)
	return (pRootNode->find(sourceObject));
else
	return 0;
}

template <class type>
inline binaryTree<type>::operator bool() const
{
return pRootNode;
}

template <class type>
inline ostream &operator<<(ostream &os, const binaryTree<type> &btree)
{
if(btree.pRootNode)
	return (os<<(*(btree.pRootNode)));

return os;
}

}
		
#endif