#include <Arduino.h>

// ============================================================================
// CONFIGURACIÓN DE PINES - Cada LED representa una operación del árbol
// ============================================================================

const int PIN_LED_ROJO = 16;     // LED para nodos de color ROJO
const int PIN_LED_VERDE = 17;    // LED para nodos de color NEGRO  
const int PIN_LED_AZUL = 18;     // LED para rotaciones IZQUIERDAS
const int PIN_LED_AMARILLO = 19; // LED para rotaciones DERECHAS

// ============================================================================
// ENUMERACIÓN DE COLORES - Define los dos colores posibles en un árbol R-N
// ============================================================================

enum Color { 
    ROJO,   // 0 - Los nuevos nodos empiezan ROJOS
    NEGRO   // 1 - La raíz y los nodosNulo deben ser NEGROS
};

// ============================================================================
// ESTRUCTURA DEL NODO - Cada "caja" que guarda un dato en el árbol
// ============================================================================

struct Nodo {
    // ATRIBUTOS (lo que cada nodo contiene):
    int dato;           // El número que almacena este nodo (ej: 10, 20, etc.)
    Color color;        // ROJO o NEGRO - crucial para el balanceo
    Nodo *izquierda;    // Puntero al hijo de la IZQUIERDA (menor)
    Nodo *derecha;      // Puntero al hijo de la DERECHA (mayor)  
    Nodo *padre;        // Puntero al nodo PADRE (para navegar hacia arriba)

    // CONSTRUCTOR - Se ejecuta AUTOMÁTICAMENTE al crear un nuevo nodo
    Nodo(int valor) {
        dato = valor;           // Guarda el valor recibido en el atributo 'dato'
        color = ROJO;           // REGLA: Nuevos nodos siempre son ROJOS inicialmente
        izquierda = nullptr;    // Al crearse, no tiene hijo izquierdo (vacío)
        derecha = nullptr;      // Al crearse, no tiene hijo derecho (vacío)
        padre = nullptr;        // Al crearse, no tiene padre (se asignará después)
    }
};

// ============================================================================
// CLASE ARBOL ROJO-NEGRO - Contiene toda la lógica del árbol
// ============================================================================

class ArbolRN {
private:
    // ATRIBUTOS PRIVADOS (solo la clase puede acceder):
    Nodo *raiz;        // Puntero al nodo principal (el de más arriba del árbol)
    Nodo *nodoNulo;    // Nodo especial que representa posiciones VACÍAS

    // Función privada para imprimir recursivamente
    void imprimirRecursivo(Nodo *nodo, String prefijo, bool esIzquierdo) {
        if (nodo != nodoNulo) {
            // Imprimir el nodo actual
            Serial.print(prefijo);
            Serial.print(esIzquierdo ? "L-----" : "R-----");
            
            // Elegir emoji según el color
            if (nodo->color == NEGRO) {
                Serial.print("🟩");
            } else {
                Serial.print("🟥");
            }
            
            Serial.print("(");
            Serial.print(nodo->dato);
            Serial.println(")");
            
            // Preparar el prefijo para el siguiente nivel
            String nuevoPrefijo = prefijo + (esIzquierdo ? "|     " : "      ");
            
            // Llamar recursivamente para los HIJOS
            imprimirRecursivo(nodo->derecha, nuevoPrefijo, false);  // Hijo DERECHO primero
            imprimirRecursivo(nodo->izquierda, nuevoPrefijo, true); // Hijo IZQUIERDO después
        }
    }

public:
    // ============================================================================
    // CONSTRUCTOR DEL ÁRBOL - Se ejecuta al crear el objeto ArbolRN
    // ============================================================================
    
    ArbolRN() {
        // Crear el nodoNulo - es un marcador especial para hojas vacías
        nodoNulo = new Nodo(0);     // Crea un nodo normal (dato 0 no importa)
        nodoNulo->color = NEGRO;    // REGLA: nodoNulo SIEMPRE debe ser NEGRO
        nodoNulo->izquierda = nullptr;   // No puede tener hijos
        nodoNulo->derecha = nullptr;
        raiz = nodoNulo;            // Al inicio, el árbol está VACÍO (raíz = vacío)
    }

    // ============================================================================
    // FUNCIONES DE VISUALIZACIÓN CON LEDs
    // ============================================================================

