/*
 * ordered_tree.cpp
 *
 *  Created on: 05.12.2013
 *      Author: trifon
 */

#include "binary_tree.cpp"

template <typename T>
class OrderedTree;

/**
 * Итератор, който позволява модифициране на структурата на дървото
 * Реализация чрез двоен указател
 */
template <typename T>
class BinaryTreeModifyingIterator {
private:
	node<T>** p;

	// връща псевдоним на указателя, който представя итераторът
	node<T>*& operator~() {
		return *p;
	}

	friend class OrderedTree<T>;

public:
	BinaryTreeModifyingIterator(node<T>** _p = NULL) : p(_p) {}

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

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

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

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

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


template <typename T>
class OrderedTree : public BinaryTree<T>,
					public SearchTree<T, BinaryTreeIterator<T> >
{
private:

	typedef BinaryTreeIterator<T> I;
	typedef BinaryTreeModifyingIterator<T> MI;

	// намира модифициращ итератор към x или там, където би трябвало да бъде x
	MI findNode(T const& x) {
		MI it = MI(&this->rootNode);
		while (it && *it != x)
			if (x < *it)
				it = ++it;
			else
				it = it++;
		// ДА - *it == x
		// НЕ - !it
		return it;
	}

	// намира модифициращ итератор към най-левия (най-малкия) елемент
	MI findLeftmostNode(MI it) {
		while (++it)
			it = ++it;
		return it;
	}
public:

	I search(T const& x) const {
		I it = BinaryTree<T>::iterator();
		while (it && *it != x)
			if (x < *it)
				it = ++it;
			else
				it = it++;
		// ДА - *it == x
		// НЕ - !it
		return it;
	}

	bool insert(T const& x) {
		// намираме модифициращ итератор към мястото, където би трябвало да е x
		MI it = findNode(x);
		if (!it) {
			// модифицираме дървото, като поставяме нова клетка на мястото на итератора
			~it = new node<T>(x);
			return true;
		}
		return false;
	}

	bool remove(T const& x) {
		// намираме модифициращ итератор към x
		MI it = findNode(x);
		if (!it)
			return false;
		// it && *it == x

		// запомняме кутията, която ще трием
		node<T>* toDelete = ~it;
		if (!++it)
			// ако нямаме ляво поддърво, модифицираме дървото, като закачаме дясното поддърво на мястото на x
			~it = ~(it++);
		else
		if (!it++)
			// ако нямаме дясно поддърво, модифицираме дървото, като закачаме лявото поддърво на мястото на x
			~it = ~(++it);
		else {
			// ++it && it++
			// имаме ляво и дясно поддърво
			// намираме модифициращ итератор към най-малкия елемент m в дясното поддърво
			MI mit = findLeftmostNode(it++);
			// запомняме дясното му поддърво, понеже ще ни трябва после
			node<T>* mr = ~(mit++);
			// правим m новия корен като копираме левите и десните указатели
			~(++mit) = ~(++it);
			~(mit++) = ~(it++);
			~it = ~mit;
			// където преди беше m, закачаме бившото му дясно поддърво
			~mit = mr;
		}
		delete toDelete;
		return true;
	}
};