Sort Permutation

sort_permutation.rs

fn main(){

    // let list = ["zabc", "ghjjklhgkj", "kgjgfhfgdg", "zabcd", "hghfgft", "afsbdgshng"];
    let mut list = [3,6,2,1];
    let mut list_ = [3,6,2,1];
    let mut other_list = *b"abcd";
    let mut other_list_ = *b"abcd";
    let mut perm = Vec::new();
    let mut perm_perm = Vec::new();
    let mut perm_perm_perm = Vec::new();

    sort_permutation(&list, &mut perm);
    println!("{:?}", perm);                     // positions declaring where values should come from
    sort_permutation(&perm, &mut perm_perm);
    println!("{:?}", perm_perm);                // values declaring where the belong/should go

    sort_permutation(&perm_perm, &mut perm_perm_perm);
    core::assert_eq!(perm,perm_perm_perm);

    println!();

    apply_permute(&mut list, &mut perm);
    apply_permute(&mut other_list, &mut perm);

    apply_permute(&mut list_, &mut perm_perm);
    apply_permute(&mut other_list_, &mut perm_perm);

    println!("perm   : {:?}", perm);
    println!("list   : {:?}", list);
    println!("o_list :{:?}", other_list);
    println!();
    println!("p_perm : {:?}", perm_perm);
    println!("list   : {:?}", list_);
    println!("o_list : {:?}", other_list_);

    


}


fn sort_permutation<T:Ord>(src : &[T], out : &mut Vec<usize>){
    out.clear();
    out.reserve(src.len());
    out.extend(0..src.len());
    out.sort_by_key(|k| &src[*k]);
}

fn apply_permute<T>(arr :  &mut [T], perm : &mut [usize]) {
    core::assert_eq!(arr.len(), perm.len());
    core::assert!(arr.len() < usize::MAX/2);
    
    for i in 0..arr.len() {
        let mut prev = i;
        let mut next = perm[i];
        if next >= perm.len() { continue; }

        while next != i {
            arr.swap(next, prev);
            prev = next;
            next = perm[next];
            perm[prev] ^= !0;
        }
        perm[next] ^= !0;

    }
    for each in perm {
        *each ^= !0;
    }
}

// // Zig https://github.com/jakubDoka
// pub fn applyPermuteNoJunk(comptime T: type, vec: []T, perm: []usize) void {
//     for (0..) |i| {
//         var prev = i;
//         var next = perm[i];
//         if (next == perm.len) continue;
//         while (next != i) {
//             std.mem.swap(T, &vec[next], &vec[prev]);
//             prev = next;
//             next = perm[next];
//             perm[prev] = perm.len;
//         }
//     }
// }