/*
 * tree.cpp
 *
 *  Created on: 28.11.2012
 *      Author: trifon
 */

#ifndef __TREE_CPP
#define __TREE_CPP

#include <iostream>
#include "tree.h"
using namespace std;


template <typename T>
struct node {
	T inf;
	node<T> *left, *right;
};

template <typename T>
class BinTree;

template <typename T>
class BinTreeIterator : public TreeIterator<T> {
private:
	node<T>* p;
public:
	BinTreeIterator(node<T>* _p = NULL) : p(_p) {}

	BinTreeIterator<T> operator++() const {
		return BinTreeIterator(p->left);
	}

	BinTreeIterator<T> operator++(int) const {
		return BinTreeIterator(p->right);
	}

	T& operator*() const {
		return p->inf;
	}

	operator bool() const {
		return p != NULL;
	}

	bool operator==(TreeIterator<T> const& it) const {
		BinTreeIterator<T> const& btit = (BinTreeIterator<T> const&)it;
		return p == btit.p;
	}
};

template <typename T = int>
class BinTree : public Tree<T, BinTreeIterator<T> > {
protected:
	node<T>* root;

	void adopt(node<T>*& dest, node<T>*& src) {
		dest = src;
		src = NULL;
	}

	void deleteNode(node<T>* n) {
		if (n != NULL)
		{
			deleteNode(n->left);
			deleteNode(n->right);
			delete n;
		}
	}

	void copyNode(node<T>*& dest, node<T> const * src)
	{
		if (src == NULL)
			dest = NULL;
		else
		{
			dest = new node<T>;
			dest->inf = src->inf;
			copyNode(dest->left, src->left);
			copyNode(dest->right, src->right);
		}
	}

public:
	BinTree() : root(NULL) {}

	BinTree(BinTree<T> const& bt) {
		copyNode(root, bt.root);
	}

	BinTree<T>& operator=(BinTree<T> const& bt)
	{
		if (&bt != this)
		{
			deleteNode(root);
			copyNode(root, bt.root);
		}
		return *this;
	}

	~BinTree() { deleteNode(root); }

	bool empty() const {
		return root == NULL;
	}

	typedef BinTreeIterator<T> I;

	I iterator() const {
		return I(root);
	}

	void adoptLeft(BinTree<T>& t)
	{
		if (root != NULL)
			adopt(root->left, t.root);
	}

	void adoptRight(BinTree<T>& t)
	{
		if (root != NULL)
			adopt(root->right, t.root);
	}

	void createTree(T const& inf, BinTree<T>& ltree, BinTree<T>& rtree)
	{
		deleteNode(root);
		root = new node<T>;
		root->inf = inf;
		adoptLeft(ltree);
		adoptRight(rtree);
	}

	bool rootTree(T& inf) const
	{
		if (root == NULL)
			return false;
		inf = root->inf;
		return true;
	}

	void print() const
	{
		print(iterator());
	}

	void print(I it) const
	{
		if (!it)
			return;
		cout << '(' << *it << ',';
		print(++it);
		cout << ',';
		print(it++);
		cout << ")";
	}
};

#endif