"""
Uses the genetic algorithm (GA) to solve various problems.

Run with -turbo for maximum speed as in:

	cobra -turbo GeneticAlgorithm.cobra

Links

	http://en.wikipedia.org/wiki/Genetic_algorithm
		http://en.wikipedia.org/wiki/Tournament_selection
		http://en.wikipedia.org/wiki/Crossover_(genetic_algorithm)
		http://en.wikipedia.org/wiki/Mutation_(genetic_algorithm)
	http://en.wikipedia.org/wiki/Travelling_salesman_problem

Credit

	Written by Charles Esterbrook
	Based in part on http://code.activestate.com/recipes/199121/

TODO

	[ ] Record with each member the generation it was created in
	[ ] implement the travelling salesman problem (TSP)
	[ ] Solve a "minimize/maximize function" problem where bitstring is broken
	    into numeric args
"""

@number float


class BaseObject
	"""
	The base class of all other classes in this library/program.
	Provides basics like serial numbers, .random (shared) and .innerString.
	"""

	shared
	
		var _nextSerialNum = 1_000

		var _random as Random?
		
		pro random as Random
			"""
			Shared random number generator.
			"""
			get
				if _random is nil, _random = Random()
				return _random to !
			set
				_random = value

	cue init
		base.init
		__serialNum = _nextSerialNum
		_nextSerialNum += 1
	
	get serialNum from __serialNum as int

	def toString as String is override
		""" Invoke .toString; override .innerString. """
		return '[.typeOf.name]([.serialNum][.innerString])'
	
	def innerString as String
		"""
		Subclasses can override to:
			return base.innerString + ', foo=[value1], bar=[value2]'
		"""
		return ''

	def dump
		print this


class Params inherits BaseObject
	"""
	Contains the parameters for a GA run.
	"""

	shared
	
		get default as Params
			p = Params()
			p.populationSize = 1_000
			p.tournamentSize = 5
			p.crossoverRate = 0.90
			p.mutationRate = 0.03
			p.maxGenerations = 100
			p.randomSeed = 0
			return p

	invariant
		.populationSize >= 4
		.tournamentSize >= 1
		.crossoverRate  >= 0 and .crossoverRate <= 1
		.mutationRate   >= 0 and .mutationRate <= 1
		.maxGenerations >= 0
		.scoreGoal      >  0
	
	cue init
		base.init
		_populationSize = 10
		_tournamentSize = 2
		_scoreGoal = 1.0

	pro populationSize from var as int
	
	pro tournamentSize from var as int
	
	pro crossoverRate from var as number
	
	pro mutationRate from var as number
	
	pro maxGenerations from var as int
	
	pro randomSeed from var as int
		"""
		A .randomSeed of zero is ignored in which the stream of random numbers
		will be different on each run.
		"""

	pro memberType from var as Type?
		"""
		The type of the members of the population.
		Used when creating a new members for an initial population.
		"""

	pro scoreGoal from var as number
		"""
		The score you want to achieve among the population. Once reached,
		evolution will stop.
		"""


class Population inherits BaseObject
	"""
	Holds a population of members and provides population-level operations such
	as reporting the best and worst member.
	"""

	var _members = List<of Member>()

	cue init(size as int, memberType as Type)
		base.init
		for i in size, _members.add(memberType())

	cue init(member as Member)
		ensure
			.members.toList == [member]
			.count == 1
		body
			base.init
			_members.add(member)
		
	get count as int
		ensure result > 0
		return _members.count

	get members as Member*
		for m in _members, yield m

	get best from var as Member?

	get worst from var as Member?

	get averageScore from var as number
	
	def add(m as Member)
		_members.add(m)

	def examine
		"""
		Examine the population for the best and worst members as well compute
		the average score.
		"""
		require
			.count > 0
		ensure
			.best and .best.score >= .averageScore
			.worst and .worst.score <= .averageScore
		body
			total = 0.0
			best as Member?
			worst as Member?
			for m in .members
				if best is nil or best.score < m.score, best = m
				if worst is nil or worst.score > m.score, worst = m
				total += m.score
			_averageScore = total / .count
			_best, _worst = best, worst

	def randomMember(r as Random) as Member
		require .count > 0
		return _members.random(r)

	def removeLast
		_members.removeLast
		
	def dump
		base.dump
		for i, m in _members.numbered
			print '[i] ' stop
			m.dump

	def report
		print 'best  =', .best
		print 'worst =', .worst
		print 'avg   =', .averageScore


