/***************************************************************************
  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
    This subdivision holds all the Breeding functions available

    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"

// counts all return types in a tree.  also returns total count.
int count_types(int type_freq[], GOperator *tree)
{
	int size = 0, i;
	int num_children = tree->children.GetSize();

	// bump count of appropriate operator
	type_freq[optable.GetType(tree->GetOperatorType())] += 1;
	size += 1;

	// recurse with children
	for(i = 0; i < num_children; i++)
		size += count_types(type_freq, tree->children[i]);

	return size;
}

/////////////////////////////////////////////////////////////////////////////
// make_operator_list
//
// input:
//		type: the return type to search for
//		prog_root: the root node of the tree to search
//
// output:
//		parent_list: the list of all nodes which have children which match
//		child_list: corresponding to parent_list, which children match
//
// function:
//		scans the entire tree looking for nodes which have a child of
//		type 'type'.  when found, it inserts a pointer to the parent
//		node into parent_list, and the index of the child found into
//		child_list.
/////////////////////////////////////////////////////////////////////////////
void make_operator_list(GArray<GOperator> &parent_list,
					    GIntArray &child_list, GOperator *node,
					    type_enum type, GOperator *parent = NULL,
					    int child = 0)
{
	int num_children = node->children.GetSize();

	// if we match, add to list
	if(type == TYPE_INVALID ||
	   optable.GetType(node->GetOperatorType()) == type)
	{
		parent_list.Append(parent);
		child_list.Append(child);
	}

	// recurse with children
	for(int i = 0; i < num_children; i++)
		make_operator_list(parent_list, child_list, node->children[i],
						   type, node, i);
}

/**************************************************************************
  Perform the crossover operation on the given programs (by index)

  Arguments:
    prog_id1: The first program index to crossover
    prog_id2: The second program index to crossover
    (NOTE: These can refer to the same program)

  Strategy:
    Duplicate the two programs.
	Determine the frequency of operator appearance in each tree.
	Pick an operator type which is common to both lists.
	Pick a random node which has a child of the chosen type (in both lists).
	Cross over trees by rearranging pointers.
    
  Globals Used:
    GOperatorTable optable;
  ************************************************************************/
void GGeneration::Crossover(int prog_id1, int prog_id2)
{
	GOperator *prog_root[2];			// pointer to root node of program
	int prog_size[2];					// the number of nodes in the programs
	int prog_index[2];					// program indeces (in new_programs)
	
	GArray<GOperator> parent_list;	// all parents of selected operators
	GOperator *parent[2];				// chosen parent nodes
	GIntArray child_list;				// child numbers of selected operators
	int child[2];						// chosen child indices
	GOperator *pivot[2];				// chosen crossover nodes

	type_enum type;					// data type to cross over
	GIntArray common_types;			// data types which are in both programs
	int type_freq[2][NUM_TYPES];	// data type frequency lists
	
	int i, j, index, randval;

	// make copies of the programs which we are crossing over (select)
	prog_index[0] = new_programs.Append(new GProgram(*programs[prog_id1]));
	prog_index[1] = new_programs.Append(new GProgram(*programs[prog_id2]));
	
	// for both programs
	for(i=0; i < 2; i++)
	{
		// get a pointer to the root node of both programs
		prog_root[i] = new_programs[prog_index[i]]->GetRoot();

		// clear operator frequency array		
		for(j = 0; j < NUM_TYPES; j++)
			type_freq[i][j] = 0;
		
		// build array of frequency of operators in both trees
		prog_size[i] = count_types(type_freq[i], prog_root[i]);
		if(prog_size[i] == 0)
    	{
			cerr << "GGeneration::Crossover: empty program" << endl;
			exit(-1);
    	}
	}

	// find common data types (indexes in array in which both are != 0)
	prog_size[0] = 0;
	for(j = 0, i = 0; i < NUM_TYPES; i++)
	{
		// if the operator has at least one instance in both trees, add to list
		if(type_freq[0][i] > 0 && type_freq[1][i] > 0)
		{
			common_types.Append(i);
			
			// update frequency tables for proper random distribution
			type_freq[0][j] = type_freq[0][i] + type_freq[1][i];
			prog_size[0] += type_freq[0][j++];
		}
	}

	// if there are no common operators at all, no crossover is possible
	if(common_types.GetSize() == 0) 
	{
#ifdef DEBUG_GENERATION
		cout << "Warning: no crossover performed" << endl;
#endif //DEBUG_GENERATION
		return;
	}

	// pick a random type from list
	randval = rand() % prog_size[0];
	for(j=0; randval >= 0 && j < common_types.GetSize(); j++)
		randval -= type_freq[0][j];
		
	type = (type_enum)common_types[j-1];

	// for both programs
	for(i=0; i < 2; i++)
	{
		// create a list of all operators of type 'type'
		make_operator_list(parent_list, child_list, prog_root[i], type);

		// pick one of the operators at random
		index = rand() % parent_list.GetSize();
		
		// save the parent node
		parent[i] = parent_list[index];

		// save the chosen child index
		child[i] = child_list[index];

		// save the chosen node
		if(parent[i] == NULL)
			pivot[i] = prog_root[i];
		else
			pivot[i] = parent[i]->children[child[i]];

		// clear lists DO NOT DELETE!
		parent_list.Clear();
		child_list.SetSize(0);
	}

	// now we have chosen pivot[0..1] and parent[0..1], do the crossover

#ifdef DEBUG_GENERATION
	cout << optable.GetName(pivot[0]->GetOperatorType()) << ":" 
		<< optable.GetName(pivot[0]->GetOperatorType()) << endl;
	if (!pivot[0]->Valid())
		cout << "Pivot 0 invalid" << endl;
	if (!pivot[1]->Valid())
		cout << "Pivot 1 invalid" << endl;
	cout << "prog1:" << prog_id1 << "|" << new_programs[prog_index[0]]->GetLength()
		<< "  prog2:" << prog_id2 << "|" << new_programs[prog_index[1]]->GetLength() << endl;
#endif // DEBUG_GENERATION

	if(parent[0] != NULL)
		parent[0]->children[child[0]] = pivot[1];
	else
		new_programs[prog_index[0]]->SetRoot(pivot[1]);

	if(parent[1] != NULL)
		parent[1]->children[child[1]] = pivot[0];
	else
		new_programs[prog_index[1]]->SetRoot(pivot[0]);

#ifdef DEBUG_GENERATION
	if (!new_programs[prog_index[0]]->GetRoot()->Valid())
	{
		cout << "New program 0 invalid" << endl << "prog0" << endl;
		new_programs[prog_index[0]]->GetRoot()->Print();
		cout << "prog1" << endl;
		new_programs[prog_index[1]]->GetRoot()->Print();
	}
	if (!new_programs[prog_index[1]]->GetRoot()->Valid())
	{
		cout << "New program 1 invalid" << endl << "prog0" << endl;
		new_programs[prog_index[0]]->GetRoot()->Print();
		cout << "prog1" << endl;
		new_programs[prog_index[1]]->GetRoot()->Print();
	}
#endif // DEBUG_GENERATION
	
#ifdef DEBUG_EVALUATE
	if (!new_programs[new_programs.GetSize()-2]->GetRoot()->Valid())
	{
		cout << "Greet pain danny-boy - Crossover 1 failed the valid test" << endl;
		new_programs[new_programs.GetSize()-2]->GetRoot()->Print();
		cout << endl << "Original prog 1: " << prog_id1 << endl;
		programs[prog_id1]->GetRoot()->Print();
		cout << endl << "Original prog 2: " << prog_id2 << endl;
		programs[prog_id2]->GetRoot()->Print();
		cout << endl;
	}
	if (!new_programs.Last()->GetRoot()->Valid())
	{
		new_programs.Last()->GetRoot()->Print();
		cout << endl;
		cout << "Greet pain danny-boy - Crossover 2 failed the valid test" << endl;
	}
#endif // DEBUG_EVALUATE
}

