/***************************************************************************
  This is part of the evolver toolkit for exploring genetic progamming.
  Copyright (C) 1996 Benjamin Bennett and Yeasah G. Pell

  This library is free software; you can redistribute it and/or modify
  it under the terms of the GNU Library General Public License as
  published by the Free Software Foundation; either version 2 of the
  License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Library General Public License for more details.

  You should have received a copy of the GNU Library General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

  Contact information: Benjamin Bennett<fiji@limey.net> and Yeasah
    G. Pell<yeasah@wpi.edu>
  *************************************************************************/

/************************************************************************
  Member functions for the Generation class
  Perform evaluation, generation of new and successive generations

    This class holds all the information about a particular generation
  of programs and contains functions to evaluate, mutate and report on
  the programs.

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

#include "generation.H"

/* evaluates all the programs which comprise this generation */
void GGeneration::EvaluateGeneration()
{
	/* call evaluation on each model */
 	for (int i=0; i<programs.GetSize(); i++)
		programs[i]->Evaluate(models);
}

/* creates a random new program, given tree depth parameters */
GOperator *GGeneration::make_new_program(int min_depth, int max_depth, 
										 int cur_depth, int head_type, 
										 type_enum ret_type)
{
	GIntArray matching_ops;	// valid operators
	GOperator *new_node;		// new operator node
	int i;						// simple counter for the op types
	int accept;					// do we accept the node

	// build a list of appropriate operators
	for(i=0; i < NUM_OPERATORS; i++)
	{
		accept = 0;

		// if less than the tree's given minimum depth, make a non-terminal
		if(min_depth > cur_depth) 
		{
			if(optable.GetNumChildren((oper_enum)i) > 0)
			accept = 1;
		}
		// or if at the tree's maximum depth, make a terminal operator
		else if((max_depth <= cur_depth) 
			 && (optable.GetNumChildren((oper_enum)i) == 0))
			accept = 1;
		// or if less than the tree's given maximum depth, make any operator
		else if(max_depth > cur_depth)
			accept = 1;
		
		// finally check the type of the operator
		if((ret_type != TYPE_INVALID) && 
			(optable.GetType((oper_enum)i) != ret_type))
			accept = 0;
		if(accept)
			matching_ops.Append(i);
	}

	// if matching_ops is empty, all our operators are terminals
	if (matching_ops.GetSize() == 0)
	{
		cout << "make_new_program: no available operators of type " 
			<< (int)ret_type << endl;
		exit(1); 
	}
	
	if ((cur_depth == 0) && (head_type >= 0))
		// use the specified head
		new_node = new GOperator((oper_enum)head_type);
	else
	{
		// pick random head (must have kids if min_depth is greater than 1)
		i = (int)rand() % matching_ops.GetSize();
		new_node = new GOperator((oper_enum)matching_ops[i]);
	}

	// recursively create children
	for(i=0; i < optable.GetNumChildren(new_node->GetOperatorType()); i++)
		new_node->children.Append(make_new_program(min_depth, max_depth, 
						cur_depth+1, head_type, 
						optable.GetChildType(new_node->GetOperatorType(), i)));
	
	return new_node;
}

/* creates an initial set of programs */  
void GGeneration::GenerateNewGeneration(int num_progs, int min_depth, 
										int max_depth, int head_type)
{
	// save the depth values in the generation class
	stored_min_depth = min_depth;
	stored_max_depth = max_depth;

	// initialize stuff
	generation_num = 0;

	// make all the programs
	for(int i=0; i < num_progs; i++)
		programs.Append(new GProgram(make_new_program(min_depth, max_depth, 
													  0, head_type)));
	/* evaluate the programs */
	EvaluateGeneration();
}

// choose a program based on its fitness given ranks and sum of all ranks
int pick(GArray<GProgFit> &ranks, double total, double worst, double best)
{
	double choice;
	int i;

	// prevent the silly compiler message
	worst = best;

	/* pick a value between 0.0 and total */
	choice = total * ((double)rand() / RAND_MAX);
	// make sure choice is positive
	if (choice < 0.0)	choice = -1.0 * choice;

	/* keep subtracting the rank values from value until we go negative */
	for(i=0; i < ranks.GetSize() && choice >= 0.0; i++)
		choice -= ranks[i]->fitness;
	
#ifdef DEBUG_GENERATION
	cout << "Picked program: " << i << ':' << ranks[i-1]->prog_off << endl;
#endif // DEBUG_GENERATION
  
	return ranks[i-1]->prog_off;
}

