=begin rdoc

== Traveling Salesman Lab

=end

=begin
  todo unit tests
  todo keep track of how tour made, color those from crosses a different color
  todo ? later -- hightlight changes when drawing tour
  todo possible error in call to m.make_tour(:mutate,t) when t is not full size tour of m
  todo kinda brittle with popsize param -- interaction between histogram and popsize needs 
          to be stabilized (see esp need to pass popsize to rebuild_population)
  todo fix labels -- top level methods need to erase labels from rsearch or other experiments
  todo to_s for maps should print : in front of symbol labels
  todo clean up rsearch, add :begin/:end wrapper
  todo catch ^C interrupt in esearch?  each_permutation?
=end

module RubyLabs
  
module TSPLab

  require 'set'
  require "permute.rb"
  
  MapView = Struct.new(:cities, :nodes, :links, :labels, :histogram, :options)
  ItemWithDirection = Struct.new(:value, :direction)
  
  class ItemWithDirection
    def inspect
      (self.direction ? "<" : ">") + self.value.inspect
    end
  end
  
=begin rdoc
  A Map is a 2D array of distances between pairs of cities.  A new Map object
  will initially be empty.  Call m[i,j] = x to assign the distance between i and
  j.  Maps are symmetric (i.e. m[i,j] == m[j,i] for all i and j) so assigning a
  value to m[i,j] automatically assigns the same value to m[j,i].  Indices can be 
  strings, symbols, or integers.
