/*
 * li.h -- Lithium Genetic Programming Toolkit
 *
 # Copyright (c) 2006 Henry Strickland -- <strick> in the domain <yak.net>
 #
 # Permission is hereby granted, free of charge, to any person obtaining a
 # copy of this software and associated documentation files (the "Software"),
 # to deal in the Software without restriction, including without limitation
 # the rights to use, copy, modify, merge, publish, distribute, sublicense,
 # and/or sell copies of the Software, and to permit persons to whom the
 # Software is furnished to do so, subject to the following conditions:
 #
 # The above copyright notice and this permission notice shall be included
 # in all copies or substantial portions of the Software.
 #
 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 # THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 # OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 # ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 # OTHER DEALINGS IN THE SOFTWARE.
 #
 #         (* http://www.opensource.org/licenses/mit-license.php *)
 *
 */
 
#ifndef LI_H
#define LI_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>


#include <string>
#include <vector>
#include <exception>
#include <algorithm>


//#define FOR_SHORTNESS
#define NUM_ROGERS 1000

#define	Trace if(trace)Say
#define	Trace2 if(trace>=2)Say
#define	Trace3 if(trace>=3)Say

// A convenient place to breakpoint in gdb
extern "C" { extern void br(const char* where); }

namespace Li {

// Inject all the standard stuff into the Li namespace
using namespace std;

template <typename T>  // Builtin std::abs() doesnt handle double?!  This one does.
T abs(T x) { return (x>0) ? x : -x; }

typedef unsigned int word;  // Important that `word' be unsigned

void FATAL(const char* fmt, const char* a= "?", const char* b= "?", const char* c= "?");

void FATAL(const char* fmt, string a, string b= string("?"), string c= string("?"));


inline bool streq(const char*a, const char*b) { return not strcmp(a,b); }
inline bool streq(string a, string b) { return streq( a.c_str(), b.c_str() ); }



typedef int SAYER(FILE* stream, const char* format, ...);

extern SAYER DontSay;
extern SAYER* Say;

// Stringification
extern std::string ToString(int x);
extern std::string ToString(uint x);
extern std::string ToString(long x);
extern std::string ToString(unsigned long x);
extern std::string ToString(float x);
extern std::string ToString(double x);
extern std::string ToString(void* x);
extern std::string ToString(class Sampling x);
inline std::string ToString(const std::string& x) { return x; }

  template <typename T>
  std::string 
ToString(const std::vector<T>& x, size_t maxItems = 256 )
{
	std::string z= "[";
	z += ToString( x.size() );
	z += "]{ ";
	maxItems = std::min ( maxItems, x.size() );
	for (uint i=0; i<maxItems; i++) {
		z += ToString( x.at(i) ) + " ";
	}
	z += "}";
	return z;
}

// String Utilities
extern bool GetLine(FILE* f, string& z);
extern vector<string> SplitWords(string s);
bool SplitOnce( string in, char c, string& leftOut, string& rightOut ); // false if not found
string BraceEncodeStr( string b );
string BraceDecodeStr( string s );


inline word hex_char_to_word(char c) {
        return
                '0'<=c & c<='9'  ?  c-'0'       :
                'A'<=c & c<='Z'  ?  c-'A'+10    :
                'a'<=c & c<='z'  ?  c-'a'+10    : 0;
}


inline bool IsWhiteChar(char c) {
	return c==0 || c=='\t' || c=='\v' || c=='\n' || c=='\r' || c==' ';
}

class Logger;
class PartialLoggerLine {
	Logger&		logger;
	string		accum;

public:
	~PartialLoggerLine( );
	PartialLoggerLine( Logger& _logger, string _label );
	PartialLoggerLine& operator << (string item);

	template <typename T>
	PartialLoggerLine& operator << (T item) {
		*this << ToString(item);
		return *this;
	}

};
class Logger {
	FILE*	fd;
	string	enc_banner;

public:
	Logger(string _banner, FILE* fd);
	Logger(string _banner, string filename, string mode);
	~Logger();
	void writeAccumulatedItems(string s);

	PartialLoggerLine operator<< (string _label) {
		return PartialLoggerLine( *this, _label );
	}

