/*
 * binary_tree.cpp
 *
 *  Created on: 28.11.2013
 *      Author: trifon
 */

#ifndef __BINARY_TREE
#define __BINARY_TREE

#include <cstddef>
#include <iostream>
#include "tree.h"


using namespace std;

template <typename T>
class BinaryTree;

template <typename T>
struct node {
	node(T const& _inf, node<T>* _left = NULL,
						node<T>* _right = NULL) :
			inf(_inf), left(_left), right(_right) {}
	T inf;
	node<T> *left, *right;
};



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

	BinaryTreeIterator(BinaryTreeIterator<T> const& bti)
		: p(bti.p) {}

	// it++;
	// преместване надясно, копие
	BinaryTreeIterator operator++(int) {
		if (p != NULL)
			return BinaryTreeIterator(p->right);
		return *this;
	}

	// ++it;
	// преместване наляво, копие
	BinaryTreeIterator operator++() {
		if (p != NULL)
			return BinaryTreeIterator(p->left);
		return *this;
	}

	// if (it) { ... } else { ... }
	// проверка за валидност
	operator bool() const {
		return p != NULL;
	}

	// cout << l.getElementAt(it);
	// cout << *it;
	// *it = 3;
	// получаване и установяване на стойност през итератор
	T& operator*() const {
		return p->inf;
	}

	// сравняване на итератори
	bool operator==(TreeIterator<T> const& it) const {
		BinaryTreeIterator const& btit = (BinaryTreeIterator const&)it;
		return p == btit.p;
	}

};

template <typename T>
class BinaryTree : public Tree<T, BinaryTreeIterator<T> > {
protected:
	node<T> *rootNode;

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

	node<T>* copyNode(node<T> *n) {
		if (n == NULL)
			return NULL;
		return new node<T>(n->inf,
				 		   copyNode(n->left),
						   copyNode(n->right));
	}

	ostream& printNode(ostream& os, node<T>* n) const {
		if (n == NULL) {
			os << '#';
			return os;
		}
		os << '(' << n->inf << ' ';
		printNode(os, n->left) << ' ';
		return printNode(os, n->right) << ')';
	}

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

	void adoptLeft(node<T> *&child) {
		adopt(child, rootNode->left);
	}

	void adoptRight(node<T> *&child) {
		adopt(child, rootNode->right);
	}

public:
	typedef BinaryTreeIterator<T> I;

	BinaryTree() : rootNode(NULL) {}

	BinaryTree(T const& x) : rootNode(new node<T>(x)) {}

	BinaryTree(T const& x, BinaryTree& l,
						   BinaryTree& r) {
		rootNode = new node<T>(x);
		adoptLeft(l.rootNode);
		adoptRight(r.rootNode);
	}

	BinaryTree(BinaryTree const& bt) {
		rootNode = copyNode(bt.rootNode);
	}

	BinaryTree& operator=(BinaryTree const& bt) {
		if (&bt != this) {
			deleteNode(rootNode);
			rootNode = copyNode(bt.rootNode);
		}
		return *this;
	}

	~BinaryTree() {
		deleteNode(rootNode);
	}

	ostream& print(ostream& os) const {
		return printNode(os, rootNode);
	}

	T root() const {
		if (rootNode == NULL)
			return T();
		return rootNode->inf;
	}

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

};

template <typename T>
ostream& operator<<(ostream& os, BinaryTree<T> const& bt) {
	return bt.print(os);
}



#endif