/*
 *  A*.cpp
 *  Untitled
 *
 *  Created by Lionel BUCHELE on 05/04/11.
 *  Copyright 2011 EFREI. All rights reserved.
 *
 */
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include "Buchele-Thebault-A.h"


pcube CreationRotationCube(pcube cubeF)
{
	pcube list = NULL;
	pcube listt = NULL;
	//Rotation Horaire
	list = copy(cubeF, 0);
	/*while(list != NULL)
	{
		ind++;
		list = list->suivant;
	}
	printf("ind %d",ind);
	*/

	 listt = list;
		//printf("je tenmerde %d",listt->suivant->face[0]->name));
	pivotGauche(listt->face[0], 1, NULL, 0);
	listt->cost = 1;
	listt->rotation = 1;
	
	
	listt = listt->suivant;
	pivotDroit(listt->face[0], 1, NULL,0);
	listt->cost = 1;
	listt->rotation = 2;
	
	listt = listt->suivant;
	pivotGauche(listt->face[4], 5, NULL, 0);
	listt->cost = 1;
	listt->rotation = 3;
	
	listt = listt->suivant;
	pivotDroit(listt->face[4], 5, NULL,0);
	listt->cost = 1;
	listt->rotation = 4;
	
	listt= listt->suivant;
	pivotbas(listt->face[0], 1, NULL,0);
	listt->cost = 1;
	listt->rotation = 5;
	
	listt= listt->suivant;
	pivothaut(listt->face[0], 1, NULL,0);
	listt->cost = 1;
	listt->rotation = 6;

	//Rotation du milieu horaire
	listt = listt->suivant;
	pivotGauche(listt->face[0], 1, NULL, 0);
	pivotDroit(listt->face[0], 1, NULL,0);
	listt->cost = 2;
	listt->rotation = 7;
	
	listt = listt->suivant;
	pivothaut(listt->face[0], 1, NULL, 0);
	pivotbas(listt->face[0], 1, NULL,0);
	listt->cost = 2;
	listt->rotation = 8;
	
	
	listt = listt->suivant;
	pivotGauche(listt->face[4], 5, NULL, 0);
	pivotDroit(listt->face[4], 5, NULL,0);
	listt->cost = 2;
	listt->rotation = 9;
	
	
	//Rotation anti horaire
	listt= listt->suivant;
	pivotGauche(listt->face[0], 1, NULL,0);
	pivotGauche(listt->face[0], 1, NULL,0);
	pivotGauche(listt->face[0], 1, NULL,0);
	listt->cost = 3;
	listt->rotation = 10;
	
	listt = listt->suivant;
	pivotDroit(listt->face[0], 1, NULL,0);
	pivotDroit(listt->face[0], 1, NULL,0);
	pivotDroit(listt->face[0], 1, NULL,0);
	listt->cost = 3;
	listt->rotation = 11;
	
	listt = listt->suivant;
	pivothaut(listt->face[0], 1, NULL,0);
	pivothaut(listt->face[0], 1, NULL,0);
	pivothaut(listt->face[0], 1, NULL,0);
	listt->cost = 3;
	listt->rotation = 12;
	
	listt = listt->suivant;
	pivotbas(listt->face[0], 1, NULL,0);
	pivotbas(listt->face[0], 1, NULL,0);
	pivotbas(listt->face[0], 1, NULL,0);
	listt->cost = 3;
	listt->rotation = 13;
	
	listt = listt->suivant;
	pivotGauche(listt->face[4], 5, NULL, 0);
	pivotGauche(listt->face[4], 5, NULL, 0);
	pivotGauche(listt->face[4], 5, NULL, 0);
	listt->cost = 3;
	listt->rotation = 14;
	
	listt = listt->suivant;
	pivotDroit(listt->face[4], 5, NULL,0);
	pivotDroit(listt->face[4], 5, NULL,0);
	pivotDroit(listt->face[4], 5, NULL,0);
	listt->cost = 3;
	listt->rotation = 15;
	
	//Rotation du milieu anti horaire
	listt = listt->suivant;
	pivotGauche(listt->face[0], 1, NULL, 0);
	pivotDroit(listt->face[0], 1, NULL,0);
	pivotGauche(listt->face[0], 1, NULL, 0);
	pivotDroit(listt->face[0], 1, NULL,0);
	pivotGauche(listt->face[0], 1, NULL, 0);
	pivotDroit(listt->face[0], 1, NULL,0);
	listt->cost = 6;
	listt->rotation = 16;
	
	
	listt = listt->suivant;
	pivotGauche(listt->face[4], 5, NULL, 0);
	pivotDroit(listt->face[4], 5, NULL,0);
	pivotGauche(listt->face[4], 5, NULL, 0);
	pivotDroit(listt->face[4], 5, NULL,0);
	pivotGauche(listt->face[4], 5, NULL, 0);
	pivotDroit(listt->face[4], 5, NULL,0);
	listt->cost = 6;
	listt->rotation = 17;
	
	listt = listt->suivant;
	pivothaut(listt->face[0], 1, NULL, 0);
	pivotbas(listt->face[0], 1, NULL,0);
	pivothaut(listt->face[0], 1, NULL, 0);
	pivotbas(listt->face[0], 1, NULL,0);
	pivothaut(listt->face[0], 1, NULL, 0);
	pivotbas(listt->face[0], 1, NULL,0);
	listt->cost = 6;
	listt->rotation = 18;
	
	return list;
}


