#include "algo.h"
#include<fstream>
#include<iostream>


/* lecture dans un fichier: on lit le nombre d'objets,
   le nombre de proprietes,
   puis on lit toutes les valeurs de la relation (0 ou 1) */

void algo::lecture(const string & nom_fic)
{
	int nb_objets,nb_proprietes;
	fstream fic;
	
	int val;
		
	fic.open(nom_fic.c_str(),ios::in);
		if (fic.fail())
			cout<<"fichier d'entree inexistant. ";
			
		else
		{
			
  			fic>>nb_objets;
  			fic>>nb_proprietes;

			for(int k=0;k<nb_objets;k++) relation_a_examiner.objets.push_back(k);
			for(int l=0;l<nb_proprietes;l++) relation_a_examiner.proprietes.push_back(l);
  
  			for(int i=0;i<nb_objets;i++)
  				{
					vector <int> objet;
					for(int j=0;j<nb_proprietes;j++)
						{
							fic>>val;
							objet.push_back(val);
						}
					relation_a_examiner.tableau.push_back(objet);
				}
		}
}

/* sauvegarde des résultats */

void algo::ecriture_resultats(const string & nom_fic)
{
	ofstream fic;
	fic.open(nom_fic.c_str(),ios::out);
	concept conc,conc2;
	stack <concept> pile_inverse;

	// on a empilé les concepts dans l'ordre de leur génération
	// donc pour les stocker dans l'ordre de leur génération
	// on les met dans une autre pile en sens inverse

	while (treillis.size()!=0)
	{
		conc2=treillis.top();
		pile_inverse.push(conc2);
		treillis.pop();
	}

	while (pile_inverse.size()!=0)
	{
		conc=pile_inverse.top();

		int vide=1;
		for(int j=0;j<conc.intension.size();j++)
			if	(conc.intension[j]==1)
			{
				fic<<nom_propriete(j+1)<<" ";
				vide=0;
			}
		if (vide==1) fic<<"vide ";
		fic<<"* ";
		int vide2=1;
		for(int k=0;k<conc.extension.size();k++)
			if	(conc.extension[k]==1)
			{
				fic<<k+1<<" ";
				vide2=0;
			}
		if(vide2==1) fic<<"vide";
		fic<<"\n";
		pile_inverse.pop();

	}
	fic.close();
}


/* Cette méthode calcule le nom d'une propriété à partir du numéro de colonne correspondant
   en utilisant l'ordre suivant:
   a b c d ... z aa bb cc ... zz aaa bbb ccc ddd ... */

string algo::nom_propriete(int num)
{
	string res;
	while (num>0)
	{
		switch(num%26)
		{
		case 0: 
			{
				res=res+'z';
				num=num-26;
				break;
			}
		case 1: 
			{
				res=res+'a';
				num=num-26;
				break;
			}
		case 2: 
			{
				res=res+'b';
				num=num-26;
				break;
			}
		case 3: 
			{
				res=res+'c';
				num=num-26;
				break;
			}
		case 4: 
			{
				res=res+'d';
				num=num-26;
				break;
			}
		case 5: 
			{
				res=res+'e';
				num=num-26;
				break;
			}
		case 6: 
			{
				res=res+'f';
				num=num-26;
				break;
			}
		case 7: 
			{
				res=res+'g';
				num=num-26;
				break;
			}
		case 8: 
			{
				res=res+'h';
				num=num-26;
				break;
			}
		case 9: 
			{
				res=res+'i';
				num=num-26;
				break;
			}
		case 10: 
			{
				res=res+'j';
				num=num-26;
				break;
			}
		case 11: 
			{
				res=res+'k';
				num=num-26;
				break;
			}
		case 12: 
			{
				res=res+'l';
				num=num-26;
				break;
			}
		case 13: 
			{
				res=res+'m';
				num=num-26;
				break;
			}
		case 14: 
			{
				res=res+'n';
				num=num-26;
				break;
			}
		case 15: 
			{
				res=res+'o';
				num=num-26;
				break;
			}
		case 16: 
			{
				res=res+'p';
				num=num-26;
				break;
			}
		case 17: 
			{
				res=res+'q';
				num=num-26;
				break;
			}
		case 18: 
			{
				res=res+'r';
				num=num-26;
				break;
			}
		case 19: 
			{
				res=res+'s';
				num=num-26;
				break;
			}
		case 20: 
			{
				res=res+'t';
				num=num-26;
				break;
			}
		case 21: 
			{
				res=res+'u';
				num=num-26;
				break;
			}
		case 22: 
			{
				res=res+'v';
				num=num-26;
				break;
			}
		case 23: 
			{
				res=res+'w';
				num=num-26;
				break;
			}
		case 24: 
			{
				res=res+'x';
				num=num-26;
				break;
			}
		case 25: 
			{
				res=res+'y';
				num=num-26;
				break;
			}
		}
	}

	return res;
}