=end
  
  class Map

  	# Make a new distance matrix.

    def initialize(arg)
  		@labels = Array.new
  		@dist = Array.new
  		@coords = Array.new
      if arg.class == String || arg.class == Symbol
        read_file(arg)
      elsif arg.class == Fixnum
        make_random_map(arg)
      elsif arg.class == Array
        make_map(arg)
      elsif arc.class != NilClass
        raise "Map.new: parameter must be a file name, array of points, or an integer"
      end
    end

    def inspect
      sprintf "#<TSPLab::Map [%s]>", @labels.join(",") 
    end
  
    alias to_s inspect

  	# print the current state of the metric; the parameter is the field width (number
  	# of chars in each matrix entry)

  	def display(fw = nil)
  	  if fw.nil?
        lw = labels.inject(0) { |max, x| n = x.to_s.length;  (n > max) ? n : max }
        dw = (log10(@maxdist).ceil+4)
        fw = max(lw+1,dw)
	    end
      res = " " * fw
      @labels.each { |name| res << sprintf("%#{fw-1}s ", name.to_s[0..fw-1]) }
      res += "\n"
  		@dist.each_with_index do |a,i| 
  		  res += sprintf("%#{fw-1}s ", @labels[i].to_s[0..fw-1])
  			a.each { |x| res += (x.nil? ? "  --  " : sprintf("%#{fw}.2f", x)) }
  			res += "\n"
  		end
  		puts res
  	end
  	
  	# method to make tours
  	
  	def make_tour(*args)
  	  begin
  	    args << :any if args.length == 0
  	    case args[0]
	      when :any
	        tour = Tour.new(self, labels)    # note labels returns clone of @labels array...
  	    when :random
  	      tour = Tour.new(self, permute!(labels))
	      when :mutate
	        raise "usage" unless args.length >= 2 && args[1].class == Tour && (args[2].nil? || args[2].class == Fixnum)
  	      child = args[1].clone
  	      dmax = args[2] ? args[2] : 1
  	      i = rand(size)
          d = 1 + rand(dmax)
          # puts "mutate #{i} #{d}"
      	  tour = child.mutate!(i,d)
  	      child.parent = args[1]
  	      child.op = [:mutate, i, d]
      	when :cross
	        raise "usage" unless args.length == 3 && args[1].class == Tour && args[2].class == Tour
  	      child = args[1].clone
  	      i = rand(size)
  	      n = 1 + rand(size-1)
          # puts "cross #{i} #{n}"
      	  tour = child.cross!(args[2], i, n)
      	  child.parent = args[1]
      	  child.op = [:cross, args[2], i, n]
      	else
      	  raise "usage" unless args[0].class == Array
      	  a = args[0]
      	  errs = 0
      	  a.each do |x|
      	    if ! @labels.include?(x)
      	      puts "unknown city: #{x}"
      	      errs += 1
    	      end
      	  end
      	  raise "errors in list of cities" if errs > 0
      	  tour = Tour.new(self, a)  
  	    end
  	  rescue Exception => e
  	    if e.message == "usage"
    	    puts "Usage:"
    	    puts "  make_tour( [x,y,..] )"
    	    puts "  make_tour( :random )"
    	    puts "  make_tour( :mutate, t [,n] )"
    	    puts "  make_tour( :cross, t1, t2 )"
  	    else
  	      puts "make_tour: #{e.message}"
	      end
  	    return nil
  	  end
  	  
      return tour
      
  	end
  	  	  	
  	# Generate all possible tours using the Johnson-Trotter algorithm.  The method
  	# works by generating all permutations of array indices, then for each permutation
  	# generating an array of labels.
  	  	
  	def each_tour
  	  a = []
  	  n = @labels.length
  	  for i in 1...n do
  	    a << ItemWithDirection.new(i, true)
	    end
  	  loop do
        # yield [0] + a
        yield Tour.new(self, [@labels[0]] + a.map { |x| @labels[x.value] })
  	    mover = nil
  	    for i in 0...a.length
  	      mover = i if movable(a,i) && (mover.nil? || a[i].value > a[mover].value)
        end
  	    break if mover.nil?
  	    k = a[mover].value
        # puts "mover = #{mover} k = #{k}"
  	    break if k == 2
  	    adj = a[mover].direction ? mover-1 : mover+1
  	    a[adj], a[mover] = a[mover], a[adj]
  	    for i in 0...a.length
  	      if a[i].value > k
  	        a[i].direction ^= true 
	        end
        end
	    end
  	end

  	# return the number of rows in the matrix

  	def size
  	  return @dist.length
  	end
  	
  	# return the first pair of city labels

  	def first
  	  return @labels[0..1]
    end

  	# this iterator will generate the remaining pairs of labels

  	def rest
  		n = @labels.length
  		@labels.each_with_index do |x,i| 
  			@labels.last(n-i-1).each_with_index do |y,j|
  			  next if i == 0 && j == 0
  				yield(x,y)
  			end
  		end
  	end

  	# get/set the distance between labels i and j (which can be)
  	# given in either order, i.e. d[i,j] is the same as d[j,i]

    def [](i,j)
      ix = @labels.index(i) or return nil
      jx = @labels.index(j) or return nil
      ix, jx = jx, ix if ix < jx
      @dist[ix][jx]
    end

    def []=(i,j,val)
      raise "Map: can't assign to diagonal" if i == j
      ix = index_of(i)
      jx = index_of(j)
      ix, jx = jx, ix if ix < jx
      @dist[ix][jx] = val.to_f
    end

    def labels
      return @labels.clone
    end

    def dist
      d = Array.new
      @dist.each { |row| d << row.clone }
      return d
    end
    
    def coords(x)
      return @coords[index_of(x)]
    end

    # method left over from Metric class, probably not useful for TSP, but...

    def delete(i)
      ix = @labels.index(i) or return nil
      (ix...@labels.length).each { |x| @dist[x].slice!(ix) }
      @dist.slice!(ix)
      @labels.slice!(ix)
    end

    private
    
    def index_of(i)
      if (ix = @labels.index(i)) == nil
        ix = @labels.length
        @labels << i
        @dist[ix] = Array.new
        @dist[ix][ix] = 0.0
      end
      return ix
    end

    def read_file(fn)
      matrixfilename = fn.to_s + ".txt"
      matrixfilename = File.join(@@tspDirectory, matrixfilename)
      raise "Matrix not found: #{matrixfilename}" unless File.exists?(matrixfilename)

      readingLocations = true
      @maxdist = 0.0
      
      File.open(matrixfilename).each do |line|
        line.chomp!
        next if line.length == 0
        next if line[0] == ?#
        rec = line.split
        if rec[0][0] == ?:
          readingLocations = false if rec[0] == ":matrix"
          # tbd -- deal with other directives
        elsif readingLocations
          x = rec[2].to_sym
          # printf "loc #{x} at #{rec[0]}, #{rec[1]}\n"
          @coords[index_of(x)] = [rec[0].to_i, rec[1].to_i]
          # p index_of(x)
          # p @coords[index_of(x)]
        else
          i = rec[0].to_sym
          j = rec[1].to_sym
          d = rec[2].to_f
          # printf "dist #{rec[0]} to #{rec[1]} = #{rec[2]}\n"
          self[i,j] = d
          @maxdist = d if d > @maxdist
        end
      end
      
      errs = []
      i, j = first
      errs << [i,j] if j.nil?
      self.rest do |i,j|
        errs << [i,j] unless self[i,j] != nil
      end
      raise "Map.new: missing distances #{errs.inspect}" if errs.length > 0
    end

    def make_random_map(n)
      h = Hash.new
      a = Array.new      
  		while h.size < n
  			h[rand(400)] = 1		
  		end
  		h.keys.each do |k|
  		  x = k / 20
  		  y = k % 20
  		  a << [x*20 + rand(5) + 50, y*20 + rand(5) + 50]
  		end    
      make_map(a)
    end

    def make_map(a)
      @maxdist = 0.0
      for i in 0...a.length
        for j in (i+1)...a.length
          x = a[i][0] - a[j][0]
          y = a[i][1] - a[j][1]
          d = sqrt(x**2 + y**2)
          self[i,j] = d
          @maxdist = d if d > @maxdist
        end
        @coords[i] = a[i]
      end
    end
    
    # helper method for each_tour iterator, used by Johnson-Trotter algorithm
    
    def movable(a, i)
      if a[i].direction
        return i > 0 && a[i].value > a[i-1].value
      else
        return i < a.length-1 && a[i].value > a[i+1].value
      end
    end

  end # class Map
  

