/*******************************
REP - Redundancy Elimination Problem

Developed by: Daniele Vitali [daniele@oldsail.net]
First implementation of the algorithm: 
Giuliano Casale

********************************/


#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <time.h>
#include "glpk.h"

struct station {
  double *classarr;
  struct station *next;
};

struct mr {
  int M;
  int R;
};

int rep_exec(struct station * head, int stnum, int R, int debuglevel, int verbose);
void rep_generate_list(struct station * head, int M, int R, int debuglevel, int verbose);
void Push_New_Entry(double classes_list[], struct station *current, int classesnumber, int debuglevel, int verbose);
int rep_prescan(struct station * head, int M, int R, int debuglevel, int verbose);
void rep_result_stdout(struct station * head, int R);
struct mr * rep_load_rboxfile(char location[], struct station * head, int debuglevel, int verbose);
struct mr * rep_load_rboxfile_stdin(struct station * head, int debuglevel, int verbose);
int r_services(char line[],struct station * current,int classnum, int debuglevel, int verbose);
int rep_M_rboxfile(char location[], int debuglevel, int verbose);
int rep_project(struct station * head, int R, int finalnum, int debuglevel, int verbose);
struct station * rep_retrieve_max(struct station * head, int R, int r, int debuglevel, int verbose);
int rep_list_to_rbox_str(struct station * head, int R, int M);

char prompt[]= "\n\
*************************************\n\
-REP- Redundancy Elimination Problem.\n\
*************************************\n\
\n\
\n\
USAGE: rep [[stations_number classes_number] | [-f filename] | [-stdin]] [args]\n\
\n\
\n\ 
args (any order, space separated):                    Version: 2004/07/08\n\
  HUMAN READABILITY:\n\
  -Dn           enable debug mode. `n` indicates the debug level [1 to 4]\n\
                warning: debug generates an ENORMOUS amount\n\
                of debug messages, better > to file.\n\
  -v            be verbose.\n\
  -h, --help    printout this help page.\n\
  \n\
  DATA RETRIEVAL:\n\
  num1 num2     if the first two args are numbers, the first one is intended to be the number\n\ 
                of stations and the second the number of classes. The load matrix is generated\n\
                as a num1xnum2 matrix with rand(). This is meant for algorithm evaluation since\n\
                rand() generates the same set for equals numbers calls.\n\
  -r filename   reads matrix from an rbox generated file.\n\
  -s            use with `|` will grab the rbox generated matrix from stdin\n\
  \n\
  DATA ANALYSIS:\n\
  -q            use qhull instead of rep internal algorthm. Warning: `qhull` must be in PATH\n\
  \n\ 
  OUTPUT HANDLING: \n\
  -o            output the final set of stations as matrix to STDOUT\n\
                warning: 'qhul' must be in path.\n\
  -G            output the final set of stations as GEOMVIEW formatted matrix to STDOUT\n\
                warning: qhull must be in path\n\
  -M            output the final set of statopns ready for mathematica 3d plotting to STDOUT\n\
\n\
\n\
USAGE EXAMPLES:\n\
\n\
rep 100000 10 -v -d1   //executes rep on a rand() generated matrix 100000x10 in verbose+debuglevel 1\n\
rep 100000 5 -q //same as above, but uses qhull (do not use more than 5 classes)\n\
rep -r rboxgeneratedfile.dat //reads input matrix from rbox file\n\
rbox 10000 D5 -O0.5 | rep -s //reads from stdin in rbox format\n\
\n\
\n\
";