	bool isNull() { return fd==NULL; }
};

template <typename T>
T PopFront( vector<T> &v )
{
	T z= v.at(0);
	vector<T> temp;
	for (uint i=1; i<v.size(); i++) temp.push_back( v.at(i) );
	v= temp;
	return z;
}


/////////////////////////////////////////////////
////
////   Trivial Unit Test Framework
////
////
////  To write a test in C++, use the TEST macro with a unique test name.
////  Use Assert() with a big A.   Notice you do not specify the void return
////  type, nor the void parameters; the macro provides those.
////
////	TEST(multiplication) {
////		Assert( 6 == 2 * 3 );
////	}

#define TEST(NAME) \
		extern "C" void Test_##NAME (void) ;\
		TestCase TestWakeUp_##NAME ( & Test_##NAME, #NAME );\
		void Test_##NAME (void)

class AssertException : public std::exception
{
    std::string ex_what;

  public:
    AssertException(std::string _what) throw();

    virtual ~AssertException() throw();

    /** Returns a C-style character string describing the general cause
     *  of the current error.  */
    virtual const char* what() const throw();
};


// The TEST(X) macro makes instances of this:
class TestCase {
        void            (*func)(void);
        const char      *name;
        TestCase        *next;

public:
        TestCase( void (*_func)(void), const char* _name );
        static void RunAll();
	static void ThrowAssertionFailure( const char*, int ) throw (AssertException);

	static long	AssertSuccessCount;
	static long	AssertFailureCount;
	static long	TestExceptionCount;

};

extern TestCase* TestRoot;  // Linked List of all TestCases


#define Assert(COND)	Assert_Impl(COND,__STRING(COND),__PRETTY_FUNCTION__,__FILE__,__LINE__)

#define AssertEq(EXPECT,GOT)	AssertEq_Impl(EXPECT,GOT,__STRING(EXPECT),__STRING(GOT),__PRETTY_FUNCTION__,__FILE__,__LINE__)

#define AssertStrEq(EXPECT,GOT)	AssertStrEq_Impl(EXPECT,GOT,__STRING(EXPECT),__STRING(GOT),__PRETTY_FUNCTION__,__FILE__,__LINE__)
#define AssertStrBeginsWith(EXPECT,GOT)	AssertStrBeginsWith_Impl(EXPECT,GOT,__STRING(EXPECT),__STRING(GOT),__PRETTY_FUNCTION__,__FILE__,__LINE__)

  extern void 
AssertStrEq_Impl(
	const std::string expected,
	const std::string got,
	const char* expectedExpr,
	const char* gotExpr,
	const char* pretty,
	const char* file,
	int line);

  extern void 
Assert_Impl(
	bool cond,
	const char* expr,
	const char* pretty,
	const char* file,
	int line);

template <typename T1, typename T2>
  void 
AssertEq_Impl(
	const T1& expected,
	const T2& got,
	const char* expectedExpr,
	const char* gotExpr,
	const char* pretty,
	const char* file,
	int line)
{
	if ( expected == got ) {
		// good
		++ TestCase::AssertSuccessCount;
	} else {
		++ TestCase::AssertFailureCount;
		std::string expectedStr = ToString(expected);
		std::string gotStr = ToString(got);
		fprintf(stderr, "AssertEq Failure #%ld in %s at %s:%d\nExpected: %s  =>  %s\nGot: %s  =>  %s\n",
			TestCase::AssertFailureCount, 
			pretty, file, line,
			expectedExpr, expectedStr.c_str(),
			gotExpr, gotStr.c_str()
		);
		fflush(stderr);
		TestCase::ThrowAssertionFailure( file, line );
	}


}



//   Number is the numeric type that all our languages calcuate in;
//     however if the language uses Tagged numbers, then Number is effectively 1 bit shorter.
//
//   Its length should match the length of a pointer, 
//     and we assume the actual pointers never have their low bit set.

typedef long		Number;

#define	NUMBER_FMT	"%ld"

typedef unsigned char	byte;
typedef unsigned int	uint;
typedef unsigned long	ulong;

extern int trace;


// We want control of Random numbers so we can seed them to make experiments repeatable.
class Random { public:

