#include <iostream>
#include <string>
#include <vector>
#include <fstream>

using namespace std;

#include "My_include.h"

void Hongroise::Fct_Hongroise()
{
	Phase_1();

	Emplacement_Zero.resize(1,0); // Pour cette première possibilité on encadrera le 1er zéro dans la phase2
	
	p=0; // On part de la 1ere possibilité du tableau "tab", celle chargée du fichier	
	while(p<tab.size())
	{
		do{					
			while(Phase_2());
		}while(Phase_3());

		// On rajoute dans la solution dans Solution si elle n'y est pas déjà est que son cout a celle de la solution s
		int s=0;
		while(s<Solution.size())
		{
			int nbr_similitude=0;
			int i=0;
			while(i<nbr_personne)
			{
				int j=0;
				while(j<nbr_personne)
				{
					if(tab[p][i][j]==ZERO_ENCADRE && tab[p][i][j]==tab[s][i][j])
						nbr_similitude++;
					j++;
				}
				i++;
			}

			if(nbr_similitude==nbr_personne)
				break;
			s++;
		}

		if(s==Solution.size()) // Cela signifi qu'on a parcouru toute les solutions sans en trouver de similaire
			if(Calcul_Cout(0)==Calcul_Cout(p)) // Cout de la solution égal au cout de la solution initiale
				Solution.resize(Solution.size()+1, p);
	
		p++;
	}
}

void Hongroise::Lecture_Fichier()
{
	p=0; // Le chargement du fichier se fera forcément sur la 1ere possibilité du tableau "tab"
	int type_pbm;
		
	string name_file;
	cout << "Veuillez entrer le nom du fichier : ";
	cin >> name_file;
	cout << endl;

	ifstream file(name_file);

	file >> nbr_personne;
	file >> type_pbm;
	
	tab.resize( 1, vector< vector <int>>(nbr_personne, vector<int>( nbr_personne, MAX)));

	int l=0, c, classement=1;

	if(type_pbm==1 || type_pbm==2)
	{
		while(l<nbr_personne)
		{
			file >> c;
			tab[p][l][c-1]=classement;
			classement++;

			char temp=file.get();
			temp=file.get();
			if(temp!='f')
			{
				file.unget();
				file.unget();
			}
			else
			{
				l++;
				classement=1;
			}

			if(classement>nbr_personne)
			{
				l++;
				classement=1;
			}
		}
	}

	if(type_pbm==2)
	{
		l=0, classement=1;

		while(l<nbr_personne)
		{
			file >> c;
			tab[p][l][c-1]+=classement;
			classement++;

			char temp=file.get();
			temp=file.get();
			if(temp!='f')
			{
				file.unget();
				file.unget();
			}
			else
			{
				l++;
				classement=1;
			}

			if(classement>nbr_personne)
			{
				l++;
				classement=1;
			}
		}
	}
	
	if(type_pbm==3)
	{
		vector <vector <int>> tab2;
		tab2.resize(nbr_personne, vector<int>(nbr_personne, 1000));
		int l=0, c=0;

		while(l<nbr_personne)
		{
			int lu;
			file >> lu;
			tab2[l][c]=lu;
			c++;

			char temp=file.get();
			temp=file.get();
			if(temp!='f')
			{
				file.unget();
				file.unget();
			}
			else
			{
				l++;
				c=0;
			}

			if(c>=nbr_personne)
			{
				l++;
				c=0;
			}
		}

		l=0, c=0;
		while(l<nbr_personne)
		{
			int lu;
			file >> lu;
			tab[p][l][tab2[l][c]-1]=20-lu;
			c++;

			char temp=file.get();
			temp=file.get();
			if(temp!='f')
			{
				file.unget();
				file.unget();
			}
			else
			{
				l++;
				c=0;
			}

			if(c>=nbr_personne)
			{
				l++;
				c=0;
			}
		}
	}

	tab_cout.resize( nbr_personne, vector<int>( nbr_personne, MAX));
	int i=0;
	while(i<nbr_personne)
	{
		int j=0;
		while(j<nbr_personne)
		{
			tab_cout[i][j]=tab[p][i][j];
			j++;
		}
		i++;
	}
}