int main(int argc,char** argv) {

	/*****************************************************************
	* Step zero: reads flags 
	******************************************************************/
  /* ============= vars ===================== */
  int M = -1;
  int R = -1;
  int i = 0;
  char filename[100];

  /* ============= flags ==================== */
  int debuglevel = 0;
  int verbose = 0;
  int generateRandom = 1;
  int loadFromRboxFile = 0;
  int loadFromRboxStdin = 0;
  int useQhull = 0;
  int output = 0;
  int outputGeomview = 0;
  int outputMathematica = 0;
	
  /* ============= read flags =============== */
  if (argc == 1){printf ("%s",prompt); exit(1);}
  
  if (atoi(argv[1]) > 1){
    M = atoi(argv[1]);
    if (argv[2] != NULL){
      R = atoi (argv[2]);
      if (R < 2){ printf("Error, wrong format\nThere must be at least 2 classes.\n"); exit(1);}
      i=3;}
    else {
      printf("Error, wrong format\n");
      exit(1);
    }  
  }
  
  
  for (i; i < argc; i++) {
  	
       if (argv[i][0] == '-')
	  (argv[i])++;
        switch (argv[i][0]) {
	  case '-':
	    printf("%s",prompt);
	    exit(1);
	    break;
	  case 'h':
	    printf("%s",prompt);
	    exit(1);
	    break;
	  case 'v':
	    /*if R and M are not set, and loadFromRboxFile, loadFromRboxStdin are not set to 1, error!*/
	    if ((!loadFromRboxFile)&&(!loadFromRboxStdin)&&(R < 1 )&&(M < 1)){
	      printf ("Syntax error.\n"); exit(1);
	    }
	    verbose=1;
	    break;
	  case 'd':
	    printf("debug\n");
	    if (!((int)argv[i][1] > 1)){
	      printf("Wrong debug level, please use with -d1 or -d2 or -d3 or -d4\n\n");
	      exit(1);
	    }
	    debuglevel = (int)argv[i][1];
	    printf ("Redunancy Elimination Problem running in debug mode: debuglevel = %i\n",debuglevel);
	    break;
	  case 'r':
	    loadFromRboxFile = 1;
	    generateRandom = 0;
	    if (argv[i+1] != NULL) stpcpy (filename,argv[i+1]);
	    else {printf ("Please specify filename\n"); exit(1);}
	    i++;
	    break;
	  case 's':
	    loadFromRboxStdin = 1;
	    generateRandom = 0;
	    break;
	  case 'q':
	    useQhull = 1;
	    break;
	  case 'o':
	    output = 1;
	    break;
	  case 'G':
	    outputGeomview = 1;
	    break;
	  case 'M':
	    outputMathematica = 1;
	    break;
	}
  }    

/* part end */


	
		
        /******************************************************************
          part: data definition
	******************************************************************/
		
	time_t t0,t1,t00;
		
	/*head struct pointer*/
	struct station * head;
	
	/*malloc and memset, in order to clear ->next pointer */
	head = (struct station *) malloc (sizeof (struct station));
	memset(head, 0, sizeof(struct station));
	
	/*start timing*/
	t0 = clock();
		
	/*****************************************************************
	* Second part: data generation
	******************************************************************/
	
	/*reads from input file, returns number of classes and stations and list attached to head*/
	if (loadFromRboxFile){
	  struct mr * m_and_r;
	  m_and_r = rep_load_rboxfile(filename,head,debuglevel,verbose);

	  
	  M = m_and_r->M;
	  R = m_and_r->R;
	 
	}
	
	/*reads from input file, returns number of classes and stations and list attached to head*/
	if (loadFromRboxStdin){
	  struct mr * m_and_r;
	  m_and_r = rep_load_rboxfile_stdin(head,debuglevel,verbose);

	  
	  M = m_and_r->M;
	  R = m_and_r->R;
	 
	}
  
	if (verbose && (loadFromRboxFile || loadFromRboxStdin)) fprintf(stderr,"Loading from rbox file took: %g sec\n",(double)(t1-t0)/CLOCKS_PER_SEC);

	/*generates with rand()*/
	if (!(loadFromRboxFile || loadFromRboxStdin)){
		rep_generate_list(head,M,R,debuglevel,verbose);
	}
	
	/*****************************************************************
	* Third part: data analysis
	******************************************************************/
	
	/*restart timing*/
	t0 = clock();
	t00 = clock();
	
	
	/*3.0 PRESCAN, stnum is the new number of stations after prescanning*/
	
	int stnum;
	int finalnum = M;
	if (!useQhull){
	stnum = rep_prescan(head,M,R,debuglevel,verbose);
					
			t1 = clock();
			if (verbose) printf("Prescan Elapsed time: %g sec\n",(double)(t1-t0)/CLOCKS_PER_SEC);
	
		
	/*chiamata a funzione che gestisce il rep*/
	finalnum = rep_exec(head, stnum,R,debuglevel,verbose);
	
			t1 = clock();
			if (verbose) fprintf(stderr,"Rep elapsed time: %g sec\n",(double)(t1-t0)/CLOCKS_PER_SEC);
	}
	else {
	  /*use qhull to resolve*/
	  if (outputGeomview || outputMathematica){
	    finalnum = rep_project(head,R,finalnum,debuglevel,verbose);	
	    finalnum = rep_project(head,R,finalnum,debuglevel,verbose);
	  }

	  rep_list_to_rbox_str(head,R,finalnum);

	  if (outputGeomview){
	    system("cat temp | qhull -G");
	  }  
	  if (output)
	    system("cat temp | qhull");
	  if (outputMathematica)
	    system("cat temp | qhull -m");
	  
	  if (!outputGeomview && !outputMathematica && !output)
	    system("cat temp | qhull > /dev/null");

	  system("rm -fr temp");
	}
	/*GEOMVIEW / MATHEMATICA OUTPUT*/	
	if ((outputGeomview || outputMathematica)&&!useQhull){
	  
	  /*check if dimensions are ok*/
	  if (R>3){
	    printf("Geomview or Mathematica output mode accepts not more than three dimensions.\n");
	    exit(1);
	  }

	  /*da sisitemare, con le proiezioni corrette. fare due volte le proiezioni risolve temporaneamente il problema*/
	  finalnum = rep_project(head,R,finalnum,debuglevel,verbose);	
	  finalnum = rep_project(head,R,finalnum,debuglevel,verbose);
	  char *tmpstr;

	  /*writes a temporary rbox formatted file called 'temp'*/
	  rep_list_to_rbox_str(head,R,finalnum);
	  
	  /*cats the file to qhull*/
	  if (outputGeomview) system("cat temp | qhull -G");
	  else if (outputMathematica) system("cat temp | qhull -m");

	  system("rm -fr temp");
	  
	}/*endo of output handling*/  

	/*total timing*/		
			t1 = clock();
			if (verbose) fprintf(stderr,"Total elapsed time: %g sec\n",(double)(t1-t00)/CLOCKS_PER_SEC);

	/*prints out the list*/	
	if (output) rep_result_stdout(head,R);
	
	return 0;
}


