/***************************************************************************
  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>
  *************************************************************************/

/***************************************************************************
  GDistNetModel - Distributed network model

  Each node executes the instructions independent of the others.  There
  is no global overseer.
 **************************************************************************/

#include "network_model1.H"

GDistNetModel::GDistNetModel(int model, int max_iters)
{
	int i;

	var[0] = var[1] = 0;
	max_iterations = max_iters;
	iteration = 0;
	out = 0;

	old_net = new GNetwork;
	new_net = new GNetwork;

	// choose between the available netework models
	switch (model)
	{
	case 0:						// trivial model w/ 2 nodes and 1 pipe
		for(i=0; i<2; i++)
			old_net->AddNode();
		old_net->AddPipe(0, 1, 20);

		old_net->SetSource(0);
		old_net->SetSink(1);
		
		best_flow = 20;

		break;
	case 1:						// simple but not trivial
		for(i=0; i<4; i++)
			old_net->AddNode();

		old_net->AddPipe(0, 1, 20);
		old_net->AddPipe(0, 2, 10);
		old_net->AddPipe(1, 2, 5);
		old_net->AddPipe(2, 1, 5);
		old_net->AddPipe(1, 3, 10);
		old_net->AddPipe(2, 3, 20);

		old_net->SetSource(0);
		old_net->SetSink(3);

		best_flow = 25;

		break;
	case 2:						// more complex with some tricky stuff
		for(i=0; i<5; i++)
			old_net->AddNode();

		old_net->AddPipe(0, 1, 10);
		old_net->AddPipe(0, 2, 10);
		old_net->AddPipe(0, 3, 10);
		old_net->AddPipe(1, 0, 5);
		old_net->AddPipe(1, 2, 5);
		old_net->AddPipe(1, 4, 5);
		old_net->AddPipe(2, 4, 25);
		old_net->AddPipe(3, 2, 10);
		old_net->AddPipe(4, 3, 10);

		old_net->SetSource(0);
		old_net->SetSink(4);

		best_flow = 30;

		break;		
	case 3:						// extremely tricky network
		for(i=0; i<7; i++)
			old_net->AddNode();

		old_net->AddPipe(0, 1, 10);
		old_net->AddPipe(0, 2, 10);
		old_net->AddPipe(0, 3, 10);
		old_net->AddPipe(2, 4, 10);
		old_net->AddPipe(2, 5, 10);
		old_net->AddPipe(2, 6, 10);
		old_net->AddPipe(6, 5, 10);

		old_net->SetSource(0);
		old_net->SetSink(6);

		best_flow = 10;
		break;
	case 4:						// 32 node nasty thing
		for(i=0; i<32; i++)
			old_net->AddNode();
		
		old_net->AddPipe(0, 2, 20);
		old_net->AddPipe(0, 4, 30);
		old_net->AddPipe(1, 7, 20);
		old_net->AddPipe(1, 8, 20);
		old_net->AddPipe(2, 1, 20);
		old_net->AddPipe(3, 0, 20);
		old_net->AddPipe(4, 5, 30);
		old_net->AddPipe(4, 10, 30);
		old_net->AddPipe(5, 6, 30);
		old_net->AddPipe(5, 11, 30);
		old_net->AddPipe(5, 12, 30);
		// no pipes from 6
		old_net->AddPipe(7, 13, 20);
		old_net->AddPipe(8, 13, 20);
		old_net->AddPipe(9, 3, 20);
		old_net->AddPipe(9, 8, 20);
		old_net->AddPipe(10, 9, 30);
		// no pipes from 11
		// no pipes from 12
		old_net->AddPipe(13, 14, 40);
		old_net->AddPipe(13, 19, 40);
		old_net->AddPipe(14, 15, 40);
		old_net->AddPipe(14, 20, 40);
		old_net->AddPipe(15, 16, 40);
		old_net->AddPipe(15, 22, 20);
		old_net->AddPipe(16, 17, 40);
		old_net->AddPipe(17, 11, 40);
		old_net->AddPipe(17, 12, 40);
		old_net->AddPipe(17, 18, 40);
		old_net->AddPipe(17, 23, 20);
		old_net->AddPipe(18, 17, 20);
		old_net->AddPipe(18, 24, 20);
		old_net->AddPipe(19, 20, 40);
		old_net->AddPipe(19, 25, 40);
		old_net->AddPipe(19, 26, 10);
		old_net->AddPipe(20, 21, 40);
		old_net->AddPipe(21, 28, 30);
		old_net->AddPipe(22, 27, 30);
		old_net->AddPipe(23, 22, 10);
		old_net->AddPipe(23, 28, 20);
		old_net->AddPipe(23, 29, 20);
		old_net->AddPipe(23, 30, 20);
		// no pipes from 24
		// no pipes from 25
		old_net->AddPipe(26, 31, 40);
		old_net->AddPipe(27, 26, 30);
		// no pipes from 28
		old_net->AddPipe(29, 28, 40);
		old_net->AddPipe(30, 29, 20);
		old_net->AddPipe(31, 27, 40);
		old_net->AddPipe(31, 28, 40);

		old_net->SetSource(0);
		old_net->SetSink(31);

		best_flow = 40;		
		break;
	default:
		cout << "GDistNetModel::GDistNetModel - Invalid model: " 
			 << model << endl;
	}
	// copy old_net to new_net
	*new_net = *old_net;
}

