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

#include "GrafoNoDirigido.h"
#include "ColaDePrioridad.h"

GrafoNoDirigido::Arco::Arco(int elVecino, float elPeso, Arco * elSiguiente)
  : vecino{elVecino}, peso{elPeso}, siguiente{elSiguiente} {

}

GrafoNoDirigido::Vertice::Vertice()
  : primerArco{nullptr}, grado{0} {

}

void GrafoNoDirigido::mostrar() const {

   cout << "Arcos para cada vertice: " << endl;
   for (int v = 0; v < vertices.size(); v++) {
      cout << "  vertice " << v << ":" << endl;
      for (Arco * arco = vertices[v].primerArco; arco != nullptr; arco = arco->siguiente)
	 cout << "    " << v << "---" << arco->vecino << " (peso = " << arco->peso << ")" << endl;
      cout << endl;
   }
  

}

GrafoNoDirigido::GrafoNoDirigido(const char * nombreFichero) {

   ifstream flujoFichero(nombreFichero);

   if (! flujoFichero.is_open() )
      throw string("ERROR: imposible abrir el fichero ") +  nombreFichero;

   string linea;
   char tipoLinea;
   int cantidadVertices = -1, mayorVertice = -1;
  
   struct DatosArco {
      int origen, destino;
      float peso;
   } datosArco;

   vector<DatosArco> datos;

   while(getline(flujoFichero, linea)) {
      istringstream flujoLinea(linea);
      if (flujoLinea >> tipoLinea)
	 if (tipoLinea == 'n') {
	    if (!(flujoLinea >> cantidadVertices) || cantidadVertices <= 0)
	       throw string("ERROR: cantidad de vertices incorrecta en el fichero ") +  nombreFichero;
	 } else if (tipoLinea == 'a') {
	    if (!(flujoLinea >> datosArco.origen >> datosArco.destino >> datosArco.peso))
	       throw string("ERROR: arco incompleto en el fichero ") +  nombreFichero;
	    if (datosArco.origen < 0 || datosArco.destino < 0)
	       throw string("ERROR: vertice negativo en el fichero ") +  nombreFichero;
	    datos.push_back(datosArco);
	    mayorVertice = max(mayorVertice, datosArco.origen);
	    mayorVertice = max(mayorVertice, datosArco.destino);
	 }
   }
  
   flujoFichero.close();

   if (cantidadVertices != -1) {
      if (mayorVertice >= cantidadVertices)
	 throw string("ERROR: vertice supera cantidad de vertices declarada en el fichero ") +  nombreFichero;
   } else
      if (mayorVertice == -1)
	 throw string("ERROR: no hay vertices en el fichero ") +  nombreFichero;
      else
	 cantidadVertices = mayorVertice + 1;

   vertices.resize(cantidadVertices);

   for (const auto & datosArco : datos) {
      vertices[datosArco.origen].primerArco = new Arco(datosArco.destino,
						       datosArco.peso,
						       vertices[datosArco.origen].primerArco);
      vertices[datosArco.origen].grado++;
      vertices[datosArco.destino].primerArco = new Arco(datosArco.origen,
							datosArco.peso,
							vertices[datosArco.destino].primerArco);
      vertices[datosArco.destino].grado++;
   }

}

int GrafoNoDirigido::cantidadDeVertices() const {

   return vertices.size();

}


void GrafoNoDirigido::mostrarCaminoOptimoConPesos(int origen, int destino) const {
   
   int cantidadDeVertices = vertices.size();
					       
   ColaDePrioridad colaDePrioridad(cantidadDeVertices);

   vector<float> pesoCaminoOptimo(cantidadDeVertices, numeric_limits<float>::infinity());
   vector<int> padre(cantidadDeVertices, -1);

   pesoCaminoOptimo[origen] = 0;

   for (int v = 0; v < cantidadDeVertices; v++)
      colaDePrioridad.insertar(v, pesoCaminoOptimo[v]);

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();

      cout << "vertice elegido: " << verticeElegido << "\tpeso: " << pesoCaminoOptimo[verticeElegido] << endl;

      if (verticeElegido == destino || pesoCaminoOptimo[verticeElegido] == numeric_limits<float>::infinity())
	 break;

      for (Arco * arco = vertices[verticeElegido].primerArco; arco != nullptr; arco = arco->siguiente) {
	 int vecino = arco->vecino;
	 float nuevoPeso = pesoCaminoOptimo[verticeElegido] + arco->peso;
	 if (nuevoPeso < pesoCaminoOptimo[vecino]) {
	    pesoCaminoOptimo[vecino] = nuevoPeso;
	    padre[vecino] = verticeElegido;
	    colaDePrioridad.cambiarPrioridad(vecino, nuevoPeso);
	 }
      }
   }

   if (padre[destino] == -1)
      cout << "No existe camino desde " << origen << " hasta " << destino << endl;
   else {
      int v = destino;
      cout << "Camino optimo: " << v;
      while (v != origen) {
	 v = padre[v];
	 cout << " --- " << v;
      };
      cout << endl;
   }

}

void GrafoNoDirigido::mostrarCaminoOptimoConPesos(int origen, int destino, const vector<float> & distanciaRecta) const {

   int cantidadDeVertices = vertices.size();
					       
   ColaDePrioridad colaDePrioridad(cantidadDeVertices);

   vector<float> pesoCaminoOptimo(cantidadDeVertices, numeric_limits<float>::infinity());
   vector<int> padre(cantidadDeVertices, -1);

   pesoCaminoOptimo[origen] = distanciaRecta[origen];

   for (int v = 0; v < cantidadDeVertices; v++)
      colaDePrioridad.insertar(v, pesoCaminoOptimo[v]);

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();

      cout << "vertice elegido: " << verticeElegido << "\tpeso: " << pesoCaminoOptimo[verticeElegido] << endl;

      if (verticeElegido == destino || pesoCaminoOptimo[verticeElegido] == numeric_limits<float>::infinity())
	 break;

      for (Arco * arco = vertices[verticeElegido].primerArco; arco != nullptr; arco = arco->siguiente) {
	 int vecino = arco->vecino;
	 float nuevoPeso = pesoCaminoOptimo[verticeElegido] - distanciaRecta[verticeElegido] + arco->peso + distanciaRecta[vecino];
	 if (nuevoPeso < pesoCaminoOptimo[vecino]) {
	    pesoCaminoOptimo[vecino] = nuevoPeso;
	    padre[vecino] = verticeElegido;
	    colaDePrioridad.cambiarPrioridad(vecino, nuevoPeso);
	 }
      }
   }

   if (padre[destino] == -1)
      cout << "No existe camino desde " << origen << " hasta " << destino << endl;
   else {
      int v = destino;
      cout << "Camino optimo: " << v;
      while (v != origen) {
	 v = padre[v];
	 cout << " --- " << v;
      };
      cout << endl;
   }

}