Wrapped delta of index into Vec

help
1

I find myself rewriting the logic for adjusting the value of an index into a vector (with wrapping, or with rejection of movement beyond the ends), for the Nth time.

If you want to change the index by a negative amount, you end up converting back and forth between signed and unsigned types ... or you can create an enum to distinguish the forward and back directions, and then you have to deal with the behaviour at the boundaries.

It's fiddly and distracting. So I'm wondering if there is a neat idiom for this kind of thing, or some utilities that make it less fiddly.

In other words, can you suggest a better way of writing something like this:

enum Delta {
    R(usize),
    L(usize),
}

fn move_index_by<T>(index: usize, delta: Delta, vec: &[T]) -> usize {
    match delta {
        Delta::R(d) => index.wrapping_add(            d),
        Delta::L(d) => index.wrapping_add(vec.len() - d),
    }.rem_euclid(vec.len())

}

?

2

So is this related to a specific algorithm you're working with, or is it more of a general issue?

For a specific case, you can always wrap a type and add custom methods to it. Here's an example:

struct ExtVec<T>(Vec<T>);

impl<T> ExtVec<T> {
    fn new() -> Self {
        ExtVec(Vec::new())
    }

    fn move_index(&self, index: usize, delta: isize) -> usize {
        todo!() // Add your logic here
    }
}

impl<T> std::ops::Deref for ExtVec<T> {
    type Target = Vec<T>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl<T> std::ops::DerefMut for ExtVec<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

Since the wrapper implements both Deref and DerefMut, you can use it like a regular Vec:

let mut ev = ExtVec::new();

ev.push(1);
ev.push(2);

let moved = ev.move_index(17, -98);
let x = ev[moved];

For a more general case, you could create a trait and implement it for Vec. This is known as the Extension Traits pattern. While useful, it does have some downsides, so it’s worth exploring more about this technique in various posts and discussions.

3

You could write your own index type with your required semantics.

#[derive(Clone, Copy)]
pub struct WrappingIndex(isize);

impl WrappingIndex {
    #[inline(always)]
    fn into_usize(self, len: usize) -> usize {
        self.0.rem_euclid(self.len() as isize) as usize
    }
}

impl<T> Index<WrappingIndex> for [T] {
    type Output = T;
    fn index(&self, idx: WrappingIndex) -> &T {
        &self[idx.into_usize(self.len())]
    }
}

// TODO: impl Add and Mul for WrappingIndex
3 Likes
4

Maybe you're looking for things like https://doc.rust-lang.org/std/primitive.usize.html#method.checked_add_signed?

5

Wow, how miserably I failed to describe what my issue is!

All I want is a clean way of writing

(x + dx).rem_euclid(size)

for an unsigned type.

I only mentioned Vec and indices, because they are what imposes the need to do this with an unsigned type, and I expected legions of other people to have faced the need to wrap around indices before and thus have been irked by how ugly this triviality gets.

This is a question about a trivial mathematical operation, complicated be the introduction of unsigned types, rather than being about interfaces behind which that operation might be hidden.

Oooh, the *_signed methods had escaped my notice thus far. Thanks!

But I don't see one that helps me get something that is any more robust and concise than converting everything to isize, doing the calculation and converting back to usize:

fn wrap(x: usize, dx: isize, size: usize) -> usize {
    (x as isize + dx).rem_euclid(size as isize) as usize
}

16 tokens instead of 10. I can live with that.

6

It doesn't reduce the number of tokens, but I had some fun in golfing it down by a few more bytes:

fn wrap(x: usize, dx: isize, size: usize) -> usize {
    (x as isize + dx).rem_euclid(size as _) as _
}
7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.