#include <stdio.h>
 
void intenta_modificar_arreglo( const int b[] );
 
/* Inicia la ejecucion */
int main()
{
	int a[] = { 1, 2, 10 };
 
	intenta_modificar_arreglo( a );
 
	printf( "%d %d %d\n", a[0], a[1], a[2] );
 
	return 0;
} /* Fin de main */
 
/*------------------Definicion de funciones-----------------------*/
void intenta_modificar_arreglo( const int b[] )
{
	b[0] /= 2;
	b[1] /= 2;
	b[2] /= 2;
} /* Fin de funcion intenta_modificar_arreglo */
 

/*
 
FIC - 2º GRADO - Algortimos
Practica 4
Maquina donde se han testado los algoritmos:
Equipo portatil personal. Intel(R) Core(TM) i3 CPU M 370 @ 2.40GHz x64
 
*/
 
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <limits.h>
#include <math.h>
#include "lista.h"
 
typedef int ** matriz;
 
// algoritmo de prim
lista prim(matriz m, int tam) {
    int min, i, j, r, k=0;
    arista a;
    lista l;
    int *masProximo = (int *) malloc(tam*sizeof(int));
    int *distanciaMinima = (int *) malloc(tam*sizeof(int));
    crear_lista(&l);
    distanciaMinima[0] = -1;
    for(i = 1; i < tam; i++) {
        masProximo[i] = 0;
        distanciaMinima[i] = m[i][0];
    }
    for (r=1; r<tam; r++) { /* bucle voraz */
        min = INT_MAX;
        for (j=1;j<tam;j++) {
            if (0<=distanciaMinima[j] && distanciaMinima[j]<min) {
                min = distanciaMinima[j];
                k = j;
            }
        }
		a.x = masProximo[k]; a.y = k; a.peso = min;
		insertar(a,&l);
		distanciaMinima[k] = -1;
		for (j=1;j<tam;j++) {
			if (m[j][k] < distanciaMinima[j]) {
				distanciaMinima[j] = m[j][k];
				masProximo[j] = k;
			}
		}
    }
    free(masProximo);
    free(distanciaMinima);
    return l;
}
 
// crea una matriz
matriz crear_matriz(int n) {
    int i;
    matriz aux;
    if ((aux = (int **) malloc(n*sizeof(int *))) == NULL)
        return NULL;
    for (i=0; i<n; i++)
        if ((aux[i] = (int *) malloc(n*sizeof(int))) == NULL)
            return NULL;
    return aux;
}
 
// genera la matriz del primer ejemplo
matriz matriz_primer_ejemplo() {
	int i,j;
	matriz m = (matriz)crear_matriz(5);
	m[0][1] = 1; m[0][2] = 8; m[0][3] = 4; m[0][4] = 7;
	m[1][2] = 2; m[1][3] = 6; m[1][4] = 5;
	m[2][3] = 9; m[2][4] = 5;
	m[3][4] = 3;
	for (i=0; i<5; i++)
		for (j=0; j<=i; j++)
			if (i==j)
				m[i][j] = 0;
			else
				m[i][j] = m[j][i];
	return m;
}
 
// genera la matriz del segundo ejemplo
matriz matriz_segundo_ejemplo() {
	int i,j;
	matriz m = (matriz)crear_matriz(4);
	m[0][1] = 1; m[0][2] = 4; m[0][3] = 7;
	m[1][2] = 2; m[1][3] = 8;
	m[2][3] = 3;
	for (i=0; i<4; i++)
		for (j=0; j<=i; j++)
			if (i==j)
				m[i][j] = 0;
			else
				m[i][j] = m[j][i];
 
	return m;
}
 
// genera la matriz del tercer ejemplo
matriz matriz_tercer_ejemplo() {
	int i,j;
	matriz m = (matriz)crear_matriz(7);
	m[0][1] = 7; m[0][2] = 99; m[0][3] = 5; m[0][4] = 99; m[0][5] = 99; m[0][6] = 99;
	m[1][2] = 8; m[1][3] = 9; m[1][4] = 7; m[1][5] = 99; m[1][6] = 99;
	m[2][3] = 99; m[2][4] = 5; m[2][5] = 99; m[2][6] = 99;
	m[3][4] = 15; m[3][5] = 6; m[3][6] = 99;
	m[4][5] = 8; m[4][6] = 9;
	m[5][6] = 11;
	for (i=0; i<7; i++)
		for (j=0; j<=i; j++)
			if (i==j)
				m[i][j] = 0;
			else
				m[i][j] = m[j][i];
	return m;
}
 
