#include "libtbxcast.h"
#include "libtbxcast_priv.h"
#include <netinet/in.h>

/* fichiers de librairie standard */
#include <stdio.h>
#include <stdlib.h>
#include <netdb.h>
#include <string.h>
#include <limits.h>

#include <arpa/inet.h>


/* table de routage */
struct rt_entry *rtable;

/* table de routage inversee */
struct rev_rt *rev_rtable;

/* matrice de liens */
int *rmatrix;

/* imprime une adresse IPv6 */
void printAdr(struct in6_addr adr)
	{
	int i;

	for(i = 0; i < 16; i++)
		printf("%x ",adr.s6_addr[i]);
}

/* fonctions de debouggage, a ne pas utiliser */
struct rt_entry* _getRoutingTable() { return rtable; }

struct rev_rt* _getReverseTable() {	return rev_rtable; }

int* _getRoutingMatrix() { return rmatrix; }


int TBXcastAddRoute(int source, int dest, struct in6_addr dest_int, struct q_o_s qos)
{
	struct rt_entry *new_entry;
	struct rev_rt *new_rev;
	struct rev_rt *cur_rev;
	
	new_entry = (struct rt_entry*)(malloc(sizeof(struct rt_entry)));
	
	if (new_entry == NULL)
		return TBXCAST_FAILURE;
	
	new_rev = (struct rev_rt*)(malloc(sizeof(struct rev_rt)));
	
	if (new_rev == NULL)
		return TBXCAST_FAILURE;
	
	
	new_entry->source = source;
	new_entry->dest = dest;
	new_entry->dest_int = dest_int;
	new_entry->qos = qos;
	
	new_entry->next = rtable;
	rtable = new_entry;
	
	
	new_rev->interface = dest_int;
	new_rev->node = dest;
	
	/* ajout dans la table inverse */
	
	cur_rev = rev_rtable;
	

	if (cur_rev != NULL)
		while (cur_rev->next != NULL)
		{
			if ( (cur_rev->next)->node > new_rev->node)
				break;
			
			cur_rev = cur_rev->next;		
		}
	
		
	if (cur_rev == NULL) // si la table est vide
	{
		rev_rtable = new_rev;
		new_rev->next = NULL;
	}
	else if (cur_rev == rev_rtable) // si on est au debut de la table
	{
		if ( rev_rtable->node > new_rev->node) // on rajoute avant
		{
			new_rev->next = rev_rtable;
			rev_rtable = new_rev;
		}
		else // on rajoute apres
		{
			new_rev->next = rev_rtable->next;
			rev_rtable->next = new_rev;
		}
	}
	else if (cur_rev->next == NULL) // si on est au bout
	{
		cur_rev->next = new_rev;
		new_rev->next = NULL;
	}
	else // cas normal
	{
		new_rev->next = cur_rev->next;
		cur_rev->next = new_rev;
	}
	
	return TBXCAST_SUCCESS;
}

/* fonction pour compter le nombre de noeuds */

int _count_nodes()
{
	int count = 0;
	struct rev_rt *cur_rev;
	
	if (rev_rtable != NULL)
		count = 1;
	
	
	cur_rev = rev_rtable;
	
	while (cur_rev != NULL)
	{
		if (cur_rev->next != NULL)
			if (cur_rev->next->node != cur_rev->node)
				count++;
		
		cur_rev = cur_rev->next;
	}
	
	
	return count;
}

/* fonction pour recuperer le noeud d'une interface */
int _get_node(struct in6_addr addr)
{
	struct rev_rt *cur_rev;
	cur_rev = rev_rtable;
	
	while (cur_rev != NULL)
	{
		if (IN6_ARE_ADDR_EQUAL(&addr, &(cur_rev->interface)))
			return cur_rev->node;
					
		cur_rev = cur_rev->next;
	}
	
	return -1;
}

