#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <signal.h>

#define N 8 
 
#define DIMENSION 4 
#define AFFICHERREUR 0.01
#define AFFICHERESULTAT 10
#define TYPERESULTAT long

#define CALCULATED '1'
#define NOTCALCULATED '0'

int tableauPartition[N*(N+1)/2 * DIMENSION];
int tableauPartitionTrille[N*(N+1)/2 * DIMENSION];
int offsetTableau[N];
int NMoinsK[N];
FILE *fichier;


TYPERESULTAT resultat[N];
int coefficient[N];
int indicesCourant[N * DIMENSION];
int activePartition[N];
int partitionCourante;

typedef struct _HashMap {
	unsigned char part;
	TYPERESULTAT* resultat;
	struct _HashMap* next;
	struct _HashMap* fils;
}HashMap,*HashMap_p;

char* tableauRemember;
HashMap_p ptrHashMap;
TYPERESULTAT* ptrResultat;

unsigned long int memoire;

inline void initialise(int* tableau,const int taille,const int value){
	int i;
	for(i=0;i<taille;++i){
		tableau[i]=value;
	}
}

int rememberComplet;

#define OFFSETTABLEAU(x,y,z) ( offsetTableau[(z)] + (x)*(N-(z)) + (y) )


void printRemember()
{
	HashMap_p ptr;
	for(ptr=(HashMap_p)tableauRemember;ptr!=ptrHashMap;ptr++){
		fprintf(stderr,"--------------------------------\n");
		fprintf(stderr,"Pointeur : %u\n", (unsigned int) ptr);
		fprintf(stderr,"part : %d\n",ptr->part);
		fprintf(stderr,"resultat : %d, value : %ld \n", (unsigned int) ptr->resultat,((ptr->resultat==NULL)?-99999999:*(ptr->resultat)));
		fprintf(stderr,"next : %u \n", (unsigned int) ptr->next);
		fprintf(stderr,"fils : %u \n",(unsigned int) ptr->fils);
	}
}



inline int plusGrand(const int* partition1,const int* partition2){
	int k;
	for(k=0;k<N-partitionCourante;++k){
		if(partition1[k]!=partition2[k]){
			if(partition1[k]>partition2[k]){
				return 1;
			}else {
				return 0;
			}
		}
	}
	return 0;
}

inline void triPartition(void){
	//A Améiorer
	int i,j,k,l;
	int tmp;
	for(k=0;k<N-partitionCourante;++k){
		tableauPartitionTrille[OFFSETTABLEAU(0,k,partitionCourante)]=tableauPartition[OFFSETTABLEAU(0,k,partitionCourante)];
	}
	for(i=1;i<DIMENSION;++i){
		l=i;
		//On stock
		for(k=0;k<N-partitionCourante;++k){
			tableauPartitionTrille[OFFSETTABLEAU(i,k,partitionCourante)]=tableauPartition[OFFSETTABLEAU(i,k,partitionCourante)];
		}
		for(j=i-1;j>=0;--j){
			if( plusGrand(tableauPartitionTrille+OFFSETTABLEAU(j,0,partitionCourante) , tableauPartitionTrille+OFFSETTABLEAU(l,0,partitionCourante)) ){
				for(k=0;k<N-partitionCourante;++k){
					tmp=tableauPartitionTrille[OFFSETTABLEAU(j,k,partitionCourante)];
					tableauPartitionTrille[OFFSETTABLEAU(j,k,partitionCourante)]=tableauPartitionTrille[OFFSETTABLEAU(l,k,partitionCourante)];
					tableauPartitionTrille[OFFSETTABLEAU(l,k,partitionCourante)]=tmp;
				}
				--l;
			}else{
				break;
			}
		}
	}
}

inline void initialiseRemember(){
	ptrHashMap=(HashMap_p)tableauRemember;
	ptrHashMap->part=-1;
	ptrHashMap->resultat=NULL;
	ptrHashMap->next=NULL;
	ptrHashMap->fils=NULL;
	++ptrHashMap;
	ptrResultat=(TYPERESULTAT*) (tableauRemember +  memoire - sizeof(TYPERESULTAT) );
#if DEBUG
	fprintf(stderr,"size hash : %d, size TYPERESULTAT : %d\n",sizeof(HashMap),sizeof(TYPERESULTAT));
	fprintf(stderr,"%u %u %u \n",(unsigned int) tableauRemember ,(unsigned int) ptrHashMap,(unsigned int) ptrResultat);
#endif
	*ptrResultat=0;
}