        // choose from range 0 .. n-1
        static uint choose(uint n) {
                Assert( n > 0 );
                return (uint)::random() % n;
        }

        static void setSeed(uint seed) {
                ::srandom(seed);
        }

        static uint currentTime(void) {
                return (uint) ::time(NULL);
        }


}; // end Random


string ReplaceCharWithString(string src, char c, string replace);


/*
 *  Linked  --  base class for any reference counted objects.
 *
 *      References can be done by calling link() and unlink() manually,
 *	or by using Link<T> to hold a reference to a T.
 */

class Linked {
public:
	int	linkCount;

protected:
	// Only unlink() should delete me.
	virtual	~Linked();

public:
	Linked() : linkCount(0) {}

	void link() {
		check();
		assert(linkCount>=0);
		++linkCount;
	}
	void unlink() {
		check();
		assert(linkCount>0);
		--linkCount;
		if (not linkCount) delete this;
	}
#ifdef NDEBUG
	void check() const {}
#else
	virtual void check() const;
#endif
};

/*
 *   Link<T>     -- reference-counted smartpointer,  holding a reference to a T, a subclass of Linked.
 *
 *	Fairly minimal.  Does not attempt hierarchical type conversions.
 *
 *      Be careful with operator ->() and operator *() :
 *		Geniune T* pointers from those are not reference counted.
 */

template <typename T>
class Link {

	T	* ptr;

public:
	Link() : ptr(0) {}
	Link(T* _p)
	  : ptr(_p)
	{
		if (ptr) { _p->check(); ptr->link(); }
	}
	Link(const Link<T>& _r) : ptr(_r.ptr) {
		_r.check();
		if (ptr) ptr->link();
	}

	Link<T>& operator=(const Link<T>& _r) { 
		check();
		_r.check();
		if (ptr) ptr->unlink();  // unlink the old
		ptr= _r.ptr;
		if (ptr) ptr->link();  // link the new
		check();
		return *this;
	}

	~Link() { if (ptr) { ptr->check(); ptr->unlink(); ptr= 0; } }

	operator T*() const { check(); return ptr; }
	T* operator ->() const { check(); return ptr; }

	void check() const {
		if (ptr) ptr->check();
	}
};

class Creature;
class Generation;
class Machine;
class Language;

typedef Link<Creature> CreatureLink;
typedef Link<Generation> GenerationLink;
typedef Link<Machine> MachineLink;
typedef Link<Language> LanguageLink;


class Error : public std::exception {
    const char*	why;
public:
    Error(const char* _why) throw() : why( strdup(_why) ) {}
    Error(string _why) throw() : why( strdup(_why.c_str()) ) {}
    Error() throw() : why( NULL ) {}

    virtual ~Error() throw();

    virtual const char* what() const throw();
};

class Stopped : public Error {
public:
    enum Because { OUT_OF_NODES, EVAL_TOO_DEEP, EVAL_TOO_MANY_STEPS, ENOUGH_OUTPUT };

    Because because;

public:

    Stopped(Because _because) throw();

    virtual ~Stopped() throw();

    virtual const char* what() const throw();

    static int Count_OUT_OF_NODES;
    static int Count_EVAL_TOO_DEEP;
    static int Count_EVAL_TOO_MANY_STEPS;
    static int Count_ENOUGH_OUTPUT;
};

/////////////////////////////////////
//
//  Numbers
//      A vector of Numbers, common target 

template <typename T>
class Vec : public Linked {

protected:
	virtual ~Vec<T>() {}
	
public:
	typedef typename vector<T>::size_type size_type;

	vector<T>	vec;

	Vec<T>() {}

	string asString();
	void reset() { vec.clear(); }

	T& at(size_type i) { return vec.at(i); }
	const T& at(size_type i) const { return vec.at(i); }

	T& operator[] (size_type i) { return vec[i]; }
	const T& operator[] (size_type i) const { return vec[i]; }

	size_type size() { return vec.size(); }
	void resize(size_type n) { vec.resize(n); }

