#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "mapa.h"
#include "arvore.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 hash2(Mapa* m, int a) {
  a = (a ^ 61) ^ (a >> 16);
  a = a + (a << 3);
  a = a ^ (a >> 4);
  a = a * 0x27d4eb2d;
  a = a ^ (a >> 15);
  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) {
}

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

  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 { /* conflito */
    /* procura proxima posição livre */
    int 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 */
    int hashocupadora = hash(m, m->tabpos[pos].chave);
    if (hashocupadora==pos) { /* conflito primario: encadeia */
    /* completar */
    }
    else { /* conflito secundario: expulsa o item atual de pos */
    /* completar */
    }
  }
  (m->ocupadas)++; /* aumentou o número de itens na tabela */
  return m;
}

int busca (Mapa *m, int chave) {
  if (m==NULL) return -1;
  /* completar */
  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);
}