/*
   To compile:
	$gcc nodom.c -o nodom
 
  To execute:
         $./nodom inputfile outfile objectives  
      or only 
	$./nodom
      and the program ask for all data to user
*/

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

#define ERROR(x)  fprintf(stderr, x), fprintf(stderr, "\n"), exit(1)

void  freeFront(double**  front, int  noPoints);
int  readFront(double  **frontPtr[], FILE  *file, int  noObjectives);
int nodom2(double  *front1[], int nofront1, double **front2[], int noObjetivos);
void printfile (double *[], int , int , FILE *);
int dominate (double *ind1, double *ind2, int noObjetivos);
int same (double *ind1, double *ind2, int noObjetivos);

int  main(int  argc, char  *argv[])
{
	int solutions, objectives, nondominated;
	FILE *file;
	char infile[100], outfile[100];
	double **front1, **front2;
	clock_t c0, c1;

 	if (argc == 4){
		sprintf (infile, argv[1]);
		sprintf (outfile, argv[2]);
		objectives = atoi (argv[3]);
	
	
	}
	else{
       	printf ("\n Input File: ");
		scanf ("%s", infile);
	
    	printf ("\n Output File: ");
		scanf ("%s", outfile);
	
		printf ("\n Number of objectives: ");
		scanf ("%d", &objectives);
	}
	printf ("\nFile to be read: %s\n", infile);

	file = fopen(infile, "r");
    	if (file == NULL)  ERROR("Cannot open file\n");
    	solutions = readFront(&front1, file, objectives);
	fclose(file);

	printf ("\n There are %d solutions in the file: %s \n", solutions, infile);

	// Start the clock timer
	c0 = clock();
	// Call the nondominated function
	nondominated = nodom2(front1, solutions, &front2, objectives);	
	printf ("\n Nondominated solutions = %d \n", nondominated);
	// Stop the timer
	c1 = clock();
	printf( "Time in seconds: %f s\n", ((float)(c1 - c0) / (double)CLOCKS_PER_SEC) );

	printf ("\nFile to write in: %s\n", outfile);
	file = fopen(outfile, "w");
    	if (file == NULL)  ERROR("Cannot open file");

	// Write the solutions in the output file
	printfile (front2, nondominated, objectives, file);
	freeFront(front1, solutions);	
	fclose(file);
	printf("Succesfuly Finished !! \n\n");
	return 0;
}

void printfile (double *front1[], int nofront1, int noObjetivos, FILE  *file)
{
	int i, j;
	for (i = 0; i < nofront1; i++){
		for (j = 0; j < noObjetivos; j++)
			fprintf(file,"%f ", front1[i][j]); 
		fprintf(file,"\n"); 
	}

}

// Read the solutions from the front1 and store the nondominated in front2
// Return the number of nondominated solutions
int nodom2(double *front1[], int nofront1, double **front2[], int noObjectives)
{
	int i, j, flag;
	int nodominados = 0;
	double *frente[nofront1];
	*front2 = malloc(nofront1 * sizeof(double *));

	frente[nodominados++] = front1[0];
	for (i = 1; i < nofront1; i++){
		flag = 1;
		for (j=0; j < nodominados; j++){
			if (dominate (front1[i], frente[j], noObjectives))
				frente[j--] = frente[--nodominados];
			else if (dominate (frente[j], front1[i], noObjectives)){
				flag = 0;
				break;
			}
		}
		if (flag){  // Check if the solution is in the Nondominated Population
			if (nodominados == 0)
				frente[nodominados++] = front1[i];
			for (j=0; j < nodominados; j++){
				flag = 1;
				if (same (frente[j], front1[i], noObjectives)){
					flag = 0;
					break;
				}
			}
			if (flag)	// If the solution is not in the nondominated set, then it is added
				frente[nodominados++] = front1[i];
		}
	}
	for (i = 0; i < nodominados; i++){
		(*front2)[i] = frente[i];
	}	
	return nodominados;
}

// Read and check the file and store it in frontPtr
int  readFront(double **front[], FILE  *file, int noObjectives)
{
  int     noPoints;
  int     i;
  double  value;

//  check file and count points 
  noPoints = 0;
  while (!feof(file)) {
    for (i = 0; i < noObjectives && fscanf(file, "%lf", &value) != EOF; i++);
    if (i > 0 && i < noObjectives)  ERROR("data in file incomplete");
    noPoints++;
  }
//  allocate memory
  *front = malloc(noPoints * sizeof(double *));
  if (*front == NULL)  ERROR("memory allocation failed");
  for (i = 0; i < noPoints; i++) {
    (*front)[i] = malloc((noObjectives+1) * sizeof(double));
    if ((*front)[i] == NULL)  ERROR("memory allocation failed");
  }
  // read data 
  rewind(file);
  noPoints = 0;
  while (!feof(file)) {
    for (i = 0; i <= noObjectives; i++) {
	  if (i == noObjectives)
		(*front)[noPoints][i] = noPoints;
      else if (fscanf(file, "%lf", &value) != EOF)
		(*front)[noPoints][i] = value;
      else
		break;
    }
    if (i > 0 && i < noObjectives)  ERROR("data in file incomplete");
    noPoints++;
  }
  noPoints--;
  if (noPoints < 1)  ERROR("file contains no data");
  return noPoints;
} 

void  freeFront(double**  front, int  noPoints)
{
  int  i;

  if (front != NULL) {
    for (i = 0; i < noPoints; i++)
      if (front[i] != NULL)
	free(front[i]);
    free(front);
  }
} 

// Make a Comparison to know if the one dominates the second solution
//Return:
// 0.- If the first one does not dominate the second one
// 1.- If the first one dominates the second one
int dominate (double *ind1, double *ind2, int noObjectives)
{
	int i, flag = 3;
	for (i = 0; i < noObjectives; i++){
		if (ind1[i] < ind2[i])
			flag = 1;
		else if (ind2[i] < ind1[i])
			return 0;
	}
	if (flag == 3)
		return 0;
	return flag;
}

// Make a Comparison to determine if the solutions are the same
//Return:
// 0.- If they are different
// 1.- If they are equal
int same (double *ind1, double *ind2, int noObjectives)
{
	int i;
	for (i = 0; i < noObjectives; i++){
		if (ind1[i] < ind2[i])
			return 0;
		else if (ind2[i] < ind1[i])
			return 0;
	}
	return 1;
}