=begin rdoc
  A Tour object is an array of city names, corresponding to the cities visited, in order,
  by the salesman.  Attributes are the path, its cost, a unique tour ID, and a reference to
  the matrix used to define the distance between pairs of cities.
  
  Class methods access the number of tours created, or reset the tour counter to 0.
=end

  # TODO don't give access to path (unless there's a way to make it read-only -- freeze it?)

  class Tour 
    attr_reader :id, :path, :cost, :matrix
    attr_accessor :parent, :op

    @@id = 0
    
    def Tour.reset
      @@id = 0
    end
    
    def Tour.count
      return @@id
    end

    def initialize(m, s)
      @matrix = m
      @path = s.clone
      @cost = pathcost
      @id = @@id
      @@id += 1
    end

    def inspect
      sprintf "#<TSPLab::Tour %s (%.2f)>", @path.inspect, @cost
    end

    alias to_s inspect

    # A copy of a tour needs its own new id and copy of the path and pedigree

    def clone
      # return Tour.new(@matrix, @path, @nm, @nx)
      return Tour.new(@matrix, @path)
    end
 
    # Exchange mutation (called 'EM' by Larranaga et al).  Swaps node i with one
    # d links away (d = 1 means neighbor).  An optimization (has a big impact when
    # tours are 20+ cities) computes new cost by subtracting and adding single
    # link costs instead of recomputing full path length.  Notation:  path
    # through node i goes  xi - i - yi, and path through j is  xj - j - yj.
  
    def mutate!(i, d = 1)
      raise "mutate!: index #{i} out of range 0..#{@path.length}" unless (i >=0 && i < @path.length)
      return if d == 0                # these two special cases won't occur when
      if d == @path.length-1          #    mutate! called from evolve, but....
        i = (i-1) % @path.length
        d = 1
      end
      
      j = (i+d) % @path.length        # location of swap
      
      xi = (i-1) % @path.length       # locations before, after i
      yi = (i+1) % @path.length
      xj = (j-1) % @path.length       # locations before, after j
      yj = (j+1) % @path.length
      
      if d == 1
        @cost -= @matrix[ @path[xi], @path[i] ]
        @cost -= @matrix[ @path[j], @path[yj] ]
        @cost += @matrix[ @path[xi], @path[j] ]
        @cost += @matrix[ @path[i], @path[yj] ]
      else
        @cost -= @matrix[ @path[xi], @path[i] ]
        @cost -= @matrix[ @path[i], @path[yi] ]
        @cost -= @matrix[ @path[xj], @path[j] ]
        @cost -= @matrix[ @path[j], @path[yj] ]
        @cost += @matrix[ @path[xi], @path[j] ]
        @cost += @matrix[ @path[j], @path[yi] ]
        @cost += @matrix[ @path[xj], @path[i] ]
        @cost += @matrix[ @path[i], @path[yj] ]
      end
      
      @path[i], @path[j] = @path[j], @path[i]

      # uncomment to verify path cost logic
      # if (@cost - pathcost).abs > 0.001
      #   puts "#{i} #{j}" + self.to_s + " / " + @cost.to_s
      # end
      
      self
    end
  
    # Order cross-over (called 'OX1' by Larranaga et al).  Save a chunk of the 
    # current tour, then copy the remaining cities in the order they occur in 
    # tour t.  i is the index of the place to start copying, n is the number to
    # copy.
  
    def cross!(t, i, n)
      j = (i + n - 1) % @path.length
      if i <= j
        p = @path[i..j]
      else
        p = @path[i..-1]
        p += @path[0..j]
      end
      @path = p
      t.path.each do |c|
        @path << c unless @path.include?(c)
      end
      @cost = pathcost
      self
    end
    
    # Not used normally, but is use in unit tests to make sure mutate! is computing
    # the right costs with its optimized strategy
        
    def pathcost
      sum = @matrix[ @path[0], @path[-1] ]
      for i in 0..@path.length-2
        sum += @matrix[ @path[i], @path[i+1] ]
      end
      return sum
    end

  end # class Tour
  
