// relations.c : definit le point d'entree pour l'application .
//
typedef int bool;
#define false 0
#define true -1

#include "stdlib.h"
#include "memory.h"
#include "stdio.h"
#include "string.h"

////////////////////////////////////////
// Exercice 1: Classement des Relations

typedef enum{
	FRERE = 2, COUSIN, PARENT, ONCLE, EPOUX, AMI, VIT, CONNAIT,
	CHEF, COLLEGUE, LOCATAIRE, TRAVAILLE, PROPRIETAIRE, SITUE, DECOUVERT
}rtype;

bool est_lien_parente(rtype id){
	return (id == FRERE || id == COUSIN || id == PARENT || id == ONCLE); 
}
bool est_lien_professionel(rtype id){
	return (id == CHEF || id == COLLEGUE); 
}
bool est_lien_connaissance(rtype id){
	return (id == EPOUX || id == AMI || id == CONNAIT || id == VIT);
}

static char* RelationsTable[] = {
	[0] = "omega", [1] = "inconnue",
	[2] = "frère ou soeur de", [3] = "cousin ou cousine de", [4] = "père ou mère",
	[5] = "oncle ou tante de", [6] = "époux ou épouse de", [7] = "ami de",
	[8] = "vit avec", [9] = "connait", [10] = "supérieur de",
	[11] = "collègue de", [12] = "locataire de", [13] = "travaille à",
	[14] = "propriétaire de", [15] = "situé à", [16] = "découvert à"
};

// PRE CONDITION: id > 1 
char* toStringRelation(rtype id){
	return RelationsTable[id];
}

////////////////////////////////////////
// Exercice 2: Liste de pointeurs

typedef struct s_node{
	void *val;  // pointeur vers objet quelconque
	struct s_node *suiv;
}*listeg;
#define LONG_NOM_MAX 64
typedef enum{
	PERSONNE=1, OBJET, ADRESSE, VILLE
}etype;
typedef struct s_entite{
	char nom[LONG_NOM_MAX]; // le nom de l entite p.ex " Peugeot 106 "
	etype ident; // l identifiant associe, p.ex OBJET
}*Entite;
//3.1 les structures de donnees
typedef struct s_sommet{
	struct s_node* larcs;
	Entite x;
}*Sommet;

typedef struct s_arc{
	rtype t; 
	struct s_entite* x;
}*Arc;

typedef struct s_relations{
	listeg listDeRelations;
}*Relations;

listeg listegnouv(){
	return NULL;
}
listeg adjtete(listeg lst, void *x){
	listeg new = malloc(sizeof(struct s_node));
	if (new == NULL) {
        fprintf(stderr, " malloc == NULL fonction adjtete(lst,x) \n");
        exit(EXIT_FAILURE);
    }
	new->val = x;
	new->suiv = lst;
	return new;
}
listeg adjqueue(listeg lst, void *x){
	listeg new = malloc(sizeof(struct s_node));
	if (new == NULL) {
        fprintf(stderr, " malloc == NULL fonction adjqueue(lst,x) \n");
        exit(EXIT_FAILURE);
    }
	new->val = x;
	new->suiv = NULL;
	if( lst != NULL ){
		listeg copy = lst;
		while(copy->suiv != NULL){
			copy = copy->suiv; 
		}
		copy->suiv = new;
		return lst;
	}else
		return new;
}
listeg suptete(listeg lst){
	listeg deuxieme = lst->suiv;
	free(lst);
	return deuxieme;
}

void *tete(listeg lst){
	return lst->val;
}
int longueur(listeg lst){
	int res = 0;
	if( lst == NULL )
		return res;
	res++;
	listeg copy = lst;
	while(copy->suiv != NULL){
		copy = copy->suiv; 
		res++;
	}
	return res;
}
bool estvide(listeg lst){
	return lst == NULL;
}
void detruire(listeg lst){
	if( estvide(lst) )
		return;
	if(lst->suiv == NULL){
		free(lst);
		return;
	}
	listeg copy = lst;
	while(copy != NULL){
		copy = copy->suiv;
		free(lst);
		lst = copy;
	}
}//
listeg rech(listeg lst, void *x, int(*comp)(void *, void *)){
	listeg resultat = listegnouv();
	int i=0;
	while(lst != NULL){
		if( comp(lst->val, x)==0 ){
			resultat = adjqueue(resultat, lst->val);
			i++;
		}
		lst = lst->suiv;
	}
	printf("			%d  \n", i);
	return resultat;
}

