/*
 * Instituto Superior de Engenharia do Porto
 *
 * Estruturas de Informação
 *
 * 2000/2001
 *
 * ------------------------------------------
 *
 * classe template Arvore Binária
 *
 * teste_myarvbin.cpp
 *
 */

#include <iostream>
using namespace std;


	struct S {
		char chave;
		int valor;
		S()
		{
			chave = '0';
			valor = 0;
		}
		S(char c, int v)
		{
			chave = c; valor = v;
		}
	};


char getChave(const S& o);
int getChave(int o);


#include "arvbinaria.h"
#include "arvbpesq.h"


/*
bool operator==(const S& o, char chave)
{
	if (o.chave == chave)
		return true;
	return false;
}

bool operator<(const S& o, char chave)
{
	if (o.chave < chave)
		return true;
	return false;
}

bool operator>(const S& o, char chave)
{
	if (o.chave > chave)
		return true;
	return false;
}
*/

char getChave(const S& o)
{
	return o.chave;
}

ostream& operator<<(ostream& output, const S& o)
{
	output << "(" << o.chave << ", " << o.valor << ")";
	return output;
}

int getChave(int o)
{
	return o;
}

void ordArv(list<int>& L)
{
	arvBpesq<int, int> arv;

	for(list<int>::iterator p = L.begin(); p != L.end(); p++)
		arv.inserir(*p);
	L.clear();
	arv.findall(L);
}

void teste_arvbin()
{
	/*

			A
		+---+---+
		B		C
	+---+---+   +---+
	D		E		F
		+---+
		G
	
	nº nos = 7  
	folhas = D, G, F = 3
	internos = A, B, C, E = 4
	*/

	arvBinaria<char> a;

	a.criaRaiz('A');
	a.criaNo('B', esquerda, 'A');
	a.criaNo('C', direita, 'A');
	a.criaNo('D', esquerda, 'B');
	a.criaNo('E', direita, 'B');
	a.criaNo('F', direita, 'C');
	a.criaNo('G', esquerda, 'E');

	cout << "Pre-Ordem" << endl;
	a.preOrdem();

	cout << "in-Ordem" << endl;
	a.ordemSimetrica();

	cout << "Pos-Ordem" << endl;
	a.postOrdem();

	cout << "num nós: " << a.numNos() << " folhas: " << a.numNosFolha() << " internos: " << a.numNosInternos() << endl;

	int n = 1;
	while (n >= 0)
	{
		cout << "introduza um nivel (-1 para acabar)" << endl;
		cin >> n;
		if (n >= 0)
			cout << "nós nivel " << n << " " << a.numNosNivel(n) << endl;
	}


	arvBinaria<char> b;
	b = a;

	b.postOrdem();
}

void teste_arvpesq()
{
	arvBpesq<char, S> a2;

/*
	a2.juntar_no('e', S('e', 5));
	a2.juntar_no('a', S('a', 1));
	a2.juntar_no('d', S('d', 4));
	a2.juntar_no('f', S('f', 6));
	a2.juntar_no('c', S('c', 3));
	a2.juntar_no('b', S('b', 2));
*/
	/*
	//a2.inserir(S('w', 9));
	a2.inserir(S('e', 5));
	a2.inserir(S('a', 1));
	a2.inserir(S('d', 4));
	a2.inserir(S('f', 6));
	a2.inserir(S('c', 3));
	a2.inserir(S('b', 2));
	*/
	arvBpesq<int, int> a3;
	a3.inserir(5);
	a3.inserir(1);
	a3.inserir(4);
	a3.inserir(6);
	a3.inserir(4);
	a3.inserir(3);
	a3.inserir(4);
	a3.inserir(2);


	cout << "ordem simétrica (arv. pesquisa" << endl;
	a3.ordemSimetrica();
	cout << endl;

	int x;
	a3.pesquisar_r(5, x);


	list<int> l2;
	a3.findall(0, l2);
	cout << l2.size();


	list<int> l;
	l.push_front(4);
	l.push_front(5);
	l.push_front(1);	
	l.push_front(7);
	l.push_front(3);
	l.push_front(2);

	ordArv(l);

	for(list<int>::iterator p = l.begin(); p != l.end(); p++)
		cout << *p;
}

void teste_miniteste()
{
	arvBinaria<char> a;

	a.criaRaiz('A');
	a.criaNo('B', esquerda, 'A');
	a.criaNo('C', direita, 'A');
	a.criaNo('D', esquerda, 'B');
	a.criaNo('E', direita, 'B');
	a.criaNo('F', direita, 'C');
	a.criaNo('G', esquerda, 'E');

	arvBinaria<char> b(a);

	//operator==
	if (a == b)
		cout << "sao iguais" << endl;
	else
		cout << "Nao sao iguais" << endl;

	//operator!=
	if (a != b)
		cout << "Nao sao iguais" << endl;
	else
		cout << "sao iguais" << endl;

	//operator+
	arvBinaria<char> a1;
	a1.criaRaiz('H');
	a1.criaNo('I', esquerda, 'H');
	a1.criaNo('E', direita, 'H');

	cout << endl;

	arvBinaria<char> c;
	c = a1 + b;
	c.ordemSimetrica();
	
	cout << endl;

	//operator*
	arvBinaria<char> a2;
	a2.criaRaiz('H');
	a2.criaNo('I', esquerda, 'H');
	a2.criaNo('E', direita, 'H');

	cout << endl;

	arvBinaria<char> d;
	d = a2 * b;
	d.ordemSimetrica();
}

void main()
{

	//teste_arvbin();

	//teste_arvpesq();

	teste_miniteste();


	cin.get();
}