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


#include "tree.cpp"

template <typename K, typename V>
struct Pair
{
	K key;
	V value;
};

template <typename K, typename V>
ostream& operator<<(ostream& os, Pair<K,V> const& pair)
{
	os << '[' << pair.key << ',' << pair.value << ']';
	return os;
}

template <typename K=int, typename V=int>
class BinOrdTree : public BinTree<Pair<K, V> >
{
	typedef Pair<K,V> T;
private:
	void createTree(T const&, BinTree<T >&, BinTree<T >& ) {}

	node<T>* minTree(node<T>*& n)
	{
		node<T>** p = &n;
		while ((*p)->left != NULL)
		{
			p = &((*p)->left);
		}
		// (*p)->left == NULL
		node<T>* result = *p;
		*p = (*p)->right;
		return result;
	}

	node<T>** findNode(K const& key, node<T>*& start)
	{
		node<T>** n = &start;
		while(*n && (*n)->inf.key != key)
		{
			if (key < (*n)->inf.key)
				n = &((*n)->left);
			else
				n = &((*n)->right);
		}
		// *n == NULL || *n->inf.key == key
		return n;
	}


public:
	V* search(K const& key) const
	{
		BinTreeIterator<T> it = this->iterator();
		while (it && (*it).key != key)
		{
			if (key < (*it).key)
				it = ++it;
			else
				it = it++;
		}
		// !it || *it.key == key
		if (!it)
			return NULL;
		return &((*it).value);
	}

	bool insert(K const& key, V const& value)
	{
		node<T >** n = findNode(key, this->root);
		if (*n == NULL)
		{
			*n = new node<T>;
			T pair = { key, value };
			(*n)->inf = pair;
			(*n)->left = (*n)->right = NULL;
			return true;
		}
		return false;
	}

	bool remove(K const& key)
	{
		node<T>** n = findNode(key, this->root);
		if (*n == NULL)
			return false;
		node<T>* p = *n;
		if ((*n)->left == NULL)
			*n = (*n)->right;
		else
		if ((*n)->right == NULL)
			*n = (*n)->left;
		else
		{
			// заменяме *n с най-малкия елемент
			node<T>* q = minTree((*n)->right);
			*n = q;
			q->left = p->left;
			q->right = p->right;
		}
		delete p;
		return true;
	}
};