gistfile1.txt

"""
    circshift_gcdless!(arr::AbstractVector, shift)

Circularly shift the array `arr` by the given `shift` amount.
The algorithm used is the well-known GCD-less (aka implicit GCD)
juggling algorithm (e.g. STL3 in [SHENE97]).

[SHENE97] https://pages.mtu.edu/~shene/PUBLICATIONS/1997/Array-Rotation.pdf
"""
function circshift_gcdless!(arr::AbstractVector, shift::Integer)
    i = 1
    n = length(arr)
    shift = mod(shift, n)
    shift == 0 && return
    total = 0
    while total < n
        total += _circshift_gcdless_iter!(arr, shift, i)
        i += 1
    end
end

@inline function _circshift_gcdless_iter!(arr::AbstractVector, shift::Integer, i::Integer)
    n = length(arr)
    @inbounds tmp = arr[i]
    idx = i
    nextidx = shift > 0 ? n + (idx - shift) : idx - shift
    l = 0
    @inbounds while l == 0 || idx != i
        arr[idx] = arr[nextidx]
        idx = nextidx
        nextidx -= shift
        nextidx <= 0 && (nextidx += n)
        l += 1
    end
    arr[i] = tmp
    return l
end