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

#include "binary_tree.cpp"

template <typename T>
class OrderedTree : public BinaryTree<T>,
					public SearchTree<T, BinaryTreeIterator<T> >
{
private:
	// намира псевдоним на указателя към тройната кутия, съдържаща x
	node<T>*& findNode(T const& x) {
		node<T>** n = &this->rootNode;
		while (*n != NULL && (*n)->inf != x)
			if (x < (*n)->inf)
				n = &(*n)->left;
			else
				n = &(*n)->right;
		// *n == NULL || (*n)->inf == x
		return *n;
	}

	// намира псевдоним на указателя към най-левия (т.е. най-малкия) възел
	node<T>*& findLeftmostNode(node<T>*& n) {
		node<T>** nn = &n;
		while ((*nn)->left != NULL)
			nn = &(*nn)->left;
		return *nn;
	}
public:

	typedef BinaryTreeIterator<T> I;

	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
		node<T>*& n = findNode(x);
		if (n == NULL) {
			// създаваме нова клетка
			n = new node<T>(x);
			return true;
		}
		return false;
	}

	bool remove(T const& x) {
		// намираме псевдоним на указателя, който сочи към x
		node<T>*& n = findNode(x);
		if (n == NULL)
			return false;
		// n != NULL
		// n->inf == x
		// запомняме кутията, която ще трием
		node<T>* toDelete = n;
		if (n->left == NULL)
			// ако нямаме ляво поддърво, просто закачаме дясното на мястото на изтритата кутия
			n = n->right;
		else
		if (n->right == NULL)
			// ако нямаме дясно поддърво, просто закачаме лявото на мястото на изтритата кутия
			n = n->left;
		else {
			// имаме и ляво и дясно поддърво
			// намираме псевдоним към указателя към кутията на най-малкия елемент m в дясното поддърво
			node<T>*& m = findLeftmostNode(n->right);
			// запомняме дясното му поддърво, понеже ще ни трябва после
			node<T>* mr = m->right;
			// правим m новия корен като копираме левите и десните указатели
			m->left = n->left;
			m->right = n->right;
			n = m;
			// където преди беше m, закачаме бившото му дясно поддърво
			m = mr;
		}
		// накрая изтриваме кутията с x
		delete toDelete;
		return true;
	}
};