# Combinatorics...  tempting to write factorial with inject, but this is for the 
# students to look at....

  def factorial(n)
    f = 1
    for i in 2..n
      f *= i
    end
    return f
  end
  
  def ntours(n)
    return factorial(n-1) / 2
  end
  
# Random search
  
  def rsearch( matrix, nsamples )
    Tour.reset
    best = matrix.make_tour(:random)
    if @@drawing
      make_histogram([])      # clear histogram display
      view_tour(best) 
      init_labels(["tours:", "cost:"])
    end
    (nsamples-1).times do |i|
      t = matrix.make_tour(:random)
      update = t.cost < best.cost
      best = t if update
      if @@drawing
        view_tour(t) if update
        labels = []
        labels << sprintf( "#tours: %d", Tour.count )
        labels << sprintf( "cost: %.2f", best.cost )
        update_labels( labels )
      end
    end
    Canvas.sync
    return best
  end

=begin rdoc
  Make a set of +n+ random tours from map +m+
=end

# :begin :init_population
  def init_population( m, n )
    a = Array.new

    n.times do
      a << m.make_tour(:random)
    end
  
    a.sort! { |x,y| x.cost <=> y.cost }
    
    if @@drawing
      make_histogram(a) 
      Canvas.sync
    end
    
    return a
  end
# :end :init_population
  
  
=begin rdoc
  +select_survivors(p, options)+  Apply "natural selection" to population +p+.  Sort by 
  fitness, then remove individual +i+ with probability +i/n+ where +n+ is the population
  size.  Note the first item in the array is always kept since +0/n = 0+.
=end

# p.sort! { |x,y| (x.cost == y.cost) ? (x.id <=> y.id) : (x.cost <=> y.cost) }

# :begin :select_survivors
  def select_survivors( population, toplevel = true )
    population.sort! { |x,y| x.cost <=> y.cost }
    n = population.size
    
    (n-1).downto(1) do |i|
      if ( rand < (i.to_f / n) )
        # population.delete_at(i) 
        population[i].op = :zap 
      end
    end
    
    if @@drawing && toplevel
      show_survivors( population ) 
      Canvas.sync
    end
    
    return population
  end