/*****************************************************************
 Distribute the fitness scores to place different evolutionary
   pressures on the programs depending on the fitness scores.

 Strategy:
   Calculate mean and deviance
   Then depending on the conditions:
               Low Deviance         High Deviance
	  Low Mean    Narrow1              Narrow2
	 High Mean    Widen                Narrow3
	 
	 Narrow indicates that the best ones should be emphasized
	 Widen means that the low end should be emphasized
	 The numbers indicate the degree of adjustment, 1 is highest

	 The height of the mean is computed by 
   Iterate through the ranks and adjust each fitness score
   

 Arguments: 
   ranks: the fitness scores and program id's ordered in 
     descending order by fitness of the evaluated programs.
 *****************************************************************/
void spread_fitness(GArray<GProgFit> &ranks)
{
	int i, j;

	j = ranks.GetSize();
	for(i = 0; i < j; i++)
		ranks[i]->fitness += 1.0;

	//cheezy hack to test evaluation, put extra pressure on the first 1/4
	j = ranks.GetSize()/4;
	for(i = 0; i < j; i++)
		ranks[i]->fitness *= (j-i)*2;

	return;
}

/*****************************************************************
 Breed the "successful" programs then evaluate the new batch
 
 Arguments: 
   num_progs:   The size of the generation being bred
   prob_cross:  The frequency of crossover
   prob_mutate: The frequency of mutation
   prob_select: The frequency of selection (if - always select best)
 *****************************************************************/
void GGeneration::BreedNewGeneration(int num_progs, int prob_cross, 
									 int prob_mutate, int prob_select)
{
	int rand_val;				// which operation to choose next
	double best,worst;			// the best and worst fitness scores
	GArray<GProgFit> ranks;	// the program rankings
	double total = 0.0;			// the grand total of the rankings
	int i;

	/* increment the generation counter */
	generation_num++;

	/* get the program ranks */
	Rank(ranks);

	/* flip the domain by calculating the largest and reversing the ranking */
	best = -1.0;
	worst = 0.0;
	for(i = 0; i < ranks.GetSize(); i++)
	{
		if (worst < ranks[i]->fitness) worst = ranks[i]->fitness;
		if (best > ranks[i]->fitness || best == -1.0) 
			best = ranks[i]->fitness;
	}
#ifdef ABSOLUTE					// is the ranking absolute or relative?
	for(i = 0; i < ranks.GetSize(); i++)
		ranks[i]->fitness = worst - ranks[i]->fitness;
#endif //ABSOLUTE
	
	/* if this is the first run, set the worst (from best) */
	if (generation_num == 1) most_bad = best;

	/* change the raw fitness scores to "spread" the fitness a little */
	spread_fitness(ranks);

	/* find the total rank value */
	for(i = 0; i < ranks.GetSize(); i++)
		total += ranks[i]->fitness;

	/* do we always select the best? */
	if (prob_select < 0)
	{
		prob_select *= -1;		// set the value to its positive counterpart
		Select(ranks[0]->prog_off);	// and get the best
		i = 1;					// we have already used one program
	}
	else i = 0;

	/* step through all programs */
	while (i < num_progs)
    {
		/* pick a random value from 0 to the sum of the probabilities */
		rand_val = (int)rand() % (prob_cross + prob_mutate + prob_select);
		
		/* if crossover has been chosen */
		if (prob_cross > rand_val)
		{
#ifdef DEBUG_GENERATION
			cout << "Crossing over" << endl;
#endif // DEBUG_GENERATION

			Crossover(pick(ranks, total, worst, best), pick(ranks, total, 
															worst, best));
			i += 2;
		}

		/* if selection has been chosen */
		else if ((prob_select + prob_cross) > rand_val)
		{
#ifdef DEBUG_GENERATION
			cout << "Selecting" << endl;
#endif // DEBUG_GENERATION

			Select(pick(ranks, total, worst, best));
			i++;
		}

		/* if mutation has been chosen */
		else if ((prob_mutate + prob_select + prob_cross) > rand_val)
		{
#ifdef DEBUG_GENERATION
			cout << "Mutating" << endl;
#endif // DEBUG_GENERATION

			Mutate(pick(ranks, total, worst, best));
			i++;
		}
		
		/* if our fancy algorithm for choosing failed */
		else
		{
			cerr << "GGeneration::BreedNewGeneration: switch fell through" 
				 << endl;
			exit(-1);
		}
	}

	// delete ranks
	
	// clear out the old programs, copy in the new
	programs = new_programs;
	new_programs.Clear();

	/* evaluate the programs */
	EvaluateGeneration();
}