#ifndef ARVORE_BINARIA_LIB_H
#define ARVORE_BINARIA_LIB_H

#include <stdlib.h>

/**
 *    Esta classe é totalmente declarada aqui pois precisa ser template porque
 * senão não se consegue comparar *void == *void, para determinar a posição de
 * inserção. Os códigos das funões templates têm que ser declarados no .h 
 * OBS.: t_class deve ser capaz de fazer ao menos as operações: ==, !=, <=, >=, <, >
 *       portanto não use 'char *' e sim 'String' (feita pelo Gustavo)
 */

template<class t_class> class Arvore_Binaria{
public:
  /**
   * Construtor:
   */
  Arvore_Binaria(t_class valor) {
    Muda_Valor(valor);
    Aterra_Ponteiros();
  }

  ~Arvore_Binaria() {    
    if (Esquerda() != NULL)
      delete Esquerda();
    if (Direita() != NULL)
      delete Direita();
  }


  /**
   * Esquerda: retorna filho esquerdo
   *@return filho esquerdo
   */
  Arvore_Binaria<t_class> *Esquerda() {
    return esq;
  }

  /**
   * Direita: retorna filho direita
   *@return filho direito
   */
  Arvore_Binaria<t_class> *Direita() {
    return dir;
  }


  /**
   * Valor: retorna valor deste nó
   *@return valor deste nó
   */
  t_class &Valor() {    
    return valor;
  }


  /**
   * Insere: insere valor na árvore de busca. Se repetido, será inserido à direita
   *@param valor é o valor que deseja inserir na árvore. Note que '*valor
   */
  void Insere(t_class valor) {
    if (valor < Valor()) {
      if (Esquerda() == NULL)
	Muda_Esquerda(new Arvore_Binaria<t_class>(valor));
      else
	Esquerda()->Insere(valor);
    } else {
      if (Direita() == NULL)
	Muda_Direita(new Arvore_Binaria<t_class>(valor));
      else
	Direita()->Insere(valor);
    }
  }

  /**
   * Folha: retorna se é folha ou não
   *@return true = folha, false = não é folha
   */
  bool Folha() {
    return ((Direita()==NULL) && (Esquerda()==NULL));
  }

  
  /**
   * Muda_Esquerda: muda filho esquerdo
   *@param arvore apontador para árvore a ser colocada como filho esquerdo
   *ATENÇÃO: isto pode criar uma árvore errada! Saiba o que você está fazendo
   */
  void Muda_Esquerda(Arvore_Binaria<t_class> *arvore) {
    esq = arvore;
  }

  /**
   * Muda_Direita: muda filho direito
   *@param arvore apontador para árvore a ser colocada como filho direito
   *ATENÇÃO: isto pode criar uma árvore errada! Saiba o que você está fazendo
   */
  void Muda_Direita(Arvore_Binaria<t_class> *arvore) {
    dir = arvore;
  }

  /**
   * Procura: procura pelo nó que contenha o valor
   *@param valor a ser procurado
   *@return apontador nó da árvore resultante, NULL caso não achou
   */
  Arvore_Binaria<t_class> *Procura(t_class valor) {
    Arvore_Binaria<t_class> *aux = this;
    while (aux != NULL)
      if (valor < aux->Valor()) {
	aux = aux->Esquerda();
      } else if (valor > aux->Valor()) {
	aux = aux->Direita();
      } else
	return aux;
    return NULL;
  }

  /**
   * Remove: remove este nó da árvore e retorna a arvore resultante
   *@return a árvore sem este nó
   */
  Arvore_Binaria<t_class> *Remove() {
    Arvore_Binaria<t_class> *tmp, *tmp2, *nova;
    if (Folha()) {
      return NULL;  
    } else {
      if ((Esquerda() != NULL) && (Direita() !=NULL)) {
	tmp = Direita();
	if (tmp->Esquerda() != NULL) {
	  while (tmp->Esquerda()->Esquerda() != NULL) 
	    tmp = tmp->Esquerda();
	  nova = new Arvore_Binaria<t_class>(tmp->Esquerda()->Valor());
	  
	  tmp2 = tmp->Esquerda();
	  tmp->Muda_Esquerda(tmp->Esquerda()->Direita());
	  tmp2->Remove();
	  delete tmp2;	  
	  nova->Muda_Esquerda(Esquerda());
	  nova->Muda_Direita(Direita());
	  Aterra_Ponteiros();
	  return nova;
	} else {
	  tmp->Muda_Esquerda(Esquerda());
	  Aterra_Ponteiros();
	  return tmp;
	} 
      } else {
	if (Esquerda() != NULL) {
	  tmp = Esquerda();
	  Aterra_Ponteiros();	  
	  return tmp;
	} else {
	  tmp = Direita();
	  Aterra_Ponteiros();
	  return tmp;
	}
      }
    }
  }

  /**
   * Maior_Valor: Retorna o maior valor da árvore
   *@return maior valor da árvore
   */ 
  t_class Maior_Valor() {
    Arvore_Binaria<t_class> *aux;
    aux = this;
    
    while (aux->Direita() != NULL) 
      aux = aux->Direita();

    return aux->Valor();
  }
  
  /**
   * Maior_Valor: Retorna o maior valor da árvore
   *@return maior valor da árvore
   */
  t_class Menor_Valor() {
    Arvore_Binaria<t_class> *aux;
    aux = this;
    
    while (aux->Esquerda() != NULL) 
      aux = aux->Esquerda();

    return aux->Valor();
  }


  /**
   * Muda_Valor: muda o valor do nó atual
   *@param valor valor a ser adicionado
   *OBS: isso pode trazer danos à estrutura da árvore. Lembre-se Valores menores à esquerda, Maiores ou Iguais à direita
   */
  void Muda_Valor(t_class valor) {
    this->valor = valor;
  }



protected:
  t_class valor;
  Arvore_Binaria<t_class> *esq, *dir;

  
  void Aterra_Ponteiros() {
    Muda_Esquerda(NULL);
    Muda_Direita(NULL);
  }

};

#endif