Shifting a segment

Shifting a segment is a generalization of the concept of shifting a node: instead of shifting a single city, we shift a whole segment (chain of cities) to other position in tour.

The idea:

Diagrams:

Segment Shift move is a the same as the symmetric pure 3-opt move (case 7).

Node Shift is a special case of Segment Shift, when a segment has length of 1 (j==i+1).

proc Shift_Segment(tour: var Tour_Array; i, j, k: Tour_Index) =
  ## Shifts the segment of tour:
  # cities from t[i+1] to t[j] from their current position to position
  # after current city t[k], that is between cities t[k] and t[k+1].
  # Assumes:  k, k+1 are not within the segment [i+1..j]
  let
    segmentSize = (j - i + N) mod N
    shiftSize = ((k - i + N)  - segmentSize + N) mod N
    offset = i + 1 + shiftSize
  var
    pos: Tour_Index
    segment: seq[City_Number] = newSeq[City_Number](segmentSize)

  # make a copy of the segment before shift
  for counter in 0 .. segmentSize-1:
    segment[pos] = tour[(pos + i+1) mod N]

  # shift to the left by segmentSize all cities between old position
  # of right end of the segment and new position of its left end
  pos  = (i + 1) mod N
  for counter in 1 .. shiftSize:
    tour[pos] = tour[(pos + segmentSize) mod N]
    pos  = (pos + 1) mod N

  # put the copy of the segment into its new place in the tour
  for pos in 0 .. segmentSize-1:
    tour[(pos + offset) mod N] = segment[pos]