#include <iostream>
#include <string>
#include <limits>
using namespace std;

#include "Conjunto.h"

Conjunto::Nodo::Nodo(int elDato) : dato{elDato}, izquierdo{nullptr}, derecho{nullptr} {
}

Conjunto::Conjunto() : raiz{nullptr} {
}
  
void Conjunto::insertar(int unDato) {
   insertar(unDato, raiz);

   if (!esArbolBinarioDeBusqueda())
      throw string("ERROR al insertar ") + to_string(unDato);

}

void Conjunto::insertar(int unDato, Nodo * & n) {
   if (n == nullptr)
      n = new Nodo(unDato);
   else if (unDato < n->dato)
      insertar(unDato, n->izquierdo);
   else if (unDato > n->dato)
      insertar(unDato, n->derecho);
   // No insertamos duplicados
}

int Conjunto::minimoEnSubarbol(Nodo * n) const { // Sabiendo que n != nullptr
   if (n->izquierdo == nullptr)
      return n->dato;
   return minimoEnSubarbol(n->izquierdo);
}

void Conjunto::eliminar(int unDato) {
   eliminar(unDato, raiz);

   if (!esArbolBinarioDeBusqueda())
      throw string("ERROR al eliminar ") + to_string(unDato);;

}

void Conjunto::eliminar(int unDato, Nodo * & n) {
   if (n == nullptr)
      return;
   if (unDato < n->dato)
      eliminar(unDato, n->izquierdo);
   else if (unDato > n->dato)
      eliminar(unDato, n->derecho);
   else if (n->izquierdo != nullptr && n->derecho != nullptr) {
      n->dato = minimoEnSubarbol(n->derecho);
      eliminar(n->dato, n->derecho);
   } else {
      Nodo * basura = n;
      if (n->izquierdo != nullptr)
	 n = n->izquierdo;
      else
	 n = n->derecho;
      delete basura;
   }
}

bool Conjunto::buscar(int unDato) const {
   Nodo * n = raiz;
   while (n != nullptr) {
      if (unDato < n->dato)
	 n = n->izquierdo;
      else if (unDato > n->dato)
	 n = n->derecho;
      else
	 return true;
   }
   return false;
}

/*
bool Conjunto::esArbolBinarioDeBusqueda() const {
   int maximoInt = numeric_limits<int>::max();
   int minimoInt = numeric_limits<int>::min();
   return raiz == nullptr || datosEstanEntreLimites(raiz, minimoInt, maximoInt);
}

bool Conjunto::datosEstanEntreLimites(Nodo * n, int limiteInferior, int limiteSuperior) const {
   return n->dato >= limiteInferior
          && n->dato <= limiteSuperior
          && (n->izquierdo == nullptr || datosEstanEntreLimites(n->izquierdo, limiteInferior, n->dato))
          && (n->derecho == nullptr || datosEstanEntreLimites(n->derecho, n->dato, limiteSuperior));
}
*/

bool Conjunto::esArbolBinarioDeBusqueda() const {
   int maximoInt = numeric_limits<int>::max();
   int minimoInt = numeric_limits<int>::min();
   return datosEstanEntreLimites(raiz, minimoInt, maximoInt);
}

bool Conjunto::datosEstanEntreLimites(Nodo * n, int limiteInferior, int limiteSuperior) const {
   return n == nullptr
          || (n->dato >= limiteInferior
              && n->dato <= limiteSuperior
              && datosEstanEntreLimites(n->izquierdo, limiteInferior, n->dato)
              && datosEstanEntreLimites(n->derecho, n->dato, limiteSuperior));
}