#include <iostream>
using namespace std;

#include "Conjunto.h"

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

Conjunto::Conjunto() : raiz{nullptr}, laTalla{0} {
}
  
void Conjunto::insertar(int unDato) {
   if (raiz == nullptr)
      insertar(unDato, raiz);
   else {
      Nodo * n = raiz;
      bool fin = false; 
      while (! fin)
	 if (unDato < n->dato)
	    if (n->izquierdo != nullptr)
	       n = n->izquierdo;
	    else {
	       insertar(unDato, n->izquierdo);
	       fin = true;
	    }
	 else if (unDato > n->dato)
	    if (n->derecho != nullptr)
	       n = n->derecho;
	    else {
	       insertar(unDato, n->derecho);
	       fin = true;
	    }
	 else
	    fin = true; // No insertamos duplicados
   }
}  

void Conjunto::insertar(int unDato, Nodo * & n) {
   n = new Nodo(unDato);
   laTalla++;
}

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

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

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


bool Conjunto::buscar(int unDato) const {
   return buscar(unDato, raiz);
}

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

void Conjunto::mostrarOrdenados() const {
   cout << "{";
   mostrarOrdenados(raiz);
   cout << "}";
}

void Conjunto::mostrarOrdenados(Nodo * n) const {
   if (n != nullptr) {
      mostrarOrdenados(n->izquierdo);
      cout << " " << n->dato << " ";
      mostrarOrdenados(n->derecho);
   }
}

void Conjunto::obtenerOrdenados(Nodo * n, vector<int> & v, int & i) const {
   if (n != nullptr) {
      obtenerOrdenados(n->izquierdo, v, i);
      v[i] = n->dato;
      i++;
      obtenerOrdenados(n->derecho, v, i);
   }
}

vector<int> Conjunto::obtenerOrdenados() const {
   vector<int> v(laTalla);
   int i = 0;
   obtenerOrdenados(raiz, v, i);
   return v;
}

int Conjunto::talla() const {
   return laTalla;
}

int Conjunto::consultarMinimo() const {
   if (raiz == nullptr)
      throw string("Intentando consultar minimo de conjunto vacio");
   return minimoEnSubarbol(raiz);
}

void Conjunto::vaciar() {
   vaciar(raiz);
   raiz = nullptr;
   laTalla = 0;
}

void Conjunto::vaciar(Nodo * n) {
   if (n != nullptr) {
      vaciar(n->izquierdo);
      vaciar(n->derecho);
      delete n;
   }
}