/*========================================================================
  PISA  (www.tik.ee.ethz.ch/pisa/)
  ========================================================================
  Computer Engineering (TIK)
  ETH Zurich
  ========================================================================
  SPAM - Set Preference Algorithm for Multiobjective Optimization

  authors: Johannes Bader, johannes.bader@tik.ee.ethz.ch
           Eckart Zitzler, eckart.zitzler@tik.ee.ethz.ch
           Marco Laumanns, laumanns@tik.ee.ethz.ch

  revision by: Stefan Bleuler, stefan.bleuler@tik.ee.ethz.ch
			   Dimo Brockhoff, dimo.brockhoff@tik.ee.ethz.ch

  last change: 01.12.2008
  ========================================================================
 */

#include <float.h>
#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#include "reduction.h"
#include "population.h"
#include "utils.h"
#include "spam_functions.h"
#include "prefrel.h"
#include "epsilon.h"
#include "hypervolume.h"

void front_reduction( fpart* partp, int newsize, int* left, front** fp )
/* Reduces the population by removing the worst fronts, returns the next front
 * to consider */
{
	int i = partp->fronts - 1;
	*left = partp->size - newsize;

	while ( i >= 0 && ( (*left) - partp->front_array[i].size >= 0 ) )
	{
		partp->size -= partp->front_array[i].size;
		(*left) -= partp->front_array[i].size;
		partp->front_array[i].size = 0;
		partp->fronts--;
		i--;
	}
	if( i >= 0 )
		*fp = &(partp->front_array[i]);
	else
		fp = NULL;
}

void heuristicReductionSPAM(fpart* partp, int newsize )
/* front[0] = Pareto Front */
{
	/* "prefrelType" denotes the type of preference */
	int i,j,l;

	int remainingType; /*???xx*/
	int paretoFrontType; /*?xx??*/
	int procedure; /*x????*/

	getReductionTypes( prefrelType, &procedure, &paretoFrontType, &remainingType  );

	int left = -1;
	/* temporary storage */
	front* fp;
	fpart dum1_part;
	create_front_part(&dum1_part, partp->size );
	dum1_part.max_fronts = partp->max_fronts;
	dum1_part.size = partp->size;

	switch( procedure )
	{
	case 1:
		/* Reduce front wise, sorting needs to be 1. Apply reduction
		 * remainingType to non pareto fronts and paretoFrontType and then
		 * remainingType to the pareto front */
	case 2:
		/* As 1, but moves on if paretoFrontType does not lead to a decision*/
		for( i = 0; i < partp->fronts; i++ ) {
			dum1_part.front_array[ i ] = partp->front_array[ i ];
		}
		dum1_part.fronts = partp->fronts;
		break;
	case 3:
		/* Merge all non-pareto fronts */
		dum1_part.front_array[0] = partp->front_array[ 0 ];
		l = 0;
		for( i = 1; i < partp->fronts; i++ )
		{
			for( j = 0; j < partp->front_array[ i ].size; j++ )
				dum1_part.front_array[ 1 ].members[ l++ ] =
					partp->front_array[i].members[ j ];
		}
		dum1_part.front_array[ 1 ].size = l;
		dum1_part.fronts = 2;
		break;
	}
	fp = NULL;
	if( sorting )
		front_reduction( &dum1_part, newsize, &left, &fp );
	while( left > 0 )
	{
		/* Operate on non pareto points */
		if( dum1_part.fronts > 1 )
		{
			if( remainingType > 0 )
			{
				assignFitness(fp, remainingType );
				removeTheWorstIndividual(&dum1_part, fp );
			}
			else {
				randomReduction( &dum1_part, dum1_part.size-1);
			}
		}
		/* Operate on pareto points */
		else {
			if( paretoFrontType > 0 )
			{
				assignFitness(fp, paretoFrontType );
				int indices[ fp->size ];
				int indLen = removeTheWorstIndividualUnique(&dum1_part, fp, indices );
				if( indLen > 0 )
				{
					if( procedure == 2 )
					{
						assignFitness(fp, remainingType );
						removeTheWorstIndividualFromSet(&dum1_part, fp, indices, indLen );
					}
					else {
						removeTheWorstIndividualFromSet(&dum1_part, fp, indices, indLen );
					}
				}
			}
			else {
				randomReduction( &dum1_part, newsize);
			}
		}
		left--;
	}
	copyPart( &dum1_part, partp );
	assert( partp->size == alpha );
}

void randomReduction(fpart*  partp, int newsize)
{
	if( newsize < 0 )
		return;

	assert( partp->size >= newsize );
	int i;
	int left;

	i = partp->fronts - 1;
	left = partp->size - newsize;
	assert( left >= 0 );
	assert( i >= 0 );
	while (left - partp->front_array[i].size >= 0 && i >= 0 )
	{
		partp->size -= partp->front_array[i].size;
		left -= partp->front_array[i].size;
		partp->front_array[i].size = 0;
		partp->fronts--;
		i--;
	}
	if( left != 0 && (i < 0 || partp->front_array[i].size < left ) )
	{
		fprintf(stderr, "left = %d, i = %d, actfrontsize = %d\n",
				left, i, partp->front_array[i].size );
	}
	assert(left == 0 || (i >= 0 && partp->front_array[i].size >= left));
	while (left > 0)
	{
		int sel = irand(partp->front_array[i].size);
		partp->front_array[i].size--;
		partp->front_array[i].members[sel] =
			partp->front_array[i].members[partp->front_array[i].size];
		left--;
		partp->size--;
	}
}

fpart* environmentalSelection( fpart* redu_part, fpart* repl_part,
		fpart* curr_part, int alpha, int sorting, char* varfile)
{
	heuristicReductionSPAM(redu_part,alpha);

	if( prefrel(curr_part, redu_part, prefrelType, sorting, ranking, bound, scaling ) )
		return curr_part;
	else
		return redu_part;

	return redu_part;
}