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

// define a estrutura do no
struct _no {
  struct _no *anterior;
  char nome[40];
  char telefone[15];
  struct _no *proximo;
};

typedef struct _no No;

// define um ponteiro para o no raiz
No *Raiz=NULL;

// define um ponteiro para o ultimo no
No *Ultimo=NULL;

void Insere(char *nome, char *telefone) {
  No *Atual;
  No *NoAnterior;
  No *NoPosterior;
  No *NovoNo;

  // verifica se o nó raiz é nulo, que é o caso quando a lista está vazia.
  // Se for, cria nó raiz com os dados fornecidos e faz o último nó
  // coincidir com ele
  if (Raiz==NULL) {
    Raiz = (No *)malloc(sizeof(No));
    strcpy (Raiz->nome,nome);
    strcpy (Raiz->telefone,telefone);
    Raiz->proximo = NULL;
    Raiz->anterior = NULL;
    Ultimo = Raiz;
  }
  else {  // se já houver raiz

    // percorre a lista duplamente encadeada, comecando da raiz.
    // Inicialmente, não há nó anterior
    NoAnterior = NULL;
    Atual = Raiz;
    while (Atual!=NULL) {
      if (strcmp(Atual->nome,nome)>=0) break; // se o nó atual é
                                              // lexicograficamente superior,
					      // pára
      else {
	NoAnterior = Atual;
	Atual = Atual->proximo;
      }
    }

    if (Atual != NULL) // só faz a comparação abaixo se existe o nó Atual
      if (strcmp(Atual->nome,nome)==0) {
          printf ("Nome já existente!\n");
 	  return;
    }
    
    // agora, iremos inserir o novo nó entre o nó atual e o nó anterior
    NoPosterior = Atual;
    
    // aloca memória para o novo nó
    NovoNo = (No *)malloc(sizeof(No));

    // coloca dados no nó a ser inserido
    strcpy (NovoNo->nome,nome);
    strcpy (NovoNo->telefone,telefone);

    // atualiza ponteiros do novo nó
    NovoNo->proximo = NoPosterior;
    NovoNo->anterior = NoAnterior;
    
    // atualiza ponteiros dos nós vizinhos
    if (NoAnterior != NULL)
        NoAnterior->proximo = NovoNo;
    if (NoPosterior != NULL)
	NoPosterior->anterior = NovoNo;
    
    // verifica se o novo nó foi inserido no início ou no fim da lista
    // se foi, atualiza referências
    if (NovoNo->anterior == NULL)
	Raiz = NovoNo;
    if (NovoNo->proximo == NULL)
	Ultimo = NovoNo;
  }
}

void Busca(char *nome) {
  No *Atual;
 
  // percorre a lista duplamente encadeada desde a raiz
  Atual = Raiz;
  while (Atual!=NULL) {
    // verifica se já encontrei ou já passei do nome procurado
    if (strcmp(Atual->nome,nome)>=0)  break;
    else    // se ainda não passou
      Atual = Atual->proximo;
  }
 
  // verifica se o nó atual é mesmo o nó procurado
  if (Atual != NULL)
    if (strcmp(Atual->nome,nome)==0) {
      printf ("Telefone: %s\n",Atual->telefone);
      return;
  }
  
  // se não achou, avisa
  printf ("Nao achei!\n");
}

void Lista() {
  No *Atual;

  printf ("\n");
  // percorre a lista duplamente encadeada desde a raiz
  Atual = Raiz;
  while (Atual!=NULL) {
    printf ("Nome: %s\n",Atual->nome);
    printf ("Telefone: %s\n\n",Atual->telefone);
    Atual = Atual->proximo;
  }
}

void ListaReversa() {
  No *Atual;
  printf ("\n");
  // percorre a lista duplamente encadeada, começando pelo último 
  Atual = Ultimo;
  while (Atual!=NULL) {
    printf ("Nome: %s\n",Atual->nome);
    printf ("Telefone: %s\n\n",Atual->telefone);
    Atual = Atual->anterior;
  }
}
  

void Deleta(char *nome) {
  No *Atual;
  No *Anterior=NULL;
  No *Posterior;
  char *nomeatual;

  // primeiro, percorre a lista duplamente encadeada desde a raiz
  Atual = Raiz;
  while (Atual!=NULL) {
    // verifica se já encontrei ou já passei do nome procurado
    if (strcmp(Atual->nome,nome)>=0) break;
    else  {  // se ainda não passou
      Anterior = Atual;
      Atual = Atual->proximo;
    }
  }

  if (Atual!=NULL)
    Posterior = Atual->proximo;
	  
  // verifica se o nó atual é mesmo o nó procurado
  if (Atual != NULL)
    if (strcmp(Atual->nome,nome)==0) {  // se for, deleta
      // faz com que o nó subsequente ao atual seja o subsequente ao nó
      // anterior para manter a integridade da lista
      if (Atual != Raiz)
	  Anterior->proximo = Atual->proximo;
      else  // se o no atual é a raiz, atualizo a referência para a raiz
	  Raiz = Atual->proximo;
      // faz com que a referência para o nó anterior do próximo nó seja
      // o nó anterior ao que será deletado, para manter a integridade
      if (Atual != Ultimo)
	  Posterior->anterior = Anterior;
      else  // se o nó atual é o último, atualiza a referência para o último
	  Ultimo = Anterior;
      // agora, o nó atual MÓÓÓRRÉU
      free(Atual);
      printf ("Nome deletado!\n\n");
      return;
  }

  printf("Nao achei!\n");
}


main () {
int opcao;
char nome[40];
char telefone[15];


do {
  printf("\nLista de telefones:\n\n");
  printf("1 - Buscar por nome\n");
  printf("2 - Listar em ordem alfabetica\n");
  printf("3 - Listar em ordem reversa\n");
  printf("4 - Inserir\n");
  printf("5 - Deletar\n");
  printf("0 - Sair\n\n");
  printf("Opcao: ");
  scanf("%d",&opcao);

  if (opcao == 1 || opcao == 4 || opcao == 5) {
    printf("\nDigite nome: ");
    scanf("%s",nome);
  }

  switch (opcao) {
    case 1: Busca(nome); break;
    case 2: Lista(); break;
    case 3: ListaReversa(); break;
    case 4: printf ("Digite telefone: ");
	    scanf ("%s",telefone);
	    Insere(nome,telefone);
	    break;
    case 5: Deleta(nome);
  }
} while (opcao != 0);
	 
}