# :end :select_survivors

=begin rdoc
  +rebuild_population(p, n, options)+  Add new Tour objects to population +p+ until the size
  of the population reaches +n+.  Each new Tour is a mutation of one or two Tours currently
  in +p+.  The hash +options+ has mutation parameters, e.g. the probability of doing a crossover
  vs. point mutation.
=end

# :begin :rebuild_population
  def rebuild_population( population, popsize, userOptions = {} )
    options = @@tourOptions.merge(userOptions)
    tracing = (options[:trace] == :on)
    
    map = population[0].matrix      # assume they're all from the same map...
    
    dist = options[:distribution]
    psmall, plarge, pcross = options[:profiles][dist]
    sdmax  = options[:sdmax] || ((map.size > 10) ? (map.size / 10) : 1)
    ldmax  = options[:ldmax] || ((map.size > 10) ? (map.size / 4) : 1)

    (popsize-1).downto(1) do |i|
      population.delete_at(i) if population[i].op == :zap
    end
    
    prev = population.length        # items before this index are from previous generation

    while population.length < popsize
      r = rand
      if r < 1.0 - (psmall + plarge + pcross)
        kid = map.make_tour( :random )
      elsif r < 1.0 - (plarge + pcross)
        mom = population[ rand(prev) ]
  	    kid = map.make_tour( :mutate, mom, sdmax )
	    elsif r < 1.0 - pcross
        mom = population[ rand(prev) ]
  	    kid = map.make_tour( :mutate, mom, ldmax )
      else
        mom = population[ rand(prev) ]
        dad = population[ rand(prev) ]
  	    kid = map.make_tour( :cross, mom, dad )
      end
      population << kid
    end
    
    if @@drawing
      update_histogram(population) 
      Canvas.sync
    end

    return population
  end
# :end :rebuild_population

# :begin :evolve
  def evolve( population, maxgen, ngen = 0, options = {} )
    popsize = population.length
    best = population[0]
    while ngen < maxgen
      select_survivors( population, false )
      rebuild_population( population, popsize, options)
      if (population[0].cost - best.cost).abs > 1e-10
        best = population[0] 
        updated = true
        # @@bestGeneration = ngen
      else
        updated = false
      end
      ngen += 1
      update_tour_display( population, ngen, updated ) if @@drawing
    end    
    Canvas.sync if @@drawing
    return best
  end
# :end :evolve

=begin rdoc
  +esearch( map, n, options)+  Top level method for the genetic algorithm.  +m+ is a Map
  containing pairwise distances between a set of cities.  The hash named
  +options+ contains tour parameters, e.g. population size and mutation probabilities.
  Make an initial population of random tours, then iterate +n+ times, calling +select_survivors+
  and +rebuild_population+ to evolve an optimal tour.  The return value is the lowest cost
  tour after the last round of evolution.
=end

  def esearch( matrix, maxgen, userOptions = {} )
    options = @@tourOptions.merge(userOptions)
    
    if options[:continue]
      if @@previousPopulation
        population = @@previousPopulation
        options = @@previousOptions
        ngen = @@previousNGen
      else
        puts "no saved population"
        return nil
      end
    else
      Tour.reset
      population = init_population( matrix, options[:popsize] )
      ngen = 0
      if @@drawing
        init_labels(["generations:", "tours:", "cost:"])
        view_tour( population[0] )
      end
    end
    
    begin
      check_mutation_parameters(options)      
    rescue Exception => e
      puts "esearch: " + e
      return false
    end
   
    evolve( population, maxgen, ngen, options )
    
    @@previousPopulation = population
    @@previousOptions = options
    @@previousNGen = maxgen
    
    Canvas.sync if @@drawing

    return population[0]
  end
  
  def update_tour_display(population, ngen, draw_tour)    
    view_tour(population[0]) if draw_tour
    update_histogram(population)
    labels = []
    labels << sprintf( "generations: %d", ngen )
    labels << sprintf( "#tours: %d", Tour.count )
    labels << sprintf( "cost: %.2f", population[0].cost )
    update_labels(labels)
  end
  
