#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;
}  

static Mapa* menorChave (Mapa *m) {
  if (m==NULL) return NULL;
  while (m->esq != NULL) m = m->esq;
  return m;
}


Mapa* retira (Mapa *m, int chave) {
  Mapa *sucessor;

  if (m == NULL) return NULL; 
  if (chave < m->chave)
    m->esq = retira(m->esq, chave); 
  else if (chave > m->chave)
    m->dir = retira(m->dir, chave);
  else { /* achou o nó a remover */
    if (m->esq == NULL && m->dir == NULL) { /* nó sem filhos */
      free (m); m = NULL; 
    }
    else if (m->esq == NULL) {/* nó só tem filho à direita */ 
      Mapa* t = m; m = m->dir; free(t);
      return m;
    }
    else if (m->dir == NULL) {/* só tem filho à esquerda */
      Mapa* t = m; m = m->esq; free (t); 
    }
    else {/* nó tem os dois filhos: busca o sucessor */ 
      sucessor = menorChave(m->dir);
      m->chave = sucessor->chave;
      m->dados = sucessor->dados;
      m->dir = retira (m->dir, m->chave);
    }
  } 
  return m;
}

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


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* m) {
  printf("[");
  if (m != NULL) {
    printf("<%d:%d> ", m->chave, m->dados);
    mostra(m->esq);
    mostra(m->dir);
  }
  printf("]");
}

void mostra_chaves_decrescentes(Mapa *m) {
  if (m == NULL) return;
  /* COMPLETAR */
}

static int chavek_rec(Mapa *m, int k, int *quantos) {
  /* FAZER */
  return 0; /* apenas para compilar ok */
}

int chavek(Mapa *m, int k) {
  int ordem = 0;
  int chave = chavek_rec(m, k, &ordem);
  if (ordem < k) return -1;
  return chave;
}
  
static int e_abbr (Mapa *m, int min, int max) {
  /* FAZER */
  return 1; /* apenas para compilar ok */ 
}

int e_abb (Mapa *m) {
  return (e_abbr(m, INT_MIN, INT_MAX));
}

void debug_troca_chave (Mapa *m, int original, int novachave){
  if (m==NULL) return;
  else if (original < m->chave)
    debug_troca_chave (m->esq, original, novachave);
  else if (original > m->chave) 
    debug_troca_chave (m->dir, original, novachave);
  else m->chave = novachave;
}