Friday, May 12, 2017

Swapping segments

s1 e1 s2 e2 A B
B A
proc Swap_Segments(tour: var Tour_Array;
                   start_1, end_1, start_2, end_2: Tour_Index;
                   position: var City_Position_In_Tour) =
  ## Swaps two consecutive segments of tour:
  ## [start_1, end_1] and [start_2, end_2]
  ## NOTE: start_2 should be tour successor of end_1
  var
    left, right: Tour_Index
    segment: seq[City_Number]

  let size_1 = (N + end_1 - start_1 + 1) mod N
  let size_2 = (N + end_2 - start_2 + 1) mod N
    
  # make a copy of first segment:
  segment = newSeq[City_Number](size_1)
  right = end_1
  for pos in 0 .. size_1-1:
    segment[pos] = tour[right]
    right = t_pred(right)

  # move second segment backward, it should start at start_1:
  left  = start_2
  right = start_1
  for counter in 1 .. size_2:
    tour[right] = tour[left]
    position[tour[right]] = right
    left  = t_succ(left)
    right = t_succ(right)

  # put the copy of first segment in its new place in tour:
  left = end_2
  for pos in 0 .. size_1-1:
    tour[left] = segment[pos]
    position[tour[left]] = left
    left = t_pred(left)

No comments:

Post a Comment