/***************************************************
*	REP EXECUTION FUNCTION
*	OVERVIEW: executes the rep algorithm. starts from HEAD 
*				 and depth is defined by stnum
* 	EFFECTS: modifies the linked list, removing redundant
				stations
***************************************************/


int rep_exec(struct station * head, int stnum, int R, int debuglevel, int verbose){
	
	/*now the initial number of stations is stnum*/
	int M1 = stnum;
	/* indices */
	int m,r,n; 
	int dominate = 0;
	int dominanti = 0; /*very important, it is the dinamic rapresentation of "m-1"*/
	struct station * current;
	
	
  for(m=1;m<=stnum;m++) /* for each station */
  {	

		/********************************************
		*	PART 1 : matrix generation from linked list
		********************************************/
		
		/*data definition*/	
		double L[M1][R];   			

		/*generazione matrice da linked list*/		
		current = head->next;

		int tr,td;
		for(tr=0;tr<M1;tr++){ 
			 for(td=0;td<R;td++){ 
				  L[tr][td] = current->classarr[td];
				  if (debuglevel > 0 ) printf ("%lf ",L[tr][td]);				  
				  }
			current = current->next;	  
			if (debuglevel > 0) printf ("\n");
		}	

		
		if (debuglevel > 0) printf("Effettuo il simpl su: %lf %lf %lf\n",L[dominanti][0],L[dominanti][1],L[dominanti][2]);
		
		if (debuglevel > 0) printf("M1: %i\n",M1);
		
		/********************************************
		*	PART 2 : simplex 
		********************************************/		
	
	/*inizio simplesso*/	
		if (debuglevel > 0) printf("\nNew simplex round. M1=%i, dominanti=%i\n",M1,dominanti);
   	LPX *lp;
   	int *ia=malloc((1+(M1-1)*(R+1))*sizeof(int));
   	int *ja=malloc((1+(M1-1)*(R+1))*sizeof(int)); 
   	double *A=malloc((1+(M1-1)*(R+1))*sizeof(double));

   	if (verbose) 
   		if (m % 25 == 0) 
			{		
				printf ("Progress: %d points out of %d \r",m,M1);
				fflush(stdout);
			}
   	if (debuglevel > 0) printf("[m=%d] L[%i][0]=%g\n",m,dominanti,L[dominanti][0]);

		/* creiamo un problema di massimo */
   	lp = lpx_create_prob();
   	lpx_set_prob_name(lp, "rep");
   	lpx_set_obj_dir(lp, LPX_MAX);
   	/* niente allo stdout*/
   	lpx_set_int_parm(lp, LPX_K_MSGLEV, 0);
   	lpx_set_int_parm(lp, LPX_K_OUTFRQ, 1000000);
   	lpx_set_real_parm(lp, LPX_K_OUTDLY, 1e6);
   	/* questo flag abbassa il tempo di esecuzione, 
   		cambiando il criterio di scelta per la 'leaving variable'. 
   		Il flag a '0' impone il 'textbook pricing method' per la scelta, 
   		invece dello 'steepest edge method' (default e migliore in alcuni casi,
   		ma qua non ci interessa il risultato del simplesso bensì la velocità 
   		di esecuzione del trovare una base iniziale)*/
   	lpx_set_int_parm(lp, LPX_K_PRICE, 0);

		/* fissiamo le righe della matrice dei coefficienti */
   	lpx_add_rows(lp, R+1);

   	if(debuglevel > 0) printf("Rows:%d\n",R+1);
   
		for(r=1;r<=R;r++)
		{
   		char name[15];
   		sprintf(name,"lincomb%d",r);
   		lpx_set_row_name(lp, r, name);
   		lpx_set_row_bnds(lp, r, LPX_LO, L[dominanti][r-1], L[dominanti][r-1]); /* the r-th linear combination equals the r-th component of the current station*/
   		if(debuglevel > 1) printf("Added rows %s that equals %g \n",name, L[dominanti][r-1]);
		}
   
   	lpx_set_row_name(lp, R+1, "convexity");
   	lpx_set_row_bnds(lp, R+1, LPX_FX, 1.0, 1.0);
   	if(debuglevel > 0) printf("Added convexity constraint \n");

		/* fissiamo le variabili con i relativi bound */
   	lpx_add_cols(lp, M1-1);

   	if(debuglevel > 1) printf("Added %d variables \n", M1);

		for(n=1;n<=M1;n++)
		{			
   		char name[15];
  	 		sprintf(name,"lambda%d",n);
  	 		if (debuglevel > 1) printf("m=%i,n=%i,dominanti=%i,dominate=%i,M1=%i\n",m,n,dominanti,dominate,M1);
			if(n < dominanti+1) /*era 'm', dovrebbe essere la nuova notazione dinamica*/
   		{
    			
    			lpx_set_col_name(lp, n, name);
    			lpx_set_col_bnds(lp, n, LPX_DB, 0.0, 1.0);
    			lpx_set_col_coef(lp, n, 1.0);
    			if(debuglevel > 1) printf("(n<dominanti) Added variable %s with id %d in [0.0, 1.0] \n", name,n);
   		}
		  	else if(n > dominanti+1) /*come sopra*/ 
   		{
    			lpx_set_col_name(lp, n-1, name);
    			lpx_set_col_bnds(lp, n-1, LPX_DB, 0.0, 1.0);
    			lpx_set_col_coef(lp, n-1, 1.0);
    			if(debuglevel > 1) printf("(n>dominanti) Added variable %s with id %d in [0.0, 1.0] \n", name,n);
   		}
   		else if(n == dominanti+1) if(debuglevel > 1) printf("(n==m) mmm.. that's me.\n");
		}
		

	if(debuglevel > 1) printf("Coefficient matrix A: \n");

	/* creates A matrix */

	/*inverte la matrice, togliendo la riga della stazione considerata*/

 		int i,j,ctr=0;
 		for(i=1;i<=R;i++)
 		{
   		for (j=1;j<=M1;j++)
   		{
    			if(j<dominanti+1)
    			{  ia[++ctr] = i, ja[ctr]= j , A[ctr]= L[j-1][i-1]; 
      			if(debuglevel > 1) printf("%d: A[%d][%d]=%g \n",ctr,ia[ctr],ja[ctr],A[ctr]);
    			}
    			else if(j>dominanti+1)
    			{  ia[++ctr] = i, ja[ctr]= j-1 , A[ctr]= L[j-1][i-1]; 
      			if(debuglevel > 1) printf("%d: A[%d][%d]=%g \n",ctr,ia[ctr],ja[ctr],A[ctr]);
    			}
   		}
 		}
 		for (j=1;j<=M1;j++)
 		{
  			if(j<dominanti+1)
  			{  ia[++ctr] = R+1, ja[ctr]= j , A[ctr]= 1.0; 
    			if(debuglevel > 1) printf("%d: A[%d][%d]=%g \n",ctr,ia[ctr],ja[ctr],A[ctr]); 
    		}
  			else if (j>dominanti+1)
  			{  ia[++ctr] = R+1, ja[ctr]= j-1 , A[ctr]= 1.0; 
    			if(debuglevel > 1) printf("%d: A[%d][%d]=%g \n",ctr,ia[ctr],ja[ctr],A[ctr]); 
    		}
    		else if (j == dominanti) printf("");
 		}


	/* imposta la matrice dei coefficienti e risolvi il problema */ 
  
  	if (debuglevel > 1) printf("M1*(R+1)=%i\n",M1*(R+1));
  
  	lpx_load_mat3(lp,(M1-1)*(R+1), ia, ja, A); 
  	lpx_simplex(lp);	

	/*stazione dominata o dominante*/

	if (lpx_get_status(lp) == LPX_NOFEAS)
  		dominanti++;
	else 
	{	  
		dominate++;

	/*********************************************
	* PART 3
	* line removal part
	* here 'dominate' tells the depth in the list of the 
	* station we are considering. 
	* we browse the linked list until we find the 
	* node and remove it.
	*********************************************/
		
		if (debuglevel > 0) printf("Station %lf %lf %lf dominated\n",L[dominanti][0],L[dominanti][1],L[dominanti][2]);
		
		int d = 1;
		struct station * tmp; /*used to temporarily store the '->next' address*/
		current = head;
		
		while (d<=dominanti){ /*only the dominants remains in list*/
			current = current->next;
			d++;
		}	
	
		if (debuglevel > 0) printf("d:%i, dominanti:%i\n",d,dominanti);
		/*remove a node*/	
		tmp = current->next;
		current->next = tmp->next;
		if (debuglevel > 0) printf("sto rimuovendo: %lf %lf %lf\n",tmp->classarr[0],tmp->classarr[1],tmp->classarr[2]);
		
		/*decrease total number of stations*/
		M1--;
		
		/*free memory*/
		free(tmp);
	
	/**  end of line removal part **/
	
	}
	
  lpx_delete_prob(lp);
  free(ia);
  free(ja);
  free(A); 

 }/*end of for*/
		
	if (verbose){
	printf("Stazioni dominanti: %d - Stazioni dominate: %d\n",dominanti,dominate);
	fprintf(stderr,"M=%d R=%d \n",M1,R);
	}
	
	return M1;
	
}/*end of rep_exec*/


