# == Synopsis
#
# Library to support genetic algorithms
# 
# == Author
# Neil Smith
# 
# == Change history
# Version 1.1::  23 April 2008 

# A single genome in a population
class Genome
  
  attr_accessor :genome
  
  # Create a random genome of the given length
  def initialize(bitstring_or_length)
    if bitstring_or_length.class == Fixnum
      @genome = []
      (1..bitstring_or_length).each do |i|
        @genome << rand(2)
      end
    else
      @genome = bitstring_or_length
    end
  end
  
  # Mutate a genome with the given rate per bit
  def mutate(mutation_probability = 0.05)
    new_genome = Genome.new(@genome.length)
    (0...@genome.length).each do |i|
      if rand < mutation_probability
        if @genome[i] == 0
          new_genome.genome[i] = 1
        else
          new_genome.genome[i] = 0
        end
      else
        new_genome.genome[i] = @genome[i]
      end
    end
    new_genome
  end
  
  # Mutate a genome in-place with the given rate per bit
  def mutate!(mutation_probability = 0.05)
    (0...@genome.length).each do |i|
      if rand < mutation_probability
        if @genome[i] == 0
          @genome[i] = 1
        else
          @genome[i] = 0
        end
      end
    end
    @genome
  end
  
  # Crossover two genomes at the given point
  def crossover(other_genome, crossover_point)
    raise ArgumentError, "Different size genomes" if @genome.length != other_genome.genome.length
    raise ArgumentError, "Our of bounds crossover point" if crossover_point < 0 or crossover_point > @genome.length
    child1 = Genome.new(0)
    child2 = Genome.new(0)
    child1.genome = @genome[0, crossover_point] + other_genome.genome[crossover_point, @genome.length]
    child2.genome = other_genome.genome[0, crossover_point] + @genome[crossover_point, @genome.length]
    [child1, child2]
  end
  
end


class Array
  def to_decimal
    val = 0
    bits = self.dup
    while not bits.empty?
      val = val * 2 + bits[0]
      bits = bits[1..bits.length]
    end
    val
  end
  
  def gray_encode
    gray = self[0..0]
    (1...self.length).each do |i|
      if (self[i - 1] == 1) ^ (self[i] == 1)
        gray << 1
      else
        gray << 0
      end
    end
    gray
  end
  
  def gray_decode
    binary = self[0..0]
    (1...self.length).each do |i|
      if (binary[i - 1] == 1) ^ (self[i] == 1)
        binary << 1
      else
        binary << 0
      end
    end
    binary
  end
 
end

class Fixnum
  def to_bitstring(min_length = 0)
    bits = []
    k = self
    while k > 0 do
      if k % 2 == 1
        bits << 1
      else
        bits << 0
      end
      k = k >> 1
    end
    while bits.length < min_length do
      bits << 0
    end
    bits.reverse
  end
end


# A population of genomes
class Population
  attr_accessor :individuals
  
  # Create a population of a given size
  def initialize(population_size, genome_length = 0)
    @individuals = []
    1.upto(population_size) { @individuals << Genome.new(genome_length) }
  end
  
  # Perform the crossover step in a population, giving a new population
  def crossover(crossover_rate)
    parents = @individuals.dup # genomes that haven't been parents yet
    next_population = Population.new(0)
    while parents.length > 1
      parent1 = parents.delete_at(rand(parents.length)).dup
      parent2 = parents.delete_at(rand(parents.length)).dup
      if rand < crossover_rate        
        child1, child2 = parent1.crossover parent2, rand(parent1.genome.length)
        next_population.individuals << child1 << child2
      else
        next_population.individuals << parent1 << parent2
      end
    end
    next_population.individuals.concat parents # pick up any parents that didn't get a chance to mate
    next_population
  end
  
  # Perform the mutation step in a population, giving a new population
  def mutation(mutation_rate)
    parents = @individuals.dup # genomes that haven't been parents yet
    next_population = Population.new(0)
    while parents.length > 0
      parent = parents.pop.dup
      child = parent.mutate mutation_rate
      next_population.individuals << child
    end
    next_population
  end
  
  def make_next_generation(tournament_winner_success_rate = 0.8, game_length = 1000, crossover_rate = 0.7, mutation_rate = 0.05)
    @individuals = tournament_select_population(tournament_winner_success_rate, game_length, false)
    @individuals = crossover(crossover_rate)
    @individuals = mutation(mutation_rate)
  end
  
end