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

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

/* IMPLEMENTAÇÃO DE MAPA */

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

/* Funções auxiliares */

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

/* Funções exportadas */

Mapa* cria (void) {
  return NULL;
}
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;
}  

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

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

Mapa *retira (Mapa *m, int chave) {
  Mapa *sucessor, *t;
  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ó com filho à direita */
      t = m; m = m->dir; free(t);
    }
    else if (m->dir == NULL)  { /* nó com filho à esquerda */
      t = m; m = m->esq; free(t);
    }
    else { /* nó tem dois filhos */
      sucessor = m->dir;
      while (sucessor->esq) sucessor = sucessor->esq;
      m->chave = sucessor->chave;
      m->dados = sucessor->dados;
      sucessor->chave = chave;
      m->dir = retira(m->dir, chave);
    }
  }
  return m;
}

/* IMPLEMENTAÇÃO DE ÁRVORE */

void mostra(Mapa* m) {
  printf("[");
  if (m != NULL) {
    printf("<%d %d> ", m->chave, m->dados);
    mostra(m->esq);
    mostra(m->dir);
  }
  printf("] ");
}

int num_nos (Mapa *m) {
  if (m == NULL) return 0;
  return num_nos(m->esq) + num_nos(m->dir) + 1;
}

int maior_chave (Mapa *m) {
  if (m == NULL) return INT_MIN;
  if (m->dir) return maior_chave(m->dir);
  return m->chave;
}

int num_maiores_que (Mapa *m, int n) {
  int nos = 0;
  if (m == NULL) return 0;
  if (m->chave > n)
    nos += num_maiores_que(m->esq, n);
  nos += num_maiores_que(m->dir, n);
  if (m->chave > n)
    nos += 1;
  return nos;
}


/* Funções para implementar */

int altura (Mapa *m) {
  return 0; /* troque por sua implementação */
}

int e_balanceada (Mapa *m) {
  return 0; /* troque por sua implementação */
}

Mapa *balancear(Mapa *m) {
  return m; /* troque por sua implementação */
}