How do I turn a circular buffer into a vector in O(n) without an allocation?

Question

I have a Vec that is the allocation for a circular buffer. Let's assume the buffer is full, so there are no elements in the allocation that aren't in the circular buffer. I now want to turn that circular buffer into a Vec where the first element of the circular buffer is also the first element of the Vec. As an example I have this (allocating) function:

fn normalize(tail: usize, buf: Vec<usize>) -> Vec<usize> {
    let n = buf.len();
    buf[tail..n]
        .iter()
        .chain(buf[0..tail].iter())
        .cloned()
        .collect()
}

Playground

Obviously this can also be done without allocating anything, since we already have an allocation that is large enough, and we have a swap operation to swap arbitrary elements of the allocation.

fn normalize(tail: usize, mut buf: Vec<usize>) -> Vec<usize> {
    for _ in 0..tail {
        for i in 0..(buf.len() - 1) {
            buf.swap(i, i + 1);
        }
    }
    buf
}

Playground

Sadly this requires buf.len() * tail swap operations. I'm fairly sure it can be done in buf.len() + tail swap operations. For concrete values of tail and buf.len() I have been able to figure out solutions, but I'm not sure how to do it in the general case.

My recursive partial solution can be seen in action.

Answer 1

The simplest solution is to use 3 reversals, indeed this is what is recommended in Algorithm to rotate an array in linear time.

//  rotate to the left by "k".
fn rotate<T>(array: &mut [T], k: usize) {
    if array.is_empty() { return; }

    let k = k % array.len();

    array[..k].reverse();
    array[k..].reverse();
    array.reverse();
}

While this is linear, this requires reading and writing each element at most twice (reversing a range with an odd number of elements does not require touching the middle element). On the other hand, the very predictable access pattern of the reversal plays nice with prefetching, YMMV.

Answer 2

This operation is typically called a "rotation" of the vector, e.g. the C++ standard library has std::rotate to do this. There are known algorithms for doing the operation, although you may have to quite careful when porting if you're trying to it generically/with non-Copy types, where swaps become key, as one can't generally just read something straight out from a vector.

That said, one is likely to be able to use unsafe code with std::ptr::read/std::ptr::write for this, since data is just being moved around, and hence there's no need to execute caller-defined code or very complicated concerns about exception safety.

A port of the C code in the link above (by @ker):

fn rotate(k: usize, a: &mut [i32]) {
    if k == 0 { return }

    let mut c = 0;
    let n = a.len();
    let mut v = 0;
    while c < n {
        let mut t = v;
        let mut tp = v + k;
        let tmp = a[v];
        c += 1;
        while tp != v {
            a[t] = a[tp];
            t = tp;
            tp += k;
            if tp >= n { tp -= n; }
            c += 1;
        }
        a[t] = tmp;
        v += 1;
    }
}