/* partitionnement récursif :
   on passe l'ensemble à partitionner, l'intension de l'objet par rapport auquel on va partitionner
   et un vecteur dans lequel on va récupérer les feuilles de l'arbre d'execution
   correspondant à la partition finale */

void algo::partitionnement(const vector <int> & ensemble_a_partitionner,const sous_relation & SR,const int & niveau,vector <vector <int> > &calcul_index)
{
	/* à chaque étape, l'ensemble à partitionner va être divisé
	   en deux: dans l'ensemble gauche on va mettre les propriétés qui appartiennent
	   à l'objet considéré, et dans l'ensemble droite on va mettre les propriétés qui
	   ne lui appartiennnent pas. On va appliquer à ces deux
       ensembles le même procédé en passant à l'objet suivant. Celui-ci s'arrêtera
	   lorsqu'on aura considéré l'ensemble des objets ou lorsque l'ensemble à
	   partitionner ne contiendra qu'une seule propriété.
	*/

	vector < int > droite;
	vector < int > gauche;
	
	/* test d'arrêt sur la taille de l'ensemble */

	if (ensemble_a_partitionner.size()==1)
		{
			calcul_index.push_back(ensemble_a_partitionner);
		}
	else
		{

			// division de l'ensemble à partitionner en deux sous-partitions

			
			for(int i=0;i<ensemble_a_partitionner.size();i++)
			{
				if (relation_a_examiner.tableau[SR.objets[niveau]][ensemble_a_partitionner[i]]==1)
					gauche.push_back(ensemble_a_partitionner[i]);
				else
					droite.push_back(ensemble_a_partitionner[i]);
			}

			
			
			// test pour lancer l'algorithme sur les deux sous-partitions

			if (niveau+1<SR.objets.size())
				{
					if (gauche.size()!=0)
						partitionnement(gauche,SR,niveau+1,calcul_index);
					if (droite.size()!=0)
						partitionnement(droite,SR,niveau+1,calcul_index);
				}
			else	// on arrive à la fin du partitionnement et il y a plusieurs propriétés dans la partition
					// on met l'ensemble de ces propriétés comme élément de la partition
				{
					if (gauche.size()!=0)
						calcul_index.push_back(gauche);
					if (droite.size()!=0)
							calcul_index.push_back(droite);
				}
		}
}


/* algorithme de marquage des concepts dominants dans une partition */

vector <int> algo::marquer_dominants(const vector <vector <int> > & index, const sous_relation & SR)
{
	vector < int > dominants;
	
	for(int k=0;k<index.size();k++) dominants.push_back(0);

	
	/*
		On parcourt les concepts de la partition de droite à gauche
		et on les compare deux à deux.
		En effet, l'algorithme nous garantit que le concept le plus
		à gauche est un non dominant.
		De plus, un concept ne peut en dominer un autre seulement
		si il est placé à droite de celui-ci dans la partition,
		ce qui permet de n'effectuer que la moitié des comparaisons.
	*/
	
	for(int i=index.size()-1;i>0;i--)
		for(int j=i-1;j>-1;j--)

			// on évite de calculer si un concept se domine lui-même

			if (i!=j)
				{
					int domine=1;
					for(int k=0;k<SR.objets.size();k++)
					{
						int i_dedans=1;
						int j_dedans=1;
						for(int a=0;a<index[i].size();a++)
						{
							if (relation_a_examiner.tableau[SR.objets[k]][index[i][a]]==0) i_dedans=0;
						}
						for(int b=0;b<index[j].size();b++)
						{
							if (relation_a_examiner.tableau[SR.objets[k]][index[j][b]]==0) j_dedans=0;
						}
						
		
						if (i_dedans==1)
							if (j_dedans==0)
							{
								domine=0;
							}
					}
					if (dominants[i]==0) dominants[i]=domine;
					
				}
	return dominants;
}



