#include "Grafo.h"
#include <iostream>


	

/*! Mapeia uma aresta (u,v) para uma posição (i,j) dentro
    da matriz de adjacencias ( que é triangular)
 */
const Aresta Grafo::mapeiaTriangular(Vertice u, Vertice v){
	Aresta a(0,0);
	if (u >= v){
		a.first=u;
		a.second=v;
	}else{
		a.first=v;
		a.second=u;
	}
	
	return a;
}

const Aresta Grafo::mapeiaTriangular(Aresta e)
{
	return mapeiaTriangular(e.first,e.second);
}

//! Insere uma areta na matriz de adj.
void Grafo::insAresta(Vertice u, Vertice v) throw (VerticeDesconhecido)
{
	Aresta e = mapeiaTriangular(u,v);
	try {
		this->matriz_adj[e.first][e.second] = true;
	} catch(std::out_of_range) {
		/* out_of_range podem ser causados apenas por acessos
		   Fora do limite da matriz, ou seja: o valor de
		   u ou de v não está em {0,...|V|-1}
		 */
		throw VerticeDesconhecido("Voce forneceu um valor invalido como vertice.");
	}

}

//! Remove uma areta da matriz de adj.
void Grafo::delAresta(Vertice u, Vertice v) throw (VerticeDesconhecido)
{
	Aresta e = mapeiaTriangular(u,v);
	try {
		this->matriz_adj[e.first][e.second] = false;
	}catch(std::out_of_range){
		/* out_of_range podem ser causados apenas por acessos
		   Fora do limite da matriz, ou seja: o valor de
		   u ou de v não está em {0,...|V|-1}
		 */
		throw VerticeDesconhecido("Voce forneceu um valor invalido como vertice.");
	}

}



//! Obtem o valor de uma "aresta" na matriz.
/*! Função para tratamento direto da matriz de adj.
    Adicionalmente ela garante que o grafo é não-direcionado
    Lança uma exception caso a aresta não exista
 */
int Grafo::getAresta(Vertice u, Vertice v) throw(ArestaDesconhecida,VerticeDesconhecido)
{

	Aresta e = mapeiaTriangular(u,v);

	// Teste de consistência...
	if ( !existeAresta(e) ){
		throw ArestaDesconhecida("A aresta fornecida não existe");
	}

	// Obtem o valor da aresta
	try{
		return matriz_pesos[e.first][e.second];
	} catch(std::out_of_range){
		/* out_of_range podem ser causados apenas por acessos
		   Fora do limite da matriz, ou seja: o valor de
		   u ou de v não está em {0,...|V|-1}
		 */
		throw VerticeDesconhecido("Voce forneceu um valor invalido como vertice.");
	}
}

//! Modifica o valor de uma "aresta" na matriz
/*! Função para tratamento direto da matriz de adj.
    Adicionalmente ela garante que o grafo é não-direcionado
    Lanca uma exception ArestaDesconhecida caso a aresta não exista
 */
void Grafo::setAresta(Vertice u, Vertice v,int peso) throw (ArestaDesconhecida,VerticeDesconhecido)
{
	Aresta e = mapeiaTriangular(u,v);
	
	// Teste de consistência...
	if ( !existeAresta(e) ){
		throw ArestaDesconhecida("A aresta fornecida não existe");
	}
	
	// Modifica o valor da aresta 
	try{
		this->matriz_pesos[e.first][e.second]=peso;
	} catch(std::out_of_range) {
		/* out_of_range podem ser causados apenas por acessos
		   Fora do limite da matriz, ou seja: o valor de
		   u ou de v não está em {0,...|V|-1}
		 */
		throw VerticeDesconhecido("Voce forneceu um valor invalido como vertice.");

	}
}

//!Cria o grafo.
/*! 
 * \param n eh o numero de verticesque o novo gravo deve ter.
 */	
Grafo::Grafo(int n){

	this->n=n;
	// O grafo inicia tendo E == vazio
	this->matriz_adj= std::vector<std::vector<bool> >(n,std::vector<bool>(n,false));
	this->matriz_pesos= std::vector<std::vector<int> >(n,std::vector<int>(n,0));
	
	// Todos os vertices sao inicialmente brancos
	this->cores=std::vector<CorVertice>(n,branco);

}
		
//! Retorna o numero de vértices do grafo
int Grafo::numeroVertices(){
	return this->n;
}

//! Verifica a existencia de uma aresta
/*! 
    Lanca uma VerticeDesconhecido exception caso os vertices
    informados nao existam
    \param u vertice de saida da aresta a ser testada
    \param v vertice de chegada da aresta a ser testada
 */
bool Grafo::existeAresta(Vertice u, Vertice v) throw (VerticeDesconhecido)
{
	Aresta e = mapeiaTriangular(u,v);
	
	try{
		return this->matriz_adj[e.first][e.second];
	} catch(std::out_of_range) {
		/* out_of_range podem ser causados apenas por acessos
		   Fora do limite da matriz, ou seja: o valor de
		   u ou de v não está em {0,...|V|-1}
		 */
		throw VerticeDesconhecido("Voce forneceu um valor invalido como vertice.");

	}
}

