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

// define a estrutura do no
struct _no {
  char nome[40];
  int numero;
  float popularidade;
  struct _no *anterior;
  struct _no *proximo;
};                      

typedef struct _no No;

// armazena o número de candidatos inscritos.
int NumCandidatos=0;

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

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

void Insere(char *nome, int numero, float popularidade) {
  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);
    Raiz->numero=numero;
    Raiz->popularidade=popularidade;
    Raiz->proximo = NULL;
    Raiz->anterior = NULL;
    Ultimo = Raiz;
    // incrementa o número de candidatos
    NumCandidatos++;
  }
  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);
    NovoNo->numero=numero;
    NovoNo->popularidade=popularidade;

    // 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;

    // incrementa o número de candidatos
    NumCandidatos++;
  }
}

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 ("Número: %d\n",Atual->numero);
      printf ("Popularidade: %g\%\n",Atual->popularidade);
      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 ("Número: %d\n",Atual->numero);
    printf ("Popularidade: %g\%\n\n",Atual->popularidade);
    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 ("Número: %d\n",Atual->numero);
    printf ("Popularidade: %g\%\n\n",Atual->popularidade);
    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");

      // decrementa o número de candidatos
      NumCandidatos--;
      return;
  }

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

// definição para a estrutura do vetor de ordenação
struct _candidato {
  char nome[40];
  int numero;
  float popularidade;
};

typedef struct _candidato candidato;

// função para trocar 2 candidatos de posição no vetor
void troca(candidato *c1, candidato *c2) {
  char tempnome[40];
  int tempnum;
  float temppop;

  strcpy(tempnome,c1->nome);
  tempnum=c1->numero;
  temppop=c1->popularidade;

  strcpy(c1->nome,c2->nome);
  c1->numero=c2->numero;
  c1->popularidade=c2->popularidade;

  strcpy(c2->nome,tempnome);
  c2->numero=tempnum;
  c2->popularidade=temppop;
}

// ordena os candidatos por número e lista-os
void ord_num() {
  candidato *candidatos;
  No *Atual;

  int i,j;
  
  // se não há nenhum candidato, não preciso fazer nada
  if (NumCandidatos==0) return;
  
  candidatos=(candidato *)malloc(NumCandidatos*sizeof(candidato));

  // copia a lista endadeada para o vetor, percorrendo-a do início ao
  // fim
  Atual=Raiz;
  i=0;
  while (Atual!=NULL) {
    strcpy(candidatos[i].nome,Atual->nome);
    candidatos[i].numero=Atual->numero;
    candidatos[i].popularidade=Atual->popularidade;
    i++;
    Atual=Atual->proximo;
  }

  // faz a ordenação por bolha 
  for(i=0;i<NumCandidatos;i++)
    for(j=i+1;j<NumCandidatos;j++)
      if (candidatos[i].numero>candidatos[j].numero)
	 troca(&candidatos[i],&candidatos[j]);

  // lista os candidatos já ordenados por número
  for (i=0;i<NumCandidatos;i++) {
    printf ("Nome: %s\n",candidatos[i].nome);
    printf ("Número: %d\n",candidatos[i].numero);
    printf ("Popularidade: %g\%\n\n",candidatos[i].popularidade);
  }
  free(candidatos);
}

/**********************************************************************
 * Funções para fazer a ordenação por heap                            *
 **********************************************************************/

// devolve o índice do filho esquerdo no no de indice i
int filho_esq(int i) {
  return 2*i;
}

// devolve o indice do filho direito do no de indice i
int filho_dir(int i) {
  return 2*i+1;
}