inline void initialisationStructuresDonnees(char* type,char * arg,const char* memoireArg){
	int i,j;
	rememberComplet=1;
	//Initialisation de tableauPartition et partition
	initialise(tableauPartition,N*(N+1)/2 * DIMENSION,0);

        //Initialsiation de tableau de calculs
        for(i=0;i<N;i++){
                offsetTableau[i]=( DIMENSION * ( (i)*(N-(i)+1 ) + (i)*((i)-1)/2 ) );
                NMoinsK[i]=N-i;
        }

	if(strcmp(type,"-partition")==0){
		//Initialisation de la partition
		char* essai=strtok(arg,"[], ");
		i=0;
		while(i<N && essai!=NULL){
			tableauPartition[N-1-i]=atoi(essai);
			++i;
			essai=strtok(NULL,"[], ");
		}
		if(i<N){
			for(j=i;j<N;++j){
				tableauPartition[N-1-j]=0;
			}
		}
		partitionCourante=0;
		triPartition();
		
		//La première partition à traiter se trouve sur la ligne 0 du tableau
		//Initialisation des partitions actives (aucune au debut )
		initialise(activePartition,N,0);
	}
		
	//Initialisation de la table remember
	//On creer un tableau pour la fonction remember
	memoire = atol( memoireArg ) ;
	tableauRemember=(char *) calloc( memoire,sizeof(char));
	initialiseRemember();
	resultat[0]=0;
}

inline void desalocationMemoire(void){
	free(tableauRemember);
}

inline int hankel(int *indices,const int partitionCourante){
	int resultat=-(DIMENSION-1)*(N-1);
	int i;
	for(i=0;i<DIMENSION;i++)
	{
		resultat=resultat+indices[i]+tableauPartition[OFFSETTABLEAU(i,indices[i],partitionCourante)];
	}
	return resultat;
}

inline int firstIndice(int * indices)
{
	int i;
	for(i=0;i<DIMENSION;++i){
		indices[i]=0;
	}
	int retenue=0;
	i=0;
	while(i<DIMENSION && hankel(indices,partitionCourante)!=0){
		retenue=1;
		i=0;
		while((retenue>0 && i<DIMENSION) )
		{
			if(indices[i]==N-partitionCourante-1){
				indices[i]=0;
			}else{
				++(indices[i]);
				retenue=0;
			}
			++i;
		}
	}
	return indices[DIMENSION-1];
}

inline int nextIndice(int * indices)
{
	int i;	
	int retenue=1;
	do {
		retenue=1;
		i=0;
		while((retenue>0 && i<DIMENSION) )
		{
			if(indices[i]==N-1-partitionCourante){
				indices[i]=0;
			}else{
				++(indices[i]);
				retenue=0;
			}
			++i;
		}
	}while(i<DIMENSION && hankel(indices,partitionCourante)!=0);
	return indices[DIMENSION-1];
}



inline HashMap_p load(void)
{
	int i,j;
	HashMap_p ptr= (HashMap_p) tableauRemember;
	for(i=0;i<DIMENSION;++i){
		for(j=0;j<N-partitionCourante;++j){
			ptr=ptr->fils;
			while( (ptr!=NULL) && (ptr->part!=tableauPartitionTrille[OFFSETTABLEAU(i,j,partitionCourante)]) &&  ptr->next!=NULL){
				ptr=ptr->next;
			}
			if( (ptr==NULL) || (ptr->part != tableauPartitionTrille[OFFSETTABLEAU(i,j,partitionCourante)]) )
			{
				return NULL;
			}
		}
	}
	return ptr;
}