/* recupere l'addresse destinataire d'un lien */
struct in6_addr _get_address(int source, int dest)
{
	struct in6_addr undef = IN6ADDR_ANY_INIT;
	struct rt_entry *cur_rtable;
	cur_rtable = rtable;
	
	while (cur_rtable != NULL)
	{
		if (cur_rtable->source == source && cur_rtable->dest == dest)
			return cur_rtable->dest_int;
		
		cur_rtable = cur_rtable->next;
	}
	
	
	return undef;
}

/* fonction transformant une chaine de caracteres en une adresse IP */
struct in6_addr _mk_in6_addr(char *str)
{
	struct in6_addr addr;
	
	inet_pton(AF_INET6, str, &addr);
	
	return addr;
}

int TBXcastInitTopology()
{
	rtable = NULL;
	rev_rtable = NULL;
	
	return TBXCAST_SUCCESS;
}

int TBXcastCreateRoutingMatrix()
{
	int nbnodes = _count_nodes();
	
	struct rt_entry *cur_rtable;
	cur_rtable = rtable;
	
	rmatrix = (int*)( malloc( sizeof(int) * nbnodes * nbnodes) );
	memset(rmatrix, 0, sizeof(int) * nbnodes * nbnodes);
	
	while (cur_rtable != NULL)
	{
// 		printf("%d : %d\n", cur_rtable->source, cur_rtable->dest);
		rmatrix[cur_rtable->source * nbnodes + cur_rtable->dest] = 1;
		cur_rtable = cur_rtable->next;
	}
	
	return TBXCAST_SUCCESS;
}




