#include <iostream>
using namespace std;

#include "Conjunto.h"

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

Conjunto::Conjunto() : raiz{nullptr} {
}
  
void Conjunto::insertar(int unDato) {
   bool insertado = false;
   insertar(unDato, raiz, insertado);
}

void Conjunto::insertar(int unDato, Nodo * & n, bool & insertado) {
   if (n == nullptr) {
      n = new Nodo(unDato);
      insertado = true;
   } else if (unDato < n->dato) {
      insertar(unDato, n->izquierdo, insertado);
      if (insertado)
	 n->tallaIzquierdo++;
   } else if (unDato > n->dato)
      insertar(unDato, n->derecho, insertado);
   // 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) {
   bool eliminado = false;
   eliminar(unDato, raiz, eliminado);
}

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

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

int Conjunto::buscarKesimo(int k) const {
   if (k < 0)
      throw string("Usando buscarKesimo con un valor de k que no existe");
   return buscarKesimo(k, raiz);
}

int Conjunto::buscarKesimo(int k, Nodo * n) const {
   if (n == nullptr) // Si tenemos laTalla, esto se podria sustituir por
      // comprobar que k < laTalla en el metodo anterior
      throw string("Usando buscarKesimo con un valor de k que no existe");
   else if (k < n->tallaIzquierdo)
      return buscarKesimo(k, n->izquierdo);
   else if (k > n->tallaIzquierdo)
      return buscarKesimo(k - (n->tallaIzquierdo + 1), n->derecho);
   else
      return n->dato;
}