void Hongroise::Phase_1()
{
	p=0; // La phase_1 se fait forcément  sur la 1ere possibilité du tableau "tab" (celle chargée du fichier)

	// On soustrait ligne par ligne puis colonne par colonne le plus petit élément de la ligne ou de la colonne
	// ligne par ligne...
	int i, j;
	i=0;
	while(i<nbr_personne)
	{
		j=0;
		int temp=tab[p][i][j++];
		while(j<nbr_personne)
		{
			if(tab[p][i][j]<temp)
				temp=tab[p][i][j];
			j++;
		}
		
		j=0;
		while(j<nbr_personne)
		{
			tab[p][i][j]=tab[p][i][j]-temp;
			j++;
		}

		i++;
	}

	// Colonne par colonne...
	j=0;
	while(j<nbr_personne)
	{
		int i=0;
		int temp=tab[p][i++][j];
		while(i<nbr_personne)
		{
			if(tab[p][i][j]<temp)
				temp=tab[p][i][j];
			i++;
		}
		
		i=0;
		while(i<nbr_personne)
		{
			tab[p][i][j]=tab[p][i][j]-temp;
			i++;
		}

		j++;
	}
}

bool Hongroise::Phase_2()
{
	// On choisi la ligne contenant le moins de zéros
	int i, j;
	int nbr_zero_min=MAX;
	int ligne_moins_zero;
	i=0;
	while(i<nbr_personne)
	{
		j=0;
		int nbr_zero=0;
		while(j<nbr_personne)
		{
			if(tab[p][i][j]==0)
				nbr_zero++;
			j++;
		}
		
		if(nbr_zero<nbr_zero_min && nbr_zero>0)
		{
			nbr_zero_min=nbr_zero;
			ligne_moins_zero=i;
		}

		i++;
	}
	
	if(nbr_zero_min==MAX)
		return 0; // terminé (impossibilité d'encadrer un zéro)

	// Dans la variable ligne_moins_zero on a la ligne avec le moins de zéro
	// On va encadrer le zero indiqué par le tableau Emplacement_Zero
	j=0;
	int i_encadre, j_encadre;
	int emplacement_zero=0;
	while(j<nbr_personne)
	{
		if(tab[p][ligne_moins_zero][j]==0)
		{
			if(emplacement_zero==Emplacement_Zero[p] || Emplacement_Zero[p]==-1)
			{	
				tab[p][ligne_moins_zero][j]=ZERO_ENCADRE;
				i_encadre=ligne_moins_zero;
				j_encadre=j;
				break;
			}
			emplacement_zero++;
		}
		j++;
	}
	if(Emplacement_Zero[p]==0) // Si egal a zéro il y a peut d'etre d'autre zéro a traiter on va donc faire en sorte de les traiter ultérieurement
	{						   // En rajoutant une copie de la configuration actuelle et a la fin de la 1ere dimension de tab et en indiquant quel zéro encadrer ultérieurment
			j=0;
		emplacement_zero=1;
		while(j<nbr_personne)
		{
			if(tab[p][ligne_moins_zero][j]==0)
			{
				tab.resize( tab.size()+1, vector<vector<int>>(nbr_personne, vector<int>( nbr_personne)));
				int ii=0;
				while(ii<nbr_personne)
				{
					int jj=0;
					while(jj<nbr_personne)
					{
						tab[tab.size()-1][ii][jj]=tab[p][ii][jj];
						jj++;
					}
					ii++;
				}
				tab[tab.size()-1][i_encadre][j_encadre]=0;
				Emplacement_Zero.resize(Emplacement_Zero.size()+1, emplacement_zero);

				emplacement_zero++;
			}
			j++;
		}
	}
	Emplacement_Zero[p]=-1;

	// On barre les autres zéro de la ligne et de la colonne du zéro encadré
	i=0;
	while(i<nbr_personne)
	{
		if(tab[p][i][j_encadre]==0)
			tab[p][i][j_encadre]=ZERO_BARRE;
		i++;
	}
	j=0;
	while(j<nbr_personne)
	{
		if(tab[p][i_encadre][j]==0)
			tab[p][i_encadre][j]=ZERO_BARRE;
		j++;
	}

	return 1; // il faudra recommencer la phase 2
}