	void clear() { vec.clear(); }
	void push_back(T x) { vec.push_back(x); }
};

typedef Vec<Number> Numbers;
typedef Vec<double> Doubles;
typedef Vec<uint> Uints;


///////////////////////////////////////
//
//   Runtime Parameters
//

class Params : public Linked {

protected:
	virtual ~Params();

public:
	uint	seed; // pseudo-random seed
	
	// specific to language
	uint	creatureInitialLength;
	uint	creatureMaxLength;
	uint	creatureGoalLength;
	double	creatureGoalLengthWeight;
	string	creatureAlphabet;	

	// specific to evaluation
	uint	maxNumOutputs;

	uint	limitDepth;
	uint	limitEvals;

	// specific to rating
	double	wedge;			// how much to exaggerate earliest distances
	double	shortPenalty;		// substitute this for log(dist) if output is shorter than target

	uint	P;	// population size
	uint	G;	// number of generations to run
	uint	mutateTimes;
	double	percentMutate;
	double	percentCross;
	uint	elitist;	// number of best fits to give free pass to

	uint	showBeaconFrequency;			// how often to print progress to stdout
	uint	finalBestToShow;			// how many of the final best to output
	uint	mrRogersNeighborhoodSize;		// how many neighbors to test for MrRogers
	uint	mrRogersNeighborhoodDepth;		// how deep to explore neighborhoods

	double	percentageUnderTwoToStop;

	Params(); // assigns default values, which Language may update.

	void setParam(string key, string value);
	void setParams( const vector<string> &args );
	string toString();
};


////////////////////////////////
//
//   Creatures are actually Program, 
//	represented by sourceCode and a language
//

class Creature : public Linked {
	//   As an optimization, Creature might be subclassed, but not yet.

protected:
	virtual ~Creature();

public:

	string		sourceCode;
	Language*	language;

	// 0 (best) to +infinity (worst)
	double		stdFitness;


public:
	// 1.0 (best) to 0.0 (worst)
	double	adjustedFitness() {
		Assert( stdFitness >= 0.0 );
		return 1.0 / 1.0 + stdFitness;
	}

	Creature( string _sourceCode, Language* _language ) 
		: sourceCode( _sourceCode )
		, language( _language )
		, stdFitness(-1) // Unknown
	{
	}
};


///////////////////////////////////
//
//   a Generation

class Generation : public Linked {

	void	potentialBestYet( Creature* prog, Machine* mach );  // may set bestYet and bestYetOutputs

protected:
	virtual ~Generation();
	
public:
	vector<CreatureLink>	vec;

	Link<Creature>		bestYet;
	Link<Numbers>		bestYetOutputs;
	string			bestYetReadableCode;

	uint			genNum;
	uint			numUnderFitnessTwo;

	Generation() : genNum(0), numUnderFitnessTwo(0) { }

	void sortByFitness();
	void addRatedCreature( Creature* prog, Machine* mach );
};



/*
 *  MachineIO is just the input & output part of a Machine; it has no eval().
 */
class MachineIO : public Linked {

protected:
	virtual ~MachineIO();

public:
	MachineIO( Link<Params> p );

	Link<Params>	m_params;

	Link<Numbers>	m_outputs;

	// vector<Number>	m_globals; // future

	void putnum(Number x) throw(Stopped) { 
		vector<Number> &v= m_outputs->vec;
		v.push_back(x);
		if (v.size() >= m_params->maxNumOutputs ) throw Stopped(Stopped::ENOUGH_OUTPUT);
	}

};
	
/*
 *  Machine adds a creature, so it has a program to eval.
 */
class Machine : public MachineIO {

protected:
	virtual ~Machine();
	virtual void eval_virtual( ) = 0;

public:
	Link<Creature>	m_creature;

	uint	depthCounter;
	uint	evalCounter;

	Machine( Link<Params> p, Link<Creature> c );

	void eval( ) throw (Error);

	virtual string readableCode();
};


class EvalCounter {
        Machine* mach;
public:
        EvalCounter(Machine* _mach);