// efetua um push down no no de indice i, segundo a popularidade
void pushDown(int i,candidato *heap,int tam) {
  int ha_esq=0,ha_dir=0;

  if (filho_esq(i)<=tam) ha_esq=1;
  if (filho_dir(i)<=tam) ha_dir=1;

  if (ha_esq&&!ha_dir) {
    if (heap[i].popularidade<heap[filho_esq(i)].popularidade) {
       troca(&heap[filho_esq(i)],&heap[i]);
       pushDown(filho_esq(i),heap,tam);
    }
  }
  else
  if (ha_esq&&ha_dir) {
    if ((heap[i].popularidade<heap[filho_esq(i)].popularidade)
         ||(heap[i].popularidade<heap[filho_dir(i)].popularidade)) {
      if (heap[filho_esq(i)].popularidade>heap[filho_dir(i)].popularidade) {
	troca(&heap[filho_esq(i)],&heap[i]);
	i = filho_esq(i);
      }
      else {
	troca(&heap[filho_dir(i)],&heap[i]);
	i = filho_dir(i);
      }
      pushDown(i,heap,tam);
    }
  }
}

// funcao para fazer a montagem da heap
void montaHeap(candidato *heap,int tam) {
  int i;
  for (i=tam/2;i>=1;i--) {
    pushDown(i,heap,tam);
  }
}

// funcao para fazer a desmontagem da heap
void desmontaHeap(candidato *heap,int tam) {
  int i;
  int n=tam;
  for (i=1;i<=n;i++) {
    troca(&heap[1],&heap[tam]);
    tam--;
    pushDown(1,heap,tam);
  }
}

// heapSort: funcao que ordena uma lista de candidatos dada, chamando,
// em ordem, a rotina que monta a heap e a que efetua a desmontagem
void heapSort(candidato *lista,int tam) {
  montaHeap(lista,tam);
  desmontaHeap(lista,tam);
}

/*************************************************************************
 * Fim das funções para fazer ordenação por heap                         *
 *************************************************************************/

// função para ordenar os candidatos por popularidade e listá-los
void ord_pop() {
  candidato *candidatos;
  No *Atual;

  int i,j;
  
  // se não há nenhum candidato, não preciso fazer nada
  if (NumCandidatos==0) return;
  
  candidatos=(candidato *)malloc((NumCandidatos+1)*sizeof(candidato));

  // copia a lista endadeada para o vetor, percorrendo-a do início ao
  // fim
  Atual=Raiz;
  i=1;
  while (Atual!=NULL) {
    strcpy(candidatos[i].nome,Atual->nome);
    candidatos[i].numero=Atual->numero;
    candidatos[i].popularidade=Atual->popularidade;
    i++;
    Atual=Atual->proximo;
  }

  // faz a ordenação por heap 
  heapSort(candidatos,NumCandidatos);

  // lista os candidatos já ordenados por número
  for (i=1;i<=NumCandidatos;i++) {
    printf ("Nome: %s\n",candidatos[i].nome);
    printf ("Número: %d\n",candidatos[i].numero);
    printf ("Popularidade: %g\%\n\n",candidatos[i].popularidade);
  }

  free(candidatos);
}



main () {
int opcao;
char nome[40];
int numero;
float popularidade;

do {
  printf("\nCandidatos às eleições:\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("6 - Mostrar número de inscritos\n");
  printf("7 - Ordena por número\n");
  printf("8 - Ordena por popularidade\n");
  printf("0 - Sair\n\n");
  printf("Opcao: ");
  scanf("%d",&opcao);

  if (opcao == 1 || opcao == 4 || opcao == 5) {
    getchar();
    printf("\nDigite o nome do candidato: ");
    fgets(nome,225,stdin);
  }

  switch (opcao) {
    case 1: Busca(nome); break;
    case 2: Lista(); break;
    case 3: ListaReversa(); break;
    case 4: printf ("Digite o número: ");
	    scanf ("%d",&numero);
	    printf ("Digite a popularidade, em %: ");
	    scanf ("%f",&popularidade);
	    Insere(nome,numero,popularidade);
	    break;
    case 5: Deleta(nome); break;
    case 6: printf ("\nHá %d candidato(s) inscrito(s).\n\n",NumCandidatos);
	    break;
    case 7: ord_num(); break;
    case 8: ord_pop(); break;
  }
} while (opcao != 0);
	 
}