GDistNetModel::~GDistNetModel()
{
	delete new_net;
	delete old_net;
}

/* returns the fitness values for a target of final evaluation = 50 */
GFitness GDistNetModel::GetFitness()
{
	GFitness fit;
	int pipe, num_pipes, sink, flow = 0;

	/* reset number of iterations  */
	/* (assuming we call GetFitness() at the end of a run) */
	iteration = 0;
	
	/* cahk-a-late the output flow from sink */
	sink = new_net->GetSink();
	num_pipes = new_net->QueryNumInPipes(sink);
	for(pipe=0; pipe < num_pipes; pipe++)
		flow += new_net->QueryInputFlow(sink, pipe);

	num_pipes = new_net->QueryNumOutPipes(sink);
	for(pipe=0; pipe < num_pipes; pipe++)
		flow -= new_net->QueryOutputFlow(sink, pipe);
	
	fit.fitness = flow;
	
	/* calculate a hit */
	if(flow >= best_flow)
	{
		fit.hits = 1;
		if(flow > best_flow)
		cerr << "Evaluated flow exceeded given maximum flow for network" << endl;
	}
	else
		fit.hits = 0;
	
#ifdef DEBUG
	cerr << "GDistNetModel::GetFitness(): hits=" << fit.hits << 
		" fitness=" << fit.fitness << endl;
#endif

	/* reset flows and messages */
	new_net->Reset();
	*old_net = *new_net;

	return fit;
}

