#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct cliente
{
   char * nome;
   int telefone;
   int chave;
   struct cliente * dir;   //right
   struct cliente * esq;   //left
} Cliente;

Cliente * buscar (Cliente * raiz, int k)    // fetch the node
{
   while (raiz != NULL && raiz->chave != k)
   {
      if (raiz->chave > k)
      {
         raiz = raiz->esq;
      }
      else
      {
         raiz = raiz->dir;
      }
   }
   return raiz;
}

 void imprime_in (Cliente * no, FILE * arquivo)
 {
    int altura;
    if(no != NULL)
    {
        imprime_in (no->esq, arquivo);
        fprintf (arquivo, "Altura = %d, Nome: %s, Telefone %d\n", altura, no->nome, no->telefone);
        imprime_in (no->dir, arquivo);
    }
 }

 void imprime_pre (Cliente * no, FILE * arquivo)
 {
    int altura;
    if(no != NULL)
    {
        fprintf (arquivo, "Altura = %d, Nome: %s, Telefone %d\n", altura, no->nome, no->telefone);
        imprime_pre (no->esq, arquivo);
        imprime_pre (no->dir, arquivo);
    }
 }

 void imprime_pos (Cliente * no, FILE * arquivo)
 {
    int altura;
    if(no != NULL)
    {
        imprime_pos (no->esq, arquivo);
        imprime_pos (no->dir, arquivo);
        fprintf (arquivo, "Altura = %d, Nome: %s, Telefone %d\n", altura, no->nome, no->telefone);
    }
 }

Cliente * remover (Cliente * raiz, int chave)    // removes a node
{
   Cliente * p,* p2;
   if (raiz == NULL)
   {
       return raiz;
   }
   if(raiz->chave == chave)
   {
       if (raiz->esq == raiz->dir)
       {
           free (raiz);
           return NULL;
       }
       else if (raiz->esq == NULL)
       {
           p = raiz->dir;
           free (raiz);
           return p;
       }
       else if (raiz->dir == NULL)
       {
           p = raiz->esq;
           free (raiz);
           return p;
       }
       else
       {
           p2 = raiz->dir;
           p = raiz->dir;
           while (p->esq)
           {
               p = p->esq;
           }
           p->esq = raiz->esq;
           free (raiz);
           return p2;
       }
   }
   if (raiz->chave < chave)
   {
       raiz->dir = remover (raiz->dir, chave);
   }
   else
   {
       raiz->esq = remover (raiz->esq, chave);
   }

   return raiz;
}

Cliente * insere (Cliente * r, Cliente * novo)   // includes a new node
{
   Cliente *f, *p;
   if (r == NULL)
   {
       return novo;
   }
   f = r;
   while (f != NULL)
   {
      p = f;
      if (f->chave > novo->chave)
      {
          f = f->esq;
      }
      else
      {
          f = f->dir;
      }
   }
   if (p->chave > novo->chave)
   {
       p->esq = novo;
   }
   else
   {
       p->dir = novo;
   }
   return r;
}

int main()
{
   FILE * fin = fopen ("L1Q3.in", "r");
   FILE * fout = fopen ("L1Q3.out", "w");
   char * str = (char *) malloc (31 * sizeof (char));
   Cliente * aux;
   Cliente * arvore;
   int para = 0;
   int chave;
   int i = 1;
   int stop;
   int teste;
   if (fscanf (fin, "%s", str) == EOF)
   {
       para++;
   }
   while (para == 0)
   {

       fprintf (fout, "Conjunto #%d\n", i);
       arvore = NULL;
       stop = 0;
       teste = 0;
       do {
       if (teste != 0)
       {
           fscanf (fin, "%s", str);
       }
       if (strcmp (str, "Inserir") == 0)
       {
           aux = (Cliente *) malloc (1 * sizeof (Cliente));
           aux->nome = (char *) malloc (31 * sizeof (char));
           aux->esq = NULL;
           aux->dir = NULL;
           fscanf (fin, "%s", aux->nome);
           fscanf (fin, "%d", &aux->telefone);
           fscanf (fin, "%d", &aux->chave);
           arvore = insere (arvore, aux);
           fprintf (fout, "Cliente %s cadastrado\n", aux->nome);
           //printf ("Cliente %s cadastrado\n", aux->nome);
           //printf ("%s\n", arvore->nome);
           free (aux->nome);
           free (aux);
           aux = NULL;
       }
       else if (strcmp (str, "Remover") == 0)
       {
           fscanf (fin, "%d", &chave);
          // printf ("O Programa vai remover o no de chave %d\n", chave);
           aux = buscar (arvore, chave);
           fprintf (fout, "Cliente %s removido\n", aux->nome);
          // printf ("Cliente %s removido\n", aux->nome);
           arvore = remover (arvore, chave);
           free (aux->nome);
           free (aux);
       }
       else if (strcmp (str, "Buscar") == 0)
       {
           fscanf (fin, "%d", &chave);
           aux = buscar (arvore, chave);
           if (aux == NULL)
           {
               fprintf (fout, "Cliente nao encontrado\n");
           //    printf ("Cliente nao encontrado\n");
           }
           else
           {
               fprintf (fout, "Nome: %s, Telefone  %d\n", aux->nome, aux->telefone);
             //  printf ("Nome: %s, Telefone  %d\n", aux->nome, aux->telefone);
           }
           free (aux->nome);
           free (aux);
       }
       else if (strcmp (str, "Imprimir") == 0)
       {
           fscanf (fin, "%s", str);
           if (strcmp (str, "pre") == 0)
           {
               fprintf (fout, "Visita pre\n");
               imprime_pre (arvore, fout);
           }
           else if (strcmp (str, "in") == 0)
           {
               fprintf (fout, "Visita in\n");
               imprime_in (arvore, fout);
           }
           else if (strcmp (str, "pos") == 0)
           {
               fprintf (fout, "Visita pos\n");
               imprime_pos (arvore, fout);
           }
       }
       else if (strcmp (str, "Fim") == 0)
       {
           stop++;
       }
       teste++;
       } while (stop == 0);
       if (fscanf (fin, "%s", str) == EOF)
       {
           para++;
       }
       free (arvore);
       i++;
   }

   return 0;
}