content: module S9_6 where
  -- to get access to the imported modules in Hugs do
  -- :set -P../Chapter7:../Chapter5:{Hugs}/lib:{Hugs}/lib/hugs:{Hugs}/lib/exts
  
  import Dynamic
  import Graph
  
  -- implementation of a Set with an Int 
  -- open and concrete version of the bit string implementation of the ADT Set
  -- check bounds only for fullset which is called at the start of the TSP
  
  type Set = Int
  
  emptySet = 0
  
  setEmpty n = n==0
  
  fullSet n | (n>=0) && (n<=maxSet) = 2^(n+1)-2 -- element 0 is not there...
            | otherwise = error ("fullset:illegal set =" ++ show n)
  
  addSet i s = d'*e+m
      where (d,m) = divMod s e
            e  = 2^i
            d' = if odd d then d else d+1
  
  delSet i s = d'*e+m
      where (d,m) = divMod s e
            e = 2^i
            d' = if odd d then d-1 else d
  
  set2List s = s2l s 0
      where s2l 0 _             = []
            s2l n i | odd n     = i : s2l (n `div` 2) (i+1)
                    | otherwise = s2l (n `div` 2) (i+1)
  
  maxSet = truncate (logBase 2 (fromInt (maxBound::Int))) - 1
  
  -- start of TSP
  
  type TspCoord = (Int,Set)
  type TspEntry = (Int,[Int])
  
  compTsp :: Graph Int Int -> Int -> Table TspEntry TspCoord 
                           -> TspCoord -> TspEntry 
  compTsp g n a (i,k) 
      | setEmpty k = (weight i n g,[i,n])
      | otherwise = minimum [ addFst (findTable a (j, delSet j k))
                                     (weight i j g)
                              | j <- set2List k]
      where addFst (c,p) w = (w+c,i:p)
  
  bndsTsp   :: Int -> ((Int,Set),(Int,Set))
  bndsTsp n =  ((1,emptySet),(n,fullSet n))
  
  tsp   :: Graph Int Int -> (Int,[Int])
  tsp g = findTable t (n,fullSet (n-1))
      where n = length (nodes g)
            t = dynamic (compTsp g n) (bndsTsp n)
  
  -- examples of graphs 
  
  dm::Graph Int Int
  dm = mkGraph True (1,6) [(i,j,(v1!!(i-1))!!(j-1)) |i<-[1..6],j<-[1..6]]
  v1::[[Int]]
  v1 =[[  0,  4,  1,  6,100,100],
       [  4,  0,  1,100,  5,100],
       [  1,  1,  0,100,  8,  2],
       [  6,100,100,  0,100,  2],
       [100,  5,  8,100,  0,  5],
       [100,100,  2,  2,  5,  0]]
  
  oldbrassardP103 :: Graph Int Int
  oldbrassardP103
      = mkGraph True (1,6) [(i,j,(v'!!(i-1))!!(j-1)) |i<-[1..6],j<-[1..6]]
  v'::[[Int]]
  v' =  [[  0,  3, 10, 11,  7, 25],
         [  3,  0,  6, 12,  8, 26],
         [ 10,  6,  0,  9,  4, 20],
         [ 11, 12,  9,  0,  5, 15],
         [  7,  8,  4,  5,  0, 18],
         [ 25, 26, 20, 15, 18,  0]]
  
  
  {- Examples of evaluations and results 
  
  ? tsp dm
  (20, [6, 4, 1, 3, 2, 5, 6])
  ? tsp oldbrassardP103
  (56, [6, 3, 2, 1, 5, 4, 6])
  
  -}
  