#include "./implems.c"
#include "./struct_tp2.h"
#include "./plotout.h"
#include <stdio.h>
#include <stdlib.h>


// g une liste d'adjacence décrivant le graphe
// out res un tableau de taille g->n
// ensures
	// out res [i] contient le degré du noeud i
void calc_deg(adjlist *g, unsigned long *out_res) {
	unsigned long i;
	for (i = 0; i < g->n; i += 1) {
		out_res[i] = g->cd[i+1] - g->cd[i];
	}
	return;
}




// g une liste d'adjacence décrivant le graphe
// eta_tab un tableau d'entiers de taille g->n (initialisé à zero)
// c_tab un tableau d'entiers de taille g-> n (initialisé à zero)
// eta_tab contient l'orde du k-orderind :
//  	eta[0] = noe1
// 		eta[1] = noe2 etc
void core_decomposition(adjlist *g, unsigned long *eta_tab, int *c_tab) {
	// mise à zero des tableaux
	for (unsigned long iter = 0; iter < g->n; iter+=1) {
		eta_tab[iter] = 0;
		c_tab[iter] = 0;
	}
	unsigned long v;
	tp2_t deg_track;
	int i, c;
	i = g->n;
	c = 0;

	// initialise la structure
	deg_track = new_tp2(g->n);

	for (unsigned long k = 0; k < g->n; k += 1) {
		int tmp_deg = (g->cd[k+1]) - (g->cd[k]);
		if (set_deg(deg_track, k, tmp_deg) == 0) {
			printf("error initialisation deg_struct\n");
			return;
		}
	}
	for (unsigned long k = 0; k < g->n; k += 1) {
		int tmp_deg = (g->cd[k+1]) - (g->cd[k]);
		if (get_deg(deg_track, k) != tmp_deg) {
			printf("samuh à merdé\n");
			return;
		}
	}
    printf("initialisation terminée\n");


	// itère jusqu'à avoir traité tous les noeuds
	while (i > 0) {
		// trouver un élément de degré min dans le graphe
		v = elem_min_deg(deg_track);

		int tmp_deg = get_deg(deg_track, v);
		if (tmp_deg < 0) {
			printf("error elem_min_deg est de degré -1 (tous les noeuds ont été retirés)\n");
			for (unsigned long k = 0; k < g->n; k += 1) {
				if (get_deg(deg_track, k) != -1) {
					printf("%lu est de degré %i\n", k, get_deg(deg_track, k));
					printf("samuh à merdé\n");
				}
			}
			return;
		}

		c = (c>tmp_deg) ? c : tmp_deg;

		// mettre à jour les degrés par "retrait" du noeud v
			// retrait de v
		if (remove_elem(deg_track, v) == 0) {
			printf("error en retirant le noeud v\n");
			return;
		}
			// mise à jour du degré des voisins
		unsigned long i_find_vois;
		for (i_find_vois = g->cd[v]; i_find_vois < g->cd[v+1]; i_find_vois += 1) {
			if (decrease_deg(deg_track, g->adj[i_find_vois]) == 0) {
				printf("error pour dec deg d'un noeud\n");
				return;
			}
		}

		// sauvegarde des valeurs pour le k-ordering et la core value du noeud
		eta_tab[i - 1] = v;
		c_tab[v] = c;
		i -= 1;
		// printf("c = %i\nnoeuds retirés = %lu\n", c, g->n - i);
	}

	// destruction de la structure
	if (destruct_tp2(deg_track) == 0) {
		printf("error destruction de la structure tp2\n");
		return;
	}

	return;
}



int max_c_val(int* tabl, int size) {
	int max = tabl[0];
	for(int i = 0; i < size; i +=1) {
		// printf("|%i|", tabl[0]);
		if (tabl[i] > max) {
			max = tabl[i];
		}
	}
	return max;
}




