// DiVHA - Distributed Virtual Hypercube Algorithm

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "graph.h"
#include "cisj.h"
#include <math.h>

//auxiliares:
int h(int origem,int destino); //calcula distancia no hipercubo utiizando XOR

int bitcount (unsigned int n); //conta bits setados em 1

bool pertence (int valor,int* lista,int size); //retorna true ou false se valor esta na lista

void mostrarLOG(GRAPH* grafo,int N,int* falhos,int size,int dim); /*mostra resultado, recebe grafo realizados(T), n total de nodos, lista de falhos, tam da lista e dimesao*/

//Main:
int
main(int argc, char** argv){
	static int i,j,x,s,distance,dist,bits,dim,N,num_falhos=0;
	int* falhos;
	GRAPH *grafo;
	node_set* nodos_cis;
	
	if (argc < 2) 
        {
		printf("    Sintaxe: ./trab3 %s dimensoes  falhos[1] ... falhos[n] \n", argv[0]);
		puts("----------------------------------------------------------------------------------------------------------");
		puts("                            Dimensão     - Número de Dimensões )");
		puts("                            Nodos falhos  - Lista de nodos falhos. Ex.:0 1 4   (opcional)");
		return 0;
	}	
	
        //Número de dimensões
	dim = atol(argv[1]);
	
        //Número de nodos
	N = pow(2,dim);
	
        //Número de nodos falhos corresponde no máximo ao número de argumentos passados
	falhos = malloc (sizeof(int)*argc);

	//Criar lista de nodos falhos com base nos argumentos de entrada
	for (i=2;i<argc;i++)
        {
		falhos[num_falhos] = atoi(argv[i]);
		if (falhos[num_falhos] >= N)//controlar nodos falhos dentro do intervalo válido
                {
			printf(" O Nodo falho introduzido [%d] está fora do máximo de nodos possivel [%d - %d].\n ",falhos[num_falhos],0,N-1);
			return 0;
		}//fim if
		num_falhos++;
	}//fim for

	//Inicializar um grafo com uma matriz de adjacencia de tamanho NxN
	grafo = init_graph(N);
	
	
	for (i=0;i<N;i++)
        {
		for (j=0;j<N;j++)
                {
			if ((h(i,j)==1) && (!pertence(i,falhos,num_falhos)))
				addArc(grafo,i,j);
		}//fim for j
	}//fim for i

	for (s=2;s<=dim;s++)
        { 			
		for (distance=2;distance<=s;distance++)
                {				
			for (i=0;i<N;i++)
                        {		
				if (!pertence(i,falhos,num_falhos))
                                {		
					nodos_cis = cis(i,s);		//calcular o cis
					for (x=0;x<nodos_cis->size;x++)
                                        {			//percorrer os elementos do cis
						j = nodos_cis->nodes[x];		
						if ((dijkstra(grafo,i,j,N)>s) && (h(i,j) == distance)) 
							addArc(grafo,i,j);			
					}
				}
			}
		}
	}
	mostrarLOG(grafo,N,falhos,num_falhos,dim);		//log
	free(falhos); 			//Liberar memória da lista de falhos
	freeGraph(grafo,N); 		//Liberar memória do grafo de testes
	return 1;
}


//distancia dos nodos no hipercubo
int h(int origem,int destino)
{
	static unsigned int c;

	//XOR
	c = origem ^ destino;
	return bitcount (c);
}


//count
int bitcount (unsigned int n) 
{
   int count = 0;
   while (n) 
   {
      count += n & 0x1u;
      n >>= 1;
   }
   return count;
}


//pertence
bool pertence (int valor,int* lista,int size)
{
	static int j;
	for (j=0;j<size;j++)
        {
		if (lista[j] == valor)
			return true;
	}
	return false;
}

//mostra
void mostrarLOG(GRAPH* grafo,int N,int* falhos,int size,int dim)
{
	static int i,j,num_testes=0,ind_extr=0;
	int* testes_extras;
	puts("***********************************************************************************************");	
	puts("***********************************************************************************************");
	puts("**                                        RESULTADO                                          **");
	puts("***********************************************************************************************");
	puts("***********************************************************************************************");
	if (size>0)
	{
		printf("   NODOS FALHOS  ->  ");
		for ( i = 0; i < size; i++) 
			printf("  %d  ",falhos[i]);	
		printf(" \n\n ");		
	}

   for ( i = 0; i < N; i++) 
   {
   	testes_extras = malloc (sizeof(int)*N);
   	ind_extr=0;
   	if (!pertence(i,falhos,size))
        {
   		printf("          NODO  %2d  TESTA  O   NODO  ",i);
	   	for ( j = 0; j < N; j ++) 
                {
	         if (grafo->arcs[i][j] == 1)
                 {
	         	if (h(i,j) == 1)
                        {
         			printf(" |  %2d ",j);	         	
         		}
	         	else
                        {
	         		testes_extras[ind_extr]=j;
	         		ind_extr++;
	         	}
	         	num_testes++;	         	
	         }//fim if grafo
	      }//fim for j

	      printf("  |  ");
	      if (ind_extr>0)
              {
	      	printf("    [ TESTES EXTRAS: ");
	   		for ( j = 0; j < ind_extr; j ++)
         			printf("  |  %2d",testes_extras[j]);
	        	printf(" ] ");
	      }//fim if ind_extr
	  puts(""); 
	   free(testes_extras);    //libera memoria grafo de testes extras
       }//fim if pertence
   }//fim for
   puts("");
   puts("**********************************************************************************************");
   printf("         NÚMERO MÁXIMO DE TESTE, SENDO (N*LOG N):  %d\n  ",N*dim);   
   puts("");
   printf("         TOTAL DE TESTES:  %d\n ",num_testes);  
   puts("**********************************************************************************************");
}