class Member inherits BaseObject is abstract

	get age from var as int
		"""
		Returns the age in number of generations
		that this member has survived.
		"""
	
	pro score from var as number
		"""
		The score represents how well this member performs
		or how "good" it is.
		"""
	
	def evaluate as number is abstract
		""" Computes the score of this member. """
		ensure .score == result

	def copy as dynamic
		ensure result is not this
		return .memberwiseClone
	
	def crossover(other) as List<of Member> is abstract
		require
			other is not this
		ensure
			result.count == 2
			result[0].typeOf.isKindOf(.typeOf)
			result[1].typeOf.isKindOf(.typeOf)
			result[0] is not this and result[0] is not other
			result[1] is not this and result[1] is not other
	
	def incAge
		_age += 1
	
	def mutate(rate as number) as bool is abstract
		""" Potentially mutates the member. Returns true if member is mutated. """
		require rate >= 0
	
	def innerString as String
		return base.innerString + ', age=[.age], score=[.score]'


class DummyMember inherits Member
	"""
	A DummyMember does nothing practical on its own, but can be used for simple
	unit tests.
	"""

	def evaluate as number is override
		return 1
		
	def crossover(other) as List<of Member> is override
		t = List<of Member>()
		t.add(this)
		t.add(this)
		return t
	
	def mutate(rate as number) as bool is override
		return false


class BitstringMember inherits Member is abstract
	"""
	A member whose genome is comprised of 1s and 0s that are subsequently
	translated/interpreted as one or more phenotypes.
	
	TODO: add util method to convert a range of the bitstring to an integer
	"""

	shared
			
		def randomBits(length as int) as int[]
			bits = int[](length)
			for i in length, bits[i] = .random.next % 2
			return bits

	var _bits as int[]
	
	cue init(bits as int[])
		require bits.length >= 2
		ensure .bits is bits
		base.init
		_bits = bits

	cue init(length as int)
		""" Initializes the bitstring with `length` random bits. """
		require length >= 2
		.init(.randomBits(length))

	get bits from var
	
	get length as int
		ensure result >= 2
		return _bits.length

	def copy as dynamic
		and ensure
			result.bits is not .bits
		body
			copy = base.copy to BitstringMember
			n = .length
			bits = int[](n)
			for i in n, bits[i] = _bits[i]
			copy._bits = bits
			return copy

	def crossover(other) as List<of Member> is override
		""" Override this method to customize the crossover operation. """
		return .twoPointCrossover(other)
	
	def mutate(rate as number) as bool is override
		""" Override this method to customize the crossover operation. """
		return .randomMutation(rate)
	
	def twoPointCrossover(other as BitstringMember) as List<of Member>
		left, right = _pickPivots
		n = .length
		a, b = int[](n), int[](n)
		for i in left
			a[i], b[i] = _bits[i], other._bits[i]
		for i in left : right
			a[i], b[i] = other._bits[i], _bits[i]
		for i in right : n
			a[i], b[i] = _bits[i], other._bits[i]
		list = List<of Member>()
		type = .typeOf
		childA, childB = type(a), type(b)
		childA.repair(this, other)
		childB.repair(this, other)
		list.add(childA)
		list.add(childB)
		return list

	def randomMutation(rate as number) as bool
		didMutate = false
		for i in .length
			if .random.nextDouble < rate
				_bits[i] = if(_bits[i], 0, 1)
				didMutate = true
		return didMutate

	def _pickPivots as List<of int>
		ensure
			result.count == 2
			result[1] >= result[0]
		body
			left = .random.next(1, .length-2)
			right = .random.next(left, .length-1)
			return [left, right]

	def repair(parent1 as BitstringMember, parent2 as BitstringMember)
		""" Override this method to fix duplicated genes, if necessary. """
		pass