//! Verifica a existencia de uma aresta
/*! 
    Lanca uma VerticeDesconhecido exception caso os vertices
    informados nao existam
    \param e aresta a ser testada
 */
bool Grafo::existeAresta(Aresta e) throw (VerticeDesconhecido)
{
	return existeAresta(e.first, e.second);
}


/* //! Retorna uma ListaVertices == V do Grafo G=(V,E)
ListaVerticesCIterator listaVertices(){
	return this.m
}*/

//! Retorna a lista de vertices adjacentes ao vertice n
ListaVertices& Grafo::listaAdjacencia(Vertice vertice)
{
	ListaVertices* adj = new ListaVertices();
	for (Vertice u = 0; u < numeroVertices(); u++){
		if (existeAresta(vertice,u)){
			adj->push_back(u);
		}
	}
	
	return (*adj);
}

//! Lista as arestas do grafo 
ListaArestas& Grafo::listaArestas()
{
	ListaArestas* arestas =  new ListaArestas();
	Vertice i,j;
	
	// Loop nos itens da matriz triangular superior...
	for (i = 1; i < this->numeroVertices(); i++){
		for (j = 0; j < i ; j++){
			if ( existeAresta(i,j) ){
				arestas->push_back(Aresta(i,j));
			}
		}
	}

	return (*arestas);
}

//! Insere uma nova aresta no grafo
/*!
    \param u vertice de saida da aresta a ser inserida
    \param v vertice de chegada da aresta a ser inserida
    \param peso  peso a ser colocado nessa aresta
 */
void Grafo::insereAresta(Vertice u, Vertice v, int peso) throw(ArestaDuplicada,VerticeDesconhecido)
{
	if (existeAresta(u,v)){
		throw ArestaDuplicada("A aresta fornecida já existe.");
	}else{
		insAresta(u,v);
		setAresta(u,v,peso);
	}
}

//! Remove uma aresta.
/*!
    Caso a aresta nao exista, uma exception.
    Caso os vertices nao existam (mencionar arestas com vertices que nem a V pertencem),
    uma exception eh lancada.
 */
void Grafo::removeAresta(Vertice u, Vertice v) throw (ArestaDuplicada,VerticeDesconhecido)
{
	this->delAresta(u,v);
}

//! Retorna o peso de uma aresta.
/*
    Caso ela não exista, uma exception é lancada.
 */
int Grafo::obtemAresta(Vertice u, Vertice v)  throw(ArestaDesconhecida,VerticeDesconhecido)
{
	return getAresta(u,v);
}

//! Modifica o peso de uma aresta.
/*! 
    Caso a aresta nao exista, uma exception eh lancada.
    Caso os vertices nao existam, uma exception eh lancada.
 */
void Grafo::modificaAresta(Vertice u, Vertice v, int peso) throw(ArestaDesconhecida,VerticeDesconhecido)
{
	this->setAresta(u,v,peso);
}
		

//! Modifica a cor de um vértice
void Grafo::setCor(Vertice vertice,CorVertice cor) throw (VerticeDesconhecido)
{
	try{
		this->cores[vertice]=cor;
	} catch(std::out_of_range& e) {
		/* out_of_range podem ser causados apenas por acessos
		   Fora do limite da matriz, ou seja: o valor de
		   u ou de v não está em {0,...|V|-1}
		 */
		throw VerticeDesconhecido("Voce forneceu um valor invalido como vertice.");

	}
}


//! Retorna a cor de um vértice
const CorVertice Grafo::getCor(Vertice vertice) throw (VerticeDesconhecido)
{
	try{
		return this->cores[vertice];
	} catch(std::out_of_range& e) {
		/* out_of_range podem ser causados apenas por acessos
		   Fora do limite da matriz, ou seja: o valor de
		   u ou de v não está em {0,...|V|-1}
		 */
		throw VerticeDesconhecido("Voce forneceu um valor invalido como vertice.");

	}
}

//! Imprime a matriz de adj.
void Grafo::imprimeMatrizAdj()
{
	int i,j,n;
	n = this->numeroVertices();
	
	std::cout << "+-------------- Matriz de Adjacência ----------------+\n";
	for (j = 0; j < n; j++){
		for (i = 0; i < n; i++){
			if ( existeAresta(i,j) ) {
				std::cout << " "<< this->obtemAresta(i,j) << " ";
			}else {
				std::cout << " - ";
			}
		}
		std::cout << "\n";
	}
}

/*
//! Retorna uma copia desse grafo 
def copy(self):
	g=Grafo(self.__n)
	for e in self.listaArestas():
		u,v=e
		g.insereAresta(u,v,self.obtemAresta(u,v))
	return g

//! Retorna o valor da maior aresta.
+*  E se não existir aresta nenhuma?!
def obtemMaiorAresta(self):
	
	arestas=self.listaArestas()
	maior=None
	
	if len(arestas) == 0 :
		return None

	# Obtem um valor inicial para 'maior'
	e=arestas.pop()
	u,v=e
	maior=self.obtemAresta(u,v)
	
	for e in arestas:
		u,v=e
		valor=self.obtemAresta(u,v)
		if valor > maior:
			maior = valor

	return maior
*/