/***************************************************
*	DATA GENERATION
*  OVERVIEW: generates the linked list starting from head
*				 (actually HEAD itself is not used, the first 
*				 node is head->next) of M stations in R classes.
*	EFFECTS: starting from HEAD there will be a linked list
				of stations with depth M and classarr of R
				columns.
***************************************************/


void rep_generate_list(struct station * head, int M, int R, int debuglevel, int verbose){
	/*the classes array. overwritten for every station*/
	double arr[R];
	int m,r;
	
	struct station * current;			
	current = head;
	
	for(m=1;m<=M;m++) /* for each station */
	{	
		/*first, generates the array line.*/
		for(r=0;r<R;r++) /* for each class */
		{
			arr[r] = (double)rand()/RAND_MAX;
		}
		/*second, push it in the list*/
		Push_New_Entry(arr,current,R,debuglevel,verbose);	
		/*third, moveon to the next*/
		current=current->next;
	
	}
	
	/*this reads the list content*/
	if (debuglevel > 3){ 
		current = head->next;
		for(m=1;m<=M;m++) /* for each station, printout*/
		{
			printf("P current->classarr: ");
			for(r=1;r<=R;r++) /* for each class */
			{
				printf("%lf ",current->classarr[r]);
			}
			printf("\n");
			if (current->next != NULL) current = current->next;
			
		}
	}
	
}/*end of rep_generate_list*/


