Reversing a segment

One of the standard transformations of a tour used in local optimization is reversing a segment. In the new tour all the cities of the segment occur in reverse order.

pos.    0 1 2 3 4 5 6 7 ...
before  A-B-C-D-E-F-G-H-...
after   A-B-F-E-D-C-G-H-...

We use the following algorithm: swap the first and the last city of the segment, then the second and one before last, and so on, to the middle of the segment. This way number of swaps is equal half of the segment size.

Beware

We should not forget that a tour is cyclic, and therefore after tour[N-1] city (in ascending order of indices) goes tour[0], to close the tour. Therefore segment from tour[N-2] to tour[2] is 5 cities long — it constists of: tour[N-2], tour[N-1], tour[0], tour[1] and tour[2], in this order. Note that reversing the complementary segment, consisting of the cities on positions from 2 to (N-2), is not the exactly same and in some cases may lead to erroneous results. (But see later reversing a segment given by city numbers, not by positions, more complex and using additional structure, but where this problem does not occur).

proc Reverse_Segment(tour: var Tour_Array;
                     startIndex, endIndex: Tour_Index) =
  ## Reverses order of elements in segment [startIndex, endIndex]
  ## of tour.
  ## NOTE: Final and initial part of tour make one segment.
  ## NOTE: While the order of arguments can be safely changed when
  ## reversing segment in 2-optimization, it makes difference for
  ## 3-opt move - be careful and do not reverse (x,z) instead of (z,x).
  var
    left, right: Tour_Index

  let inversionSize = ((N + endIndex - startIndex + 1) mod N) div 2
   
  left  = startIndex
  right = endIndex

  for counter in 1 .. inversionSize:
    swap(tour[left], tour[right])
    left  = (left + 1) mod N
    right = (N + right - 1) mod N