/*
fonction créant l'arbre de routage pour pouvoir être envoyé
NOTE : surement optimisable (appliquer l'algo directement avec les structures ???)
*/
int TBXcastCreateTree(struct in6_addr src, int groupid, struct tbxcast6_node** gtree)
{
		
	/*****************************************************
				variables
	******************************************************/
	/* variables de structure */	
	int i,j;
	int nb_dests = TBXcastCountMembers(groupid); // on suppose que la source n'est pas dans le groupe
	
	int nbnodes = _count_nodes();
	
	struct in6_addr *addr_dests = (struct in6_addr*)(malloc(nbnodes * sizeof(struct in6_addr))); 	// tableau des adresses ip des destinataires
		
	struct tbxcast6_node *tree;
	
	/* variables de l'algo */	
	int src_i;				// indice de la source
#define INIT_INT_TAB(n) (int*)(malloc(n * sizeof(int)))
	
	int *dests = INIT_INT_TAB(nbnodes); 	// tableau des indices des destintaires	
	int *distances = INIT_INT_TAB(nbnodes);// distances de la source au sommet i
	int *pred = INIT_INT_TAB(nbnodes);		// prédécesseur de i dans l'arbre
	int *sommets = INIT_INT_TAB(nbnodes);	// sommets deja utilisés dans l'arbre
	int s = 0;
	int infinity = INT_MAX;			// valeur très grande de début
	int fin = 0;			// condition d'arret

	int *pred_elag = INIT_INT_TAB(nbnodes);
	int nb_addrs_elag = 0;
	
	int *pred_courant = INIT_INT_TAB(nbnodes);
	int p = 0;
	
	int *noeuds;
	
	/*****************************************************
			recuperation des structures
	******************************************************/
	
	/* récupération de la source */
	src_i = _get_node(src);
	
// 	printf("source : %d\n", src_i);
	
	/* recuperation de la liste des adresses des membres du groupe */
	TBXcastListMembers(addr_dests, nb_dests, groupid);
	
	// recuperation des indices des destinataires dans le graphe	
	for(i = 0; i < nb_dests; i++){
		dests[i] = _get_node(addr_dests[i]);
	}
	
	printf("affichage des destinataires\n");
	for (i = 0; i < nb_dests; i++) {
		printf("%d ",dests[i]);
	}
	printf("\n");
	
	/*****************************************************
					algo
	******************************************************/
	
	// initialisation des sommets du graphe liés a la racine
	for (i = 0; i < nbnodes; i++) {
		if (rmatrix[src_i*nbnodes + i] != 0) { // il y a une arête entre la src et i dans le graphe
			distances[i] = rmatrix[src_i*nbnodes + i];
			pred[i] = src_i;
		}
		else {
			distances[i] = infinity;
			pred[i] = -1;
		}
	}
	
	// initialisation de la racine	
	sommets[s++] = src_i;
	pred[src_i] = -1;
	distances[src_i] = 0;
	/*
	printf("affichage de l'arbre initial\n");
	for(i=0; i<nbnodes; i++){
		printf("som=%d, pred=%d, d=%d\n", i, pred[i], distances[i]);
	}
	printf("sommets utilises : ");
	for(i=0; i<s; i++){
		printf("%d ", sommets[i]);
	}
	*/
	/* Recherche des chemins de longueurs minimales */
	while (!fin) {
	
		// si tous les destinataires peuvent atteints par la source, on arrete l'algo
		fin = 1;
		for (i = 0; i<nb_dests && fin; i++) {
			fin = (distances[dests[i]] != infinity);
		}
		
		// sinon
		if (!fin) {
			
			// on prend le sommet non encore dans l'arbre avec la distance minimale a la source
			int som = 0;
			int dmin = infinity;
			
			for (i = 0; i < nbnodes; i++) {
				// i n'appartient pas aux sommets de l'arbre
				int appartient = 0;
				for (j = 0; j < s && !appartient; j++) {
					appartient = ( i == sommets[j] );
				}
				
				// i a la plus petite distance pour le moment
				if ( !appartient && distances[i] < dmin) {
					som = i;
					dmin = distances[i];
				}
			}
			
			/*  mise a jour des variables */
			sommets[s++] = som;
			
			// mise a jour des distances des sommets i reliés à som et non encore pris dans l'arbre
			for (i = 0; i < nbnodes; i++) {
				
				// i est relié a som
				if (rmatrix[som*nbnodes + i] != 0) {
				
					// i n'appartient pas aux sommets de l'arbre
					int appartient = 0;
					for (j = 0; j < s && !appartient; j++) {
						appartient = (i == sommets[j]);
					}
					
					// on met a jour la distance de src a i si elle est plus petite
					if (!appartient && distances[i] > distances[som] + rmatrix[som*nbnodes + i]) {
						distances[i] = distances[som] + rmatrix[som*nbnodes+i];
						pred[i] = som;
					}
					
				}
			} //for sommets relies a som
		} // if ! fin
	} // boucle algo
	/*
	printf("affichage de l'arbre final\n");
	for(i=0; i<nbnodes; i++){
		printf("som=%d, pred=%d, d=%d\n", i, pred[i], distances[i]);
	}
	printf("sommets utilises : ");
	for(i=0; i<s; i++){
		printf("%d ", sommets[i]);
	}
	printf("\n\n");
	*/
	/*****************************************************
				elagage de l'arbre
	******************************************************/
	// les seules feuilles doivent etre des destinataires, on supprime donc les autres branches
	
	for(i = 0; i < nbnodes; i++)
		pred_elag[i] = -1;
	
	// on prend chaque destinataires et on recopie les predecesseurs en remontant dans l'arbre
	for(j = 0; j < nb_dests; j++) {
		i = dests[j];
		while (i >= 0) {
			pred_elag[i] = pred[i];
			i = pred[i];
		}		
	}
	
	/*
	printf("affichage de l'arbre elague\n");
	for(i=0; i<nbnodes; i++){
		printf("som=%d, pred=%d, d=%d\n", i, pred_elag[i], distances[i]);
	}
	printf("sommets utilises : ");
	for(i=0; i<s; i++){
		printf("%d ", sommets[i]);
	}
	printf("\n\n");
	*/
	//on récupère le nouveau nombre d'adresses
	for(i = 0; i < nbnodes; i++){
		if (pred_elag[i] != -1) nb_addrs_elag++;
	}
	
	// on ajoute 1 pour compter la source
	nb_addrs_elag++;
	
	/*****************************************************
		transformation de l'arbre en structure TBXcast
	******************************************************/
	tree = (struct tbxcast6_node*)(malloc( sizeof(struct tbxcast6_node) * nb_addrs_elag ));
		
	p = 0;
	// pile des noeuds parcourus (en indices dans les tableaux internes)
	pred_courant[p++] = 0;
	
	// tableaux des noeuds dans l'arbre
	noeuds = INIT_INT_TAB(nb_addrs_elag);

	noeuds[0] = src_i;
	tree[0].tbx6n_lgbm = (1<<1)|0; // on initialise la longueur a 1
	tree[0].tbx6n_addr = src;
	
	i=1;
	while (i < nb_addrs_elag) {
	
		int trouve = 0;
		
		for (j = 0; j < nbnodes && !trouve; j++) {
		
			//printf("indice du pred courant %d\n", pred_courant[p-1]);
			// on recupere le prochain successeur du pred en sommet de pile (qui n'a donc pas ete utilise)
			int utilise = 0;
			int k;
			int dest;
			
			for (k = 0; k < i && !utilise; k++) {
				utilise = (j == noeuds[k]);
			}
			
			if ( !utilise && pred_elag[j] == noeuds[pred_courant[p - 1]]) {
			
				//printf("noeud choisi %d\n", j);
				// on a trouve un successeur non encore placé dans l'arbre
				trouve = 1;
				noeuds[i] = j;
				
				// pour tous les ancetres (les predecesseurs), on augmente la lg de 1
				for (k = 0; k < p; k++) {
// 					printf("ajout dans %d\n", pred_courant[k]);
					tree[ pred_courant[k] ].tbx6n_lgbm = 
						((TBXCAST6_NODE_SUBTREELEN(tree[pred_courant[k]].tbx6n_lgbm) + 1) << 1) 
						| TBXCAST6_NODE_ISDEST(tree[pred_courant[k]].tbx6n_lgbm);
				}
					
				dest = 0;
				
				// on verifie si j est un destinataire
				for (k = 0; k < nb_dests && !dest; k++) {
					dest = (dests[k] == j);
				}
				
				// on l'ajoute dans l'arbre
				tree[i].tbx6n_lgbm = (1 << 1) | dest; // on initialise la longueur a 1
				tree[i].tbx6n_addr = _get_address(noeuds[pred_courant[p - 1]], j);
// 				printf("%d -> %d :: addr : ", noeuds[pred_courant[p - 1]], j);
// 				printAdr(tree[i].tbx6n_addr);
// 				printf("\n");
				// c'est le prochain noeud dont il faut trouver les successeurs
				pred_courant[p++] = i;
				i++;
			}
		}
		
		// si on ne trouve plus de successeur, on revient en arriere
		if (!trouve)
			p--;
	
	}
	
	free(addr_dests);
	free(dests);
	free(distances);
	free(pred);
	free(sommets);
	free(pred_elag);
	free(pred_courant);
	free(noeuds);
	
	/*
	printf("taille de l'arbre : %d\n", TBXCAST6_NODE_SUBTREELEN(tree[0].tbx6n_lgbm));
	
	for (i = 0; i < TBXCAST6_NODE_SUBTREELEN(tree[0].tbx6n_lgbm); i++)
	{
		printf("%d  -  l : %d , d : %d, addr :", i, TBXCAST6_NODE_SUBTREELEN(tree[i].tbx6n_lgbm),	TBXCAST6_NODE_ISDEST(tree[i].tbx6n_lgbm));
		printAdr(tree[i].tbx6n_addr);
		printf("\n");
	}
	*/
	*gtree = tree;
	
	return TBXCAST_SUCCESS;
}