inline void save(void)
{
	HashMap_p ptr,ptrTmp;
//	printf("%u %u %u \n",(unsigned int)ptrResultat - (unsigned int)ptrHashMap ,(unsigned int) ptrHashMap,(unsigned int) ptrResultat);
//	printf("%d\n",DIMENSION*N*sizeof(HashMap));
	if( ((unsigned int)ptrResultat - (unsigned int)ptrHashMap) >= DIMENSION*N*sizeof(HashMap)){
		int i,j;
		ptr =(HashMap_p) tableauRemember;
		for(i=0;i<DIMENSION;++i){
			for(j=0;j<N-partitionCourante;++j){
				ptrTmp=ptr;
				ptr=ptr->fils;
				while( (ptr!=NULL) && (ptr->part!=tableauPartitionTrille[OFFSETTABLEAU(i,j,partitionCourante)]) &&  ptr->next!=NULL){
					ptr=ptr->next;
				}
				if(ptr==NULL)
				{
					ptrHashMap->part=tableauPartitionTrille[OFFSETTABLEAU(i,j,partitionCourante)];
					ptrHashMap->next=NULL;
					ptrHashMap->fils=NULL;
					ptrHashMap->resultat=NULL;
					ptrTmp->fils=ptrHashMap;
					ptr=ptrHashMap;
					++ptrHashMap;
				}else if(ptr->part != tableauPartitionTrille[OFFSETTABLEAU(i,j,partitionCourante)]){
					ptrHashMap->part=tableauPartitionTrille[OFFSETTABLEAU(i,j,partitionCourante)];
					ptrHashMap->next=NULL;
					ptrHashMap->fils=NULL;
					ptrHashMap->resultat=NULL;
					ptr->next=ptrHashMap;
					ptr=ptrHashMap;
					++ptrHashMap;
				}
			}
		}
		ptr->resultat=ptrResultat;
		*ptrResultat=resultat[partitionCourante];
		--ptrResultat;
	}else{
		if(rememberComplet){
			fprintf(
				stderr,
				"taille arbre utilise : %d -- taille resultat utilise : %d\n",
				ptrHashMap - ( (HashMap_p) tableauRemember ),
				( (TYPERESULTAT*) (tableauRemember+memoire-sizeof(TYPERESULTAT)) ) - ptrResultat  
			);
			fprintf(
				stderr,
				"taille Reelement Remember utilise ( Octet ): %ld \n",
				(
					(unsigned long int)(   ptrHashMap -( (HashMap_p) tableauRemember ))
			       	) * sizeof(HashMap) +
				(
				 	(unsigned long int) ( ((TYPERESULTAT*) (tableauRemember + memoire - sizeof(TYPERESULTAT))) -ptrResultat )
				) * sizeof(TYPERESULTAT) 
			);

			fprintf(stderr,"le tableau remember est complet !\n");
			rememberComplet=0;
		}
		initialiseRemember();
	}
}

inline int calculSigne(int* indices)
{
	int i;
	int signe=1;
	for(i=0;i<DIMENSION;++i){
		signe=( (signe==((indices[i]%2==0)?1:-1))?1:-1 );
	}
	return signe;
}

inline void constructPartition(int* indices){
	int i,j;
	for(i=0;i<DIMENSION;++i){
		if(indices[i]!=0){
			for(j=0;j<indices[i];++j){
				tableauPartition[OFFSETTABLEAU(i,j,partitionCourante)]=tableauPartition[OFFSETTABLEAU(i,j,partitionCourante-1)];
			}
		}
		if(indices[i]<N-partitionCourante){
			for(j=indices[i];j<N-partitionCourante;++j){
				tableauPartition[OFFSETTABLEAU(i,j,partitionCourante)]=tableauPartition[OFFSETTABLEAU(i,j+1,partitionCourante-1)]+1;
			}
		}
	}
	triPartition();
}

inline void stepCalculHyperdeterminant(void){
	//On regarde si c'est un nouveau tableau
	if(activePartition[partitionCourante]){
		resultat[partitionCourante]= resultat[partitionCourante]   +   calculSigne(indicesCourant+DIMENSION*partitionCourante) * resultat[partitionCourante+1];
		if(nextIndice(indicesCourant+DIMENSION*partitionCourante)){
			activePartition[partitionCourante]=0;
			//on sauvegarde
			save();
			--partitionCourante;
		}else{
			++partitionCourante;
			resultat[partitionCourante]=0;
			//On construit la future partition
			constructPartition(indicesCourant+DIMENSION*(partitionCourante-1));
		}
	}else{
		if(partitionCourante!=N-1){
			//On regarde si la partition a été déjà enregistré
			HashMap_p stockage = load();
			if(stockage==NULL || stockage->resultat == NULL){
				//On fait le calcul
				if(firstIndice(indicesCourant+DIMENSION*partitionCourante)){
					resultat[partitionCourante]=0;
					//on sauvegarde
					save();
					--partitionCourante;
				}else{
					activePartition[partitionCourante]=1;
					++partitionCourante;
					resultat[partitionCourante]=0;
					//On construit la future partition
					constructPartition(indicesCourant+DIMENSION*(partitionCourante-1));
				}
			}else{
//				printf("Load\n");
				resultat[partitionCourante]=*(stockage->resultat);
				--partitionCourante;
			}
		}else{
			int i;
			for(i=0;i<DIMENSION;++i){
				*(indicesCourant+DIMENSION*partitionCourante+i)=0;
			}
			if(hankel(indicesCourant+DIMENSION*partitionCourante,partitionCourante) != 0 ){
				resultat[partitionCourante]=0;
				--partitionCourante;
			}else{
				resultat[partitionCourante]=1;
				--partitionCourante;
			}
		}
	}
	//Elle n'a pas été calculé, on choisit un indice et on passe au calcul suivant
}

