#include <stdio.h>
#include <stdlib.h>
#include "mapa.h"
#include "arvore.h"

int dados (int chave) {
  /* inventa dados associados a uma chave */
  return 2*chave;
}

Mapa *preenche(Mapa *m, int inicio, int fim) {
  int meio;
  if(inicio > fim) return m;
  meio = (fim + inicio)/2;
  m = insere(m, meio, dados(meio));
  m = preenche(m, inicio, meio-1);
  m = preenche(m, meio+1, fim);
  return m;
}

int main(int argc, char **argv) {
  int res, i, tammapa;

  if (argc!=2) {
    printf ("uso do programa: %s <tamanhomapa>\n", argv[0]);
    exit(0);
  }
  tammapa = atoi(argv[1]);
  Mapa *m1 = cria();
  Mapa *m2 = cria();

  /* preenchendo sem balancear */
  for (i=0;i<tammapa;i++) m1 = insere(m1, i, dados(i));
  printf("mapa desbalanceado -------------- \n");
  mostra(m1);

  printf("\nbusca desbalanceada --------------\n");
  for (i=0; i<=(tammapa+1); i++) {
    res = busca(m1, i);
    printf ("achou %d? %s\n", i, (res!=INT_MIN)?"sim":"não");
  }

  /* preenchendo balanceado */
  m2 = preenche (m2, 0, tammapa-1);
  printf("mapa balanceado ------------ \n");
  mostra(m2);

  printf("\nbusca balanceada --------------\n");
  for (i=0; i<=(tammapa+1); i++) {
    res = busca(m2, i);
    printf ("achou %d? %s\n", i, (res!=INT_MIN)?"sim":"não");
  }

  destroi(m1);
  destroi(m2);


  return 0;
}