/*
	etape de l'algorithme récursif.
	à chaque étape, on va calculer la sous relation associée
	au concept considéré, on va partitionner l'ensemble d'intensions
	par rapport aux objets de cette sous-relation,
	et on va calculer l'ensemble des successeurs, auxquels on va appliquer
	le même algorithme.
	L'algorithme s'arrête quand il n'y a plus de successeurs non marqués
*/

void algo::etape(const concept & conc, const sous_relation & SR, vector <int> marques)
{
	vector <concept> successeurs;

	vector < vector < int > > index_partition;
			
	vector < int > dominants;

	treillis.push(conc);

	
	partitionnement(SR.proprietes,SR,0,index_partition);

	
	//test d'arrêt
	if (index_partition.size()!=0)
		{
	
			// marquage des dominants
	
			dominants=marquer_dominants(index_partition,SR);

			// test d'arrêt et lancement de l'algorithme sur les successeurs
			for(int m=0;m<index_partition.size();m++)
				if (dominants[m]==0)
				{
					int marque1=0;
					for(int marq=0;marq<index_partition[m].size();marq++)
						if (marques[index_partition[m][marq]]==1) marque1=1;
						if (marque1==0)
						{
							concept suivant;
							for(int copie=0;copie<conc.intension.size();copie++)
								suivant.intension.push_back(conc.intension[copie]);
							for(int copie2=0;copie2<conc.extension.size();copie2++)
								suivant.extension.push_back(conc.extension[copie2]);
					
					
							// calcul successeur
					
							for(int n=0;n<index_partition[m].size();n++)
							{
								suivant.intension[index_partition[m][n]]=1;
							}
			
							for(int o=0;o<SR.objets.size();o++)
								for(int p=0;p<index_partition[m].size();p++)
									if (relation_a_examiner.tableau[SR.objets[o]][index_partition[m][p]]==0)
										suivant.extension[SR.objets[o]]=0;
	
							// calcul sous relation successeur
							sous_relation SR_suivante;
	
							for(int i2=0;i2<suivant.intension.size();i2++)
								if(suivant.intension[i2]==0)
								{
									SR_suivante.proprietes.push_back(i2);
								}
							for(int j2=0;j2<suivant.extension.size();j2++)
								if(suivant.extension[j2]==1)
								{
									SR_suivante.objets.push_back(j2);
								}
							etape(suivant,SR_suivante,marques);
							for(int mar=0;mar<index_partition[m].size();mar++)
								marques[index_partition[m][mar]]=1;
							//mise à jour de marques
						}
				}
		}
}
	



void algo::lancer_algo_berry()
{

	vector<int> extens;
	vector<int> intens;
	vector<int> marques;

	sous_relation SR;
	
	int i,j;

	//initialisation
	
	//l'intension est vide
	
	for(i=0;i<relation_a_examiner.objets.size();i++) extens.push_back(1);
	for(j=0;j<relation_a_examiner.proprietes.size();j++) intens.push_back(0);

	for(i=0;i<relation_a_examiner.proprietes.size();i++) marques.push_back(0);

	concept conc(extens,intens);

	// on calcule la sous-relation associée au concept

	for(int i2=0;i2<conc.intension.size();i2++)
	{
		if(conc.intension[i2]==0) SR.proprietes.push_back(i2);
	}
	for(int j2=0;j2<conc.extension.size();j2++)
	{
		if(conc.extension[j2]==1) SR.objets.push_back(j2);
	}
	
	//premier appel d'une étape: le concept de départ est {}*{objets}

	etape(conc,SR,marques);
}