$LOAD_PATH.unshift(File.dirname(__FILE__))
require 'test_helper'

include TSPLab

class TestTSP < Test::Unit::TestCase

  # load a test map used by the tests
  
  @@map = Map.new(:test7)

  def test_00_banner
    print "\nTSPLab"
  end
  
  # test the factorial method
  
  def test_01_fact
    assert_equal 120, factorial(5)
    assert_equal 1, factorial(1)
    assert_equal 1, factorial(0)
  end  
  
  # ntours(n) should compute (n-1)! / 2
  
  def test_02_ntours
    assert_equal 362880, factorial(9)
    assert_equal 181440, ntours(10)   
  end
  
  # generate all permutations of a 3-letter string in lexicographic order
  
  def test_03_each_permutation
    a = "ABC".each_permutation
    assert_equal ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"], a
    a = [2,1,0].each_permutation
    assert_equal [[2, 1, 0], [2, 0, 1], [1, 2, 0], [1, 0, 2], [0, 2, 1], [0, 1, 2]], a
  end
  
  # check properties of the test map
  
  def test_04_make_map
    assert_equal 7, @@map.size
    assert_equal [:A, :B, :C, :D, :E, :F, :G], @@map.labels
    assert_equal [192, 212], @@map.coords(:A)
    assert_equal [433, 133], @@map.coords(:G)
  end
  
  # check stored distances
  
  def test_05_distances
    assert_equal 151.54, @@map[ :A, :B ]
    assert_equal 151.54, @@map[ :B, :A ]
    assert_equal 144.51, @@map[ :F, :G ]
    assert_nil @@map[:x, :y]
  end
  
  # make a short 3-city tour with the first 3 cities
  
  def test_06_make_tour
    t = @@map.make_tour [:A, :B, :C]
    assert_equal [:A, :B, :C], t.path
    assert_equal (@@map[:A,:B] + @@map[:B,:C] + @@map[:C,:A]), t.cost
    assert_equal 1, Tour.count
  end
    
  # exhaustive search for best tour -- record the best tour, and check to
  # to make sure each tour generated (by checking the count of the number made)
  
  def test_07_exhaustive
    @@best = @@map.make_tour(:random)
    Tour.reset
    @@map.each_tour { |t| @@best = t if t.cost < @@best.cost }
    assert_in_delta 1185.43, @@best.cost, 0.001
    assert_equal ntours(@@map.size), Tour.count
  end
  
  # point mutation test -- middle of the tour
  
  def test_08_mutate_middle
    t = @@map.make_tour([ :A, :B, :C, :D, :E, :F, :G ])
    tc = t.cost
    t.mutate!(2)
    assert_equal [:A, :B, :D, :C, :E, :F, :G], t.path
    assert_equal t.cost, tc - @@map[:B,:C] - @@map[:D,:E] + @@map[:B,:D] + @@map[:C,:E]
    t.mutate!(2)
    assert_equal [:A, :B, :C, :D, :E, :F, :G], t.path
    assert_equal tc, t.cost
  end
  
  # point mutation test -- wraparound
  
  def test_09_mutate_wrap
    t = @@map.make_tour([ :A, :B, :C, :D, :E, :F, :G ])
    tc = t.cost
    t.mutate!(6)
    assert_equal [:G, :B, :C, :D, :E, :F, :A], t.path
    assert_equal t.cost, tc - @@map[:F,:G] - @@map[:A,:B] + @@map[:F,:A] + @@map[:G,:B]
    t.mutate!(6)
    assert_equal [:A, :B, :C, :D, :E, :F, :G], t.path
    assert_equal tc, t.cost
  end
  
  # crossover test -- copy cities 2..4 from first tour, then get rest from other tour.
  
  def test_10_cross
    t0 = @@map.make_tour([ :A, :B, :C, :D, :E, :F, :G ])
    t1 = @@map.make_tour([ :G, :F, :E, :D, :C, :B, :A ])
    t0.cross!(t1, 2, 3)
    assert_equal [:C, :D, :E, :G, :F, :B, :A], t0.path
    t0.cross!(t1, 0, 1)
    assert_equal [:C, :G, :F, :E, :D, :B, :A], t0.path
    t0.cross!(t1, 6, 1)
    assert_equal [:A, :G, :F, :E, :D, :C, :B], t0.path
  end
  
  # random search -- check to make sure 100 tours are created when rsearch is told
  # to look at 100 random samples
  
  def test_11_rsearch
    Tour.reset
    rsearch(@@map, 100)
    assert_equal 100, Tour.count
  end
  
  # evolutionary search -- this test used to call esearch, but even with "safe"
  # parameters there were rare situations where the search got stuck and the test
  # failed; this version just does a quick check of the main routines called by
  # esearch
  
  def test_12_esearch
    Tour.reset
    # popsize = 50
    # ngen = 25
    # t = esearch(@@map, ngen, :popsize => popsize, :distribution => :mixed)
    # assert_in_delta @@best.cost, t.cost, 100*Float::EPSILON
    # assert_in_delta (popsize*ngen/2), Tour.count, 100
    popsize = 10
    ngen = 10
    pop = init_population(@@map, popsize)
    t0 = pop[0]
    assert_equal popsize, pop.length
    for i in 0..popsize-2
      assert pop[i].cost <= pop[i+1].cost
    end
    best = evolve(pop, ngen, 0, :distribution => :mixed)
    assert best.cost <= t0.cost 
  end
  
  # exhaustive search -- a method named xsearch implements the strategy used in 
  # the test above.
  
  def test_13_xsearch
    assert_equal @@best.cost, xsearch(@@map).cost
  end
  
  # Check the structure and iterators for a random map of 10 cities.
  
  def test_14_make_map
    m = Map.new(10)
    assert_equal 10, m.size
    assert_equal Array(0..9), m.labels
    assert_equal [0,1], m.first
    m.rest { |i,j| @last_pair = [i,j] }
    assert_equal [8,9], @last_pair
  end
  
end