// pareto.cc     File to perform pareto selection, build with GPQUICK-2.1
// W. Langdon cs.ucl.ac.uk 24 August 1994

#define version "9 Sep 1994 $Revision: 1.7 $"

//Modifications (in reverse order)

//WBL 13 Sep 1994 Make compilable by solaris gcc

//WBL  9 Sep 1994 Implement pMaxAge in Worstof

//WBL 7A Sep 1994 Dont discard identicals

//WBL 29 Aug 1994 Select on memory, but not on makenull or enqueue.
//                Expand top list to 50. 

//WBL 27 Aug 1994 Add discarding identicals. Scan whole list but keep only
//                top 10, rather than scanning only 1st ten.

//requires MULTREE to be defined

#include "pch.h"
#include "chrome.h"
#include "queue2.h"

#include <assert.h>
//**************************************************************************

#define IDENTICAL -2

BOOL myfitnessvalue::IsBetter(FitnessValue* fv)
{
if( this->dominates(ptrmyfitnessvalue(fv)) >0 ) return TRUE;
                                                return FALSE;
};//end myfitnessvalue::IsBetter

int myfitnessvalue::dominates(myfitnessvalue* target)
{
//cout<<"dominates this="; write();cout<<"\tover? "; target->write();

int a[4]={this->hits[front],  this->hits[dequeue],  this->hits[empty],
	  this->mem_used  <=  mem_penalty_bot? 0: -this->mem_used};

int b[4]={target->hits[front],target->hits[dequeue],target->hits[empty],
	  target->mem_used <= mem_penalty_bot? 0: -target->mem_used};

BOOL dom = IDENTICAL;

for (int i = 0; i<4; i++)
{
	if      (a[i] > b[i])
	      { if (dom == -1) return 0;
		else dom = 1;
	      }
	else if (a[i] < b[i])
	      { if (dom == 1) return 0;
		else dom = -1;
	      }
};//end loop

return dom;

};//end myfitnessvalue::dominates;

Chrome* select_hits (Chrome*  list[], int listsize,
                              int* bestinlist, BOOL best = TRUE)
{
int better [listsize]; //use static array to hold dynmic list of candidates;
int listhead  = -1;     //ie empty
int numbetter = 0;      //ie empty too!
int numbetter_max = 0;  //Indicates potential group overrruns
const int better_list_max = 50;

for (int i = 0; i<listsize; i++)
{
int old_j = -1;
for (int j = listhead; j >= 0; j = better[j])
{
	int d = ptrmyfitnessvalue(list[i]->nfitness)->dominates(
                ptrmyfitnessvalue(list[j]->nfitness)           );
//	cout<<" ans("<<i<<","<<j<<")="<<d<<endl;
	if (!best) d = -d;
	if ( d > 0 )
	{//remove j from candidates
		if ( old_j >= 0 ) better[old_j] = better[j];
		else              listhead      = better[j];
	        numbetter--;
	        numbetter_max--;
	}
        else if ( d < 0 )
	{//remove i from consideration
		goto discard_list_element;
	}
	else
	{
		old_j = j;
        }
};//end scan better

if (numbetter<=better_list_max)
	{
		better[i] = listhead; //add i to candidates
		listhead  = i;
		numbetter++;
        }
numbetter_max++;

discard_list_element: ;
};//end scan list

if (numbetter<numbetter_max)
	{
	cout<< "select_hits reduced parento group to " << better_list_max;
	cout<< " (upper limit not more than) " << numbetter_max << endl;
        }

//cout<<" final list size " << numbetter <<flush;

int chosen = rnd (numbetter);
for (i = listhead; chosen > 0; i = better[i]) chosen--;

//cout<<" select_hits: chosing " << i <<endl;

*bestinlist = i;
return list[i];

};//end select_hits;


Chrome* queue::Bestof(Chrome*  list[], int listsize,
                               int* bestinlist )
{
if ( bestinlist == NULL ) {int dummy; bestinlist = &dummy;}//discard

return select_hits (list, listsize, bestinlist );
};//end Bestof


Chrome* queue::Worstof(Chrome* list[], int listsize,
	                       int timenow, int* worstinlist)
{
// Will select a target that is too old, even if more fit.

for (int i=1; i<listsize; i++)
{
	if (list[i]->params->params[pMaxAge] != 0 &&
	     (timenow - list[i]->birth) > list[i]->params->params[pMaxAge])
	     {	*worstinlist = i;
	        return list[i];
	     }
}


return select_hits (list, listsize, worstinlist, FALSE );
};//end Worstof