Rotation revisited: Avoiding having to calculate the gcd when doing cycle decomposition

Last time, we looked at how clang’s libcxx implementation of std::rotate uses cycle decomposition to minimize the number of swaps. Doing so requires calculating the greatest common divisor, but I noted that the OpenJDK implementation of the java standard library uses a trick to avoid doing the gcd calculation.

The trick is realizing that the total number of elements is equal to the sum of the lengths of each of its cycles, and each of the initial elements belongs to a different cycle. Therefore, we can just keep rotating elements until the number of elements rotated is equal to the total. We don’t have to precalculate the number of cycles; we just let the counter tell us when we’re done.

auto a = std::distance(first, mid); // number of "A" elements
auto n = std::distance(first, last); // total elements
auto count = 0;
auto k = 0;

while (count < n) {
    // Rotate the elements in the cycle starting at k
    auto save = std::move(first[k]);
    auto i, next = k;
    while (i = next, next = (i + a) % n, next != k) {
        first[i] = std::move(first[next]);
        ++count;
    }
    first[i] = std::move(save);
    ++count;
}