Sorting methods for Slice variant

[Christopher-S-25]

Some useful methods I miss from Array Of Structs are the sorting methods, which are sort(), sort_by() and sort_by_key() for the slice primitive type. From what I've seen, the Slice variant produced by the macro does not offer any sorting methods.

I believe it is possible to implement sorting using the permutation crate, and adding a #[sort] attribute. For example, the sort() method would be like this (Example works if #[sort] is removed/commented out):

use soa_derive::StructOfArray;

#[derive(StructOfArray)]
#[soa_derive(Debug)]
struct Foo {
    // The type of the field with the `#[sort]` attribute must implement the `Ord` trait
    #[sort]
    bar: u8,
    baz: bool,
}
// --------------------------------------------------------------------------------
// The macro-generated code
impl FooSliceMut<'_> {
    fn sort(&mut self) {
        use permutation::permutation as pmut;

        let mut permutation = pmut::sort(&self.bar);

        permutation.apply_slice_in_place(&mut self.bar);
        permutation.apply_slice_in_place(&mut self.baz);
    }

    // ... Other sorting methods ...
}
// --------------------------------------------------------------------------------
// Example usage
fn main() {
    use rand::Rng;

    let mut foo_vec = FooVec::new();
    let mut rng = rand::thread_rng();

    for i in 1..=10 {
        let num = rng.gen();
        foo_vec.push(Foo { bar: num, baz: i % 2 == 0 });
    }

    println!("Before sorting: {foo_vec:#?}");

    foo_vec.as_mut_slice().sort();

    println!("After sorting: {foo_vec:#?}");
}

I don't have any experience with making macros, but I can try implementing it. I'm open to any other ideas or suggestions about the implementation.

The alternative to pulling in a whole crate for sorting is to zip the vectors from all fields, sort them, and then split them back, which is very costly due to multiple allocations. A middle-ground solution would be to provide sorting under a feature (eg. sort) to avoid increasing default dependencies.

Limitations:

• Sorting methods will sort only based on the specified field (can be solved with generating differently named sorting methods for each field or providing a #[sort(...)] syntax for naming)
• Sorting a Vec variant requires the as_mut_slice() method first, as described in the project's caveats

[Luthaf]

I agree that sorting is a worth adding to the generated code!

However I would prefer doing something which sorts based on all fields by default, so that sorting XXXStructVec produces the same output as sorting a Vec<XXXStruct>. Then sorting based on a single field can be implemented through sort_by and sort_by_key methods.

We might be able to use the permutation crate here (although adding external dependencies in a proc-macro is tricky. The crate should be added as a dependency of soa-derive, and soa-derive-internal should generate calls to soa_derive::permutations).

I think we should be able generate code that looks like this, making sure StructRef implements PartialOrd

fn sort(&mut self) {
    use soa_derive::Permutation;

    let mut permutation: Vec<usize> = (0..self.len()).collect();
    permutation.sort_by_key(|i| self.index(i));
    
    let permutation = Permutation::oneline(permutation);
    permutation.apply_slice_in_place(&mut self.bar);
    permutation.apply_slice_in_place(&mut self.baz);
}

[Christopher-S-25]

After some experimentation, I found that HRTB works perfectly for this (code includes minor corrections):

impl<'a> FooSliceMut<'a>
where
    for<'b> FooRef<'b>: Ord,
{
    fn sort(&mut self) {
        use soa_derive::Permutation;
    
        let mut permutation: Vec<usize> = (0..self.len()).collect();

        // the trait `SoAIndex<FooSlice<'_>>` is not implemented for `&usize`,
        // but it is implemented for `usize`, so we dereference `i`
        permutation.sort_by_key(|i| self.index(*i));
        
        // We need to invert the permutation in order to sort the slices correctly
        let mut permutation = Permutation::oneline(permutation).inverse();
        permutation.apply_slice_in_place(&mut self.bar);
        permutation.apply_slice_in_place(&mut self.baz);
    }

    // ... Other sorting methods ...
}

Since sort_by_key() requires FooRef to implement Ord, it should be easy enough to obtain the sorting methods by using this attribute: #[soa_attr(Ref, derive(Ord, PartialOrd, Eq, PartialEq))], or by manually implementing (some of) the traits for more complex cases.

I will try to convert it to macro code, and create a PR.