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

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;
    }
}