void inicializar_matriz(matriz m, int n) {
    /* Crea un grafo completo no dirigido con pesos aleatorios entre 1 y n */
    int i, j;
    for (i=0; i<n; i++)
        for (j=i+1; j<n; j++)
            m[i][j] = rand() % n + 1;
    for (i=0; i<n; i++)
        for (j=0; j<=i; j++)
            if (i==j)
                m[i][j] = 0;
            else
                m[i][j] = m[j][i];
}
 
void liberar_matriz(matriz m, int n) {
    int i;
    for (i=0; i<n; i++)
        free(m[i]);
    free(m);
}
 
void solucion(lista l) {
 
    pnodo it = primera(l);
    int peso_total = 0;
    printf("Aristas: ");
    while (it != NULL) {
        printf("(%d, %d) ", it->elemento.x, it->elemento.y);
        peso_total += it->elemento.peso;
        it = siguiente(it);
    }
    printf("\nPeso total minimo: %d\n", peso_total);
    eliminar_lista(&l);
}
 
void test () {
	printf("\n- test para probar el correcto funcionamiento del algoritmo -\n\n");
	matriz m = matriz_primer_ejemplo();
	matriz n = matriz_segundo_ejemplo();
	matriz o = matriz_tercer_ejemplo();
	printf("Primer ejemplo.\n");
	solucion(prim(m,5));
	printf("\nSegundo ejemplo.\n");
	solucion(prim(n,4));
	printf("\nTercer ejemplo.\n");
	solucion(prim(o,7));
	printf("\n");
	liberar_matriz(m,5);
	liberar_matriz(n,4);
	liberar_matriz(o,7);
}
 
double microsegundos() {
	struct timeval t;
	if (gettimeofday(&t, NULL) < 0 )
		return 0.0;
	return (t.tv_usec + t.tv_sec * 1000000.0);
}
 
double obtener_tiempo(int N, int *umbral){
	#define ITER 1000
	int i;
	double t1, t2, t3, t4, t5, t6, t;
	matriz M = crear_matriz(N);
	inicializar_matriz(M,N);
	t1 = microsegundos();
	prim(M,N);
	t2 = microsegundos();
	t = t2-t1;
	liberar_matriz(M,N);
	*umbral = 0; // t < 500us
	if (t<500) {
		*umbral = 1; // t >= 500us
		matriz A = crear_matriz(N);
		// t3 = tiempo de inicializacion + tiempo prim
		for (i=1; i<=ITER; i++) {
			t1 = microsegundos();
			inicializar_matriz(A,N);
			prim(A,N);
			t2 = microsegundos();
			t3 += (t2-t1);
		}
		// t6 = tiempo de inicializacion
		for (i=1; i<=ITER; i++) {
			t4 = microsegundos();
			inicializar_matriz(A,N);
			t5 = microsegundos();
			t6 += (t5-t4);
		}
		t = (t3-t6) / ITER;
		liberar_matriz(A,N);
	}
	return (t<0 ? -t : t);
}
 
void medicion_tiempos() {
 
	#define REPS 6
	int n, N, it; // variables para control de bucles y parámetros de entrada
	int umbral; // umbral de tiempo de ejecucion (500 us) { 1 = Supera umbral, 0 = No supera umbral }
	double t; // tiempo de ejecucion
	double h, g, f; // valores para acotar
 
	printf("- Medicion de tiempos del algoritmo -\n\n");
 
	printf("-> h(n) = cota subestimada\n");
	printf("-> g(n) = cota ajustada\n");
	printf("-> f(n) = cota sobrestimada\n");
	printf("\n-------------------------------------------------------------------------\n");
	printf("\n%9s%13s%13s%13s%13s%10s\n","n", "t(n)", "t(n)/h(n)", "t(n)/g(n)", "t(n)/f(n)", "Umbral"); // encabezado
 
	n = 16;
	for (it=1; it<=REPS; it++) {
		n = n*2-1;
		N = (int)sqrt(n);
		t = obtener_tiempo(N, &umbral);
		h = t / pow(N*N, 1.8); // t(n)/h(n)
		g = t / pow(N*N, 2); // t(n)/g(n)
		f = t / pow(N*N, 2.2); // t(n)/f(n)
		printf("%9d%13.6f%12.6f%13.6f%13.6f%8d\n", N*N, t, h, g, f, umbral);
	}
	printf("\n-------------------------------------------------------------------------\n");
 
}
 
int main () {
 
	printf("\nPractica 4: Analisis del algortimo de Prim.\n");
	test();
	medicion_tiempos();
 
}