For some application I need a permutation of three positions of a slice. Currently, I do this as follows:

fn permute3a<E>(lst: &mut [E], a: usize, b: usize, c: usize) {
    lst.swap(b, c);
    lst.swap(a, b);
}

This moves the element at a to b, b to c and c to a.

But I guess that doing two swaps is not the optimal solution for this problem. I would think that implementation would look like:

fn permute3b<E: Copy>(lst: &mut [E], a: usize, b: usize, c: usize) {
    let tmp = lst[c];
    lst[c] = lst[b];
    lst[b] = lst[a];
    lst[a] = tmp;
}

This implementation works for types that are Copy. It would be trivial to extend it to types that are Clone. But, cloning may be expensive, so this implementation may be worse than the one with the two swaps. If I could make it such that it moves values instead of copying, it would work for all types and would be more efficient.

Ideally, the slice type would have this function, and I could define

fn permute3c<E>(lst: &mut [E], a: usize, b: usize, c: usize) {
    lst.permute3(a,b,c);  // calls non existing function
}

Requesting this function seems unreasonable, because then next week someone may request permute4(a,b,c,d), and the week after another one permute5, and so on.

So, is there something more general that I could use to implement all those permutation functions? That would include the existing swap function, which is permute2(a,b).

I thought of a type named ValueMover. It is a mutator which takes a mutable reference to a list. The list is in an inconsistent state during the lifetime of the mutator, but the drop function will make it consistent again. Here is my implementation of ValueMover and of permute3 using it.

struct ValueMover<'a, E> {
    lst: &'a mut [E],
    pos: usize,
    tmp: MaybeUninit<E>,
}

impl<'a, E> ValueMover<'a, E> {
    pub fn take(lst: &mut [E], pos: usize) -> ValueMover<'_, E> {
        assert!(pos != usize::MAX);
        let mut tmp: MaybeUninit<E> = MaybeUninit::uninit();
        unsafe {
            tmp.write(mem::transmute_copy(&mut lst[pos]));
        }
        ValueMover { lst, pos, tmp }
    }
    pub fn move_from(&mut self, new_pos: usize) {
        if !self.is_occupied() {
            panic!("ValueMover::move_from called after release");
        }
        if new_pos == usize::MAX {
            self.panic("ValueMover::move_from may not be called with usize::MAX");
        }
        if new_pos >= self.lst.len() {
            self.panic("ValueMover::move_from called with out of bounds value");
        }
        if self.pos != new_pos {
            unsafe {
                self.lst[self.pos] = mem::transmute_copy(&mut self.lst[new_pos]);
            }
            self.pos = new_pos;
        }
    }
    fn release(&mut self) {
        assert!(self.is_occupied());
        unsafe {
            self.lst[self.pos] = mem::transmute_copy(&mut *self.tmp.as_mut_ptr());
        }
        self.pos = usize::MAX;
    }
    fn panic(&mut self, msg: &str) {
        self.release();
        panic!("{}", msg);
    }
    fn is_occupied(&self) -> bool {
        self.pos != usize::MAX
    }
}

impl<'a, E> Drop for ValueMover<'a, E> {
    fn drop(&mut self) {
        if self.is_occupied() {
            self.release();
        }
    }
}

fn permute3d<E>(lst: &mut [E], a: usize, b: usize, c: usize) {
    let mut mover = ValueMover::take(lst, c);
    mover.move_from(b);
    mover.move_from(a);
}

As you can see, my implementation uses transmute_copy, which is advertised as about the most dangerous function in the standard library. So my main question is: “Is this implementation safe?”. This is my first time I use unsafe, so I am quite uncertain about it.

If it is not safe, I would like to know why and if it can be fixed.

And finally, I would like to know your opinion if you think that such a mutator for slice would be a good addition to the standard library. I mean, that there would be a function take such that I could write:

fn permute3e<E>(lst: &mut [E], a: usize, b: usize, c: usize) {
    let mut mover = lst.take(lst, c);
    mover.move_from(b);
    mover.move_from(a);
}

2 posts - 2 participants

Read full topic