    // Función para mostrar el COLOR de un nodo en los LEDs físicos
    void visualizarLED(Color color, int duracion = 500) {
        switch(color) {
            case ROJO:
                digitalWrite(PIN_LED_ROJO, HIGH);  // Enciende LED rojo (3.3V en pin 16)
                delay(duracion);                   // Mantiene encendido por 'duracion' ms
                digitalWrite(PIN_LED_ROJO, LOW);   // Apaga LED rojo (0V en pin 16)
                break;
            case NEGRO:
                digitalWrite(PIN_LED_VERDE, HIGH); // Enciende LED verde (3.3V en pin 17)
                delay(duracion);                   // Mantiene encendido
                digitalWrite(PIN_LED_VERDE, LOW);  // Apaga LED verde
                break;
        }
    }

    // Función para mostrar ROTACIONES en los LEDs físicos  
    void visualizarRotacion(const char* tipo, int duracion = 300) {
        if(strcmp(tipo, "IZQUIERDA") == 0) {
            digitalWrite(PIN_LED_AZUL, HIGH);      // Enciende LED azul para rotación izquierda
            Serial.println("[RBT] Rotación Izquierda detectada");
        } else {
            digitalWrite(PIN_LED_AMARILLO, HIGH);  // Enciende LED amarillo para rotación derecha
            Serial.println("[RBT] Rotación Derecha detectada");
        }
        delay(duracion);                           // Mantiene encendido por 'duracion' ms
        digitalWrite(PIN_LED_AZUL, LOW);           // Apaga LED azul
        digitalWrite(PIN_LED_AMARILLO, LOW);       // Apaga LED amarillo
    }

    // ============================================================================
    // ROTACIONES - Operaciones fundamentales para balancear el árbol
    // ============================================================================

    // Rotación IZQUIERDA - "Inclina" el árbol hacia la izquierda alrededor de un nodo
    void rotacionIzquierda(Nodo *x) {
        visualizarRotacion("IZQUIERDA");  // Enciende LED azul y muestra mensaje
        
        Nodo *y = x->derecha;      // 'y' es el hijo DERECHO de 'x' (será la nueva raíz de esta sub-rama)
        x->derecha = y->izquierda; // El hijo IZQUIERDO de 'y' se convierte en hijo DERECHO de 'x'
        
        if (y->izquierda != nodoNulo) {
            y->izquierda->padre = x;  // Actualiza el PADRE del hijo movido
        }
        
        y->padre = x->padre;  // 'y' hereda el padre de 'x'
        
        // Actualiza los punteros del padre original:
        if (x->padre == nullptr) {
            raiz = y;              // Si 'x' era la raíz, 'y' ahora es la nueva raíz
        } else if (x == x->padre->izquierda) {
            x->padre->izquierda = y;  // Si 'x' era hijo IZQUIERDO
        } else {
            x->padre->derecha = y;    // Si 'x' era hijo DERECHO
        }
        
        y->izquierda = x;  // 'x' se convierte en hijo IZQUIERDO de 'y'
        x->padre = y;      // 'y' se convierte en padre de 'x'
    }

    // Rotación DERECHA - "Inclina" el árbol hacia la derecha alrededor de un nodo  
    void rotacionDerecha(Nodo *x) {
        visualizarRotacion("DERECHA");  // Enciende LED amarillo y muestra mensaje
        
        Nodo *y = x->izquierda;   // 'y' es el hijo IZQUIERDO de 'x' (será la nueva raíz de esta sub-rama)
        x->izquierda = y->derecha; // El hijo DERECHO de 'y' se convierte en hijo IZQUIERDO de 'x'
        
        if (y->derecha != nodoNulo) {
            y->derecha->padre = x;  // Actualiza el PADRE del hijo movido
        }
        
        y->padre = x->padre;  // 'y' hereda el padre de 'x'
        
        // Actualiza los punteros del padre original:
        if (x->padre == nullptr) {
            raiz = y;              // Si 'x' era la raíz, 'y' ahora es la nueva raíz
        } else if (x == x->padre->derecha) {
            x->padre->derecha = y;   // Si 'x' era hijo DERECHO
        } else {
            x->padre->izquierda = y; // Si 'x' era hijo IZQUIERDO
        }
        
        y->derecha = x;  // 'x' se convierte en hijo DERECHO de 'y'
        x->padre = y;    // 'y' se convierte en padre de 'x'
    }

    // ============================================================================
    // FUNCIÓN PARA ARREGLAR VIOLACIONES DESPUÉS DE INSERTAR
    // ============================================================================