=begin rdoc
  Make sure the mutation parameters are valid
=end

  def check_mutation_parameters(options)
    dist = options[:distribution]
    profiles = options[:profiles]
    raise "specify mutation probabilities with :distribution option" unless dist
    floaterr = "distribution must be an array of three numbers between 0.0 and 1.0"
    symbolerr = "distribution must be one of #{profiles.keys.inspect}"
    if dist.class == Symbol
      raise symbolerr unless profiles[dist]
    elsif dist.class == Array
      raise floaterr unless dist.length == 3
      sum = 0.0
      dist.each { |x| raise floaterr if (x < 0.0 || x > 1.0); sum += x}
      raise "sum of probabilities must be 1.0" unless (sum - 1).abs < Float::EPSILON
      profiles[:user] = dist
      options[:distribution] = :user
    else
      raise "#{floaterr} or #{symbolerr}"
    end
  end
  
  def checkout(matrix, filename = nil)
    matrixfilename = matrix.to_s + ".txt"
    matrixfilename = File.join(@@tspDirectory, matrixfilename)
    if !File.exists?(matrixfilename)
      puts "Matrix not found: #{matrixfilename}"
      return nil
    end
    outfilename = filename.nil? ? (matrix.to_s + ".txt") : filename
    dest = File.open(outfilename, "w")
	  File.open(matrixfilename).each do |line|
	    dest.puts line.chomp
	  end
    dest.close
    puts "Copy of #{matrix} saved in #{outfilename}"
  end
  
=begin rdoc
  Methods for displaying a map and a tour
