#include <math.h>
#include <string.h>
#include <stdlib.h>
#include "common.h"
#include "ghost.h"
#include "string.h"

extern double drand48();
extern int TURN_NUMBER;

Maze * Ghost::maze = NULL;

const int Ghost::MAX_PROGRAM_LENGTH = 200;
const int Ghost::MAX_NEW_PROGRAM_LENGTH = MAX_PROGRAM_LENGTH / 2;
const int Ghost::MAX_MUTATED_SUBTREE_LENGTH = MAX_PROGRAM_LENGTH / 3;
const int Ghost::MAX_RANDOM_MATCH_TRIES = 20;
const int Ghost::MAX_INTEGER_LENGTH = 3;
const int Ghost::MAX_FLOAT_LENGTH = 3;

inline float abs(float x);

template <class T>
void swap (T& a, T& b);

template <class T>
T min (T a, T b);

template <class T>
T max (T a, T b);

template <class T>
void swap (T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}
	
template <class T>
T min (T a, T b)
{
	return (a < b) ? a : b;
}

template <class T>
T max (T a, T b)
{
	return (a > b) ? a : b;
}

inline float abs(float x)
{
	return (x >= 0) ? x : -x;
}

bool Ghost::checkProgramLength ()
{
	programIndex = newProgram;
	skip ();

	if (*newProgramLength != programIndex - newProgram)
	{
		*newProgramLength = programIndex - newProgram;
		return true;
	}

	return false;
}

void Ghost::outputProgram (ostream& out /* = cout */)
// This function calls the various functions necessary to output the
// ghost's parsing string in understandable language
{
	programIndex = program;
	outputDirection(out, 0);
	out << endl;
	for(int i=0; i < *programLength; i++)
	{
		if (program[i] > 10)
			out << program[i];
		else
			out << short(program[i]);
	}
	out << endl;
}

void Ghost::moveCursorRight (ostream& out, int depth)
// This function moves the cursor right to indent output
{
	for(; depth > 0; depth--)
	{
		out << "   ";
	}
}
// The "output*" functions expand and output the strings one character
// at a time

