abb final

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "abb.h"
#include "pila.h"

const int TAMANIO_INICIAL= 0;
const int DAR_PADRE= 1;
const int NO_DAR_PADRE= -1;
const int IZQ= -1;
const int DER= 1;

/* Definición del struct nodo.
 */
 typedef struct nodo {
     void* dato;
     char* clave;
}nodo_t;

/* Definición del struct abb_nodo.
 */
typedef struct abb_nodo {
    nodo_t* nodo;
    struct abb_nodo* izq;
    struct abb_nodo* der;
}abb_nodo_t;

/* Definición del struct abb.
 */
struct abb {
    abb_nodo_t* raiz;
    size_t cantidad_nodos;
    abb_comparar_clave_t cmp;
    abb_destruir_dato_t destruir_dato;
};

/* Definición del struct abb_iter.
 */
struct abb_iter{
    const abb_t* arbol;
    pila_t *pila;
};

/* ******************************************************************
 *                    FUNCIONES AUXILIARES
 * *****************************************************************/
char* duplicar_clave(const char* clave) {
    size_t largo= strlen(clave)+1; //sumo 1 para el \0
    char* dup_clave = malloc(sizeof(char)*largo);
    if(dup_clave == NULL) {
        return NULL;
    }
    strcpy(dup_clave, clave);
    return dup_clave;
}

nodo_t* nodo_crear(const char* clave, void* dato) {

    nodo_t* nodo = malloc(sizeof(nodo_t));
    if (nodo == NULL) {
        return NULL;
    }
    nodo->clave = duplicar_clave(clave);
    if(nodo->clave == NULL) {
        return NULL;
    }
    nodo->dato = dato;
    return nodo;
}

abb_nodo_t* nodo_abb_crear(const char* clave, void* dato) {

    abb_nodo_t* nuevo_nodo= malloc(sizeof(abb_nodo_t));

    if(nuevo_nodo == NULL) {
        return NULL;
    }

    nuevo_nodo->nodo= nodo_crear(clave, dato);

    if(nuevo_nodo->nodo == NULL) {
        return NULL;
    }

    nuevo_nodo->der= NULL;
    nuevo_nodo->izq= NULL;
    return nuevo_nodo;
}

void* borrar_nodo(abb_nodo_t* nodo_borrar) {
    void* dato= nodo_borrar->nodo->dato;
    free(nodo_borrar->nodo->clave);
    free(nodo_borrar->nodo);
    free(nodo_borrar);
    return dato;
}

void swappeo_nodos_abb(abb_nodo_t* padre, abb_nodo_t* hijo) {
    nodo_t* nodo_aux= padre->nodo;
    padre->nodo= hijo->nodo;
    hijo->nodo= nodo_aux;
}

int hijo_izq_o_der(abb_nodo_t* padre) {
    if(padre->der) {
        return DER;
    }
    return IZQ;
}

bool guardar_nodo_en_el_arbol(abb_t* arbol, abb_nodo_t* padre, abb_nodo_t* hijo) {

    if(arbol->cmp(padre->nodo->clave, hijo->nodo->clave) < 0) {
        if(padre->der == NULL) {
            padre->der= hijo;
            arbol->cantidad_nodos += 1;
            return true;
        }else {
            return guardar_nodo_en_el_arbol(arbol, padre->der, hijo);
        }
    }else if(arbol->cmp(padre->nodo->clave, hijo->nodo->clave) > 0) {
        if(padre->izq == NULL) {
            padre->izq= hijo;
            arbol->cantidad_nodos += 1;
            return true;
        }else {
            return guardar_nodo_en_el_arbol(arbol, padre->izq, hijo);
        }
    }
    //si son iguales
    swappeo_nodos_abb(padre, hijo);
    void* dato= borrar_nodo(hijo);
    if(arbol->destruir_dato != NULL) {
        arbol->destruir_dato(dato);
    }
    return true;
}

abb_nodo_t* abb_nodo_buscar(const abb_t* arbol, abb_nodo_t* nodo_actual, const char* clave, int devuelvo_el_padre) {

    if(nodo_actual == NULL) {
        return NULL;
    }

    int cmp= arbol->cmp(nodo_actual->nodo->clave, clave);
    bool esta= false;

    if(devuelvo_el_padre == DAR_PADRE) {
        if(cmp == 0) {
            return NULL;
        }else if(arbol->cmp(nodo_actual->izq->nodo->clave, clave) == 0) {
            return nodo_actual;
        }else if(arbol->cmp(nodo_actual->der->nodo->clave, clave) == 0) {
            return nodo_actual;
        }
    }

    if( cmp < 0) {
        return abb_nodo_buscar(arbol, nodo_actual->der, clave, devuelvo_el_padre);
    }else if(cmp > 0) {
        return abb_nodo_buscar(arbol, nodo_actual->izq, clave, devuelvo_el_padre);
    }else if(cmp == 0) {
        esta= true;
    }

    if(!esta) {
        return NULL;
    }

    return nodo_actual;
}

