#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include "grafo.h"


typedef struct _viz Viz;
struct _viz {
  int noj;
  float peso;
  Viz*  prox;
};

struct _grafo {
  int nv;           /* numero de nos ou vertices */
  int na;           /* numero de arestas */
  Viz** viz;         /* viz[i] aponta para a lista de arestas vizinhas do no i */
};

/* implementação do MIN HEAP */
typedef struct heap Heap;
typedef struct _item Item;

struct _item {
  int dist;
  int idno;
};

struct heap {
  int max; /* tamanho maximo do heap */
  int pos; /* proxima posicao disponivel no vetor */ 
  Item *itens; /* vetor de itens */
  int* posnos;
}; 

static Heap *heap_cria (int max) {
  int i;
  Heap* heap=(Heap*)malloc(sizeof(struct heap));
  heap->max=max;
  heap->pos=0;
  heap->itens = (Item *)malloc(max*sizeof(struct _item));
  heap->posnos = (int *)malloc(max*sizeof(int));
  for (i = 0; i < max; i++) heap->posnos[i] = -1;
  return heap;
}

static void heap_libera(Heap *h) {
  free(h->itens);
  free(h->posnos);
  free(h);
}

static void heap_insere (Heap *h, int distancia, int idno) {
  if (h->pos >= h->max) {
    printf("Heap CHEIO!\n");
    exit(1);
  }
  h->itens[h->pos].dist = distancia;
  h->itens[h->pos].idno = idno;
  h->posnos[idno] = h->pos;
  h->pos++;
 } 

static void troca(Heap *h, int a, int b) {
  /* completar */
}

static void corrige_abaixo(Heap *h, int atual) {
  /* completar */
}

static int heap_remove(Heap *h) {
  int idno;
  if (h->pos == 0) return -1;
  idno = h->itens[0].idno;
  h->posnos[idno] = -1;

  h->itens[0].idno = h->itens[h->pos-1].idno;
  h->itens[0].dist = h->itens[h->pos-1].dist;
  h->posnos[h->itens[0].idno] = 0;

  h->pos--;
  corrige_abaixo(h, 0);

  return idno;
}
  
static void debug_heap_show (Heap *h, char* title) {
  int i;
  printf("%s={",title);
  for (i=0; i<(h->pos); i++)
    printf("[%d , %d] ",h->itens[i].idno, h->itens[i].dist);
  printf("}\n");
}

static void heap_corrige (Heap* h, int novadist, int idno) {
/* completar */
}

/*-------------------*/

static Viz* criaViz(Viz* head, int noj, float peso) {
/* insere vizinho no inicio da lista */
  Viz* no = (Viz*) malloc(sizeof(Viz));
  assert(no);
  no->noj = noj;
  no->peso = peso;
  no->prox = head;
  return no;
}

static Grafo* grafoCria(int nv, int na) {

  int i;
  Grafo* g = (Grafo *) malloc(sizeof(Grafo));
  g->nv = nv;
  g->na = na;
  g->viz = (Viz **) malloc(sizeof(Viz *) * nv);
  for (i = 0; i < nv; i++)
    g->viz[i] = NULL;
  return g;
}


Grafo* grafoLe( char* filename ) {
/* cria grafo não orientado - supõe que arquivo está correto! */

  FILE *arq = fopen(filename,"rt");
  int nv, na, no1, no2 = 0;
  float peso;
  Grafo* novo;
	
  fscanf(arq, "%d %d", &nv, &na);
  novo = grafoCria(nv, na);
  assert(novo);
  while (fscanf(arq, "%d %d %f", &no1, &no2, &peso) == 3) {
    novo->viz[no1] = criaViz(novo->viz[no1], no2, peso);
    novo->viz[no2] = criaViz(novo->viz[no2], no1, peso);
  }
  return novo;
}

Grafo*   grafoLibera(Grafo* grafo) {
  if (grafo) {
    int i = 0;
    Viz* no,*aux;
    for (i = 0; i < grafo->nv; i++){
      no = grafo->viz[i];
      while (no){
        aux = no->prox;
        free(no);
        no = aux;
      }
    }
    free(grafo->viz);
    free(grafo);
  }
  return NULL;
}

void grafoMostra (char* title, Grafo * grafo) {
  int i;
  if (title)
    printf("%s", title);
  if (grafo) {
    printf("NV: %d, NA: %d\n", grafo->nv, grafo->na);
    for (i = 0; i < grafo->nv; i++){
    Viz* viz = grafo->viz[i];
    printf("[%d]->", i);
    while (viz) {
      printf("{%d, %g}->", viz->noj, viz->peso);
      viz = viz->prox;
    }
    printf("NULL\n");
    }
  }
}

int* menoresCaminhos (Grafo *grafo, int no_inicial){

  if (no_inicial >= grafo->nv) return NULL;

  /* COMPLETAR */

  return NULL;
}