Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
"""
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment