1.1.3 Array Rotation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

/*

Rotates the half-open iterator range $[`lo`, `hi`)$ left around the split point `mid`, where
$`lo` \leq `mid` \leq `hi`$. Writing the adjacent subranges $[`lo`, `mid`)$ and $[`mid`, `hi`)$ as
`A` and `B`, respectively, the operation transforms `A B` into `B A` while preserving the relative
order within each subrange. The standard library function `std::rotate(lo, mid, hi)` performs the
same rearrangement.

All three versions below operate in place, using different algorithms and iterator capabilities.

- `rotate1(lo, mid, hi)` requires ForwardIterators and repeatedly swaps the next elements of the two
  unfinished subranges. When the right iterator reaches `hi`, it wraps to the current `mid`; when
  the left iterator reaches `mid`, that boundary advances to the right iterator.
- `rotate2(lo, mid, hi)` requires BidirectionalIterators, applying a trick with three reversals.
  Writing the input subranges as `A B`, two initial reversals yield `reverse(A) reverse(B)`; then
  the whole range is reversed to yield `B A`, restoring the order within each subrange.
- `rotate3(lo, mid, hi)` requires random-access iterators, applying a juggling algorithm which first
  divides the range into `gcd(hi - lo, mid - lo)` sets and then rotates the corresponding elements
  in each set. The method follows the permutation that sends each position to its rotated
  destination. These form that many disjoint cycles, so walking each cycle once moves every element
  to its final position.

Time Complexity:
- O(n) per call to all versions, where $n$ is the distance between `lo` and `hi`.

Space Complexity:
- O(1) auxiliary for all versions.

*/

#include <algorithm>
#include <numeric>

template<typename It>
void rotate1(It lo, It mid, It hi) {
  if (lo == mid || mid == hi) {
    return;
  }
  It next = mid;
  while (lo != next) {
    std::iter_swap(lo++, next++);
    if (next == hi) {
      next = mid;
    } else if (lo == mid) {
      mid = next;
    }
  }
}

template<typename It>
void rotate2(It lo, It mid, It hi) {
  if (lo == mid || mid == hi) {
    return;
  }
  std::reverse(lo, mid);
  std::reverse(mid, hi);
  std::reverse(lo, hi);
}

template<typename It>
void rotate3(It lo, It mid, It hi) {
  if (lo == mid || mid == hi) {
    return;
  }
  int n = static_cast<int>(hi - lo);
  int jump = static_cast<int>(mid - lo);
  int g = std::gcd(jump, n), cycle = n / g;
  for (int i = 0; i < g; i++) {
    int curr = i, next;
    for (int j = 0; j < cycle - 1; j++) {
      next = curr + jump;
      if (next >= n) {
        next -= n;
      }
      std::iter_swap(lo + curr, lo + next);
      curr = next;
    }
  }
}

/*** Example Usage ***/

#include <algorithm>
#include <cassert>
#include <vector>
using namespace std;

int main() {
  vector<int> a0, a1, a2, a3;
  for (int i = 0; i < 10000; i++) {
    a0.push_back(i);
  }
  a1 = a2 = a3 = a0;
  int mid = 5678;
  std::rotate(a0.begin(), a0.begin() + mid, a0.end());
  rotate1(a1.begin(), a1.begin() + mid, a1.end());
  rotate2(a2.begin(), a2.begin() + mid, a2.end());
  rotate3(a3.begin(), a3.begin() + mid, a3.end());
  assert(a0 == a1 && a0 == a2 && a0 == a3);

  vector<int> no_op{1, 2, 3};
  rotate1(no_op.begin(), no_op.begin(), no_op.end());
  assert((no_op == vector<int>{1, 2, 3}));
  rotate2(no_op.begin(), no_op.end(), no_op.end());
  assert((no_op == vector<int>{1, 2, 3}));
  rotate3(no_op.begin(), no_op.begin(), no_op.end());
  assert((no_op == vector<int>{1, 2, 3}));

  vector<int> a{2, 4, 2, 0, 5, 10, 7, 3, 7, 1};

  // Insertion sort.
  for (auto i = a.begin(); i != a.end(); ++i) {
    rotate1(upper_bound(a.begin(), i, *i), i, i + 1);
  }
  assert((a == vector<int>{0, 1, 2, 2, 3, 4, 5, 7, 7, 10}));

  // Simple rotation to the left.
  rotate2(a.begin(), a.begin() + 1, a.end());
  assert((a == vector<int>{1, 2, 2, 3, 4, 5, 7, 7, 10, 0}));

  // Simple rotation to the right.
  rotate3(a.rbegin(), a.rbegin() + 1, a.rend());
  assert((a == vector<int>{0, 1, 2, 2, 3, 4, 5, 7, 7, 10}));
  return 0;
}