$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
  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 -- instead of trying to test components (init_population, 
  # select_survivors, rebuild population) this test just checks to see if esearch
  # finds the best tour.  Since there are only 7 cites (360 tours) running for 
  # 25 generations with a population size of 50 should be more than enough to find
  # the optimal tour (saved by the exhaustive search in a previous test).  The search
  # should make around 625 tours; checking for a count between 525 and 725 should be safe.
  
  def test_12_esearch
    popsize = 50
    ngen = 25
    Tour.reset
    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
  end
  
end