////////////////////////////////////////
// Exercice 3: Construction du graphe
/*
#define LONG_NOM_MAX 64
typedef enum{
	PERSONNE=1, OBJET, ADRESSE, VILLE
}etype;
typedef struct s_entite{
	char nom[LONG_NOM_MAX]; // le nom de l entite p.ex " Peugeot 106 "
	etype ident; // l identifiant associe, p.ex OBJET
}*Entite;
//3.1 les structures de donnees
typedef struct s_sommet{
	struct s_node* larcs;
	Entite x;
}*Sommet;

typedef struct s_arc{
	rtype t; 
	struct s_entite* x;
}*Arc;

typedef struct s_relations{
	listeg listDeRelations;
}*Relations;
*/
//3.2 les constructeurs
Entite creerEntite(char *s, etype e){
	Entite newEntity = malloc(sizeof(struct s_entite));
	if (newEntity == NULL) {
        fprintf(stderr, " malloc == NULL fonction creerEntite(s,e) \n");
        exit(EXIT_FAILURE);
    }
	strcpy(newEntity->nom, s);
	newEntity->ident = e;
	return newEntity;
}
Sommet nouvSommet(Entite e){
	if(e == NULL){
		fprintf(stderr, " nouvSommet(e) erreur e == NULL ici fonction nouvSommet(e) \n");
    	exit(EXIT_FAILURE);
	}
	Sommet s = malloc(sizeof(struct s_sommet));
	if (s == NULL) {
        fprintf(stderr, " malloc == NULL fonction nouvSommet(e) \n");
        exit(EXIT_FAILURE);
    }
	s->x = e;
	s->larcs = listegnouv();
	return s;
}
Arc nouvArc(Entite e, rtype type){
	if(e == NULL){
		fprintf(stderr, " nouvSommet(e) erreur e == NULL ici fonction nouvArc(e,type) \n");
    	exit(EXIT_FAILURE);
	}
	Arc bow = malloc(sizeof(struct s_arc));
	if (bow == NULL) {
        fprintf(stderr, " malloc == NULL fonction nouvArc(e,type) \n");
        exit(EXIT_FAILURE);
    }
	bow->t = type;
	bow->x = e;
	return bow;
}
void relationInit(Relations *g){
	*g = malloc(sizeof(struct s_relations));
	if(*g == NULL){
		fprintf(stderr, " malloc == NULL function relationInit(*g) \n");
    	exit(EXIT_FAILURE);
	}
	(*g)->listDeRelations = listegnouv();
}
void relationFree(Relations *g){
	// il faut free g, il faut aussi free g->listeDeRelations (qui est un listeg), 
	// 999 et il faut free g->listeDeRelations->val (qui est un sommet),
	// 999 et il faut free g->listeDeRelations->val->x (qui est une entite),
	// 999 et il faut free g->listeDeRelations->val->larcs (qui est un listeg),
	// 999 et il faut free tous les g->listeDeRelations->val->larcs->val (qui sont des arcs),
	// 999 et il faut free tous les g->listeDeRelations->val->larcs->val->x (qui sont des entites)
	
	// commençont par tous les g->listeDeRelations->val->larcs->val->x et du val qui va avec
	listeg tete = (*g)->listDeRelations;
	while( tete != NULL ){
		free( ((Sommet)(tete->val))->x );
		listeg LarcsDuSommet = ((Sommet)(tete->val))->larcs;
		listeg LarcTete = LarcsDuSommet;  // la tete de larcs la liste listeg du sommet
		while( LarcsDuSommet != NULL ){
			free( ((Arc)( LarcsDuSommet->val ))->x );
			((Arc)( LarcsDuSommet->val ))->x = NULL;
			free(  ((Arc)( LarcsDuSommet->val ))  );
			LarcsDuSommet->val = NULL;
			LarcsDuSommet = LarcsDuSommet->suiv;
		}
		detruire(LarcTete);
		free( ((Sommet)(tete->val)) );
		tete->val = NULL;
		tete = tete->suiv;
	}
	detruire( (*g)->listDeRelations );
	(*g)->listDeRelations = NULL;
	free(*g);
	*g = NULL;
}

//3.3 les comparaisons
int compEntite(void *e, void *string){
	if (e == NULL || string == NULL) {
        return 0;
    }
	if( strcmp( ((Entite)e)->nom, string ) == 0 ){
		return 1;
	}
	return 0;
}
int compSommet(void *s, void *string){
	if (s == NULL || string == NULL) {
        return 0;
    }
	if( strcmp( ((Sommet)s)->x->nom, string ) == 0 ){
		return 1;
	}
	return 0;
}
int compArc(void *a, void *string){
	if (a == NULL || string == NULL) {
        return 0;
    }
	if( strcmp( ((Arc)a)->x->nom, string ) == 0 ){
		return 1;
	}
	return 0;
}