int  nextPartition(){
	char tmp[6];
	int i;
	char* essai;
	int etat=EOF+1;
	for(i=0;i<N;i++){
		essai=NULL;
		while(etat!=EOF && essai==NULL){
			etat=fscanf(fichier, "%s", tmp);
			essai=strtok(tmp,"[], ");
		}
		if(etat==EOF){
			return 0;
		}
		tableauPartition[N-1-i]=atoi(essai);
	}
	
	partitionCourante=0;
	triPartition();
	
	//La première partition à traiter se trouve sur la ligne 0 du tableau
	//Initialisation des partitions actives (aucune au debut )
	initialise(activePartition,N,0);
	resultat[0]=0;
	return 1;
}


long nb_partition;
long compteur;
time_t debut;



inline void printCourant(){
	time_t	courant=time(NULL);
	fprintf(
		stderr,
		"Calcul effectue : %f %c , nb_effectue : %ld, nb_restant : %ld,  nb_total :%ld, temps passe : %ld, temps /partition : %f , temps restant : %f \n",
		((float) compteur*100)/nb_partition,
		37,
		compteur,
		nb_partition-compteur,
		nb_partition,
		courant-debut, 
		((float)(courant-debut))/compteur,
		((float)(nb_partition-compteur)*(courant-debut))/compteur
	);
	fflush(stderr);
}

inline void printEtatMemoire(){
	fprintf(
		stderr,
		"taille arbre utilise : %d -- taille resultat utilise : %d\n",
		ptrHashMap - ( (HashMap_p) tableauRemember ),
		( (TYPERESULTAT*) (tableauRemember+memoire-sizeof(TYPERESULTAT)) ) - ptrResultat  
	);
	fprintf(
		stderr,
		"taille Reelement Remember utilise ( Octet ): %ld \n",
		(
			(unsigned long int)(   ptrHashMap -( (HashMap_p) tableauRemember ))
	       	) * sizeof(HashMap) +
		(
		 	(unsigned long int) ( ((TYPERESULTAT*) (tableauRemember + memoire - sizeof(TYPERESULTAT))) -ptrResultat )
		) * sizeof(TYPERESULTAT) 
	);
	fflush(stderr);
}

void handler(int signal){
	fclose(fichier); 
	fprintf(stderr,"Arret forcé du programme \n");
	fprintf(stdout,"\n");
	fflush(stdout);
	
	printCourant();
	printEtatMemoire();
	
	//Liberation de la mémoire
	desalocationMemoire();
}


int main(int argc,char* argv[])
{
        nb_partition=0;
        compteur=0;
        int compteur2;
        float etat=0.0;
	
	if(	(argc != 4) ||	(( strcmp(argv[1],"-partition")!=0 ) &&   ( strcmp(argv[1],"-fichier")!=0 )) ){
		fprintf(stderr,"Usage 2 :\n hyperdetermiant -partition partition memoire(octet) \n");
		return 1;
	}

	initialisationStructuresDonnees(argv[1],argv[2],argv[3]);

	if(strcmp(argv[1],"-partition")!=0){

		signal(10,&handler);
		signal(SIGINT,&handler);
		
                //On compte le nombre de partition existante
               	fichier = fopen(argv[2], "r");
		while(nextPartition()){
                        ++nb_partition;
		}
		fclose(fichier);
		
		fprintf(stderr,"Nb de partitions : %ld \n",nb_partition);
		debut = time (NULL);
		
		fichier = fopen(argv[2], "r");
		int i;
                compteur2=0;
		while(nextPartition()){
                        ++compteur;
                        ++compteur2;
			//Calcul de l'hyperdeterminant
			partitionCourante=0;
			while(partitionCourante!=-1){
				stepCalculHyperdeterminant();
			}
                        if(resultat[0]>=0){
                                fprintf(stdout,"+");
                        }
                        fprintf(stdout,"%ld*",resultat[0]);
                        fprintf(stdout,"s[");
			for(i=0;i<N-1;i++){
				fprintf(stdout,"%d,",tableauPartition[N-1-i]);
			}
                        fprintf(stdout,"%d]",tableauPartition[0]);
                        if(compteur2>AFFICHERESULTAT){
                                fprintf(stdout,"\n");
				fflush(stdout);
                                compteur2=0;
			}
                        if((((float) compteur*100)/nb_partition)-etat > AFFICHERREUR ){
                        	printCourant();
				etat=(((float) compteur*100)/nb_partition);
			}
		}
		fclose(fichier); 
	}else{
		partitionCourante=0;
		while(partitionCourante!=-1){
			stepCalculHyperdeterminant();
		}
    		printf("resutlat : %ld\n",resultat[0]);
	}
	fprintf(stdout,"\n");
	fprintf(stdout,"FIN DU CALCUL\n");
	fflush(stdout);
	printCourant();
	printEtatMemoire();
//	printRemember();
	
	//Liberation de la mémoire
	desalocationMemoire();

	return 0;
}