How to rotate a vector without standard library?

Question

I'm getting into Rust and Arduino at the same time.

I was programming my LCD display to show a long string by rotating it through the top column of characters. Means: Every second I shift all characters by one position and show the new String.

This was fairly complex in the Arduino language, especially because I had to know the size of the String at compile time (given my limited knowledge).

Since I'd like to use Rust in the long term, I was curious to see if that could be done more easily in a modern language. Not so much.

This is the code I came up with, after hours of experimentation:

#![no_std]

extern crate alloc;

use alloc::{vec::Vec};

fn main() {
}

fn rotate_by<T: Copy>(rotate: Vec<T>, by: isize) -> Vec<T> {
    let real_by = modulo(by, rotate.len() as isize) as usize;
    Vec::from_iter(rotate[real_by..].iter().chain(rotate[..real_by].iter()).cloned())
}

fn modulo(a: isize, b: isize) -> isize {
    a - b * (a as f64 /b as f64).floor() as isize
}

mod tests {
    use super::*;

    #[test]
    fn test_rotate_five() {
        let chars: Vec<_> = "I am the string and you should rotate me!   ".chars().collect();

        let res_chars: Vec<_> = "the string and you should rotate me!   I am ".chars().collect();

        assert_eq!(rotate_by(chars, 5), res_chars);
    }
}

My questions are:

• Could you provide an optimized version of this function? I'm aware that there already is Vec::rotate but it uses unsafe code and can panic, which I would like to avoid (by returning a Result).
• Explain whether or not it is possible to achieve this in-place without unsafe code (I failed).
• Is Vec<_> the most efficient data structure to work with? I tried hard to use [char], which I thought would be more efficient, but then I have to know the size at compile time, which hardly works. I thought Rust arrays would be similar to Java arrays, which can be sized at runtime yet are also fixed size once created, but they seem to have a lot more constraints.
• Oh and also what happens if I index into a vector at an invalid index? Will it panic? Can I do this better? Without "manually" checking the validity of the slice indices?

I realize that's a lot of questions, but I'm struggling and this is bugging me a lot, so if somebody could set me straight it would be much appreciated!

Answer 1

You can use slice::rotate_left and slice::rotate_right:

#![no_std]

extern crate alloc;
use alloc::vec::Vec;

fn rotate_by<T>(data: &mut [T], by: isize) {
    if by > 0 {
        data.rotate_left(by.unsigned_abs());
    } else {
        data.rotate_right(by.unsigned_abs());
    }
}

I made it rotate in-place because that is more efficient. If you don't want to do it in-place you still have the option of cloning the vector first, so this is more flexible than if the function creates a new vector, as you have done, because you aren't be able to opt out of that when you call it.

Notice that rotate_by takes a mutable slice, but you can still pass a mutable reference to a vector, because of deref coercion.

#[test]
fn test_rotate_five() {
    let mut chars: Vec<_> = "I am the string and you should rotate me!   ".chars().collect();
    let res_chars: Vec<_> = "the string and you should rotate me!   I am ".chars().collect();
    rotate_by(&mut chars, 5);
    assert_eq!(chars, res_chars);
}

There are some edge cases with moving chars around like this because some valid UTF-8 will contain grapheme clusters that are made up of multiple codepoints (chars in Rust). This will result in strange effects when a grapheme cluster is split between the start and end of the string. For example, rotating "abcdéfghijk" by 5 will result in "efghijkabcd\u{301}", with the acute accent stranded on its own, away from the 'e'.

If your strings are ASCII then you don't have to worry about that, but then you can also just treat them as byte strings anyway:

#[test]
fn test_rotate_five_ascii() {
    let mut chars = b"I am the string and you should rotate me!   ".clone();
    let res_chars = b"the string and you should rotate me!   I am ";
    rotate_by(&mut chars, 5);
    assert_eq!(chars, &res_chars[..]);
}