void Ghost::outputDirection (ostream& out, int depth)
// ouputDirection outputs directions and the conditional "if"
{
	switch (*(programIndex++))
	{
	case 'i':
	// An if statement will include a boolean, a clause for the if
	// being true, and an else clause, hence outputBool is called,
	// then outputDirection is called twice
		out << "(if ";
		outputBool(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputDirection(out, depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputDirection(out, depth);
		out << ")";
		return;
	case 'F':
		out << "Forward";
		return;
	case 'B':
		out << "Backwards";
		return;
	case 'R':
		out << "Right";
		return;
	case 'L':
		out << "Left";
		return;
	case 'N':
		out << "North";
		return;
	case 'E':
		out << "East";
		return;
	case 'S':
		out << "South";
		return;
	case 'W':
		out << "West";
		return;
	case 'o':
	// The command to drop a pheromone takes three arguments, a
	// pheromone strength, a pheromone value, and a direction in
	// which to move.
		out << "(drop-pheromone ";
		outputNumber (out, ++depth);
		out << "\n";
		moveCursorRight (out, depth);
		outputNumber (out, depth);
		out << "\n";
		moveCursorRight (out, depth);
		outputDirection (out, depth);	
		out << ")";
		return;
	default:
		cerr << "Badly formatted program string " << program << endl;
		cerr << "Before character " << programIndex << endl;
	}
}

void Ghost::outputBool (ostream& out, int depth)
// This function expands and outputs booleans
{
	switch (*(programIndex++))
	{
	case '=':
	// For example, an equals sign will be followed by two numbers,
	// so outputNumber will be called twice for every equals sign
		out << "(= ";
		outputNumber(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputNumber(out, depth);
		out << ")";
		return;
	case '<':
		out << "(< ";
		outputNumber(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputNumber(out, depth);
		out << ")";
		return;
	case '>':
		out << "(> ";
		outputNumber(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputNumber(out, depth);
		out << ")";
		return;
	case '{':
		out << "(<= ";
		outputNumber(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputNumber(out, depth);
		out << ")";
		return;
	case '}':
		out << "(>= ";
		outputNumber(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputNumber(out, depth);
		out << ")";
		return;
	case '!':
		out << "(not ";
		outputBool(out, depth+1);
		out << ")";
		return;
	case '|': // Short curcuit okay
		out << "(or ";
		outputBool(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputBool(out, depth);
		out << ")";
		return;
	case '&': // Short circuit okay
		out << "(and ";
		outputBool(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputBool(out, depth);
		out << ")";
		return;
	default:
		cerr << "Badly formatted program string " << program << endl;
		cerr << "Before character " << programIndex << endl;
	}
}

void Ghost::outputNumber (ostream& out, int depth)
// This function outputs numbers, including such ghost-determined
// functions as "pacmen-in-direction"
{
	switch (*(programIndex++))
	{
	case '+':
		out << "(+ ";
		outputNumber(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputNumber(out, depth);
		out << ")";
		return;
	case '-':
		out << "(- ";
		outputNumber(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputNumber(out, depth);
		out << ")";
		return;
	case '*':
		out << "(* ";
		outputNumber(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputNumber(out, depth);
		out << ")";
		return;
	case '/':
		out << "(/ ";
		outputNumber(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputNumber(out, depth);
		out << ")";
		return;
	case '%':
		out << "(% ";
		outputNumber(out, ++depth);
		out << "\n";
		moveCursorRight(out, depth);
		outputNumber(out, depth);
		out << ")";
		return;
	case '_':
		out << "(_ ";
		outputNumber (out, depth+1);
		out << ")";
		return;
	case 'C':
		out << "CONSECUTIVE_MOVES_FORWARD";
		return;
	case 'P':
		out << "PHEROMONE-STRENGTH";
		return;
	case 'Q':
		out << "NUM_SQUARES";
		return;
	case 'T':
		out << "TURN_NUMBER";
		return;
	case 'V':
		out << "PHEROMONE-VAL";
		return;
	case 'a':
		out << "(abs ";
		outputNumber (out, depth+1);
		out << ")";
		return;
	case 'c':
		out << "(cosine ";
		outputNumber (out, depth+1);
		out << ")";
		return;
	case 'd':
		out << "(dots-in-dir ";
		outputDirection (out, depth+1);
		out << ")";
		return;
	case 'f':
		out << "(squares-to-ghost ";
		outputDirection (out, depth+1);
		out << ")";
		return;
	case 'g':
		out << "(ghosts-in-dir ";
		outputDirection (out, depth+1);
		out << ")";
		return;
	case 'm':
		out << "(squares-to-pacman ";
		outputDirection (out, depth+1);
		out << ")";
		return;
	case 'p':
		out << "(pacmen-in-dir ";
		outputDirection (out, depth+1);
		out << ")";
		return;
	case 'r':
		out << "(round ";
		outputNumber (out, depth+1);
		out << ")";
		return;
	case 's':
		out << "(sine ";
		outputNumber (out, depth+1);
		out << ")";
		return;
	case 't':
		out << "(squares-to-dot ";
		outputDirection (out, depth+1);
		out << ")";
		return;
	case 'w':
		out << "(squares-to-wall ";
		outputDirection (out, depth+1);
		out << ")";
		return;
	case 'z':
		out << "(squares-to-non-dot ";
		outputDirection (out, depth+1);
		out << ")";
		return;
	default:
	// Numeric constant
		for (programIndex--; *programIndex != ';'; programIndex++)
		{
			if (*programIndex < 10)
				out << short(*programIndex);
			else
				out << *programIndex;
		}
		programIndex++;
		return;
	}
}

void Ghost::newGame ()
// This functions makes the necessary changes to allow for the start
// of a new game
{
	Location* temp = maze->getGhostStart();

	x = temp->x;
	y = temp->y;

	lastDirection=randomDirection();
	consec = 0;
}

void Ghost::init (	char* inProgram,
			char* inNewProgram,
			int* inProgramLength,
			int* inNewProgramLength)
// 
{
	program = inProgram;
	newProgram = inNewProgram;

	programLength = inProgramLength;
	newProgramLength = inNewProgramLength;

	programIndex = program;
	*programLength = mutateDirection(MAX_NEW_PROGRAM_LENGTH);
}

void Ghost::move ()
// This is the public function that gets called to move
// the ghosts
{
	programIndex = program;
	makeMove (getDirection());
}

// The get* functions parse through the ghost strings
// while advancing the programIndex, which keeps track
// of where you are in the program

int Ghost::getDirection ()
{
	switch (*(programIndex++))
	{
	case 'i':
		if (getBool())
		{
			int temp = getDirection();
			skip();
			return temp;
		}
		else
		{
			skip();
			return getDirection();
		}
	case 'F':
		return lastDirection;
	case 'B':
		return backDir(lastDirection);
	case 'R':
		return nextDir(lastDirection);
	case 'L':
		return prevDir(lastDirection);
	case 'N':
		return N;
	case 'E':
		return E;
	case 'S':
		return S;
	case 'W':
		return W;
	case 'o':
		maze->dropPheromone(int(getNumber()), int(getNumber()), x, y);
		return getDirection();
	default:
		cerr << "Badly formatted program string " << program << endl;
		cerr << "Before character " << programIndex << endl;
	return N;
	}
}

bool Ghost::getBool()
{
	switch (*(programIndex++))
	{
	case '=':
		return (getNumber() == getNumber());
	case '<':
		return (getNumber() < getNumber());
	case '>':
		return (getNumber() > getNumber());
	case '{':
		return (getNumber() <= getNumber());
	case '}':
		return (getNumber() >= getNumber());
	case '!':
		return (!getBool());
	case '|': // Manually implemented short curcuit
		if (getBool())
		{
			skip();
			return true;
		}
		else 
			return getBool();
	case '&': // Manually implemented short curcuit
		if (getBool())
			return getBool();
		else
		{
			skip();
			return false;
		}
	default:
		cerr << "Badly formatted program string " << program << endl;
		cerr << "Before character " << programIndex << endl;
	return true;
	}
}

float Ghost::getNumber ()
{
	switch (*(programIndex++))
	{
	case '+':
		return getNumber() + getNumber();
	case '-':
		return getNumber() - getNumber();
	case '*':
		return getNumber() * getNumber();
	case '/':
		{
			float firstVal = getNumber();
			float secondVal = getNumber();
			if (secondVal == 0)
				return 1;
			else
				return firstVal/secondVal;
		}
	case '%':
		{
			long firstVal = long(getNumber());
			long secondVal = long(getNumber());
			if (secondVal == 0)
				return 0;
			else
				return firstVal % secondVal;
		}
	case '_':
		return -getNumber();
	case 'C':
		return consec;
	case 'P':
		return maze->pheromoneStrength(x, y);
	case 'Q':
		return Maze::NUM_SQUARES;
	case 'T':
		return TURN_NUMBER;
	case 'V':
		return maze->pheromoneVal(x, y);
	case 'a':
		return abs(getNumber());
	case 'c':
		return cos(getNumber());
	case 'd':
		return maze->dotsInDir(getDirection(), x, y);
	case 'f':
		return maze->squaresToGhost(getDirection(), x, y);
	case 'g':
		return maze->ghostsInDir(getDirection(), x, y);
	case 'm':
		return maze->squaresToPacman(getDirection(), x, y);
	case 'p':
		return maze->pacmenInDir(getDirection(), x, y);
	case 'r':
		return floor(getNumber());
	case 's':
		return sin(getNumber());
	case 't':
		return maze->squaresToDot(getDirection(), x, y);
	case 'w':
		return maze->squaresToWall(getDirection(), x, y);
	case 'z':
		return maze->squaresToNonDot(getDirection(), x, y);
	default:
	// Numeric constant
		programIndex--; // Back up
		char* end;
		char* start = programIndex;
		int tenPower = 1;
		float val = 0;

		for(; *programIndex != '.' && *programIndex != ';';
programIndex++);

		end = programIndex;

		programIndex--;
		for(; programIndex >= start; programIndex--)
		{
			val += *programIndex * tenPower;
			tenPower *= 10;
		}

		programIndex = end;

		if (*programIndex++ == '.')
		{
			float mult=.1;
			char c;
			while ((c = *programIndex++) != ';')
			{
				val += mult*c;
				mult *= .1;
			};
		}	
		return val;
	}
}

void Ghost::makeMove(int dir)
// This function performs the bookkeepping for the
// ghost's movement
{
	if (lastDirection==dir)
	{
		consec++;
	}
	else
	{
		lastDirection=dir;
		consec=1;
	}
	int xOld = x, yOld = y;
	if (directionOK(dir))
	{
		x += xChange(dir);
		y += yChange(dir);
	}

	maze->moveGhost(xOld, yOld, x, y);
}

bool Ghost::directionOK(int dir)
// This function communicates with the maze; it returns whether or
// not there is a wall in a given direction
{
	return maze->ghostMoveOK(x + xChange(dir), y + yChange(dir));
}

int Ghost::mutateNumber (int maxTreeDepth)
{
	do
	{
		switch (int(drand48() * 25))
		{
		case 0: // +
			if (maxTreeDepth >= 3)
			{
				int origMaxTreeDepth = maxTreeDepth--;
				*programIndex++ = '+';
				maxTreeDepth -= mutateNumber(maxTreeDepth-1);
				return origMaxTreeDepth - maxTreeDepth + mutateNumber(maxTreeDepth);
			}
			break;
		case 1: // -
			if (maxTreeDepth >= 3)
			{
				int origMaxTreeDepth = maxTreeDepth--;
				*programIndex++ = '-';
				maxTreeDepth -= mutateNumber(maxTreeDepth-1);
				return origMaxTreeDepth - maxTreeDepth + mutateNumber(maxTreeDepth);
			}
			break;
		case 2: // *
			if (maxTreeDepth >= 3)
			{
				int origMaxTreeDepth = maxTreeDepth--;
				*programIndex++ = '*';
				maxTreeDepth -= mutateNumber(maxTreeDepth-1);
				return origMaxTreeDepth - maxTreeDepth + mutateNumber(maxTreeDepth);
			}
			break;
		case 3: // /
			if (maxTreeDepth >= 3)
			{
				*programIndex++ = '/';
				int origMaxTreeDepth = maxTreeDepth--;
				maxTreeDepth -= mutateNumber(maxTreeDepth-1);
				return origMaxTreeDepth - maxTreeDepth + mutateNumber(maxTreeDepth);
			}
			break;
		case 4: // %
			if (maxTreeDepth >= 3)
			{
				*programIndex++ = '%';
				int origMaxTreeDepth = maxTreeDepth--;
				maxTreeDepth -= mutateNumber(maxTreeDepth-1);
				return origMaxTreeDepth - maxTreeDepth + mutateNumber(maxTreeDepth);
			}
			break;
		case 5: // _
			if (maxTreeDepth > 1)
			{
				*programIndex++ = '_';
				return mutateNumber(maxTreeDepth-1)+1;
			}
			break;
		case 6:
			*programIndex++ = 'C';
			return 1;
		case 7:
		#ifdef PHEROMONES
			*programIndex++ = 'P';
			return 1;
		#else
			break;
		#endif
		case 8:
			*programIndex++ = 'Q';
			return 1;
		case 9:
			*programIndex++ = 'T';
			return 1;
		case 10:
		#ifdef PHEROMONES
			*programIndex++ = 'V';
			return 1;
		#else
			break;
		#endif
		case 11:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 'a';
				return mutateNumber(maxTreeDepth-1) + 1;
			}
			break;
		case 12:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 'c';
				return mutateNumber(maxTreeDepth-1) + 1;
			}
			break;
		case 13:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 'd';
				return mutateDirection(maxTreeDepth-1) + 1;
			}
			break;
		case 14:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 'f';
				return mutateDirection(maxTreeDepth-1) + 1;
			}
			break;
		case 15:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 'g';
				return mutateDirection(maxTreeDepth-1) + 1;
			}
			break;
		case 16:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 'm';
				return mutateDirection(maxTreeDepth-1) + 1;
			}
			break;
		case 17:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 'p';
				return mutateDirection(maxTreeDepth-1) + 1;
			}
			break;
		case 18:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 'r';
				return mutateNumber(maxTreeDepth-1) + 1;
			}
			break;
		case 19:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 's';
				return mutateNumber(maxTreeDepth-1) + 1;
			}
			break;
		case 20:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 't';
				return mutateDirection(maxTreeDepth-1) + 1;
			}
			break;
		case 21:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 'w';
				return mutateDirection(maxTreeDepth-1) + 1;
			}
			break;
		case 22:
			if (maxTreeDepth > 1)
			{
				*programIndex++ = 'z';
				return mutateDirection(maxTreeDepth-1) + 1;
			}
			break;
		case 23:
		// Integer constant
			if (maxTreeDepth >= 2)
			{
				int digits = int(drand48() * 
(min(maxTreeDepth-1, MAX_INTEGER_LENGTH) - 1)) + 1;
				for(int i = 0; i < digits; i++)
					*programIndex++ = int(drand48() * 10);
				*programIndex++ = ';';
				return digits+1;
			}
			break;
		case 24:
		// Floating point constant
			if (maxTreeDepth >= 4)
			{
				int i;

				int digits = randomBetween (2, 
min(maxTreeDepth-2, MAX_INTEGER_LENGTH+MAX_FLOAT_LENGTH));
				int idigits =
randomBetween(max(digits-MAX_FLOAT_LENGTH,1), min(digits-1,
MAX_INTEGER_LENGTH));

				for(i = 0; i < idigits; i++)
					*programIndex++ = int(drand48() * 10);
				*programIndex++ = '.';

				for(; i < digits; i++)
					*programIndex++ = int(drand48() * 10);
				*programIndex++ = ';';

				return digits+2;
			}
			break;
		}
	} while (true);
}

int Ghost::mutateDirection (int maxTreeDepth)
{
	do
	{
		switch (int(drand48() * 10))
		{
		case 0: // If statement
			if (maxTreeDepth <= 6)
				break;
			else
			{
				int origMaxTreeDepth = maxTreeDepth--;
				*programIndex++ = 'i';
				maxTreeDepth -= mutateBool(maxTreeDepth-2);
				maxTreeDepth -= mutateDirection(maxTreeDepth-1);
				return origMaxTreeDepth - maxTreeDepth + mutateDirection(maxTreeDepth);
			}
		case 1: // North
			*programIndex++ = 'N';
			return 1;
		case 2:
			*programIndex++ = 'E';
			return 1;
		case 3:
			*programIndex++ = 'S';
			return 1;
		case 4:
			*programIndex++ = 'W';
			return 1;
		case 5:
			*programIndex++ = 'F';
			return 1;
		case 6:
			*programIndex++ = 'L';
			return 1;
		case 7:
			*programIndex++ = 'B';
			return 1;
		case 8:
			*programIndex++ = 'R';
			return 1;
		case 9:
		#ifdef PHEROMONES
			if (maxTreeDepth <= 6)
				break;
			else
			{
				int origTreeDepth = maxTreeDepth--;
				*programIndex++ = 'o';
				maxTreeDepth -= mutateNumber(maxTreeDepth-2);
				maxTreeDepth -= mutateNumber (maxTreeDepth-1);
				return origTreeDepth - maxTreeDepth + mutateDirection (maxTreeDepth);
			}
		#else
			break;
		#endif
		}
	} while (true);
}

int Ghost::mutateBool (int maxTreeDepth)
{
	if (maxTreeDepth < 3)
	{
		cerr << "I can't fit a bool into " << maxTreeDepth << endl;
		exit(1);
	}

	int origMaxTreeDepth = maxTreeDepth--;
	do
	{
		switch (int(drand48() * 8))
		{
		case 0:
			*programIndex++ = '=';
			maxTreeDepth -= mutateNumber(maxTreeDepth - 1);
			return origMaxTreeDepth - maxTreeDepth + mutateNumber(maxTreeDepth);
		case 1:
			*programIndex++ = '<';
			maxTreeDepth -= mutateNumber(maxTreeDepth - 1);
			return origMaxTreeDepth - maxTreeDepth + mutateNumber(maxTreeDepth);
		case 2:
			*programIndex++ = '>';
			maxTreeDepth -= mutateNumber(maxTreeDepth - 1);
			return origMaxTreeDepth - maxTreeDepth + mutateNumber(maxTreeDepth);
		case 3:
			*programIndex++ = '}';
			maxTreeDepth -= mutateNumber(maxTreeDepth - 1);
			return origMaxTreeDepth - maxTreeDepth + mutateNumber(maxTreeDepth);
		case 4:
			*programIndex++ = '{';
			maxTreeDepth -= mutateNumber(maxTreeDepth - 1);
			return origMaxTreeDepth - maxTreeDepth + mutateNumber(maxTreeDepth);
		case 5:
			if (maxTreeDepth > 4)
			{
				*programIndex++ = '!';
				maxTreeDepth--;
			}

			break;
		case 6:
			if (maxTreeDepth < 7)
				break;
			*programIndex++ = '|';
			maxTreeDepth -= mutateBool(maxTreeDepth-3);
			return origMaxTreeDepth - maxTreeDepth + mutateBool(maxTreeDepth);
		case 7:
			if (maxTreeDepth < 7)
				break;
			*programIndex++ = '&';
			maxTreeDepth -= mutateBool(maxTreeDepth-3);
			return origMaxTreeDepth - maxTreeDepth + mutateBool(maxTreeDepth);
		}
	} while (true);
}

void Ghost::newGeneration ()
// This function 
{
	swap (program, newProgram);

	int temp;
	temp = *programLength;
	*programLength = *newProgramLength;
	*newProgramLength = temp;
}

Ghost::DataType Ghost::dataType (int point)

{
	switch (program[point])
	{
	case 'i':
	case 'F':
	case 'B':
	case 'R':
	case 'L':
	case 'N':
	case 'E':
	case 'S':
	case 'W':
	case 'o':
		return Direction;

	case '=':
	case '<':
	case '>':
	case '{':
	case '}':
	case '!':
	case '|':
	case '&':
		return Bool;

	case '+':
	case '-':
	case '*':
	case '/':
	case '%':
	case '_':
	case 'C':
	case 'P':
	case 'Q':
	case 'T':
	case 'V':
	case 'a':
	case 'c':
	case 'd':
	case 'f':
	case 'g':
	case 'm':
	case 'p':
	case 'r':
	case 's':
	case 't':
	case 'w':
	case 'z':
	default: // Numeric constant
		return Number;
	}
}

void Ghost::mutate (Ghost& parent)
{
	int startPoint = parent.combinationPoint();
	int endPoint = parent.matchingPoint(startPoint);

	int maxSize = min(MAX_MUTATED_SUBTREE_LENGTH,
MAX_PROGRAM_LENGTH - *parent.programLength + endPoint - startPoint);

	memcpy (newProgram, parent.program, startPoint);

	programIndex = newProgram + startPoint;
	switch (parent.dataType(startPoint))
	{
	case Direction:
		*newProgramLength = startPoint + *parent.programLength - endPoint + 
mutateDirection(maxSize);
		break;
	case Number:
		*newProgramLength = startPoint + *parent.programLength - endPoint + 
mutateNumber(maxSize);
		break;
	case Bool:
		*newProgramLength = startPoint + *parent.programLength - endPoint + 
mutateBool(maxSize);
		break;
	}
	memcpy (programIndex, parent.program + endPoint, *parent.programLength - endPoint);
}

int Ghost::combinationPoint ()
{
	int point;
	do
	{
		point = int(drand48() * *programLength);
	} while (badCombinationPoint(point));

	return point;
}

bool Ghost::badCombinationPoint (int point)
{
	if (point > 0)
		if (program[point] == '.' || program[point] == ';' ||
		   (program[point] < 10 && (program[point-1] < 10 ||
					    program[point-1] == '.')))
			return true;

	return false;
}

void Ghost::copy (Ghost& parent)
{
	*newProgramLength = *parent.programLength;
	memcpy(newProgram, parent.program, *newProgramLength);
}

void Ghost::crossover (Ghost& mom, Ghost& dad)
{

	int momEnd, dadStart, dadEnd, momRestart;
	int totalLength;
	do
	{
		do
		{
			momEnd = mom.combinationPoint();
			dadStart = dad.pointOfType(mom.dataType(momEnd));
		} while (dadStart == -1);

		dadEnd = dad.matchingPoint(dadStart);
		momRestart = mom.matchingPoint(momEnd);

		totalLength = *mom.programLength - momRestart + momEnd +
				dadEnd - dadStart;
	} while (totalLength > MAX_PROGRAM_LENGTH);

	memcpy(newProgram, mom.program, momEnd);
	memcpy(newProgram+momEnd, dad.program+dadStart, dadEnd-dadStart);
	memcpy(newProgram+momEnd+dadEnd-dadStart, mom.program+momRestart,
*mom.programLength - momRestart);

	*newProgramLength = totalLength;
}

int Ghost::pointOfType (DataType dt)
{
	int point, i;

	for(i=0; i < MAX_RANDOM_MATCH_TRIES; i++)
	{
		do
		{
			point = int(drand48() * *programLength);
		} while (badCombinationPoint(point));
		if (dataType(point) == dt)
			return point;
	}

	return -1;
}

int Ghost::matchingPoint (int point)
{
	int limbs = 1;
	do
	{
		switch (program[point++])
		{
		case 'i':
		case 'o':
			limbs += 2;
			break;

		case '+':
		case '-':
		case '*':
		case '/':
		case '|':
		case '&':
		case '=':
		case '<':
		case '>':
		case '}':
		case '{':
		case '%':
			limbs += 1;
			break;

		case '!':
		case '_':
		case 'a':
		case 'c':
		case 'd':
		case 'f':
		case 'g':
		case 'm':
		case 'p':
		case 'r':
		case 's':
		case 't':
		case 'w':
		case 'z':
			break;
		case 'F':
		case 'B':
		case 'R':
		case 'L':
		case 'N':
		case 'E':
		case 'S':
		case 'W':
		case 'C':
		case 'P':
		case 'Q':
		case 'T':
		case 'V':
			limbs--;
			break;
		default: //Numeric constant;
			while (program[point++] != ';');
			limbs--;
		}
	} while (limbs > 0);

	return point;
}

void Ghost::skip ()
{
	int limbs = 1;

	do
	{
		switch (*programIndex++)
		{
		case 'i':
		case 'o':
			limbs += 2;
			break;

		case '+':
		case '-':
		case '*':
		case '/':
		case '|':
		case '&':
		case '=':
		case '<':
		case '>':
		case '}':
		case '{':
		case '%':
			limbs += 1;
			break;

		case '!':
		case '_':
		case 'a':
		case 'c':
		case 'd':
		case 'f':
		case 'g':
		case 'm':
		case 'p':
		case 'r':
		case 's':
		case 't':
		case 'w':
		case 'z':
			break;
		case 'F':
		case 'B':
		case 'R':
		case 'L':
		case 'N':
		case 'E':
		case 'S':
		case 'W':
		case 'C':
		case 'P':
		case 'Q':
		case 'T':
		case 'V':
			limbs--;
			break;
		default: //Numeric constant;
			while (*programIndex++ != ';');
			limbs--;
		}
	} while (limbs > 0);
}