require 'lib/pareto'

module Moea

# Crowding distance computation class for preserving good spread of the pareto front (diversity of MOEA solutions).
# Fully described in the original NSGA-II paper:
# http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=996017 or
# http://sci2s.ugr.es/docencia/doctobio/2002-6-2-DEB-NSGA-II.pdf
#
class Crowding
  Inf = 1.0/0.0
  CrowdingFields = Struct.new( 'CrowdingFields', :original, :cdist, :index )

  # Compute the crowding distance for each member of the population.
  # There are two variants:
  #   population2 = Crowding.distance population
  #     where population2[i].original is the original population[i] member, population2[i].cdist is the crowding distance, or:
  #
  #   Crowding.distance( population ) { |member, cdist| .... }
  #     2-argument of the block are: the original population member, cdist is the associated crowding distance.
  #     
  # The Crowding.distance method assumes: 
  #   1. the population is the Enumerable container of individuals, and 
  #   2. the method individual.dominates?( other ) returning true if the individual dominates other one, and
  #   3. the method individual.objective_symbols returning the enumerable with symbols for accessing objective values
  #        (See Pareto#objective_symbols method)
  #   
  def Crowding.distance population
    raise "Crowding: cannot compute empty population" if population.empty? 
    result = []
    population.each_with_index { |orig,i| result.push CrowdingFields.new( orig, 0.0, i ) }
    
    population.first.objective_symbols.each do |obj|
      result.sort! { |a,b| a.original.send(obj) <=> b.original.send(obj) }
      norm = result.last.original.send(obj).to_f - result.first.original.send(obj).to_f 
      result.first.cdist = result.last.cdist = Inf
      for i in 1...(population.size-1)
        result[i].cdist += (( result[i+1].original.send(obj) - result[i-1].original.send(obj) ) / norm )
      end
    end

    result.sort! { |a,b| a.index <=> b.index }
    return result unless block_given?
    result.map { |individual| yield( population[individual.index], individual.cdist ) }
  end

end

end # Moea