Implement inplace circshift

[musm]

We have circshift but no inplace version, which would be very useful. There is a rough implementation in the lbm3d threads test.

[stevengj]

(See also the discussion at the end of #9822.)

[stevengj]

@Musmo, the circshift you're referring to is based on a chase-the-cycles approach. The Knuth algorithm (based on two reversal passes) is far better for arbitrary shifts.

[stevengj]

For example, here is a working 1d circshift!:

function circshift!(a::AbstractVector, shift::Integer)
    n = length(a)
    s = mod(shift, n)
    s == 0 && return a
    reverse!(a, 1, s)
    reverse!(a, s+1, n)
    reverse!(a)
end

The only thing I'm not sure of is how to generalize this to arbitrary dimensions without writing out a bunch of explicit loops for 2d, 3d, etcetera arrays. @timholy, is this something that your cartesian iterators could handle?

(Also, it would be nice to fuse the reversal loops in higher dimensions so that only 2 passes, not 2k passes, are required for shifting a k-dimensional array along all k dimensions simultaneously. But maybe in practice people usually shift only along a 1 or 2 dimensions at a time?)

[stevengj]

@timholy, is it worth keeping this open for a truly in-place circshift!, as opposed to a circshift! with pre-allocated output?

[timholy]

I'm fine with that, if others want that. We don't have a truly in-place transpose!, either. (Not that I want one, but someone might.)

So feel free to reopen if you are interested.

[ararslan]

Since we're consolidating rol and ror with circshift, it would be nice to have circshift!(A, i) for any array rather than just BitVectors. Currently one has to do circshift!(A, A, i) for regular arrays but circshift!(A, i) works for BitVectors (as of #23404).

[robsmith11]

It looks like circshift!(A, A, i) no longer works. Is it meant to?

julia> circshift!(X, X, 1)
ERROR: ArgumentError: dest and src must be separate arrays
Stacktrace:
 [1] circshift!(dest::Vector{Float64}, src::Vector{Float64}, shiftamt::Tuple{Int64})
   @ Base ./multidimensional.jl:1117
 [2] circshift!(dest::Vector{Float64}, src::Vector{Float64}, shiftamt::Int64)
   @ Base ./multidimensional.jl:1123
 [3] top-level scope
   @ REPL[370]:1