//3.4 ajout d'entites et de relations
void adjEntite(Relations g, char *nom, etype t){
	listeg copy = g->listDeRelations;
	while(copy != NULL){
		if( ((Sommet)(copy->val))->x->nom == nom ){
			printf("check \n");
			return;
		}
		copy = copy->suiv;
	}
	g->listDeRelations = adjqueue(g->listDeRelations, nouvSommet(creerEntite(nom, t)));
}
// PRE CONDITION: id doit etre coherent avec les types des sommets correspondants a x et y
//                p.ex si x est de type OBJET, id ne peut pas etre une relation de parente
// PRE CONDITION: strcmp(nom1,nom2)!=0
void adjRelation(Relations g, char *nom1, char *nom2, rtype id){
	Sommet sommet1 = NULL;
	Sommet sommet2 = NULL;
	Entite deuxiemeEntite = NULL;
	listeg copy = g->listDeRelations;
	while( copy != NULL ){
		if( strcmp(((Sommet)(copy->val))->x->nom, nom1)==0 ){
			sommet1 = (Sommet)(copy->val);
		}
		if( strcmp(((Sommet)(copy->val))->x->nom, nom2)==0 ){
			sommet2 = (Sommet)(copy->val);
		}
		copy = copy->suiv;
	}
	listeg copyLarcs = ((Sommet)(g->listDeRelations->val))->larcs;
	while( copyLarcs != NULL ){
		if( ((Arc)(copyLarcs))->x->nom == nom2 ){
			((Arc)(copyLarcs))->t = id;
			return;
		}
		copyLarcs = copyLarcs->suiv;
	}
	sommet1->larcs = adjqueue(sommet1->larcs, (Arc)nouvArc(creerEntite(sommet2->x->nom, sommet2->x->ident), id));
	sommet2->larcs = adjqueue(sommet2->larcs, (Arc)nouvArc(creerEntite(sommet1->x->nom, sommet1->x->ident), id));
}

////////////////////////////////////////
// Exercice 4: Explorer les relations entre personnes

// 4.1 listes de relations
listeg en_relation(Relations g, char *x){
	listeg res = listegnouv();
	listeg copyTete = g->listDeRelations;
	while(copyTete != NULL){
		if(  strcmp( ((Sommet)(copyTete->val))->x->nom, x ) == 0 ){
			return ((Sommet)(copyTete->val))->larcs;
		}
		copyTete = copyTete->suiv;
	}
	return res;
}

listeg chemin2(Relations g, char *x, char *y){		// on renvoit une LISTE D ENTITES
	listeg LarcsOfX = en_relation(g, x);
	listeg LarcsOfY = en_relation(g, y);
	
	listeg XEntites = listegnouv();			// on va stocker toutes les entites en relation avec x et y 
	listeg YEntites = listegnouv();
	listeg RES = listegnouv();				// puis mettres dans RES les entités en commun sauf x et y
	listeg LarcsOfX_copy = LarcsOfX;
	listeg LarcsOfY_copy = LarcsOfY;
	
	while(LarcsOfX_copy != NULL){
		XEntites = adjqueue(XEntites, ((Arc)(LarcsOfX_copy->val))->x );
		LarcsOfX_copy = LarcsOfX_copy->suiv;
	}
	while(LarcsOfY_copy != NULL){
		YEntites = adjqueue(YEntites, ((Arc)(LarcsOfY_copy->val))->x );
		LarcsOfY_copy = LarcsOfY_copy->suiv;
	}
	listeg XEntites_copy = XEntites;
	listeg YEntites_copy = YEntites;
	
	while(XEntites_copy != NULL){
		YEntites_copy = YEntites;
		while(YEntites_copy != NULL){
			//printf("a \n");
			if( compEntite(XEntites_copy->val, ((Entite)(YEntites_copy->val))->nom) ){
				RES = adjqueue(RES, XEntites_copy->val );
				printf("check \n");
				//printf("		___________	%s \n", ((Entite)(RES->val))->nom );
			}
			YEntites_copy = YEntites_copy->suiv;
		}
		XEntites_copy = XEntites_copy->suiv;
	}
	detruire(XEntites);
	detruire(YEntites);
	return RES;
}
// 4.2 verifier un lien de parente
// PRE CONDITION: strcmp(x,y)!=0
bool ont_lien_parente(Relations g, char *x, char *y){
	return false;
}

// 4.3 tester connaissances
// PRE CONDITION: les sommets correspondants � x et y sont de type PERSONNE
// PRE CONDITION: strcmp(x,y)!=0
bool se_connaissent(Relations g, char *x, char *y){
	return 0;
}

