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

#define TAMINICIAL 11

typedef struct {
  int chave;
  int dados;
  int prox;
} ttabpos;

struct smapa {
  int tam;
  int ocupadas;
  ttabpos *tabpos;
};

static unsigned int hash1 (Mapa* m, int a) {
  return a%(m->tam);
}
  
static unsigned int hash (Mapa* m, int chave) {
  return hash1(m, chave);
}

Mapa* cria () {
  int i;
  Mapa* m = (Mapa*) malloc (sizeof(Mapa));
  if (m==NULL) {printf("erro na alocação! \n"); exit(1);}
  m->tabpos = (ttabpos*) malloc (TAMINICIAL*sizeof(ttabpos)); 
  if (m->tabpos==NULL) {printf("erro na alocação! \n"); exit(1);}
  m->tam = TAMINICIAL;
  m->ocupadas = 0;
  for (i=0;i<TAMINICIAL;i++) {
    m->tabpos[i].chave = -1;
    m->tabpos[i].prox = -1;
  }
  return m;
}

static void redimensiona (Mapa* m) {
  int i;
  int tamanterior = m->tam;
  ttabpos* anterior = m->tabpos;
  printf ("redimensiona...\n");
  m->tam = 1.947*m->tam;
  printf("novo tamanho: %d\n", m->tam);
  m->tabpos = (ttabpos*) malloc (m->tam*sizeof(ttabpos));
  m->ocupadas = 0;
  for (i=0;i < m->tam;i++) {
    m->tabpos[i].chave = -1;
    m->tabpos[i].prox = -1;
  }
  for (i=0; i<tamanterior; i++)
    if (anterior[i].chave != -1) 
      insere (m, anterior[i].chave, anterior[i].dados);
  free (anterior);
}

/* inserção: supõe que a chave dada NÃO está no mapa */
Mapa* insere (Mapa* m, int chave, int dados) {

  int poslivre, indconf;

  printf("\ntam %d ocupadas %d\n",m->tam, m->ocupadas);
  if (m->ocupadas > 0.75*m->tam) redimensiona(m);
  int pos = hash(m, chave);

  if (m->tabpos[pos].chave == -1) { /* está vazia */
    m->tabpos[pos].chave = chave;
    m->tabpos[pos].dados = dados;
    m->tabpos[pos].prox = -1;
  }
  else { /* tem que encontrar outra posicao livre */
    poslivre = pos;
    do 
      poslivre = (poslivre+1) % (m->tam);
    while ((poslivre!=pos) && (m->tabpos[poslivre].chave!=-1));
    if (poslivre==pos) { /* tabela cheia -- não deveria acontecer */
      printf ("pânico, tabela cheia!\n"); exit(1);
    }
    /* achou posicao livre  - verificar quem vai para ela */
    indconf = hash(m, m->tabpos[pos].chave);
    if (indconf==pos) { /* conflito primario: encadeia */
      m->tabpos[poslivre].chave = chave;
      m->tabpos[poslivre].dados = dados;
      m->tabpos[poslivre].prox = m->tabpos[pos].prox;
      m->tabpos[pos].prox = poslivre;
    }
    else { /* conflito secundario: expulsa o item atual de pos */
      /* encontrar a posicao do item na lista */
      while (m->tabpos[indconf].prox != pos) indconf = m->tabpos[indconf].prox;
      /* acertar encadeamento */
      m->tabpos[poslivre].chave = m->tabpos[pos].chave;
      m->tabpos[poslivre].dados = m->tabpos[pos].dados;
      m->tabpos[poslivre].prox = m->tabpos[pos].prox;
      m->tabpos[indconf].prox = poslivre;
      m->tabpos[pos].chave = chave;
      m->tabpos[pos].dados = dados;
      m->tabpos[pos].prox = -1;
    }
  }
  (m->ocupadas)++;
  return m;
}

int busca (Mapa *m, int chave) {
  int reshash, posbusca;
  if (m==NULL) return -1;
  reshash = hash(m, chave);
  posbusca = reshash;
  while (m->tabpos[posbusca].chave != -1) {
    if (m->tabpos[posbusca].chave == chave)
      return m->tabpos[posbusca].dados;
    else if ((hash(m, m->tabpos[posbusca].chave)) != reshash)
      return -1;
    else if (m->tabpos[posbusca].prox != -1)
      posbusca = m->tabpos[posbusca].prox;
    else return -1;
  }
  return -1;
}

void destroi (Mapa *m) {
  free (m->tabpos);
  free (m);
}

int iguais (Mapa* m1, Mapa* m2) {
  int i;

  if (m1==NULL || m2==NULL) return (m1==NULL && m2==NULL);
  if (m1->tam != m2->tam) return 0;
  ttabpos* tp1 = m1->tabpos;
  ttabpos* tp2 = m2->tabpos;
  for (i = 0; i < m1->tam; i++)
    if ((tp1[i].chave != tp2[i].chave) ||
        (tp1[i].prox != tp2[i].prox))
      return 0;
  return 1;
}

void mostra (Mapa* m) {
  int i;
  for (i=0;i<m->tam;i++) 
    if (m->tabpos[i].chave!=-1) 
      printf ("posicao %d, chave %d, proximo %d\n", i, m->tabpos[i].chave, m->tabpos[i].prox);
}

Mapa * retira(Mapa *m, int chave)
{
  if (m==NULL) return NULL;
  (m->ocupadas)--;
  int pos = hash(m, chave);
  int anterior = -1;
  while(m->tabpos[pos].chave != chave)
    {
      anterior = pos;
      pos = m->tabpos[pos].prox;
      if( pos == -1)
        {
          return m;
        }
    }
  int prox = m->tabpos[pos].prox;
  if (prox != -1) {
    m->tabpos[pos].chave = m->tabpos[prox].chave;
    m->tabpos[pos].prox = m->tabpos[prox].prox;
  }
  else
  {
    m->tabpos[pos].chave = -1;
    m->tabpos[pos].dados = -1;
    m->tabpos[pos].prox = -1;
  }

  if(anterior != -1){
     m->tabpos[anterior].prox = m->tabpos[pos].prox;
  }
  return m;
}

int maior_cadeia(Mapa *m) {
  /* substituir a instrução por sua implementação */
  return 0;
}