/***************************************************
*	PUSH NEW ENTRY N LIST
* 	OVERVIEW: pushes a new entry after *current
*	EFFECTS: a new node will be appended to *current, 
*				with classes_list as classarr
***************************************************/

/*pushes a new node in the list*/
void Push_New_Entry(double classes_list[], struct station *current, int classesnumber, int debuglevel, int verbose) {
	
	if (debuglevel > 2 ) printf("arr: %lf %lf %lf\n\n",classes_list[1],classes_list[2],classes_list[3]);
	
  current->next=(struct station *) malloc (sizeof (struct station));
  memset(current->next, 0, sizeof(struct station));
  current=current->next;
  
   double *arrp;
	arrp = (double *)malloc((classesnumber) * sizeof(double)); 
   memcpy (arrp, classes_list, (classesnumber) * sizeof (double));
  	
   current->classarr = arrp;  
  
}/*end of push_new_entry*/	


/******************************************************
*	3.0 : PRESCAN:
*	OVERVIEW: controls and remove completely dominated stations .
*	EFFECTS: chooses a station, parses matrix looking 
*	for other stations dominated by the chosen one.
*	if it finds a station that dominate, the chosen 
*	staton is removed and the parse goes on
******************************************************/

int rep_prescan(struct station * head, int M, int R, int debuglevel, int verbose){
		if (debuglevel > 2) printf("*******************************************\n   	START OF PRESCAN\n*******************************************\n");		

		/***
		*	pointers: 
		*	- tmp and pre are used to parse the list looking for dominated stations,
		*	- sw is used for debugging
		*	- precur and current are used to choose main node 
		*	  and to remove it if it's dominated.
		*/
		struct station * tmp, * pre, * sw, * precur, * current;
		
		int stnum = M; /*the number of remaining stations*/
		int dominated, dominating;
		int count = 0;
		int d,e,r; /*indices*/
		
		precur = head;
		current = head;
		/*DEBUG*/
		/*rep_result_stdout(head,R);*/
		
		while(current->next != NULL)
		{		 
			pre = current;
			current =  current->next;
			tmp = current;
			if (debuglevel > 3) printf("Current MAIN NODE: %lf, %lf\n ", current->classarr[0],current->classarr[1]);
			while(tmp->next != NULL)
			{
								
				/*forward only if didn't remove a node before*/
				if (!dominated)
					pre = pre->next;
					
				/*reassign tmp*/
				tmp = pre->next;
				
				/*reset vars*/
				dominated=0;
				dominating=0;
				
				if (debuglevel > 2) printf("	confrontato:  tmp =  %lf %lf %lf %lf %lf\n",tmp->classarr[0],tmp->classarr[1],tmp->classarr[2],tmp->classarr[3],tmp->classarr[4]);
				if (debuglevel > 3) printf("\n		current:    =  %lf %lf %lf %lf %lf\n ",current->classarr[0],current->classarr[1],current->classarr[2],current->classarr[3],current->classarr[4]);				
				if (debuglevel > 3) printf("	confrontato:  tmp =  %lf %lf %lf %lf %lf ",tmp->classarr[0],tmp->classarr[1],tmp->classarr[2],tmp->classarr[3],tmp->classarr[4]);				
								
				/*for the whole line, controls if values are <*/
				d=0;
				e=0;
				if (debuglevel > 2) printf("	CONTROLLO SE DOMINATO\n");
				for (r=0;r<R;r++){
					if (tmp->classarr[r] < current->classarr[r]){		
						if (debuglevel > 2)printf("	%lf < %lf \n",tmp->classarr[r],current->classarr[r]);
						d++;						
					}
					else if ((tmp->classarr[r] > current->classarr[r])&&(!dominated)){
						if (debuglevel > 2)printf("	%lf > %lf\n",tmp->classarr[r],current->classarr[r]);						
						e++;					
					}
					else break;											
				}	
				if (d == R){ dominated=1; }	
				if (e == R){ dominating=1;}
				
				if (debuglevel > 3) printf("	dominated=%i,dominating=%i\n\n",dominated,dominating);

				
				/*********************************************
				* nodes removal part				
				*********************************************/
		
				if (dominated){ /*tmp is dominated by current*/
					if (debuglevel > 3) printf("	Station %lf %lf fully dominated, will be removed.\n\n",tmp->classarr[0],tmp->classarr[1]);
					/*remove the node*/							
					if (tmp->next != NULL) pre->next = tmp->next;
					else pre->next = NULL;
					/*free memory*/
					free(tmp);						
					stnum--;
					/*DEBUG*/
					/*rep_result_stdout(head,R);*/
				}
				if (dominating){ /*the current is dominated by tmp*/
					if (debuglevel > 3) printf("	DOMINATED! Current station %lf %lf is being dominated, will be removed.\n\n",current->classarr[0],current->classarr[1]);
					/*remove the node*/							
					precur->next = current->next;
					/*free memory*/
					free(current);	
					current = precur;					
					stnum--;
					/*DEBUG*/
					/*rep_result_stdout(head,R);*/
				}
				/**  end of line removal part **/
			
				/*exit while*/
				if (dominating){				
					break;
				}				
													
			}/*endof while->tmp*/				
				
		 /*forward precur*/
		 if (!dominating) precur = precur->next;		
		}/*endof while->current*/
		
		/*printout the final list*/		
		if (debuglevel > 3) {
				current = head;
				while(current->next != NULL) /* for each station, printout*/
				{
					current = current->next;
					printf("P current->classarr: ");
					for(r=1;r<=R;r++) /* for each class */
					{
						printf("%lf ",current->classarr[r-1]);
					}
					printf("\n");
		    	}
		}		
			
	if (debuglevel > 0) printf("Prescan eliminated %i fully dominated stations.\nNow the number of remaining stations is %i.\n", M - stnum, stnum);
	if (verbose) printf("Prescan eliminated %i fully dominated stations.\nNow the number of remaining stations is %i.\n", M - stnum, stnum);	
	if (debuglevel > 1) printf("*******************************************\n   	END OF PRESCAN\n*******************************************\n");
		
	return stnum;
	
}/*end of rep_prescan*/