/**************************************************************************
  Perform the mutation operation on the given program index

  Arguments:
    prog_id: The program index to mutate

  Strategy:
    Duplicate the program.
    Determine the size of the program by a complete traversal.
    Pick a random node with no weighting.
	Destroy the tree from the chosen node down.
	Generate a new tree below the node.

  Globals Used:
    GOperatorTable optable;
  ************************************************************************/
void GGeneration::Mutate(int prog_id1)
{
	int prog_index;				// the index of the new program
	GOperator *prog_root;		// the root of the new program
	int target_index;			// the target index for the mutation
	int i;
	type_enum saved_ret=TYPE_INVALID; // the return type of the deleted node
	GArray<GOperator> parent_list; // all parents of selected operators
	GIntArray child_list;		// child numbers of selected operators

	// make a copy of the program, get a pointer to the root node
	prog_index = new_programs.Append(new GProgram(*programs[prog_id1]));
	prog_root = new_programs[prog_index]->GetRoot();

	// create a list of all operators
	make_operator_list(parent_list, child_list, prog_root, TYPE_INVALID);

	// pick one of the operators at random
	i = parent_list.GetSize();
	if (i > 0)
		target_index = rand() % i;
	else 
	{
		cerr << "mutate(): zero sized tree" << endl;
		exit(1);
	}

	// delete the node if applicable (and all the sub nodes)
	// but first save the return type
	if(parent_list[target_index] != NULL)
	{
		saved_ret = optable.GetType(parent_list[target_index]->
			children[child_list[target_index]]->GetOperatorType());
		delete parent_list[target_index]->children[child_list[target_index]];
	}
	else
		delete prog_root;

	// actually mutate the thing by creating a new tree
	if(parent_list[target_index] != NULL)
	{
		parent_list[target_index]->children[child_list[target_index]]
			= make_new_program(stored_min_depth, stored_max_depth, 0, -1, 
								saved_ret);
	}
	else		// generate a new root
	{
		new_programs[prog_index]->SetRoot(
			make_new_program(stored_min_depth, stored_max_depth, 0, -1));
	}

#ifdef DEBUG_EVALUATE
	if (!new_programs.Last()->GetRoot()->Valid())
		cout << "Greet pain danny-boy - Mutate failed the valid test" << endl;
#endif // DEBUG_EVALUATE

	// prevent stuff from being deleted
	parent_list.Clear();
}

// select(copy) the given program
void GGeneration::Select(int prog_id1)
{
	// add the program to the new program list
	new_programs.Append(new GProgram(*programs[prog_id1]));

#ifdef DEBUG_EVALUATE
	if (!new_programs.Last()->GetRoot()->Valid())
		cout << "Greet pain danny-boy - Select failed the valid test" << endl;
#endif // DEBUG_EVALUATE
}