#include "Grafo.h"
#include "GrafoUtils.h"
#include <iostream>
#include <iterator>
#include <fstream>


// Eu evitaria globais mas complicaria demais a minha vida...
// a não ser que eu colocasse visitaTSP numa clase :-) uhauhaha
int melhor_custo = 10000000;
ListaVertices melhor_caminho(0);


//! Realiza a busca em profundidade no grafo g.
/*!
    \param g o grafo onde faremos a pesquisa...
    \param caminho deve conter o nó inicial da busca (default 0)
    \param parciais OPCIONAL determina se valores parciais são impressos ou não (bool)
    \param custo o custo inicial

    \return o menor caminho
*/
void visitaTSP(Grafo& g, ListaVertices caminho=ListaVertices(1,0), int custo=0,bool parciais=false)
{
	int vertice = 0;
	ListaVertices adj;		  // para guardar a lista de adj...
	ListaVerticesCIterator motorista; // Incrivel o que o sono pode fazer
					  // ao nome de uma variável
	
	// Teste de sanidade...
	if (caminho.size() < 1){
		std::cerr << "O caminho inicial fornecido em visitaTSP deve conter pelo menos um vertice!";
		throw ErroGrafo("Ah! Programa direito po!");
	}

	vertice=caminho.back();		// vertice é o ultimo no caminho...
	g.setCor(vertice,cinza);		// Duh!
	
	// Podando...
	if ( melhor_custo > custo ) {
		// Continua a visita, seguindo para os vizinhos
		adj=g.listaAdjacencia(vertice);
		for ( motorista = adj.begin(); motorista != adj.end(); ++motorista){
			const Vertice& u = *motorista;
			// Wow! Pop It Up!
			// Technotronics.. São os vengaboys do passado?! Putz
			/* Em python eu não tinha que fazer essa marmotagem 
			 * toda de acrescentar e remover 'u' do caminho.... */
			if (g.getCor(u) == branco){
				caminho.push_back(u);
				visitaTSP(g,
					 caminho, // Parcial+aresta
					 custo+g.obtemAresta(vertice,u),
					 parciais);
				caminho.pop_back();
			// Teste de fim da recursão....
			}else if ( (u == caminho[0]) &&  
				   (caminho.size() == g.numeroVertices())){				
			        // custo do trajeto completo....
				custo = custo + g.obtemAresta(vertice,u);
				if (melhor_custo > custo){
					melhor_caminho=caminho; // Ih.... semantica de copia?!
					melhor_custo=custo;
					if (parciais) {
						std::cout << "\nCusto do melhor caminho (parcial): " << custo << "\n";
					}
				}
			}
		}
	} else {
		if ( parciais ){
			std::cout << "+";
		}
	}
			
	// Desfaz a trilha...
	g.setCor(vertice,branco);
}



int main(int argc, char* argv[])
{
        int n = 10;
	int v;

        std::string arquivo;
	std::string saida = "saida";
	
	if (argc > 1) {
		arquivo = std::string(argv[1]);
	}else {
		std::cerr << "Você term que fornecer o nome de um ";
		std::cerr << "arquivo tipo tsp como argumento para continuar. ";
		std::cerr << "Vou tentar continuar com o defaut...";
		std::cerr << "Se der merda a culpa eh sua!\n";
		arquivo = "entrada";
	}
	
	// Fazendo o TSP-Otimo....
        Grafo g= TSPLIB2Grafo(arquivo);
	visitaTSP(g);

	// Gerando saida na tela
	std::cout << "O custo do melhor caminho foi "<< melhor_custo <<"\n";
	std::ostream_iterator<int> stdout_oi (std::cout," ");
	copy(melhor_caminho.begin(),melhor_caminho.end(),stdout_oi);
	std::cout << std::endl;

	// Gerando saida para arquivo
	if (argc > 2){
		saida = std::string(argv[2]);
	} 
	std::ofstream os_saida (saida.c_str());
	if(!os_saida){
		std::cerr << "Ieiiiiiii! Deu pau na geracao da saida.\n";
		exit(1);
	}
	std::ostream_iterator<int> saida_oi (os_saida,"\n");
	copy(melhor_caminho.begin(),melhor_caminho.end(),saida_oi);
	os_saida.close();

}