/* evaluates a given operator */
GType *GDistNetModel::Evaluate(oper_enum operation, GArray<GType> &params, int node)
{
	int a[MAX_CHILDREN];
	int retval = -1;
	GType *ret = NULL;
	
    /* display diagnostics */
#ifdef DEBUG
	cerr << "GDistNetModel::Evaluate(" << optable.GetName(operation);
	for(int i=0; i<params.GetSize(); i++)
		cerr << ", " << (*(int *)(params[i]->GetData()));
	cerr << ")" << endl;
#endif
	
	/* check for the right number of children */
	if(optable.GetNumChildren(operation) == params.GetSize())
	{
		/* read the parameters */
		for(int i=0; i<optable.GetNumChildren(operation); i++)
			a[i] = *(int *)(params[i]->GetData());
	
			/* do the appropriate operation */
			switch(operation)
			{
			case OP_INC_FLOW:
				if(new_net->QueryNumOutPipes(node))
					new_net->IncreaseFlow(node, 
						abs(a[0] % new_net->QueryNumOutPipes(node)));
				retval = a[0];
				break;

			case OP_DEC_FLOW:
				if(new_net->QueryNumOutPipes(node))
					new_net->DecreaseFlow(node, 
						abs(a[0] % new_net->QueryNumOutPipes(node)));
				retval = a[0];
				break;

			case OP_QFLOW_IN:
				if(new_net->QueryNumInPipes(node))
					retval = old_net->QueryInputFlow(node, 
						abs(a[0] % new_net->QueryNumInPipes(node)));
				break;

			case OP_QFLOW_OUT:
				if(new_net->QueryNumOutPipes(node))
					retval = old_net->QueryOutputFlow(node,
						abs(a[0] % new_net->QueryNumOutPipes(node)));
				break;

			case OP_QPIPES_IN:
				if(new_net->QueryNumInPipes(node))
					retval = old_net->QueryNumInPipes(node);
				break;

			case OP_QPIPES_OUT:
				if(new_net->QueryNumOutPipes(node))
					retval = old_net->QueryNumOutPipes(node);
				break;

			case OP_QCAP_IN:
				if(new_net->QueryNumInPipes(node))
					retval = old_net->QueryCapacityIn(node, 
						abs(a[0] % new_net->QueryNumInPipes(node)));
				break;

			case OP_QCAP_OUT:
				if(new_net->QueryNumOutPipes(node))
					retval = old_net->QueryCapacityOut(node, 
						abs(a[0] % new_net->QueryNumOutPipes(node)));
				break;

			case OP_SMSG_OUT_1:
				if(new_net->QueryNumOutPipes(node))
					new_net->SendMessageOut(node, 
						abs(a[0] % new_net->QueryNumOutPipes(node)), 
						1, a[1]);
				retval = a[1];
				break;

			case OP_RMSG_OUT_1:
				if(new_net->QueryNumOutPipes(node))
					old_net->RecieveMessageOut(node, 
						abs(a[0] % new_net->QueryNumOutPipes(node)),
						1, retval);
				break;

			case OP_SMSG_OUT_2:
				if(new_net->QueryNumOutPipes(node))
					new_net->SendMessageOut(node, 
						abs(a[0] % new_net->QueryNumOutPipes(node)),
						2, a[1]);
				retval = a[1];
				break;

			case OP_RMSG_OUT_2:
				if(new_net->QueryNumOutPipes(node))
					old_net->RecieveMessageOut(node, 
						abs(a[0] % new_net->QueryNumOutPipes(node)),
						2, retval);
				break;

			case OP_SMSG_IN_1:
				if(new_net->QueryNumInPipes(node))
					new_net->SendMessageIn(node, 
						abs(a[0] % new_net->QueryNumInPipes(node)), 
						1, a[1]);
				retval = a[1];
				break;

			case OP_RMSG_IN_1:
				if(new_net->QueryNumInPipes(node))
					old_net->RecieveMessageIn(node,
						abs(a[0] % new_net->QueryNumInPipes(node)), 
						1, retval);
				break;

			case OP_SMSG_IN_2:
				if(new_net->QueryNumInPipes(node))
					new_net->SendMessageIn(node, 
						abs(a[0] % new_net->QueryNumInPipes(node)), 
						2, a[1]);
				retval = a[1];
				break;

			case OP_RMSG_IN_2:
				if(new_net->QueryNumInPipes(node))
					old_net->RecieveMessageIn(node, 
						abs(a[0] % new_net->QueryNumInPipes(node)), 
						2, retval);
				break;

			case OP_IS_SOURCE:
				retval = (node == old_net->GetSource());
				break;

			case OP_IS_SINK:
				retval = (node == old_net->GetSink());
				break;

				// Control operations
			case OP_IF:			// If: void (bool cond, void if, void then)
				cerr << "Error: Calling Evaluate for OP_IF" << endl;
				break;

			case OP_WHILE:		// While: void (bool cond, void loop)
				cerr << "Error: Calling Evaluate for OP_WHILE" << endl;
				break;

				// logical operations
			case OP_AND:		// Logical and: bool (bool a, bool b)
				retval = (a[0] && a[1])?1:0;
				break;

			case OP_OR:			// Logical or: bool (bool a, bool b)
				retval = (a[0] || a[1])?1:0;
				break;

			case OP_NOT:		// Logical not: bool (bool a)
				retval = (!a[0])?1:0;
				break;

			case OP_LT:			// Less than: bool (int a, int b)
				retval = (a[0] < a[1])?1:0;
				break;

			case OP_EQ:			// Equal to: bool (int a, int b)
				retval = (a[0] == a[1])?1:0;
				break;

			case OP_TRUE:		// Terminal boolean
				retval = 1;
				break;

			case OP_VAR_1:		// Variable 1
				retval = var[0];
				break;

			case OP_VAR_2:		// Variable 2
				retval = var[1];
				break;

			case OP_ASSN_VAR:	// Variable assignment
				if(a[1] > 1 || a[1] < 0)
					cerr << "Error: Bad index for variable assignment " 
					     << a[1] << endl;
				else
					retval = var[a[1]] = a[0];
				break;

				// arithmetic operations
			case OP_DATA_INT:
	            retval = 1;
	            break;

	        case OP_ADD_INT:
	            retval = a[0] + a[1];
	            break;
	  
	        case OP_SUB_INT:
	            retval = a[0] - a[1];
	            break;
	  
	        case OP_MUL_INT:
	            retval = a[0] * a[1];
	            break;
	  
			default:
				cerr << "GDistNetModel::Evaluate() - unknown opcode:" 
					<< optable.GetName(operation) << endl;
			}
	}


#ifdef DEBUG
	cerr << " = " << retval << endl;
#endif
  
	/* return value */
	switch(optable.GetType(operation))
	{
	case TYPE_INT:
		ret = new GIntType(retval);
		break;
	case TYPE_BOOL:
		ret = new GBoolType(retval);
		break;
	default:
		cerr << "GDistNetModel::Evaluate() - Bad type" << endl;
	}

	return ret;
}