/***************************************************
*	PRINT LIST
* 	OVERVIEW: just prints the whole list to output, 
*				 starting from HEAD
***************************************************/


void rep_result_stdout(struct station * head, int R){
				
				int r;
				struct station * current;
				current = head->next;			
				
				
				while(current->next != NULL) /* for each station, printout*/
				{								
					for(r=0;r<R;r++) /* for each class */
					{
						printf("%lf ",current->classarr[r]);
					}
					printf("\n");
		    		current = current->next;
		    		if (current->next == NULL){
		    			for(r=0;r<R;r++) /* for each class, for the last station */
						{
							printf("%lf ",current->classarr[r]);
						}
						printf("\n");
						break;
					}
		    	}

}

/***************************************************
*	LOAD FROM RBOX FILE
* 	OVERVIEW: accepts input file in rbox format,
*				 produces a linked list starting from head
*	RETURN: 	 number of classes
***************************************************/

struct mr * rep_load_rboxfile(char location[], struct station * head, int debuglevel, int verbose){
	
	FILE *inFile;
	char line[1000];
	struct station * current;
	struct mr * m_and_r;
	int res;
	int classnum = 0;
	int statnum = 0;
	char *tmp;
	
	m_and_r = (struct mr *) malloc (sizeof (struct mr));
	