// retourne l'indice de noeud dans eta correspondant au densest core ordering prefix
unsigned long compute_densest_core_ordering_prefix(adjlist *g, unsigned long *eta, long double *res_av_deg_dens, long double *res_edge_dens) {
	unsigned long i,j,tmp_noeud;
	unsigned long *eta_inv;
	eta_inv = (unsigned long*) malloc((g->n)*sizeof(unsigned long));

	// clacul etainv (chaque entrée eta_inv[v] correspond à l'indice auquel le noeud v est ajouté dans le préfixe)
	for (i = 0; i < g->n; i+=1) {
		eta_inv[eta[i]] = i;
	}


	unsigned long grand_n, grand_m;
	grand_n = g->n;
	grand_m = g->e;

	long double max_dense = ((long double) grand_m)/((long double) grand_n); //densité du graphe complet
	unsigned long max_prefix = (g->n) - 1; // préfixe où tous les noeuds de éta sont pris


	// itère pour tous les préfixes (partant du plus grand)
	i = (g->n)-1;
	while (i > 0) {
		tmp_noeud = eta[i]; //le noeud à retirer à cette étape

		i -= 1;

		// actualise les valeurs de grand_n et grand_m
		grand_n -= 1;
		for (j = g->cd[tmp_noeud]; j < g->cd[tmp_noeud + 1]; j += 1) {
			// si son voisin a été ajouté avant lui dans l'ordre préfixe, alors on décrémente le nombre d'arrêtes
			if (eta_inv[tmp_noeud] > eta_inv[g->adj[j]]) {
				grand_m -= 1;
			}
		}

		// calcul la nouvelle densité
		long double new_density = ((long double) grand_m)/((long double) grand_n);

		if (max_dense < new_density) {
			max_dense = new_density;
			max_prefix = i;

			// mise à jour des résultats
			*res_av_deg_dens = new_density;
			*res_edge_dens = ((long double) grand_m)/((((long double) grand_n)*(((long double) grand_n) - 1))/2.);

		}




	}
	return max_prefix;
}




int main(int argc, char **argv) {
	if (argc < 2) {
		printf("un argument est attendu\n");
		return 1;
	}



	adjlist *g;
	time_t t1, t2, t3;

	// PARSING
	t1=time(NULL);

	printf("Reading edgelist from file %s\n",argv[1]);
	g=al_readedgelist(argv[1]);
	t3 = time(NULL);
	printf("- edge list time = %ldh%ldm%lds\n",(t3-t1)/3600,((t3-t1)%3600)/60,((t3-t1)%60));
	// printf("- edge list time = %I64dh%I64dm%I64ds\n",(t3-t1)/3600,((t3-t1)%3600)/60,((t3-t1)%60));

	printf("Number of nodes: %lu\n",g->n);
	printf("Number of edges: %lu\n",g->e);

	printf("Building the adjacency list\n");
	mkadjlist(g);

	t2=time(NULL);

	printf("- Overall time = %ldh%ldm%lds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));
	// printf("- Overall time = %I64dh%I64dm%I64ds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));



	// calcul du core ordering et des core value

	printf("compiting core ordering and core decomposition...\n");
	unsigned long* eta;
	int* c;
	c = (int*) malloc((g->n)*sizeof(int));
	eta = (unsigned long*) malloc((g->n)*sizeof(unsigned long));



	t1=time(NULL);
	core_decomposition(g, eta, c);
	t2=time(NULL);

	
	printf("- Overall time = %ldh%ldm%lds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));
	// printf("- Overall time = %I64dh%I64dm%I64ds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));
	printf("core value du graphe : %i\n", max_c_val(c, g->n));

	// calcul du densest prefix graph
	printf("computing densest prefix graph...\n");
	unsigned long indix_densest;
	long double densest_cop_av_deg_dens;
	long double densest_cop_edge_dens;
	t1=time(NULL);
	indix_densest = compute_densest_core_ordering_prefix(g, eta, &densest_cop_av_deg_dens, &densest_cop_edge_dens);
	t2=time(NULL);
	printf("- Overall time = %ldh%ldm%lds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));
	// printf("- Overall time = %I64dh%I64dm%I64ds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));
	printf("densest core prefix :\n\taverage degre density : %Lf\n\tedge density : %Lf\n\tsize : %lu\n", densest_cop_av_deg_dens, densest_cop_edge_dens, indix_densest+1);
	// printf("densest core prefix :\n\taverage degre density : %f\n\tedge density : %f\n\tsize : %lu\n", (double) densest_cop_av_deg_dens, (double) densest_cop_edge_dens, indix_densest+1);






	// EXERCICE 2 
		// Calcul des degrés des noeuds pour plot
	unsigned long *deg_tabl = (unsigned long*) malloc((g->n)*sizeof(unsigned long));
	calc_deg(g, deg_tabl);


	plot_out_2D_i_ul("scholar.csv", g->n, c, deg_tabl);

	free_adjlist(g);
	free(deg_tabl);
	free(eta);
	free(c);
	return 0;
}