abb_nodo_t* buscar_hijo(abb_nodo_t* padre) {
    int pos_hijo= hijo_izq_o_der(padre);

    if(pos_hijo == DER) {
        return padre->der;
    }
    return padre->izq;
}

void destruir_abb(abb_t* arbol, abb_nodo_t* nodo_actual) {

    if(nodo_actual == NULL) {
        return;
    }
    destruir_abb(arbol, nodo_actual->izq);
    destruir_abb(arbol, nodo_actual->der);
    void* dato= borrar_nodo(nodo_actual);

    if(arbol->destruir_dato != NULL) {
        arbol->destruir_dato(dato);
    }
}

// Me devuelve el nodo que esta mas a la izquierda del nodo que voy a eliminar
abb_nodo_t* buscar_minimo(abb_nodo_t* nodo_actual) {

    if(nodo_actual == NULL) {
        return NULL;
    }

    if(nodo_actual->izq != NULL) {
        return buscar_minimo(nodo_actual->izq);
    }
    return nodo_actual;
}

bool nodo_hoja(abb_nodo_t* nodo_actual) {
    if(nodo_actual->izq == NULL && nodo_actual->der == NULL) {
        return true;
    }
    return false;
}

bool nodo_un_hijo(abb_nodo_t* nodo_actual) {
    if(nodo_actual->izq != NULL && nodo_actual->der == NULL) {
        return true;
    }else if(nodo_actual->izq == NULL && nodo_actual->der != NULL) {
        return true;
    }
    return false;
}

bool nodo_dos_hijos(abb_nodo_t* nodo_actual) {
    if(nodo_actual->izq != NULL && nodo_actual->der != NULL) {
        return true;
    }
    return false;
}

void* borro_hoja(abb_t* arbol, abb_nodo_t* padre, abb_nodo_t* hijo) {

    if(hijo == arbol->raiz) {
        arbol->raiz= NULL;
        arbol->cantidad_nodos -=1;
        return borrar_nodo(hijo);
    }
    int cmp= arbol->cmp(padre->nodo->clave, hijo->nodo->clave);

    if(cmp < 0) {
        padre->der= NULL;
    }else {
        padre->izq= NULL;
    }
    arbol->cantidad_nodos -=1;
    return borrar_nodo(hijo);
}

void* borro_nodo_con_un_hijo(abb_t* arbol, abb_nodo_t* abuelo, abb_nodo_t* padre) {

    abb_nodo_t* nieto= buscar_hijo(padre);

    if(padre == arbol->raiz){
        arbol->raiz= nieto;
        arbol->cantidad_nodos -=1;
        return borrar_nodo(padre);
    }

    int pos_hijo= hijo_izq_o_der(abuelo);

    if(pos_hijo == DER) {
        abuelo->der= nieto;
    }else{
        abuelo->izq= nieto;
    }
    arbol->cantidad_nodos -=1;
    return borrar_nodo(padre);
}

/* ******************************************************************
 *                    PRIMITIVAS DEL ABB
 * *****************************************************************/
abb_t* abb_crear(abb_comparar_clave_t cmp, abb_destruir_dato_t destruir_dato) {

    abb_t* abb= malloc(sizeof(abb_t));

    if(abb == NULL) {
        return NULL;
    }

    abb->raiz= NULL;
    abb->cmp= cmp;
    abb->destruir_dato= destruir_dato;
    abb->cantidad_nodos= TAMANIO_INICIAL;
    return abb;
}

bool abb_guardar(abb_t* arbol, const char* clave, void* dato) {

    abb_nodo_t* nodo_nuevo= nodo_abb_crear(clave, dato);

    if(nodo_nuevo == NULL) {
        return false;
    }

    if(arbol->raiz == NULL) {
        arbol->raiz= nodo_nuevo;
        arbol->cantidad_nodos += 1;
        return true;
    }else {
        if(guardar_nodo_en_el_arbol(arbol, arbol->raiz, nodo_nuevo)) {
            return true;
        }
    }
    return false;
}

