#include <iostream>
using namespace std;

#include "Diccionario.h"

Diccionario::Nodo::Nodo(const string & laClave, int elDato)
   : clave{laClave}, dato{elDato}, izquierdo{nullptr}, derecho{nullptr} {
}

Diccionario::Diccionario() : raiz{nullptr}, laTalla{0} {
}
  
void Diccionario::insertar(const string & unaClave, int unDato) {
   insertar(unaClave, unDato, raiz);
}

void Diccionario::insertar(const string & unaClave, int unDato, Nodo * & n) {
   if (n == nullptr) {
      n = new Nodo(unaClave, unDato);
      laTalla++;
   } else if (unaClave < n->clave)
      insertar(unaClave, unDato, n->izquierdo);
   else if (unaClave > n->clave)
      insertar(unaClave, unDato, n->derecho);
   // No insertamos duplicados
}

Diccionario::Nodo * Diccionario::minimoEnSubarbol(Nodo * n) const { // Siendo n != nullptr
   if (n->izquierdo == nullptr)
      return n;
   return minimoEnSubarbol(n->izquierdo);
}

void Diccionario::eliminar(const string & unaClave) {
   eliminar(unaClave, raiz);
}

void Diccionario::eliminar(const string & unaClave, Nodo * & n) {
   if (n == nullptr)
      return;
   if (unaClave < n->clave)
      eliminar(unaClave, n->izquierdo);
   else if (unaClave > n->clave)
      eliminar(unaClave, n->derecho);
   else if (n->izquierdo != nullptr && n->derecho != nullptr) {
      Nodo * nodoMinimo = minimoEnSubarbol(n->derecho);
      n->dato = nodoMinimo->dato;
      n->clave = nodoMinimo->clave;
      eliminar(n->clave, n->derecho);
   } else {
      Nodo * basura = n;
      if (n->izquierdo != nullptr)
	 n = n->izquierdo;
      else
	 n = n->derecho;
      delete basura;
      laTalla--;
   }
}

int & Diccionario::buscar(const string & unaClave) const {
   return buscar(unaClave, raiz);
}

int & Diccionario::buscar(const string & unaClave, Nodo * n) const {
   if (n == nullptr)
      throw string("No existe ningun elemento en el diccionario con la clave buscada.");
   if (unaClave < n->clave)
      return buscar(unaClave, n->izquierdo);
   if (unaClave > n->clave)
      return buscar(unaClave, n->derecho);
   return n->dato;
}

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

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

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

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

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