fluffl 0.0.5

A cross-platform multimedia layer that exposes opengl,sockets,and audio utilities for desktop and browser
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

use super::*;

pub fn quick_co_sort<const N: usize, T>(list: &mut [T], mut co_lists: [&mut dyn CanSwap; N])
where
    T: PartialOrd + Copy,
{
    // let list_ptr = list as *mut [T];
    let co_lists_ptr = &mut co_lists as *mut [&mut dyn CanSwap; N];

    quick_sort(0, list.len(), list, move |(a, b)| {
        let co_lists = unsafe { &mut *co_lists_ptr };
        // let list = unsafe { &*list_ptr };
        for colist in co_lists.iter_mut() {
            colist.ext_swap(a, b);
            // println!("Swappable {{ array: {:?}", list);
            // colist.print();
        }
    });
}

fn quick_sort<T, SWAP>(lbound: usize, ubound: usize, list: &mut [T], my_swap: SWAP)
where
    T: PartialOrd + Copy,
    SWAP: FnMut((usize, usize)) + Copy,
{
    if (ubound - lbound) < 2 {
        return;
    }

    let split_idx = partition(lbound, ubound, list, my_swap);
    quick_sort(lbound, split_idx, list, my_swap);
    quick_sort(split_idx + 1, ubound, list, my_swap);
}

fn partition<T, SWAP>(lbound: usize, ubound: usize, list: &mut [T], mut my_swap: SWAP) -> usize
where
    T: PartialOrd + Copy,
    SWAP: FnMut((usize, usize)),
{
    let mut wall_pos = lbound + 1;
    let wall_val = list[lbound];

    for idx in lbound + 1..ubound {
        let val = list[idx];
        if val < wall_val {
            list.swap(wall_pos, idx);
            my_swap((wall_pos, idx));

            wall_pos += 1;
        }
    }

    list.swap(wall_pos - 1, lbound);
    my_swap((wall_pos - 1, lbound));

    wall_pos - 1
}

#[test]
fn partition_sanity() {
    let mut test = vec![3, 1, 2, 6];
    let split_idx = partition(0, test.len(), &mut test, |_| ());
    assert_eq!(split_idx, 2);
    assert_eq!(vec![2, 1, 3, 6], test);

    let mut test = vec![-10, 2, 5, 11];
    let split_idx = partition(0, test.len(), &mut test, |_| ());
    assert_eq!(split_idx, 0);
    assert_eq!(vec![-10, 2, 5, 11], test);
}

#[test]
fn partition_complex() {
    let mut test = vec![9, -3, 100, 2, 1, -10, 15];
    let pivot = partition(0, test.len(), &mut test, |_| ());
    println!("{:?}", test);
    println!("pivot = {}", pivot);
}

#[test]
fn quick_sort_sanity() {
    let mut test = vec![9i32, 3, 100, 2, 1, 10, 15];
    let mut co_test = vec![-9i32, -3, -100, -2, -1, -10, -15];
    quick_co_sort(&mut test, [&mut Swappable::new(&mut co_test)]);

    assert_eq!(
        test.len(),
        co_test.len(),
        "both arrays should be equal in length"
    );

    assert!(
        test.iter()
            .zip(co_test.iter())
            .all(|(&a, &b)| a.abs() == b.abs()),
        "test and co_test should have the same magnitude"
    );

    assert!(
        test.windows(2).all(|window| window[0] < window[1]),
        "test should be sorted"
    );

    assert!(
        test.iter()
            .zip(co_test.iter())
            .all(|(&a, &b)| a.abs() == b.abs()),
        "test and co_test should have the same magnitude after sort"
    );

}