    void arreglarInsercion(Nodo *k) {
        Nodo *u;  // 'u' representará al "TÍO" del nodo (hermano del padre)
        
        // Mientras el PADRE sea ROJO (violación: dos ROJOS seguidos)
        while (k->padre->color == ROJO) {
            
            // CASO A: El PADRE es hijo DERECHO del abuelo
            if (k->padre == k->padre->padre->derecha) {
                u = k->padre->padre->izquierda;  // TÍO por la IZQUIERDA
                
                // CASO 1: El TÍO es ROJO
                if (u->color == ROJO) {
                    Serial.println("[RBT] Caso 1: Tío ROJO - Re-coloreando");
                    u->color = NEGRO;              // Tío se vuelve NEGRO
                    k->padre->color = NEGRO;       // Padre se vuelve NEGRO  
                    k->padre->padre->color = ROJO; // Abuelo se vuelve ROJO
                    k = k->padre->padre;           // Movemos el problema hacia arriba
                    
                    // Visualizar el re-coloreo con LEDs
                    visualizarLED(ROJO, 200);
                    visualizarLED(NEGRO, 200);
                } else {
                    // CASO 2: El TÍO es NEGRO y 'k' es hijo IZQUIERDO
                    if (k == k->padre->izquierda) {
                        Serial.println("[RBT] Caso 2: Tío NEGRO - Rotación derecha");
                        k = k->padre;          // Movemos 'k' hacia arriba
                        rotacionDerecha(k);    // Rotación derecha en el padre
                    }
                    // CASO 3: El TÍO es NEGRO y 'k' es hijo DERECHO
                    Serial.println("[RBT] Caso 3: Re-coloreando y rotación izquierda");
                    k->padre->color = NEGRO;       // Padre se vuelve NEGRO
                    k->padre->padre->color = ROJO; // Abuelo se vuelve ROJO
                    rotacionIzquierda(k->padre->padre); // Rotación en el abuelo
                }
            } 
            // CASO B: El PADRE es hijo IZQUIERDO del abuelo (espejo del caso A)
            else {
                u = k->padre->padre->derecha;  // TÍO por la DERECHA
                
                // CASO 1 (espejo): El TÍO es ROJO
                if (u->color == ROJO) {
                    Serial.println("[RBT] Caso 1: Tío ROJO - Re-coloreando");
                    u->color = NEGRO;              // Tío se vuelve NEGRO
                    k->padre->color = NEGRO;       // Padre se vuelve NEGRO
                    k->padre->padre->color = ROJO; // Abuelo se vuelve ROJO
                    k = k->padre->padre;           // Movemos el problema hacia arriba
                    
                    visualizarLED(ROJO, 200);
                    visualizarLED(NEGRO, 200);
                } else {
                    // CASO 2 (espejo): El TÍO es NEGRO y 'k' es hijo DERECHO
                    if (k == k->padre->derecha) {
                        Serial.println("[RBT] Caso 2: Tío NEGRO - Rotación izquierda");
                        k = k->padre;          // Movemos 'k' hacia arriba  
                        rotacionIzquierda(k);  // Rotación izquierda en el padre
                    }
                    // CASO 3 (espejo): El TÍO es NEGRO y 'k' es hijo IZQUIERDO
                    Serial.println("[RBT] Caso 3: Re-coloreando y rotación derecha");
                    k->padre->color = NEGRO;       // Padre se vuelve NEGRO
                    k->padre->padre->color = ROJO; // Abuelo se vuelve ROJO
                    rotacionDerecha(k->padre->padre); // Rotación en el abuelo
                }
            }
            
            // Si llegamos a la raíz, terminamos el bucle
            if (k == raiz) {
                break;
            }
        }
        
        // REGLA: La raíz SIEMPRE debe ser NEGRA
        raiz->color = NEGRO;
    }

    // ============================================================================
    // FUNCIÓN PRINCIPAL DE INSERCIÓN
    // ============================================================================

