#include "heap.h"

#define pai(elemento) ((elemento)-1)/2
#define filhoesq(elemento) (2*(elemento) +1)
#define filhodir(elemento) (2*(elemento) +2)

#define testanull(elemento,funcao) if ( elemento == NULL) { comAviso(AVS1,funcao); return; }

/* ambas as funcoes sobe e desce sao muito utilizadas na 
   manipulacao de heap. Ambas as funcoes recebem um heap e
   um indice desse heap como parametros. A funcao sobe deve
   modificar a posicao do heap para cima, ate que ele esteja
   numa posicao "correta" (todos acima sendo menores do que 
   ele, todos a baixo sendo maiores do que ele). A funcao desce
   faz o contrario, diminuindo a autura do membro apontado
   pelo indice ate que ele esteja na posicao certa 
   (mas cuidado para nao estragar a estrutura do heap, heim?)
*/

void sobe(Heap *h, int index) {
  int tmp;
  void * tmp2;

  testanull(h,"sobe");

  /* Pai menor que Filho */
  if ( h->chave[pai(index)] > h->chave[index] ) {
    /* Troca chaves */
    tmp = h->chave[pai(index)];
    h->chave[pai(index)] = h->chave[index];
    h->chave[index] = tmp;
    /* Troca info */
    tmp2= h->info[pai(index)];
    h->info[pai(index)] = h->info[index];
    h->info[index] = tmp2;

    sobe(h,pai(index));
  }

  return;
}

void desce(Heap *h, int index) {
  int tmp;
  void * tmp2;
  int menor;
  testanull(h,"desce");

  if ( filhoesq(index) < h->n ) {
    menor = filhoesq(index);
    
    if ( (filhodir(index) < h->n) && (h->chave[filhoesq(index)] > h->chave[filhodir(index)]) ) 
      menor = filhodir(index);

    if ( h->chave[menor] < h->chave[index]) {
      /* Troca chaves */
      tmp = h->chave[menor];
      h->chave[menor] = h->chave[index];
      h->chave[index] = tmp;
      /* Troca infos */
      tmp2 = h->info[menor];
      h->info[menor] = h->info[index];
      h->info[index] = tmp2;
      
      desce(h,menor);
    }
  }

}


/* inicializa o contador de cheio do heap */
void CriaHeap (Heap *h) {       /* faz n=0 */
  h->n=0;
}

/* desinicializa o contador de cheio do heap */
void DestroiHeap (Heap *h) {     /* faz n=-1 */
  int i;
  for (i=0; i < h->n; i++)
    if (h->info[i] != NULL)
      free(h->info[i]);
  h->n=-1;
}


/* retorna 1 se vazio ou nao inicializado; */
/* ou 0 se nao vazio */
int VazioHeap (Heap *h) {
  if ((h == NULL) || (h->n < 1) || (h->n >= MAXTAMHEAP) )
    return 1;
  else 
    return 0;

  return 1;
}
 
/*
  insere um elemento em sua posicao apropriada do heap, retorna
  1 se deu certo ou 0 se deu algum tipo de pau
*/
 
int InsereOk (Heap *h, int chave, void *info) {
  if ((h == NULL) || (h->n < 0) || (h->n >= MAXTAMHEAP) )
    return 0;

  /* Adiciona filho na última posicao */
  h->chave[h->n] = chave;
  h->info[h->n] = info;
  h->n++;

  /* Chama a funcao sobe() para posicioná-lo corretamente */
  sobe(h,h->n-1);

  return 1;
}

/* 
   extrai o elemento de menor chave do heap, retorna 1 se deu 
   tudo certo (e os parametros chave e info possuirao os valores dos 
   campos daquele elemento). Retorna 0 se deu pau (valor deve
   entao retornar 0, e info deve retornar NULL
*/
 
int ExtraiMinOk (Heap *h, int *chave, void **info) {

  if (h == NULL) {
    comAviso(AVS1,"ExtraiMinOk");
  }

  if (h->n < 1) 
    return 0;
  
  *chave = h->chave[0];
  if ( h->info[0] != NULL)
    *info = h->info[0];

  h->n--;

  /* Poe o ultimo na raiz e manda ele descer */
  h->chave[0] = h->chave[h->n];
  if ( h->info[h->n] != NULL )
    h->info[0] = h->info[h->n];

  /* Só para ficar sem lixo */
  h->chave[h->n]=0;
  h->info[h->n]=NULL;

  /* Desce o 1o elemento, só para garantir que está ordenado,
     pois o pai passou a ser o filho esquerdo
  */
  
  desce(h,0);
  
  return 1;
}

/* imprime so' as chaves do heap, na ordem por profundidade */
/* (raiz, filho esquerdo da raiz, filho direito da raiz, */
/* filho esquerdo do filho esquerod da raiz, ...) */
 
void ImprimeChaves (Heap h){
  int i;

  for (i=0; i < h.n; i++) {
    printf("%i ",h.chave[i]);
  }
  printf("\n");
  return;
}















/* author: Gustavo Sverzut Barbieri (http://www.gustavobarbieri.com.br) */