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

#include <limits>
#define INFINITO numeric_limits<float>::infinity()

#include "GrafoDirigido.h"

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

}

GrafoDirigido::Vertice::Vertice()
  : primerArcoDeEntrada{nullptr}, primerArcoDeSalida{nullptr}, gradoDeEntrada{0}, gradoDeSalida{0} {

}

void GrafoDirigido::mostrar() const {

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

}

GrafoDirigido::GrafoDirigido(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].primerArcoDeSalida = new Arco(datosArco.destino,
							       datosArco.peso,
							       vertices[datosArco.origen].primerArcoDeSalida);
      vertices[datosArco.origen].gradoDeSalida++;
      vertices[datosArco.destino].primerArcoDeEntrada = new Arco(datosArco.origen,
								 datosArco.peso,
								 vertices[datosArco.destino].primerArcoDeEntrada);
      vertices[datosArco.destino].gradoDeEntrada++;
   }

}

int GrafoDirigido::cantidadDeVertices() const {

   return vertices.size();

}
   
void traza(int indentacion, const string & mensaje) {

   for (int i = 0; i < indentacion; i++) cout << "   ";
   cout << mensaje << endl;

}

#define DESCONOCIDO -INFINITO

float GrafoDirigido::calcularCaminoOptimo(int origen,
					  int destino,
					  vector<float> & resultado,
					  vector<int> & padre,
					  int indentacion) const { // Suponemos grafo aciclico

   traza(indentacion, string("Necesitamos resultado[") + to_string(destino) + "]");
   
   if (resultado[destino] == DESCONOCIDO) {
      if (origen == destino)
	 resultado[destino] = 0;
      else {
	 resultado[destino] = INFINITO; 
	 for (Arco * arco = vertices[destino].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente) {
	    float pesoIncidente = calcularCaminoOptimo(origen, arco->vecino, resultado, padre, indentacion + 1) + arco->peso;
	    if (pesoIncidente < resultado[destino]) {
	       resultado[destino] = pesoIncidente;
	       padre[destino] = arco->vecino;
	    }
	 }
      }
      traza(indentacion, string("Conseguido resultado[") + to_string(destino) + "] = "
	    + to_string(resultado[destino]));
   } else
      traza(indentacion, string("Ya teniamos en tabla resultado[") + to_string(destino) + "]");

   return resultado[destino]; // Vale INFINITO si no tiene incidentes o todos son inalcanzables desde el origen

}

void GrafoDirigido::mostrarCaminoOptimo(int origen, int destino) const {

   int cantidadDeVertices = vertices.size();
   
   vector<float> resultado(cantidadDeVertices, DESCONOCIDO);
   vector<int> padre(cantidadDeVertices, -1);

   float peso = calcularCaminoOptimo(origen, destino, resultado, padre, 0);
  
   if (peso == INFINITO)
      throw string ("El destino ") + to_string(destino) 
	 + string(" es inalcanzable desde el origen ") + to_string(origen);

   cout << endl << "Camino optimo de " << origen << " a " << destino << ":" << endl;
   cout << "  vertices:";
   stack<int> pila;
   for (int vertice = destino; vertice != -1; vertice = padre[vertice])
      pila.push(vertice);
   while(! pila.empty() ) {
      cout << " " << pila.top();
      pila.pop();
   }
   cout << endl << "  peso: " << peso << endl;;

}