void* abb_borrar(abb_t* arbol, const char* clave) {

    if(abb_cantidad(arbol) == 0 || !abb_pertenece(arbol, clave)){
        return NULL;
    }

    abb_nodo_t* padre= abb_nodo_buscar(arbol, arbol->raiz, clave, DAR_PADRE);
    abb_nodo_t* nodo_actual= abb_nodo_buscar(arbol, arbol->raiz, clave, NO_DAR_PADRE);

    // si nodo actual es una hoja
    if(nodo_hoja(nodo_actual)) {
        return borro_hoja(arbol, padre, nodo_actual);
    }
    if(nodo_un_hijo(nodo_actual)) {
        return borro_nodo_con_un_hijo(arbol, padre, nodo_actual);
    }

    // si nodo actual es un nodo con dos hijos
    if(nodo_dos_hijos(nodo_actual)) {
        abb_nodo_t* nodo_minimo= buscar_minimo(nodo_actual->der);
        abb_nodo_t* padre_minimo= abb_nodo_buscar(arbol, arbol->raiz, nodo_minimo->nodo->clave, DAR_PADRE);
        swappeo_nodos_abb(nodo_actual, nodo_minimo);

        if(nodo_hoja(nodo_minimo)) {
            return borro_hoja(arbol, padre_minimo, nodo_minimo);
        }else if(nodo_un_hijo(nodo_minimo)){
            padre_minimo->izq= nodo_minimo->der;
        }
        arbol->cantidad_nodos -=1;
        return borrar_nodo(nodo_minimo);
    }

    return NULL;
}

void *abb_obtener(const abb_t *arbol, const char *clave) {

    abb_nodo_t* nodo_a_buscar = abb_nodo_buscar(arbol, arbol->raiz, clave, NO_DAR_PADRE);

    if(!nodo_a_buscar) {
        return NULL;
    }
    return nodo_a_buscar->nodo->dato;
}

bool abb_pertenece(const abb_t* arbol, const char* clave) {

    abb_nodo_t* nodo_a_buscar = abb_nodo_buscar(arbol, arbol->raiz, clave, NO_DAR_PADRE);

    return (nodo_a_buscar != NULL);
}

size_t abb_cantidad(abb_t *arbol) {
    return(arbol->cantidad_nodos);
}

void abb_destruir(abb_t* arbol) {
    destruir_abb(arbol, arbol->raiz);
    free(arbol);
}

 /* *****************************************************************
 *               PRIMITIVAS DEL ITERADOR EXTERNO
 * *****************************************************************/

abb_iter_t *abb_iter_in_crear(const abb_t *arbol) {

    abb_iter_t* nuevo_iter = malloc(sizeof(abb_iter_t));
    if(!nuevo_iter) {
        return NULL;
    }
    nuevo_iter->arbol = arbol;
    nuevo_iter->pila = pila_crear();

    if(!nuevo_iter->pila) {
        free(nuevo_iter);
        return NULL;
    }

    abb_nodo_t* nodo_actual = arbol->raiz;

    while(nodo_actual != NULL) {
        pila_apilar(nuevo_iter->pila, nodo_actual);
        nodo_actual = nodo_actual->izq;
    }

    return nuevo_iter;
}

bool abb_iter_in_avanzar(abb_iter_t *iter) {
    if(abb_iter_in_al_final(iter)) {
        return false;
    }

    abb_nodo_t* nodo_actual= pila_desapilar(iter->pila);

    if(nodo_actual->der != NULL) {

        pila_apilar(iter->pila, nodo_actual->der);
        nodo_actual= nodo_actual->der;

        while(nodo_actual->izq != NULL) {
            pila_apilar(iter->pila, nodo_actual->izq);
            nodo_actual= nodo_actual->izq;
        }
    }
    return true;
}

bool abb_iter_in_al_final(const abb_iter_t *iter) {
    return pila_esta_vacia(iter->pila);
}

const char* abb_iter_in_ver_actual(const abb_iter_t *iter) {
    if(abb_iter_in_al_final(iter))
        return NULL;

    abb_nodo_t* nodo_actual = pila_ver_tope(iter->pila);
    return (nodo_actual->nodo->clave);
}

void abb_iter_in_destruir(abb_iter_t* iter){
    pila_destruir(iter->pila);
    free(iter);
}

/* ******************************************************************
 *                    PRIMITIVAS DEL ITERADOR INTERNO
 * *****************************************************************/

void abb_iterar(abb_nodo_t* nodo_actual, bool visitar(const char *, void *, void *), void *extra){

    if(nodo_actual == NULL){
        return;
    }

    abb_iterar(nodo_actual->izq, visitar, extra);
    visitar(nodo_actual->nodo->clave, nodo_actual->nodo->dato, extra);
    abb_iterar(nodo_actual->der, visitar, extra);
}

void abb_in_order(abb_t* arbol, bool visitar(const char *, void *, void *), void *extra){
    abb_iterar(arbol->raiz, visitar, extra);
}