from random import random, randint, choice
from time import time

class EvolverException(Exception):
	pass

class Evolver:
	"""
	Evolves and array of genetic information.

	breed - signifies whether there should be a sexual reproduction phase
	mutate - the percentage of mutation that there should be
	
	TODO: Implement a varying mutation rate so that very unhealthy populations have a higher mutation rate.
	"""
	mutationProbability = 0.05
	crossoverProbability = 0.9
	def __init__(self, population):
		"""
		Population is an array of arrays of genetic data. These can be any kind of data.
		The elements of the array will be shuffled and recombined.
		This class acts in place on the population array, modifying it's contents.
		"""
		self.population = population
		self.popSize = len(population)
		
		self.Mate = self.UniformCrossover
		self.Selection = self.TruncationSelection
		self.Selection_inverse = self.TruncationSelection_inverse
		
		self.numberOfFit = 10
		self.tournamentSize = 10
	
	def Evolve(self):
		"""
		Choose initial population
		Repeat (this function):
			Evaluate the fitnesses of individuals in the population 
			Select best-ranking individuals to reproduce
			Breed new generation through crossover and mutation (genetic operations)
			Give birth to offspring
			Evaluate the individual fitnesses of the offspring
			Replace worst ranked part of population with offspring
			return any solutions we have found
		"""
		# calculate the fitnesses of everyone in our population
		self.fitness = [(p, self.FitnessFunction(p)) for p in self.population]
		
		# make a sorted list of our candidates by fitness
		self.sortedByFitness = [c for c, f in sorted([(c, f) for c, f in self.fitness], lambda a, b: cmp(a[1], b[1]))]
		
		#for p in self.sortedByFitness:
		#	print self.sortedByFitness
		
		# select the fittest guys in the population
		fittest = self.Selection()
		
		# create offspring using the current breeding algorithm
		offspring = self.Breed(fittest)
		
		# mutate our offspring
		self.Mutate(offspring)
		
		# remove the least fit of our population so that we can
		# fill their spots with our new offspring
		#for p in self.Selection_inverse():
		#	print self.population.index(p)
		
		#print self.fitness[0]
		#print self.fitness[-1]
		#print self.sortedByFitness[0]
		#print self.sortedByFitness[-1]
		[self.population.remove(p) for p in self.Selection_inverse()]
		
		# add our mutated offspring to our population
		self.population.extend(offspring)
		
		# return any solutions found
		return [self.Solution(p) for p in self.population if self.Solution(p)]
	
	def Breed(self, fittest):
		"""
		This method mates each candidate in the fittest set with another random candidate
		in the fittest set to produce the offspring set.
		"""
		return [(random() < self.crossoverProbability and [self.Mate(c, choice(fittest))] or [c])[0] for c in fittest]
	
	#####
	#
	#	The following methods are to be overridden to customise the evolver.
	#
	#####
	
	def Mutate(self, pop):
		"""
		This function should use the mutation factor to decide when to mutate the data in
		a data set slightly.

		Override me to provide a mutation method that uses the mutationProbability to decide when
		to mutate.
		"""
		for s in pop:
			for b in range(len(s)):
				if random() < self.mutationProbability:
					s[b] = self.MutationOperator(s[b])
	
	def MutationOperator(self, element):
		return choice([chr(x) for x in range(ord('a'), ord('z'))])
	
	def FitnessFunction(self, candidate):
		"""
		Override me to provide your own fitness function.
		It should evaluate the candidate array of genetic information for fitness, and return
		a fitness value for each candidate in the population. Higher numbers are more fit.
		
		The default here (for testing) is to calculate the distance of all pieces from ord('a').
		"""
		return 1.0 - (sum([abs(ord(c) - ord('a')) for c in candidate]) / (25.0 * len(candidate)))
	
	def Solution(self, candidate):
		"""
		This function should return the current solutions to the problem space.
		It should be similar to the fitness function.
		
		Override me to provide your own solution detecting function.
		"""
		return ((sum([abs(ord(c) - ord('a')) for c in candidate]) / (25.0 * len(candidate))) == 0 and candidate)
	
	### These are different mating/crossover mechanisms as detailed at
	### http://en.wikipedia.org/wiki/Crossover_(genetic_algorithm)
	
	def NoCrossOver(self, a, b):
		"""
		This is asexual reproduction such as in the case of a cell-dividing bacteria.
		Returns a copy of the first individual.
		"""
		return a
	
	def MidPointCrossover(self, a, b):
		"""
		Choose the midpoint of each candidate and swap everything after that.
		"""
		return a[:len(a)/2] + b[len(b)/2:]
	
	def OnePointCrossover(self, a, b):
		"""
		Choose a specific point and cross over around that point.
		The variable self.crossoverPosition should be an array index at which to perform the crossover.
		"""
		return a[:self.crossoverPosition] + b[self.crossoverPosition:]
	
	def RandomPointCrossover(self, a, b):
		"""
		This appears to be the crossover used in tiny_gp.java
		"""
		pos = randint(0, min(len(a), len(b)))
		return a[:pos] + b[pos:]
	
	def UniformCrossover(self, a, b):
		"""
		Individual members of the offspring strings are chosen from each parent randomly.
		"""
		return [choice([a[x], b[x]]) for x in range(len(a))]
	
	#def MultiPointCrossover(self, a, b):
	#	"""
	#	Not yet implemented.
	#	"""
	#	pass
	
	#def CutAndSplice(self, a, b):
	#	"""
	#	Not yet implemented.
	#	"""
	#	pass
	
	#def HalfUniformCrossover(self, a, b):
	#	"""
	#	Not yet implemented.
	#	"""
	#	pass
	
	#def EdgeRecombinationOperator(self, a, b):
	#	"""
	#	Not yet implemented.
	#	"""
	#	pass
	
	
	### These are different selection mechanisms detailed at
	### http://en.wikipedia.org/wiki/Genetic_Algorithm
	### http://en.wikipedia.org/wiki/Selection_(genetic_algorithm)
	
	def TruncationSelection(self):
		"""
		Choose the top N candidates by fitness.
		The variable self.truncationPoint must be the number of fit solutions to choose (N).
		"""
		return self.sortedByFitness[-self.numberOfFit:]
	
	def TruncationSelection_inverse(self):
		"""
		Choose the bottom N candidates by fitness.
		"""
		return self.sortedByFitness[:self.numberOfFit]
	
	def TournamentSelection(self):
		"""
		Classic tournament selection.
		This appears to be the one used in tiny_gp.java
		
		You need to set the variable tournamentSize to represent the number of individuals in a tournament.
		"""
		fullrange = range(len(self.sortedByFitness))
		return [self._Tournament(-1, fullrange) for t in xrange(self.numberOfFit)]
	
	def TournamentSelection_inverse(self):
		"""
		Inverse of the above.
		"""
		fullrange = range(len(self.sortedByFitness))
		return [self._Tournament(0, fullrange) for t in xrange(self.numberOfFit)]
	
	def _Tournament(self, end, fullrange):
		"""
		Used by tournamnet selection and inverse tournament selection.
		"""
		if not len(fullrange) >= self.tournamentSize:
			raise EvolverException("TournamentSize must be smaller than 1/2 population size!")
		best = [fullrange.pop(randint(0, len(fullrange) - 1)) for x in xrange(self.tournamentSize)]
		best.sort()
		return self.sortedByFitness[best[end]]
	
	#def RouletteWheelSelection(self):
	#	"""
	#	Not yet implemented.
	#	"""
	#	return []