/*
 * 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) {
		while ((*n)->left != NULL)
			n = &((*n)->left);
		return n;
	}
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) {
		// ако дървото е празно
		if (BinaryTree<T>::rootNode == NULL) {
			// правим ново дърво с единствен елемент x
			BinaryTree<T>::rootNode = new node<T>(x);
			return true;
		}
		node<T>* n = BinaryTree<T>::rootNode;
		while (n->inf != x) {
			if (x < n->inf) {
				// трябва да завием наляво
				if (n->left == NULL) {
					// ако няма нищо вляво, поставяме там новия елемент
					n->left = new node<T>(x);
					return true;
				}
				n = n->left;
			}
			else {
				// трябва да завием наляво
				if (n->right == NULL) {
					// ако няма нищо вдясно, поставяме там новия елемент
					n->right = new node<T>(x);
					return true;
				}
				n = n->right;
			}
		}
		// n->inf == x
		return false;
	}
	*/

	/*
	 * не работи, понеже it.p не е псевдоним!
	bool insert(T const& x) {
		I it = search(x);
		if (it)
			return false;
		it.p = new node<T>(x);
		return true;
	}
	*/

	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;
	}
};