    void insertar(int dato) {
        Serial.print("[RBT] Insertando: ");
        Serial.println(dato);
        
        // PASO 1: Crear el nuevo nodo
        Nodo *nuevoNodo = new Nodo(dato);  // Crea nodo (color ROJO automáticamente)
        nuevoNodo->izquierda = nodoNulo;   // Conecta hijo izquierdo a nodoNulo
        nuevoNodo->derecha = nodoNulo;     // Conecta hijo derecho a nodoNulo
        
        Nodo *y = nullptr;    // Para guardar el futuro PADRE del nuevo nodo
        Nodo *x = raiz;       // Empezamos desde la RAÍZ para buscar posición
        
        // PASO 2: Buscar la posición correcta en el árbol
        while (x != nodoNulo) {
            y = x;  // Guardamos el nodo actual antes de movernos
            
            // Comparar el nuevo dato con el nodo actual
            if (nuevoNodo->dato < x->dato) {
                x = x->izquierda;  // Si es MENOR, ir a la IZQUIERDA
            } else {
                x = x->derecha;    // Si es MAYOR, ir a la DERECHA
            }
        }
        
        // PASO 3: Conectar el nuevo nodo a su PADRE
        nuevoNodo->padre = y;  // 'y' es el padre encontrado
        
        if (y == nullptr) {
            raiz = nuevoNodo;  // Si no había padre, el nuevo nodo es la RAÍZ
        } else if (nuevoNodo->dato < y->dato) {
            y->izquierda = nuevoNodo;  // Conectar como hijo IZQUIERDO
        } else {
            y->derecha = nuevoNodo;    // Conectar como hijo DERECHO
        }
        
        // PASO 4: Visualizar el COLOR del nodo insertado
        visualizarLED(nuevoNodo->color);  // Enciende LED según color del nodo
        Serial.print("[RBT] Nodo es ");
        Serial.println(nuevoNodo->color == ROJO ? "ROJO" : "NEGRO");
        
        // PASO 5: Si es nodo RAÍZ, debe ser NEGRO (Regla fundamental)
        if (nuevoNodo->padre == nullptr) {
            nuevoNodo->color = NEGRO;
            visualizarLED(NEGRO, 300);  // Muestra que se volvió NEGRO
            return;  // Termina aquí porque la raíz no necesita balanceo
        }
        
        // PASO 6: Si el ABUELO no existe, no hay necesidad de balancear
        if (nuevoNodo->padre->padre == nullptr) {
            return;
        }
        
        // PASO 7: Arreglar posibles violaciones de las reglas rojo-negro
        arreglarInsercion(nuevoNodo);
    }

    // ============================================================================
    // FUNCIÓN PARA IMPRIMIR EL ÁRBOL EN CONSOLA
    // ============================================================================

    void imprimirArbol() {
        Serial.println("🌳 Estado del árbol:");
        if (raiz == nodoNulo) {
            Serial.println("   [ÁRBOL VACÍO]");
            return;
        }
        imprimirRecursivo(raiz, "", true);
    }
};

// ============================================================================
// VARIABLES GLOBALES
// ============================================================================

ArbolRN arbol;  // Crear una instancia del árbol rojo-negro

// ============================================================================
// SETUP - Configuración inicial (se ejecuta UNA vez al iniciar)
// ============================================================================

void setup() {
    Serial.begin(115200);  // Iniciar comunicación serial a 115200 baudios
    
    // Configurar todos los pines de LEDs como SALIDAS:
    pinMode(PIN_LED_ROJO, OUTPUT);
    pinMode(PIN_LED_VERDE, OUTPUT);  
    pinMode(PIN_LED_AZUL, OUTPUT);
    pinMode(PIN_LED_AMARILLO, OUTPUT);
    
    // Asegurar que todos los LEDs empiecen APAGADOS:
    digitalWrite(PIN_LED_ROJO, LOW);
    digitalWrite(PIN_LED_VERDE, LOW);
    digitalWrite(PIN_LED_AZUL, LOW);
    digitalWrite(PIN_LED_AMARILLO, LOW);
    
    Serial.println("=== INICIANDO ARBOL ROJO-NEGRO ===");
    delay(1000);  // Esperar 1 segundo antes de empezar
}

// ============================================================================
// LOOP - Bucle principal (se ejecuta REPETIDAMENTE)
// ============================================================================

void loop() {
    // FASE 1: Prueba básica con valores predefinidos
    Serial.println("\n--- FASE 1: Prueba de inserciones ---");
    
    // Arreglo con valores de prueba que causarán rotaciones interesantes
    int valores[] = {10, 20, 30, 15, 25};
    
    // Insertar cada valor del arreglo
    for(int i = 0; i < 5; i++) {
        Serial.println("-------------------");
        arbol.insertar(valores[i]);  // Insertar valor actual
        arbol.imprimirArbol();       // Mostrar estado del árbol
        delay(1000);                 // Pausa para ver los LEDs
    }
    
    // FASE 2: Simulación de aplicación IoT
    Serial.println("\n--- FASE 2: Simulación IoT ---");
    
    // Simular recepción de datos de sensores
    Serial.println("[SIM] Nuevo dato de 'temp_sensor_1' (25) almacenado.");
    // Nota: 25 ya está insertado, pero el mensaje simula la aplicación
    
    Serial.println("[SIM] Nuevo dato de 'hum_sensor_1' (52) almacenado.");
    arbol.insertar(52);  // Insertar nuevo valor 52
    
    // Simular scheduler de tareas
    Serial.println("[SCHEDULER] Nueva tarea: 'Activar_Bomba' (Pri: 10)");
    // Nota: 10 ya está insertado
    
    Serial.println("[SCHEDULER] Nueva tarea: 'Leer_Luminosidad' (Pri: 50)");
    arbol.insertar(50);  // Insertar nueva tarea con prioridad 50
    
    delay(5000);  // Esperar 5 segundos antes de repetir el ciclo
}