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

#include "binordtree.cpp"
#include "AVLtree.cpp"
#include <cmath>

void simpleTree()
{
	BinTree<> t1,t2,t3;
	t1.createTree(1, t2, t3);
	t1.print();
}

void createFullTree(BinTree<>& t, int n, int l) {
	if (l <= n)
	{
		BinTree<> lt, rt;
		createFullTree(lt, n, l+1);
		createFullTree(rt, n, l+1);
		t.createTree(l, lt, rt);
	}
}

void fullTree(int n)
{
	BinTree<> t;
	createFullTree(t, n, 1);
	t.print();
}

int depth(BinTree<>::I it)
{
	if (!it)
		return 0;
	return 1 + max(depth(++it), depth(it++));
}

void depthTree()
{
	BinTree<> t;
	createFullTree(t, 4, 1);
	cout << depth(t.iterator()) << endl;
}

template <typename T>
bool equal(BinTreeIterator<T> it1, BinTreeIterator<T> it2)
{
	if (!it1 && !it2)
		return true;
	if (!it1 || !it2)
		return false;
	if (*it1 != *it2)
		return false;
	return equal(++it1, ++it2) && equal(it1++, it2++);
}

void equalTrees()
{
	BinTree<> t1, t2;
	createFullTree(t1, 4, 1);
	createFullTree(t2, 3, 1);
	cout << "Дърветата";
	if (!equal(t1.iterator(), t2.iterator()))
	{
		cout << " НЕ";
	}
	cout << " са равни" << endl;
}

// <expr> ::= 0-9 | (<expr><op><expr>)
// <op>   ::= + | - | * | /

void createExprTree(BinTree<char>& t, char const*& s)
{
	BinTree<char> lt, rt;
	if (*s >= '0' && *s <= '9')
	{
		t.createTree(*s++, lt, rt);
	} else
	{
		// *s == '('
		createExprTree(lt, ++s);
		// *s е операция
		char op = *s;
		createExprTree(rt, ++s);
		// *s == ')'
		s++;
		t.createTree(op, lt, rt);

	}
}

int evaluate(BinTreeIterator<char> it)
{
	if (*it >= '0' && *it <= '9')
		return *it - '0';
	int lv = evaluate(++it);
	int rv = evaluate(it++);
	switch (*it)
	{
	case '+':return lv + rv;
	case '-':return lv - rv;
	case '*':return lv * rv;
	case '/':return lv / rv;
	}
	return 0;
}

void exprTree()
{
	const int MAX = 100;
	char s[MAX];
	cin.getline(s, MAX);
	BinTree<char> t;
	char const* p = s;
	createExprTree(t, p);
	t.print();
	cout << evaluate(t.iterator()) << endl;
}

void testBinOrdTree()
{
	BinOrdTree<> bt;
	bt.insert(3, 30);
	bt.insert(1, 10);
	bt.insert(5, 50);
	bt.insert(2, 20);
	bt.insert(4, 40);
	cout << *(bt.search(3)) << endl;
	if (!bt.search(7))
		cout << "7 не е в дървото" << endl;
	cout << "Преди изтриването" << endl;
	bt.print();cout << endl;
	cout << "Опит за изтриване: " << bt.remove(3) << endl;
	cout << "След изтриването на 3" << endl;
	bt.print();cout << endl;
	for(int i=1;i<=5;i++)
	{
		bt.remove(i);
		cout << "След изтриването на " << i << endl;
		bt.print();cout << endl;
	}
	for(int i=1;i<=10;i++)
		bt.insert(i, i*10);
	bt.print();cout << endl;
}

void generate(BinTree<>& t, int* a, int n)
{
	if (n == 0)
		return;
	int mid = n / 2;
	BinTree<> lt, rt;
	generate(lt, a, mid);
	generate(rt, a + mid + 1, n - (mid + 1));
	t.createTree(a[mid], lt, rt);
}

void generatePBT()
{
	const int MAX = 10;
	int a[MAX];
	for(int i = 1; i<= MAX; i++)
		a[i-1] = i;
	BinTree<> t;
	generate(t, a, MAX);
	t.print();
}

void testAVLTree()
{
	AVLTree<> t;
	for(int i = 1; i <= 10; i++)
		t.insert(i, i*i);
	t.print();
}

/*
 * ([4,16,1],
 * 		([2,4,0],([1,1,0],,),([3,9,0],,)),
 * 		([8,64,0],
 * 			([6,36,0],([5,25,0],,),([7,49,0],,)),
 * 			([9,81,1],,([10,100,0],,))))
 */

int main()
{
//	simpleTree();
//	fullTree(4);
//	depthTree();
//	equalTrees();
//	exprTree();
//	testBinOrdTree();
//	generatePBT();
	testAVLTree();
}