	current = head;
	
	if (debuglevel > 0) printf("Apro il file:\n");
	inFile = fopen(location, "r");
	
	/*first line of rbox type, contains R*/
	fgets(line, sizeof(line), inFile);
		tmp = strtok (line," ");
 		classnum = (int)atoi(tmp);
		
	fgets(line, sizeof(line), inFile);			
		statnum = atoi(line);
	
	if (debuglevel > 0) printf("classes number: %i\n",classnum);			
	if (debuglevel > 0) printf("station number: %i\n",statnum);
	
  	while( fgets(line, sizeof(line), inFile) != NULL ) {
	  
   	 /*call of service function*/
   	 res = r_services(line,current,classnum,debuglevel,verbose);
       /*if node was appended, forward*/
       if (current->next != NULL)
       	current = current->next;    	 

  	}	/*end of while fgets*/

  	fclose(inFile);
	
	m_and_r->R = classnum;
	m_and_r->M = statnum;
	
	return m_and_r;
}


/***************************************************
*	LOAD FROM RBOX SERVICE FILE
* 	OVERVIEW: service file, handdles a line
*	RETURN: 	 number of classes (just for ctrl)
***************************************************/

int r_services(char line[],struct station * current,int classnum, int debuglevel, int verbose){
	char * pch;
	double num;
	int t;
	double arr[classnum]; /*the classes array. overwritten for every station*/
		
  	pch = strtok (line," ");
  	 	
  	for (t=0;t<classnum;t++)
  	{
  	  	 if (debuglevel > 0) printf("t=%i ,%s=",t,pch);
  	  	 num = atof(pch);
  		 if (debuglevel > 0) printf("%lf=",num);
  		 
  		 arr[t] = num;
  		 if (debuglevel > 0) printf("%lf \n",arr[t]);   		 		 	
 		   	  	 
  	  	 pch = strtok (NULL, " ");
  		   	 
  	}
  	if (debuglevel > 0) printf("array: %i, [%lf][%lf][%lf]\n",sizeof(arr),arr[0],arr[1],arr[2]);
  	/******************************************
  	* node insertion part
  	******************************************/  	
	
		if (debuglevel > 0) printf ("appending: %lf %lf %lf\n",arr[0], arr[1],arr[2]);
		Push_New_Entry(arr,current,classnum,debuglevel,verbose);	
		
		  	
	return classnum;
}

/***************************************************
*	LOAD FROM RBOX STDIN
* 	OVERVIEW: reads an rbox file streamed from stdin
*	RETURN: 	 struct mr
***************************************************/

struct mr * rep_load_rboxfile_stdin(struct station * head, int debuglevel, int verbose){
	
	char line[1000];
	struct station * current;
	struct mr * m_and_r;
	int res;
	int classnum = 0;
	int statnum = 0;
	char *tmp;
	
	m_and_r = (struct mr *) malloc (sizeof (struct mr));
	
	current = head;
	
	/*first line of rbox type, contains R*/
	fgets(line, sizeof(line), stdin);
		tmp = strtok (line," ");
 		classnum = (int)atoi(tmp);
		
	fgets(line, sizeof(line), stdin);			
		statnum = atoi(line);
	
	if (debuglevel > 0) printf("classes number: %i\n",classnum);			
	if (debuglevel > 0) printf("station number: %i\n",statnum);
	
  	while( fgets(line, sizeof(line), stdin)) {
	  
   	 /*call of service function*/
   	 res = r_services(line,current,classnum,debuglevel,verbose);
       /*if node was appended, forward*/
       if (current->next != NULL)
       	current = current->next;    	 

  	}	/*end of while fgets*/

	
	m_and_r->R = classnum;
	m_and_r->M = statnum;
	
	return m_and_r;
}


/***************************************************
*	LOAD FROM RBOX FILE THE NUMBER OF STATIONS M
* 	OVERVIEW: reads from the second line of the file the
*				 M number of stations
*	RETURN: 	 number of stations 
***************************************************/