        ~EvalCounter() {
                --mach->depthCounter;
        }
};


class Target;
class TargetNumbers;
// Languages are static singletons.
class Language {
	const char*	name;
	Language*	next;

public:
	Language( const char* _name );
	virtual ~Language();
	string getName() { return name; }
	virtual Link<Params> defaultParams( );
	virtual Link<Machine> createMachine( Link<Params> p, Link<Creature> c ) = 0;
	virtual Link<Creature> createRandomCreature( Params* p );

        virtual Link<Creature> mutate( Params* p, Creature* );
        virtual void cross( Params* p, Creature* c1, Creature* c2, CreatureLink& newc1, CreatureLink& newc2 );


	static Language* root;
	static Language* Find( const char* _name );
	static Language* Find( string _name ) { return Find(_name.c_str()); }
	static string List();

};

// Target are static singletons.
class Target {
	const char *	name;
	Target *	next;

public:
	Target( const char* _name );
	virtual ~Target();
	string getName() { return name; }

	static Target* root;
	static Target* Find( const char* _name );
	static Target* Find( string _name ) { return Find(_name.c_str()); }
	static string List();

	virtual double computeRawFitness( Machine*, Params* ) = 0;
	virtual string explainTarget() = 0;
	virtual Link<Machine> playAndRate( Creature *prog, Params *params, Language* lang ) = 0;

};

class TargetNumbers : public Target {

public:
	Link<Numbers> numbers;  // subclass constructors should add to numbers

	TargetNumbers( const char* _name );
	virtual ~TargetNumbers();

	virtual double computeRawFitness( Machine*, Params* );
	virtual string explainTarget();
	virtual Link<Machine> playAndRate( Creature *prog, Params *params, Language* lang );
};





#define	NUM_NODES	9999
#define	NUM_CHARS	128	/* the first few nodes represent chars */


typedef class Node* node;
struct Node {
	node	n_hd;
	node	n_tl;
};

class EvalCounter;
class TaggedMachine : public Machine {

protected:
	Node*	nodes;		// array of NUM_NODES Nodes
	int	nextNode;

        virtual ~TaggedMachine();
	virtual void eval_virtual();

public:
        TaggedMachine(Link<Params> p, Link<Creature> c );

	bool	isNum(node p)	{ return 0 != ((word)p & 1); }
	bool	isPtr(node p)	{ return 0 == ((word)p & 1); } // Char or Pair is Ptr
	bool	isChar(node p)	{ return isPtr(p) && p < &nodes[NUM_CHARS]; }
	bool	isPair(node p)	{ return isPtr(p) && p >= &nodes[NUM_CHARS]; }

	Number	asNum(node p)	{ assert(isNum(p)); return (Number)p >> 1; }
	word	asChar(node p)	{ assert(isChar(p)); return p-nodes; }

	node	hd3(node p)	{ assert(isPair(p)); return hd(tl(p->n_tl)); }
	node	hd2(node p)	{ assert(isPair(p)); return hd(p->n_tl); }
	node	hd(node p)	{ assert(isPair(p)); return p->n_hd; }
	node	tl(node p)	{ assert(isPair(p)); return p->n_tl; }
	node	cons(node p, node q);
	int	llen(node p);

	node	charNode(word n) { assert(n<NUM_CHARS); return &nodes[n]; }
	node	numNode(Number n) { return (node)((n<<1)|1); }

};

/*
 *  Sampling may be used two different ways, at runtime:
 *    -- to hold a solitary floating point number (i.e. double)
 *    -- to hold an average of some floating point numbers, with stddev, stderr, etc.
 *	In the last case, you must call clearForInsertions() on it first,
 *	then insert the samples with insertSample(x)
 *  The s_ok_to_add field remembers if clearForInsertions() was called.
 *  The reason for this runtime flexabilty is to reuse the "Score" classes
 *      for both the solitary and the averaged case.
 */

class Sampling {
	uint		s_count;
	double		s_sum;
	double		s_sum_squares;
	bool		s_ok_to_add;

public:
	Sampling();
	Sampling(double x);
	void	clearForInsertions();  // call this before insertSample add!
	void	insertSample(double x);
	void	insertSample(const Sampling& x);
	double	mean() const;
	double	stdDev() const;
	double	stdErr() const;
	double	sumSquares() const;
	uint	count() const;

