#ifndef INDICE_ARVORE_BINARIA_H
#define INDICE_ARVORE_BINARIA_H

#include <arvore_binaria.h>
#include <indice.h>


template <class t_class1, class t_class2> 
class Indice_Arvore_Binaria : 
  public Indice<t_class1, t_class2, Arvore_Binaria<Elemento_Indice<t_class1, t_class2> > > {

public:
  Indice_Arvore_Binaria(const char* arquivo, 
			const char *campo, const char *referencia,
			TIPO tcampo, TIPO treferencia) :
    Indice<t_class1, t_class2, Arvore_Binaria<Elemento_Indice<t_class1, t_class2> > >(arquivo, 
										      campo, referencia,
										      tcampo, treferencia,"Arvore_Binaria") {     };
  
private:

  void Percorre_Estrutura_Escrevendo_Arquivo(FILE *fp) {
    Arvore_Binaria<Elemento_Indice<t_class1, t_class2> > *estr = estrutura;
    
    if (estr != NULL)
      Imprime_Registro_Arquivo(fp,estr);
      
  }


  void Imprime_Registro_Arquivo(FILE *fp, Arvore_Binaria<Elemento_Indice<t_class1, t_class2> > *estr) {
    if (estr != NULL) {
      String linha("");
      linha =  estr->Valor().chave;      
      linha += delimitador;
      linha += estr->Valor().referencia;
      linha += delimitador_linha;
      fprintf(fp,"%s",linha.Texto());
      if (estr->Esquerda() != NULL) 
	Imprime_Registro_Arquivo(fp,estr->Esquerda());
      if (estr->Direita() != NULL) 
	Imprime_Registro_Arquivo(fp,estr->Direita());
    }
  }

  bool Altera_Elemento(Elemento_Indice<t_class1, t_class2> elem, t_class2 referencia_nova) {
    if (estrutura == NULL)
      return false;
    else {
        Arvore_Binaria<Elemento_Indice<t_class1,t_class2> > *arvore = NULL;
      if ((arvore = estrutura->Procura(elem)) != NULL) {
	// OBS: A procura retora elemento com arvore->Valor().chave == elem.chave
	//   ainda temos que conferir se a referencia eh a mesma. Lembre-se: Filhos iguais 
	//   sempre `a direita
	while ((arvore != NULL) &&
	       (arvore->Valor().chave == elem.chave)) {
	  if (arvore->Valor().referencia == elem.referencia) {	    
	    elem.referencia = referencia_nova;
	    arvore->Muda_Valor(elem);
	    return true;
	  } else {
	    arvore = arvore->Direita();
	  }
	}       
      }
    }
    return false;
  }


  bool Remove_Elemento(Elemento_Indice<t_class1, t_class2> elem) {
    if (estrutura == NULL)
      return false;
    
    bool retorno = Remove_Elemento_Recursivo(&estrutura,elem);
    return retorno;
  }

  bool Remove_Elemento_Recursivo(Arvore_Binaria<Elemento_Indice<t_class1, t_class2> > **arv, Elemento_Indice<t_class1, t_class2> elemento) {
    Arvore_Binaria<Elemento_Indice<t_class1, t_class2> > *tmp;

    if ((arv == NULL) || (*arv == NULL)) {
      return false;
    } else {
      if (
	  (elemento.chave == (*arv)->Valor().chave) &&
 	  (elemento.referencia == (*arv)->Valor().referencia)
	  ) {
	tmp = (*arv)->Remove();
	delete (*arv);
	(*arv) = tmp;
	return true;
      } else {
	if (elemento < (*arv)->Valor()) {
	  bool retorno;
	  tmp = (*arv)->Esquerda();
	  retorno = Remove_Elemento_Recursivo(&tmp,elemento);
	  (*arv)->Muda_Esquerda(tmp);
	  return retorno;
	} else {
	  bool retorno;
	  tmp = (*arv)->Direita();
	  retorno = Remove_Elemento_Recursivo(&tmp,elemento);
	  (*arv)->Muda_Direita(tmp);
	  return retorno;
	}
      }
    }
  }
  


  void Insere_Elemento(Elemento_Indice<t_class1, t_class2> elem) {
    if (estrutura == NULL)
      estrutura = new  Arvore_Binaria<Elemento_Indice<t_class1, t_class2> >(elem);
    else
      estrutura->Insere(elem);
  }

};


#endif