#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#include "mapa.h"
#include "arvore.h"

struct smapa {
  int chave;
  int dados;
  Mapa* esq;
  Mapa* dir;
};

Mapa* cria (void) {
  return NULL;
}

static Mapa *cria_no (int c, int d) {
  Mapa *nn = (Mapa *)malloc(sizeof(Mapa));
  if (nn!=NULL) {
    nn->esq = nn->dir = NULL;
    nn->chave =c;
    nn->dados = d;
  }
  return nn;
}

Mapa *insere (Mapa *m, int chave, int d) {
  if (m==NULL) 
    return cria_no(chave, d);
  else if (chave < m->chave) 
    m->esq = insere(m->esq,chave,d);
  else  /* if (chave > m->chave) */ {
    m->dir = insere(m->dir,chave,d);
  }
  return m;
}

int busca (Mapa *m, int chave) {
  while (m!=NULL) {
    if (chave < m->chave)
      m = m->esq;
    else if (chave > m->chave)
      m = m->dir;
    else
      return m->dados; /* achou */
  }
  return INT_MIN;
}  

int altura (Mapa *m) {
  int ae, ad;
  if (m==NULL) return -1;
  else {
    ae = altura (m->esq);
    ad = altura (m->dir);
    return (ae>ad?ae:ad) + 1;
  }
}

void mostra_mapa_int (Mapa* m) {

  printf("[");
  if (m != NULL) {
    printf("%d ", m->chave);
    mostra_mapa_int(m->esq);
    mostra_mapa_int(m->dir);
  }
  printf("]");
}

void mostra (Mapa* m) {
  mostra_mapa_int (m); printf ("\n");
}

void destroi (Mapa *m) {
  if (m==NULL) return;
  destroi (m->esq);
  destroi (m->dir);
  free(m);
}

Mapa* retira (Mapa *m, int chave) {
  return m;
}