	operator double() const;
	string	toString() const;
};
typedef Vec<Sampling> Samplings;
struct RogersScore {
	// fitnesses above e**NUM_BUCKETS fall into last bucket,
	// so the last bucket is really the overflow bucket.
	static const uint NUM_BUCKETS = 101; 

	Sampling		r_neutrality;

	vector<Link<Samplings> >	r_histos;

	void say( Logger& lg, string label );
	RogersScore() : r_neutrality(0) {}

	void	clearForInsertions();  // call this before calling insertSample!
	void	insertSample(const RogersScore& x);
};
struct GpScore {
	string		s_label;
	Sampling	s_num_generations;

	Sampling	s_final_fitness;
	Sampling	s_best_fitness;

	RogersScore		s_rogers_bestyet;
	vector<RogersScore>	s_rogers_final;

	RogersScore		s_rogers_final_average;

	GpScore() : s_num_generations(0), s_final_fitness(0), s_best_fitness(0) {}
	void computeAverageFinal();
	void say( Logger& lg );

	void	clearForInsertions();  // call this before calling insertSample!
	void	insertSample(const GpScore& x);
};

class BasicGP {

public:
	Logger			gp_note;
	Logger			gp_answer;
	GpScore			gp_score;

private:
	vector<string>		args;

	Language*		lang;
	Target*			targ;
	Link<Params>		params;

	Link<Generation>	initialGen;
	Link<Generation>	currentGen;

	// statitics
	uint		whenFirstCreatureIsUnderTwo;
	uint		whenFirstQuarterAreEachUnderTwo;

public:

	BasicGP( string lang_s, string targ_s, vector<string> _args );

	BasicGP( BasicGP& old, string new_targ_s );


	virtual ~BasicGP();
	virtual void go(void);
	Link<Generation> getCurrentGeneration() { return currentGen; }

private:
	void nextSeed();

	void doRogersCalculationsOnManyCreatures();
	void doRogersCalculationsOnOneCreature( Creature* prog, RogersScore &rScore, string prefix );

	// returns individual scores
	Link<Doubles> exploreRogersAtOneDepth( Link<Creature> prog, int depth, /*double&*/ Sampling& neutralityOut );

	void	saySummary( Logger&, Generation* gen, uint genNum );

	// returns logarithmic histogram
	Link<Doubles> histogramOfExploration( Link<Doubles> scores, double parentScore, string prefix );

	Link<Generation> createInitialBasicGen();
	Link<Generation> nextBasicGen();
	void showFinalBest();
	template <typename T>
	void displayBuckets( Link<T> buckets, string label, uint n );
};

class OnePlayerGameTarget : Target {

	virtual ~OnePlayerGameTarget();

	// this does not seem right, unless we generate nonstatic targets.
	virtual double computeRawFitness( Machine*, Params* ) = 0;

	// just a string for the human
	virtual string explainTarget() = 0;

	// returns a Link<Machine> -- is the machine needed?  or can it return the rating?
	virtual Link<Machine> playAndRate( Creature *prog, Params *params, Language* lang ) = 0;
};

class OnePlayerGame {

public:
	virtual Numbers getGameState(void) = 0;
	virtual void applyGameMove(Numbers) = 0;
	virtual double getFinalRating() = 0;

};

// auto LabelScope objects nest on the call stack.
struct LabelScope {
	string saved;

public:
	static string Current;
	static string Decorate(string _suffix);

	LabelScope(string _label);
	~LabelScope();
};

// auto ParamScope objects nest on the call stack.
struct ParamScope {
	vector<string> saved;

public:
	static vector<string> Current;
	static vector<string> Decorate(vector<string> _suffix);

	ParamScope(string _paramName, string _paramValue);
	~ParamScope();
};

class Substitutions {
        string  vars[256];

public:
        void set( char, string );
        string get( char );
        string subst( string );
};

// auto SubstScope objects nest on the call stack.
struct SubstScope {
	Substitutions saved;

public:
	static Substitutions Current;
	static vector<string> Subst(vector<string> _suffix);

	SubstScope(char _paramName, string _paramValue);
	~SubstScope();
};


} // end namespace Li

#endif /* LI_H */