0

I have posted my solution in the answers below.

The question will not be updated with even more code to not further increase clutter.

I'm trying to rotate all elements in a Vec<Vec<T>> clockwise. The vector is guaranteed to be square, as in v.len() == v[0].len().

The idea is to

  • find all elements that are equivalent under rotational symmetry to v's center
  • swap these elements in place, using std::mem::swap

My current code does not change the state of the vec. How do I fix this?

fn rotate<T>(v: &mut Vec<Vec<T>>) {

    // swap elements equivalent to position i on each ring r 
    // limit l = side length of current ring
    //
    // + 0 - - - - +   r = 0 -> l = 6
    // | + 1 - - + |   r = 1 -> l = 4
    // | | + 2 + | |   r = 2 -> l = 2
    // | | |   | | |
    // | | + - + | |   swap:
    // | + - - - + |     a b c d
    // + - - - - - +   > b a c d
    //                 > c a b d
    //                 > d a b c

    for r in 0..((v.len() + 1) / 2 {
        let l = v.len() - 1 - r;
        for i in r..l {
            let mut a = & pieces[  r  ][ r+i ];
            let mut b = & pieces[ r+i ][ l-r ];
            let mut c = & pieces[ l-r ][l-r-i];
            let mut d = & pieces[l-r-i][  r  ];

            _rot_cw(&mut a, &mut b, &mut c, &mut d)},
        }
    }

    fn _rot_cw<T>(a: &mut T, b: &mut T, c: &mut T, d: &mut T) {
        //rotates a->b, b->c, c->d, d->a
        std::mem::swap(a, b);
        std::mem::swap(a, c);
        std::mem::swap(a, d);
    }
}

Edit:
Fixed minor issues in the original code above, thanks to @Jmb. Here's my current code, again running into borrowing issues:

fn rotate_square_slice<T>(slice: &mut Vec<T>, rows: usize) {
    for r in 0..(slice.len()+1)/2 {
        let l = slice.len() -1 - r;
        for i in r..l {
            let a = &mut slice.get_mut(rows *    r    +  r+i ).unwrap();
            let b = &mut slice.get_mut(rows *  (r+i)  +  l-r ).unwrap();
            let c = &mut slice.get_mut(rows *  (l-r)  + l-r-i).unwrap();
            let d = &mut slice.get_mut(rows * (l-r-i) +   r  ).unwrap();

            std::mem::swap(a, b);
            std::mem::swap(a, c);
            std::mem::swap(a, d);
        }
    }
}
Orphevs
  • 125
  • 7
  • Please don't prefix identifiers you use with `_`. That is an indication that the identifier must exist but the value is not used, which is not true for your `_rot_cw`. – Shepmaster Feb 27 '20 at 01:52
  • `& pieces` you are taking an **immutable** reference to the item in the vector. Since it's immutable, the vector won't be mutated. – Shepmaster Feb 27 '20 at 01:54
  • @Shepmaster is there another idiom for internal functions? Or are they generally not marked as such, because they aren't exposed? – Orphevs Feb 27 '20 at 01:54
  • All of the test cases presented compile and pass. Perhaps you should add some that fail to demonstrate the problem. – Shepmaster Feb 27 '20 at 01:55
  • The natural scoping of the function inside the other function prevents anything from outside the function from using it (much like a variable), so just call it `rot_cw`. – Shepmaster Feb 27 '20 at 01:55
  • @Shepmaster alright, I'll keep it in mind. The issue with `& v` is that I need to mutate 4 values, and can only borrow mutably once. Is there a way for this to work? – Orphevs Feb 27 '20 at 01:59
  • Edited the provided code to properly use `v` everywhere – Orphevs Feb 27 '20 at 02:01
  • [How to get mutable references to two array elements at the same time?](https://stackoverflow.com/q/30073684/155423) – Shepmaster Feb 27 '20 at 02:02
  • @Shepmaster thanks you, I didn't know about that. I will look into trying this tomorrow. If you want to provide an Answer, I'll gladly accept it if this works. Off to sleep now. Cheers! – Orphevs Feb 27 '20 at 02:06
  • 1
    I've got two side notes. First, representing a square matrix as a `Vec>` is not ideal. This type represents a variable-length vector of variable-length vectors, and you manually have to maintain the invariant that each of the inner vectors has the same length as the outer vector. Moreover, there is quite some overhead, because you need a separate allocation for each row, and element access requires multiple pointer indirections. Using a custom type wrapping a single vector can give you both better type safety and better performance. – Sven Marnach Feb 27 '20 at 04:11
  • 1
    Second, if you implement the square matrix as a custom type, you will have custom index operations. This allows you to introduce two [strides](https://en.wikipedia.org/wiki/Stride_of_an_array) for the two axes of your matrix, plus some fixed offset. Rotating the matrix then becomes a matter of modifying the strides and the fixed offset, rather than actually moving all the data around. I don't know your exact use case, so I don't know whether this would be a good fit for you, but it's a common approach that has proven useful in practice. – Sven Marnach Feb 27 '20 at 04:15
  • You shouldn't use floating point operations to manipulate the length of your vector. Using `(pieces.len()+1)/2` will be faster and more accurate (with less risk of overflow). – Jmb Feb 27 '20 at 08:13
  • @Jmb, thanks! fixed. Will post updated code later. – Orphevs Feb 27 '20 at 12:10
  • @SvenMarnach Thank you. I've altered the function to work on a `&[T]` instead. I'm stuck at fixing the indexing though. Implementing a "2d" indexing `(usize, usize) -> T` is doable, but I'm running into lifetime issues when trying to get a "symmetry" based indexing `(usize, usize, usize) -> (&T, &T, &T, &T)` for `(r, l, i) -> (a, b, c, d)`. How do I mutably index into a slice on 4 different positions at the same time? I didn't have much luck figuring out `split_at_mut()` yet, as suggested by @Shepmaster's linked answer. – Orphevs Feb 27 '20 at 12:23

1 Answers1

0

Swapping elements in a slice can be done by using the slice's swap() method.

Solving that problem, the code now looks like this:

fn rotate_square_slice<T>(slice: &mut [T], size: usize) {
    for r in 0..(size + 1) / 2 {
        let l = size - 1 - r;
        for i in r..l {    
            // b, c & d are the indices with rotational symmetry to a,
            // shifted by 90°, 180° & 270° respectively
            
            let a = size *    r    +  r+i ;
            let b = size *  (r+i)  +  l-r ;
            let c = size *  (l-r)  + l-r-i;
            let d = size * (l-r-i) +   r  ;

            slice.swap(a, b);
            slice.swap(a, c);
            slice.swap(a, d);
        }
    }
}

I have, however, run into an issue with correctly indexing the slice. The question can be found here:

Rotational Symmetry Indexing in a 1D "Square" Array

Community
  • 1
  • 1
Orphevs
  • 125
  • 7