// PRE CONDITION: les sommets correspondants � x et y sont de type PERSONNE
// PRE CONDITION: strcmp(x,y)!=0
bool se_connaissent_proba(Relations g, char *x, char *y){
	return false;
}
// PRE CONDITION: les sommets correspondants � x et y sont de type PERSONNE
// PRE CONDITION: strcmp(x,y)!=0
bool se_connaissent_peutetre(Relations g, char *x, char *y){
	return false;
}

////////////////////////////////////////
// Exercice 5: Affichages
static char* etype_string[] = { [PERSONNE] = "personne", [OBJET] = "objet", [ADRESSE] = "adresse",
[VILLE] = "ville"};

void affichelg(listeg l, void(*aff)(void *)){
	while( l != NULL ){
		aff(l->val);
		l = l->suiv;
	}
}	

void afficheEntite(void *x){
	printf("%s :%s\n", ((Entite)x)->nom, etype_string[ ((Entite)x)->ident] );
}
void afficheArc(void *x){
	printf(" --%s-->", toStringRelation(((Arc)x)->t));
	afficheEntite( ((Arc)(x))->x );
}

////////////////////////////////////////
// Exercice 6: Parcours
void affiche_degre_relations(Relations r, char *x){
	
}


int main(){
	int i,j;
	
	Relations r; relationInit(&r);
	// ajouter les entites de l'exemple
	char *tabe[] ={"KARL","LUDOVIC","CELINE","CHLOE","GILDAS","CEDRIC","SEVERINE",
		"PEUGEOT 106" ,"1, RUE DE LA RUE","STRASBOURG" };
	for (i = 0; i < 7; i++) 
		adjEntite(r, tabe[i], PERSONNE);
	adjEntite(r, tabe[7], OBJET);
	adjEntite(r, tabe[8], ADRESSE);		//
	adjEntite(r, tabe[9], VILLE);
	// ajouter les relations de l'exemple
	adjRelation(r, tabe[0], tabe[1], FRERE);		//
	adjRelation(r, tabe[0], tabe[2], AMI);
	adjRelation(r, tabe[0], tabe[3], CONNAIT);
	adjRelation(r, tabe[0], tabe[5], COUSIN);
	adjRelation(r, tabe[0], tabe[7], PROPRIETAIRE);
	adjRelation(r, tabe[0], tabe[8], PROPRIETAIRE);
	adjRelation(r, tabe[3], tabe[4], VIT);
	adjRelation(r, tabe[5], tabe[6], EPOUX);
	adjRelation(r, tabe[5], tabe[8], LOCATAIRE);
	adjRelation(r, tabe[7], tabe[8], DECOUVERT);
	adjRelation(r, tabe[8], tabe[9], SITUE);
	
	// explorer les relations
	printf("%s est en relation avec:\n", tabe[0]);
	affichelg(en_relation(r, tabe[0]),afficheArc);
	printf("\n");
	for (i = 0; i < 7; i++) for (j = i + 1; j < 10; j++){
		printf("<%s> et <%s> ont les relations communes:\n", tabe[i], tabe[j]);
		listeg ch = chemin2(r, tabe[i], tabe[j]);
		affichelg(ch, afficheEntite);
		printf("\n");
		detruire(ch);
	}
	printf("\n\n");

	return 0; /////
	for (i = 0; i < 10; i++) for (j = i + 1; j < 10; j++)
	{
		printf("<%s> et <%s> ont lien de parente: %s\n",
			tabe[i], tabe[j], ont_lien_parente(r, tabe[i], tabe[j]) ? "vrai" : "faux");
	}
	printf("\n");
	for (i = 0; i < 7; i++)
	{
		for (j = i + 1; j < 7; j++)
		{
			printf("<%s> et <%s> se connaissent: %s\n",
				tabe[i], tabe[j], se_connaissent(r, tabe[i], tabe[j]) ? "vrai" : "faux");
			printf("<%s> et <%s> se connaissent tres probablement: %s\n",
				tabe[i], tabe[j], se_connaissent_proba(r, tabe[i], tabe[j]) ? "vrai" : "faux");
			printf("<%s> et <%s> se connaissent peut etre: %s\n",
				tabe[i], tabe[j], se_connaissent_peutetre(r, tabe[i], tabe[j]) ? "vrai" : "faux");
		}
		printf("\n");
	}

	affiche_degre_relations(r, tabe[3]);

	relationFree(&r);

	printf("\nPRESS RETURN\n");
	char buff[64]; fscanf(stdin, "%s", buff);
    return 0;
}