int Hongroise::Phase_3()
{
	int i, j;
	vector <int> ligne_marquee( nbr_personne, 0);
	vector <int> colonne_marquee( nbr_personne, 0);

	// On marque les lignes ne contenant aucun 0 encadré
	i=0;
	while(i<nbr_personne)
	{
		int zero_encadre=0;
		j=0;
		while(j<nbr_personne)
		{
			if(tab[p][i][j]==ZERO_ENCADRE)
				zero_encadre=1;
			j++;
		}
		
		if(zero_encadre==0)
			ligne_marquee[i]=1;
		i++;
	}
	// Si il n'y en a pas FIN
	int nbr_ligne_marquee=0;
	i=0;
	while(i<nbr_personne)
	{
		if(ligne_marquee[i]==1)
			nbr_ligne_marquee++;
		i++;
	}
	if(nbr_ligne_marquee==0)
		return 0;

	// On marque d'une croix toute colonne qui on un 0 barré sur une ligne marquée
	j=0;
	while(j<nbr_personne)
	{
		i=0;
		while(i<nbr_personne)
		{
			if(tab[p][i][j]==ZERO_BARRE && ligne_marquee[i]==1)
				colonne_marquee[j]=1;
			i++;
		}
		j++;
	}

	// On marque d'une croix toute ligne qui a un 0 encadré dans une colonne marquée
	i=0;
	while(i<nbr_personne)
	{
		j=0;
		while(j<nbr_personne)
		{
			if(tab[p][i][j]==ZERO_ENCADRE && colonne_marquee[i]==1)
				ligne_marquee[j]=1;
			j++;
		}
		i++;
	}

	// Si toute les colonnes sont marqué
	int nbr_colonne_marquee=0;
	j=0;
	while(j<nbr_personne)
	{
		if(colonne_marquee[j]==1)
			nbr_colonne_marquee++;
		j++;
	}
	if(nbr_colonne_marquee==nbr_personne) // Obtention de la solution optimale
	{
		// Si une colonne marquée ne contient pas de zéro encadré
		// On remplace les zéros barrés(resp. encadrés) de cette colonne par des 0 encadrés (resp. barrés)
		j=0;
		while(j<nbr_personne)
		{
			if(colonne_marquee[j]==1)
			{
				int nbr_zero_barre=0;
				i=0;
				while(i<nbr_personne)
				{
					if(tab[p][i][j]==ZERO_BARRE)
						nbr_zero_barre++;
					i++;
				}

				if(nbr_zero_barre==0)
				{
					i=0;
					while(i<nbr_personne)
					{
						if(tab[p][i][j]==ZERO_BARRE)
							tab[p][i][j]=ZERO_ENCADRE;
						else if(tab[p][i][j]==ZERO_ENCADRE)
							tab[p][i][j]=ZERO_BARRE;
						i++;
					}
				}
			}
			j++;
		}
	}


	// "On trace un trait sur chaque ligne non marqué et chaque colonne marqué"
	// On choisi le plus petit élément du tableau non rayé..
	int plus_petit=MAX;
	i=0;
	while(i<nbr_personne)
	{
		j=0;
		while(j<nbr_personne)
		{
			if(tab[p][i][j]==ZERO_ENCADRE || tab[p][i][j]==ZERO_BARRE) // On remet la valeur 0
				tab[p][i][j]=0;

			if(ligne_marquee[i]==1 && colonne_marquee[j]==0 && (tab[p][i][j]<plus_petit))
				plus_petit=tab[p][i][j];
			j++;
		}
		i++;
	}

	//  ..et on l'ajoute aux lignes rayées et le soustrait aux colonnes non rayées
	i=0;
	while(i<nbr_personne)
	{
		j=0;
		while(j<nbr_personne)
		{
			if(ligne_marquee[i]==0)
				tab[p][i][j]=tab[p][i][j]+plus_petit;
			if(colonne_marquee[j]==0)
				tab[p][i][j]=tab[p][i][j]-plus_petit;
			j++;
		}
		i++;
	}

	return 1;
}

int Hongroise::Calcul_Cout(int p)
{
	int cout=0;
	int i=0;
	while(i<nbr_personne)
	{
		int j=0;
		while(j<nbr_personne)
		{
			if(tab[p][i][j]==ZERO_ENCADRE)
				cout+=tab_cout[i][j];
			j++;
		}
		i++;
	}
	return cout;
}

void Hongroise::Affiche_Solution()
{
	cout << "Valeur minimale obtenue pour la satisfaction globale : " << Calcul_Cout(0) << endl;
	cout << "Nombre de solution equivalente : " << Solution.size() << endl << endl;
	
	int p=0;
	while(p<Solution.size())
	{
		int i=0;
		while(i<nbr_personne)
		{
			int j=0;
			while(j<nbr_personne)
			{
				if(tab[p][i][j]==ZERO_ENCADRE)
					cout << "Poste " << (char) ('a'+j) << " attribue a la personne " << (char) ('A'+i) << " dans la solution " << p+1 << endl;
				j++;
			}
			i++;
		}
		p++;
	}
	cout << endl;
	cout << (char) ('a'+1) ;
}