int heuristique(pcube uncube, int index)
{
    if(index>5)
        return 0;
    else
    {
        int color, i, j, total=0;
        //we choose the central color for find a good solution
        color = uncube->face[index]->cases[1][1];
        for(i = 0; i<3;i++)
        {
            for(j = 0; j<3;j++)
            {
                if(uncube->face[index]->cases[i][j] != color)
                    total = total +1;
            }
        }
        total = total + heuristique(uncube, index+1);
        return total;
    }
}

//We caculate all futures solutions and return the best
pcube Transfert(pcube *Ouvert,pcube *Ferme,pcube rubi)
{
	pcube parcours_ouvert, parcours_ferme, temp;
	int index = 0;
	parcours_ouvert = *Ouvert;
	
	while ((parcours_ouvert != NULL)&&(parcours_ouvert->suivant != rubi)) 
	{
		parcours_ouvert = parcours_ouvert->suivant;
	}
	if(parcours_ouvert == NULL){*Ferme = *Ouvert; *Ouvert =NULL;return *Ferme;}
	else
	{
		temp = parcours_ouvert->suivant;
		parcours_ouvert->suivant = parcours_ouvert->suivant->suivant;
		parcours_ferme = *Ferme;
		while(parcours_ferme->suivant != NULL)parcours_ferme = parcours_ferme->suivant;
		parcours_ferme->suivant = temp;
		parcours_ferme->suivant->suivant = NULL;
		return parcours_ferme->suivant;
	}
	
}


//On regarde si la solution choisi de ouverte n'existe pas déja dans les états fermés
int ExisteSolution(pcube ferme, pcube beta)
{
	int val = 0;
	if(ferme == NULL)return val;
	val = checkCube(ferme, beta, 0);
	val = val+ExisteSolution(ferme->suivant, beta);
	return val;
}


//On compare les deux cubes
int checkCube(pcube ferme, pcube beta, int index)
{
	if(index == 6)return 1;
	int total = 0;
	int x, y;
	for(x = 0;x<3;x++)for(y = 0; y<3;y++)if(ferme->face[index]->cases[x][y] == beta->face[index]->cases[x][y])total++;
	
	if (total == 9)total= 1;
	else total = 0;
	
	index++;
	total = total * checkCube(ferme,beta,index);
	return total;
}



//Resolution du cube
bool Resolution(pcube *Ouvert,pcube *Ferme, pcube rubi)
{	
	
	pcube parcours_rubi, parcours_ouvert, trouve, temp, prec, parcours_ferme;
	int val;
	if(*Ferme == NULL) (*Ouvert)->heuristique =  heuristique(*Ouvert,0);
	
	//Tranfer le cube ayant lheuristique + le cout le plus faible dans les etats fermés
	
	parcours_ferme = Transfert(Ouvert,Ferme,rubi);
	
	
	//Affichage du dernier cubef mis dans l'état fermé
	printf("Patron de cube sélectionne \nValeur heuristique : %d\nCout : %d\n", parcours_ferme->heuristique, parcours_ferme->cost);
	affichageCube(parcours_ferme, 0);
	
	// Si le noeud ajouté n'est pas une solution
	if(rubi->heuristique != 0)
	{
		
		
		/*parcours_ferme = *Ferme;
		while(parcours_ferme != NULL)
		{
			printf("%d et ", parcours_ferme->heuristique);
			parcours_ferme = parcours_ferme->suivant;
		}*/
		
		
		
		//On crée les nouvelles rotations a partir du dernier ajouté dans fermé
		rubi = CreationRotationCube(parcours_ferme);	
		parcours_rubi = rubi;
		prec = parcours_rubi;
				
		//affectation heuristique	
		while (parcours_rubi != NULL) 
		{
			//Si la rotation créé est déja une solution dans les états finaux alors la supprimer des états ouverts
			if(ExisteSolution(*Ferme, parcours_rubi) == 1)
			{
				pcube tempo;
				tempo = parcours_rubi;
				if(prec == parcours_rubi)
				{
					
					rubi = parcours_rubi->suivant;
					parcours_rubi = rubi;
					prec = parcours_rubi;
				}
				else
				{
					parcours_rubi = parcours_rubi->suivant;
					prec->suivant = parcours_rubi;
				}
				DestructionNode(tempo);
				
			}
			else {
				parcours_rubi->heuristique = heuristique(parcours_rubi,0);
				prec = parcours_rubi;
				parcours_rubi = parcours_rubi->suivant;
			}
			
			
		}
		

		
		if(*Ouvert != NULL)
		{
			parcours_ferme = *Ouvert;
			while(parcours_ferme->suivant != NULL)
			{
				parcours_ferme = parcours_ferme->suivant;
				
			}
			
			parcours_ferme->suivant = rubi;
		}
		else
		{
			(*Ouvert) = rubi;
		}

		

		parcours_ouvert = *Ouvert;
		val = parcours_ouvert->heuristique+parcours_ouvert->cost;
		trouve = parcours_ouvert;
		
		//Choix de la meilleure solution
		while (parcours_ouvert != NULL) 
		{
			if((parcours_ouvert->heuristique+parcours_ouvert->cost)< val)
			{
				
				if(ExisteSolution(*Ferme, parcours_ouvert) == 0)
				{
						val = (parcours_ouvert->heuristique+parcours_ouvert->cost);
						trouve = parcours_ouvert;
				}
			}
			parcours_ouvert = parcours_ouvert->suivant;
		}
		Resolution(Ouvert,Ferme, trouve);
	}
	else return true;
}