/*********************************************************************
  Evaluate an operator (called by GProgram)

  Arguments:
    head: the head of the current tree to evaluate
  
  Returns:
    The last evaluated type if execution completed (rare)
	NULL if the execution ended early

  Strategy:
    This is tricky for the network model since we need to evaluate in
		"parallel"
	Keep an array holding the state of the evaluation
		State consists of the node that is being evaluated (like a pc)
		and the returned values from the evaluated children.
	Iterate through the nodes evaluating one instruction for each
	Remeber the steps are discrete.  We need to keep two copies of
		the network so we can have a current and a new

 *******************************************************************/
int GDistNetModel::Evaluate(GOperator *head)
{
	GArray<GHostState> hosts;
	GIntArray done;
	int ticks;							//the number of elapsed ticks
	int i;
	int all_done;
	
	// create array
	for(i=0; i < old_net->GetNumNodes(); i++)
	{
		hosts.Append(new GHostState(head));
		done[i] = 0;
	}

	all_done = 0;
	for (ticks=0; !all_done && (ticks < max_iterations); ticks++)
	{
		all_done = 1;
		for(i=0; i<hosts.GetSize(); i++)
		{
			if (!done[i])
			{
				all_done = 0;
				if(!hosts[i]->EvaluateTick(this, i))
					done[i] = 1;
			}

			// tell the model to implement all of the changes to the network
			*old_net = *new_net;
		}
	}

#ifdef DEBUG_GENERATION
	cout << "FLOW:" << old_net->QueryOutputFlow(0,0) << "|" 
		<< old_net->QueryInputFlow(1,0) << endl;
#endif // DEBUG_GENERATION
	return 1;
}


/* return the next child to evaluate, or -1 when done */
int GDistNetModel::GetNext(oper_enum operation, int last, GType *value)
{
	int retval;

	switch(operation)
	{
	case OP_IF:
		// if this is the first
		if (value == NULL)
			retval = 0;
		// if we are not on the conditional
		else if (last != 0)
			retval = -1;
		// if last evaluated returned true
		else if (*(int *)value->GetData())
			retval = 1;
		else retval = -1;
		break;
	case OP_WHILE:
		// if this is the first
		if (value == NULL)
			retval = 0;
		// if we are not on the conditional
		else if (last != 0)
			retval = 0;
		// if last evaluated returned true
		else if (*(int *)value->GetData())
			retval = 1;
		else retval = -1;		// end the loop
		break;
	default:
		cerr << "Model::GetNext - unhandled operation " << (int)operation 
			 << "/" << optable.GetName(operation) << optable.GetName((oper_enum)1) << endl;
		exit(1);
	}

	return retval;
}

/* decision function for length of runtime for a certain program */
int GDistNetModel::Running()
{
	iteration++;
	if(iteration > max_iterations)
		return 0;
	else
		return 1;
}