binary

#include "../include/info.h"
#include "../include/cadena.h"
#include "../include/binario.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <algorithm>
#include <cmath>

using namespace std;

struct rep_binario {
  info_t dato;
  rep_binario *izq;
  rep_binario *der;
};

binario_t crear_binario() { return NULL; }

bool insertar_en_binario(info_t i, binario_t &b) {
  if (b == NULL) {
    b = new rep_binario;
    b->dato = i;
    b->der = b->izq = NULL;
    return true;
  } else if (strcmp(frase_info(i), frase_info(b->dato)) < 0) {
    return insertar_en_binario(i, b->izq);
  } else if (strcmp(frase_info(i), frase_info(b->dato)) > 0) {
    return insertar_en_binario(i, b->der);
  } else {
    return false;
  }
}

info_t remover_mayor(binario_t &b) {
  info_t res;
  if (b->der == NULL) {
    res = b->dato;
    binario_t izq = b->izq;
    delete (b);
    b = izq;
  } else {
    res = remover_mayor(b->der);
  }
  return res;
}

bool es_vacio_binario(binario_t b) {
  return (b == NULL);
}

info_t raiz(binario_t b) {
  //assert(! es_vacio_binario(b));
  return b->dato;
}

binario_t izquierdo(binario_t b) {
  //assert(! es_vacio_binario(b));
  return b->izq;
}

binario_t derecho(binario_t b) {
  //assert(! es_vacio_binario(b));
  return b->der;
}

nat altura_binario(binario_t b) {
  if (es_vacio_binario(b))
    return 0;
  else
    return (1 + max(altura_binario(b->izq), altura_binario(b->der)));
}

void liberar_binario(binario_t &b) {
  if (!es_vacio_binario(b)) {
    if (b->izq != NULL)
      liberar_binario(b->izq);
    if (b->der != NULL)
      liberar_binario(b->der);
    remover_de_binario(frase_info(b->dato), b);
  }
}

bool remover_de_binario(const char *t, binario_t &b) {
  if (!es_vacio_binario(b)){
    if (strcmp(frase_info(b->dato), t) == 0) {
      if (es_vacio_binario(b->izq)) {
        binario_t aux = b;
        liberar_info(b->dato);
        b = derecho(b);
        delete aux;
        return true;
      }else if (es_vacio_binario(b->der)) {
        binario_t aux = b;
        liberar_info(b->dato);
        b = izquierdo(b);
        delete aux;
        return true;
      } else {
        liberar_info(b->dato);
        b->dato = remover_mayor(b->izq);
        return true;
      }
    } else if (strcmp(t, frase_info(b->dato)) < 0)
        return remover_de_binario(t, b->izq);
     else
        return remover_de_binario(t, b->der);
  } else
    return false;
}

binario_t buscar_subarbol(const char *t, binario_t b) {
  if (!es_vacio_binario(b)) {
    if (strcmp(t, frase_info(b->dato)) == 0) {
      return b;
    } else if (strcmp(t, frase_info(b->dato)) < 0) {
      return buscar_subarbol(t, b->izq);
    } else {
      return buscar_subarbol(t, b->der);
    }
  } else {
    return crear_binario();
  }
}

nat cantidad_binario(binario_t b) {
  if (es_vacio_binario(b))
    return 0;
  else
    return (1 + cantidad_binario(b->izq) + cantidad_binario(b->der));
}

info_t kesimo_en_binario(nat k, binario_t b) {
  assert((1 <= k) && (k <= cantidad_binario(b)));
  if (k == cantidad_binario(b->izq) + 1)
      return b->dato;
  else if( k <= cantidad_binario(b->izq))
      return (kesimo_en_binario(k,b->izq));
  else
      return (kesimo_en_binario(k-1-cantidad_binario(b->izq),b->der));
}

cadena_t linealizacion(binario_t b) {
  cadena_t res = crear_cadena();
  for (nat i = 1; i <= cantidad_binario(b); i++) {
    insertar_al_final(kesimo_en_binario(i, b), res);
  }
  return res;
}

binario_t filtrado(int clave, binario_t b) {
  if (es_vacio_binario(b))
    return NULL;
  else {
    binario_t fizq, fder, nuevo, mayor;
    fizq = filtrado(clave, izquierdo(b));
    fder = filtrado(clave, derecho(b));
    if (numero_info(raiz(b)) < clave) {
      nuevo = new rep_binario;
      nuevo->dato = copia_info(raiz(b));
      nuevo->izq = fizq;
      nuevo->der = fder;
      return nuevo;
    } else if (fizq == NULL)
        return fder;
      else if (fder == NULL)
        return fizq;
      else {
        mayor = new rep_binario;
        mayor->dato = remover_mayor(fizq);
        mayor->izq = fizq;
        mayor->der = fder;
        return mayor;
      }
  }
}

static nat busqueda_altura(const char *t, binario_t b){
    if (strcmp(t,frase_info(b->dato))==0)
        return 0;
    else if (strcmp(t,frase_info(b->dato))<0)
        return (1+ busqueda_altura(t,b->izq));
    else
        return(1+busqueda_altura(t,b->der));
}


void imprimir_binario(binario_t b) {
  if (!es_vacio_binario(b)) {
    for (nat i = cantidad_binario(b); i >= 1; i--) {
        printf("\n");
      for (nat j = 1; j <= busqueda_altura(frase_info(kesimo_en_binario(i,b)),b); j++) {
        printf("-");
      }
      printf("%s", info_a_texto(kesimo_en_binario(i, b)));
    }
  }
  printf("\n");
}

static int dfs(binario_t b){
    int r1 = 0, r2 = 0;
    if (b->izq)
        r1 = dfs(b->izq);
    if (b->der)
        r2 = dfs(b->der);
    if(r1==-1||r2==-1)
        return -1;
    if(abs(r1-r2)<2)
        return max(r1,r2);
    else
        return -1;
}


bool es_AVL(binario_t b) {
  if (es_vacio_binario(b))
    return true;
  else
      return (dfs(b) != -1);

}