int rep_M_rboxfile(char location[], int debuglevel, int verbose){

if (debuglevel > 0) printf("Apro il file per trovare M:\n");
	FILE *inFile;
	char line[1000];
	int statnum;
	char *tmp;
		
	inFile = fopen(location, "r");
	
	/*first line of rbox type, contains R*/
	fgets(line, sizeof(line), inFile);
		tmp = strtok (line," ");

  	/*the second line is M*/
  	fgets(line, sizeof(line), inFile);			
		statnum = atoi(line);
	
	if (debuglevel > 0) printf("station number: %i\n",statnum);
	fclose(inFile);
	
	return statnum;
}

/*from here not used functions*/



/***************************************************
*	THROWS PROJECTIONS
* 	OVERVIEW: starts from head, and throws projections
*				 for every highest station in class 
*	RETURN: 	 void
***************************************************/

int rep_project(struct station * head, int R, int finalnum, int debuglevel, int verbose){

		struct station * current, * new, * tmp;
		int r,k,l;
		int statnum = finalnum;
		double classes_list[R];
		
		current = head->next;
		for (r=0;r<finalnum;r++){
		
			/*genera array della proiezione*/
			for (k=0;k<R;k++){
				/*genera l'array per la proiezione*/
				for (l=0;l<R;l++){	
					if (k != l)
						classes_list[l] = current->classarr[l];
					else 
						classes_list[l] = 0.000001;	
				}		
				
				if (debuglevel > 3) {printf("arr ");
				for (l=0;l<R;l++)	printf ("%lf ",classes_list[l]);	
				printf("\n");}
				
				/*genera nuovo nodo*/
				new = (struct station *) malloc (sizeof (struct station));
  				memset(new , 0, sizeof(struct station));
   	
  				double *arrp;
				arrp = (double *)malloc((R) * sizeof(double)); 
   			memcpy (arrp, classes_list, (R) * sizeof (double));
  		
   			new->classarr = arrp;  
			
				/*node is ready, append it at the beginning.*/
				tmp = head->next; /*tmp storage, current is not needed anymore*/
				new->next = tmp;
				head->next = new;
				statnum++;
						
			}/*endof for k*/
			
			
			
		current = current->next;	
			
		}/*end of for r*/
				
		return statnum;
}

/******************************************************
*	FIND MAX. 
*	EFFECTS: returns pointer to node in linked list
*				that has the highest value for column r
*	
******************************************************/

/*this function is not actually used*/
struct station * rep_retrieve_max(struct station * head, int R, int r, int debuglevel, int verbose){
		
		struct station * tmp, * current;
		
		current = head->next;
		tmp = head->next;
		while(tmp->next != NULL) /* for each station */
				{								
					if (tmp->classarr[r] > current->classarr[r])
						current = tmp;
		    		
		    		tmp = tmp->next;
		    			
		    		if (tmp->next == NULL){
		    			if (tmp->classarr[r] > current->classarr[r])
							current = tmp;		    			
					}
		    	}
		return current;

}

/***************************************************
*	PRINT LIST TO RBOX FORMATTED STRING
* 	OVERVIEW: just prints the whole list to string, 
*				 starting from HEAD
*       returns string
***************************************************/


int rep_list_to_rbox_str(struct station * head, int R, int M){
	
  char str[200000];
  char mnum[20];
  char rnum[20]; 
  FILE *tmp;
  char t[50];

  tmp = fopen("temp","w");
  
  
      int r;
      struct station * current;
      current = head->next;	
	
      sprintf(mnum,"%d",M+1);
      sprintf(rnum,"%d",R);
	
      fprintf(tmp,rnum);
      fprintf(tmp," rbox ");
      fprintf(tmp,mnum);
      fprintf(tmp,"\n");
      fprintf(tmp,mnum);
      fprintf(tmp,"\n"); 
      
      /*addds the zero coo*/
      fprintf(tmp,"0.00 0.00 0.00\n");
      
			
      while(current->next != NULL) /* for each station, printout*/
      {								
	for(r=0;r<R;r++) /* for each class */
	{
	  sprintf(t,"%f",current->classarr[r]);
	     fprintf(tmp,t);
             fprintf(tmp," ");
	}
      fprintf(tmp,"\n");
      current = current->next;
      if (current->next == NULL){
          for(r=0;r<R;r++) /* for each class, for the last station */
   	  {
	     sprintf(t,"%f",current->classarr[r]);
	     fprintf(tmp,t);
             fprintf(tmp," ");
	  }
	  fprintf(tmp,"\n");
	  break;
      }
      }
      fclose(tmp);
      return 1;

}


/*EOF*/