=end

  def view_map(m, userOptions = {} )
    options = @@mapOptions.merge(userOptions)
    Canvas.init(800, 500, "TSPLab")
    links = Array.new
    nodes = Array.new
    r = options[:dotRadius]
    m.labels.each do |loc|
      x, y = m.coords(loc)
      nodes << Canvas.circle( x, y, r, :fill => options[:dotColor] )
      Canvas.text(loc.to_s, x+r, y+r)
    end
    @@drawing = MapView.new(m, nodes, links, [], [], options)
    Canvas.sync
    return true    
  end
  
  def view_tour(t, userOptions = {} )
    if @@drawing.nil?
      puts "call view_map to initialize the canvas"
      return nil
    end
    options = @@tourOptions.merge(userOptions)
    map = @@drawing.cities
    @@drawing.links.each { |x| x.delete }
    @@drawing.links.clear
    x0, y0 = map.coords(t.path[-1])
    for i in 0...t.path.length
      x1, y1 = map.coords(t.path[i])
      @@drawing.links << Canvas.line(x0, y0, x1, y1)
      x0, y0 = x1, y1
    end
    @@drawing.nodes.each { |x| x.raise }
    Canvas.sync
    return true
  end
  
  def init_labels(a)
    labelx = 525
    labely = 350
    dy = 20
    labels = @@drawing.labels
    if labels.length > 0
      labels.each { |x| x.text = "" }
    end
    labels.clear
    for i in 0...a.length
      if i == labels.length
        labels << Canvas.text("", labelx, labely)
        labely += dy
      end
      labels[i].text = a[i]
    end
  end
  
  def update_labels(a)
    labels = @@drawing.labels
    for i in 0...labels.length
      labels[i].text = a[i]
    end
  end
  
  # todo! color bin red if new tour comes from crossover? but what if > 1 tour per bin?
  
  # note: calling make_histogram with an empty list erases the previous histogram
  
  def make_histogram(pop)
    if @@drawing.histogram.length > 0
      @@drawing.histogram.each { |box| box.delete }
      @@drawing.histogram.clear
    end
    return if pop.length == 0
    x = @@histogramOptions[:x]
    y = @@histogramOptions[:y]
    ymax = @@histogramOptions[:ymax]
    w = @@histogramOptions[:binwidth]
    scale = ymax / pop[-1].cost
    npb = (pop.length / @@histogramOptions[:maxbins]).ceil
    nbins = pop.length / npb
    (0..pop.length-1).step(npb) do |i|
      h = pop[i..(i+npb-1)].inject(0.0) { |sum, tour| sum + tour.cost }
      h = (h/npb)*scale
      @@drawing.histogram << Canvas.rectangle(x, y+ymax-h, x+w, y+ymax, :fill => 'darkblue' )
      x += w
    end
    @@drawing.options[:scale] = scale
    @@histogramOptions[:npb] = npb
    @@histogramOptions[:nbins] = nbins
    @@recolor = false
  end
  
  def update_histogram(pop)
    y = @@histogramOptions[:y]
    ymax = @@histogramOptions[:ymax]
    npb = @@histogramOptions[:npb]
    scale = @@drawing.options[:scale]
    @@drawing.histogram.each_with_index do |box, i|
      j = i*npb
      if j > pop.length
        h = 0
      else
        h = pop[j..(j+npb-1)].inject(0.0) { |sum, tour| sum + tour.cost }
        h = (h/npb)*scale
      end
      x0, y0, x1, y1 = box.coords
      box.coords = x0, y+ymax-h, x1, y1
      box.fill = 'darkblue' if @@recolor
    end
  end
  
  def show_survivors(pop)
    hist = @@drawing.histogram
    return unless pop.length == hist.length
    hist.each_with_index do |box, i|
      box.fill = 'gray' if pop[i].op == :zap
    end
    @@recolor = true
  end
  
  def show_lineage(tour, userOptions = {} )
    options = @@lineageOptions.merge(userOptions)
    dt = options[:dt]
    a = []
    while tour.parent
      a << tour
      tour = tour.parent
    end
    init_labels(["id:", "cost:", "op:"]) if @@drawing
    a.reverse.each do |x|
      puts x.inspect + ": " + x.op.inspect
      if @@drawing
        view_tour(x)
        labels = []
        labels << sprintf( "id: %d", x.id )
        labels << sprintf( "cost: %.2f", x.cost )
        labels << sprintf( "op: %s", x.op.inspect )
        update_labels(labels)
        sleep(dt)
      end
    end
    return true
  end
    
  # Values accessible to all the methods in the module
  
  @@tspDirectory = File.join(File.dirname(__FILE__), '..', 'data', 'tsp')

  @@mapOptions = {
    :dotColor => '#cccccc',
    :dotRadius => 5.0,
  }
  
  # @@rsearchOptions = {
  #   :pause => 0.0,
  # }

  @@tourOptions = {
    :popsize => 10,
    :maxgen => 25,
    :profiles => {
      :mixed => [0.5, 0.25, 0.25],
      :random => [0.0, 0.0, 0.0],
      :all_small => [1.0, 0.0, 0.0],
      :all_large => [0.0, 1.0, 0.0],
      :all_cross => [0.0, 0.0, 1.0],
    }, 
    :distribution => :all_small,
    :pause => 0.0,
  }
  
  @@histogramOptions = {
    :x => 520.0,
    :y => 100.0,
    :ymax => 200.0,
    :maxbins => 50.0,
    :binwidth => 5,
  }
  
  @@lineageOptions = {
    :dt => 2.0,
    :first => 0,
    :last => -1,
  }
  
  @@drawing = nil
  @@previousPopulation = nil
  
end # module TSPLab

end # module RubyLabs


module Enumerable
  
=begin rdoc
  <tt>each_permtation</tt> is an iterator that makes all permutations of
  a container in lexicographic order.
=end

  def each_permutation
    p = self.clone
    n = p.length
    res = []
    loop do
      yield p if block_given?
      res << p.clone
      # find largest j s.t. path[j] < path[j+1]
      j = n-2
      while j >= 0
        break if p[j] < p[j+1]
        j -= 1
      end
      break if j < 0
      # find largest i s.t. path[j] < path[i]
      i = n-1
      loop do
        break if p[j] < p[i]
        i -= 1
      end
      # exchange path[j], path[i]
      p[j], p[i] = p[i], p[j]
      # reverse path from j+1 to end
      tmp = p.slice!(j+1, n-1)
      p += tmp.reverse
    end
    return block_given? ? nil : res
  end
    
end