class MaximizeOnesMember inherits BitstringMember
	"""
	A problem-specific member to maximize the number of ones (1s)
	that appear in the genome.
	"""
	
	cue init
		base.init(50)

	cue init(bits as int[])
		base.init(bits)

	cue init(length as int)
		base.init(length)

	def evaluate as number is override
		total = 0
		for b in _bits, total += b
		_score = total
		return total

	def innerString as String
		return base.innerString + ', ' + (for b in .bits get '01'[b]).joined('')


class Engine inherits BaseObject
	"""
	An engine runs the GA using parameters and a population.
	It pushes the population from one generation to the next,
	applying genetic operators.
	"""

	var _params as Params?
	var _pop as Population
	var _generation as int

	cue init(params as Params)
		.init(params, nil)

	cue init(params as Params, pop as Population?)
		require
			params.memberType
			params.populationSize > 0 or (pop and pop.count > 0)
		body
			base.init
			_params = params
			BaseObject.random = if(params.randomSeed, Random(params.randomSeed), Random())
			_pop = pop ? Population(params.populationSize, params.memberType)
			.evaluate

	get generation as int
		ensure result >= 0
		return _generation

	get params from var
	
	get population from _pop

	def run
		while not .isDone, .step

	def isDone as bool
		return .generation >= .params.maxGenerations or (
			.population.best and .population.best.score >= .params.scoreGoal)

	def evaluate
		for m in _pop.members, m.evaluate
		.population.examine

	def step
		.generateNextPopulation
		for member in _pop.members, member.incAge
		_generation += 1
		.population.examine
		.report

	def generateNextPopulation
		thisPop = .population
		nextPop = Population(.population.best)
		while nextPop.count < thisPop.count
			mate1 = .select
			if _random.nextDouble < .params.crossoverRate
				while true
					mate2 = .select
					if mate2 is not mate1, break
				offspring = mate1.crossover(mate2)
			else
				offspring = [mate1.copy to Member]
			for member in offspring
				member.mutate(.params.mutationRate)
				member.evaluate
				nextPop.add(member)
		while nextPop.count > thisPop.count
			nextPop.removeLast
		_pop = nextPop

	def select as Member
		"""
		Calls .tournamentSelect by default.
		A subclass can override this to implement a different selection method.
		"""
		return .tournamentSelect

	def tournamentSelect as Member
		require .population.count > 0
		# This is an interesting method because for quality control,
		# it's not clear what useful `ensure` could be added to it,
		# nor is it clear what kind of unit test would prove that
		# tournament selection was working as expected.
		# Have ideas? Post them to
		# http://cobra-language.com/forums/viewforum.php?f=4
		best as Member?
		for i in .params.tournamentSize
			competitor = .population.randomMember(.random)
			if best is nil or best.score < competitor.score
				best = competitor
		return best to !
	
	def report
		print 'gen   =', .generation
		.population.report
		print


class Program

	def main
		.maximizeOnesExample

	def maximizeOnesExample
		params = Params.default
		params.maxGenerations = 100
		params.memberType = MaximizeOnesMember
		params.scoreGoal = 50
		engine = Engine(params)
		engine.run
		# testing:
		assert engine.generation < 100
		assert engine.population.best.score == 50
		print 'done.'


extend Type

	def isKindOf(t as Type) as bool
		"""
		Returns true if this type is the same as or a subclass of the given type.
		TODO: Should this return true if t is an interface that
		      this type implements?
		"""
		return t is this or .isSubclassOf(t)


extend IList<of T>

	def joined(sep as String) as String
		sb = StringBuilder()
		sep2 = ''
		for item in this
			sb.append(sep2)
			sb.append(CobraCore.printStringMaker.makeString(item))
			sep2 = sep
		return sb.toString