wasm_quicksort_example/
lib.rs

1mod utils;
2
3use serde::{Deserialize, Serialize};
4use serde_json::{from_str, to_string};
5use tsify::Tsify;
6use wasm_bindgen::prelude::*;
7
8// This section is glue between JS and Rust:
9
10// This will be the shared type between JS and Rust.
11// This is the type that JSON will be deserailized into on the Rust side.
12// It will also generate a Typescript type exposed by the JS libraries.
13#[derive(Clone, Deserialize, Serialize, Tsify)]
14#[tsify(into_wasm_abi, from_wasm_abi)]
15#[serde(untagged)]
16pub enum Sortable {
17    Strings(Vec<String>),
18    Numbers(Vec<f64>),
19}
20
21// This will treat the destination type (Sortable) generically.
22fn quicksort_interface(s: Sortable) -> Sortable {
23    match s {
24        Sortable::Strings(mut v) => {
25            qsort(&mut v);
26            Sortable::Strings(v)
27        }
28        Sortable::Numbers(mut v) => {
29            qsort(&mut v);
30            Sortable::Numbers(v)
31        }
32    }
33}
34
35// Other than Sortable's type definition, this is the only thing exposed
36// to the consuming libraries.
37// The lack of typing at the argument level is hidden behind the better
38// typing of the JavaScript wrapper -- see quicksort_wrapper.ts
39#[wasm_bindgen]
40pub fn quicksort(vec: String) -> Result<JsValue, JsError> {
41    let vec: Sortable = from_str(&vec).map_err(|e| JsError::new(&format!("{}", e)))?;
42    let res = to_string(&quicksort_interface(vec)).map_err(|e| JsError::new(&format!("{}", e)))?;
43    Ok(res.into())
44}
45
46// This section is the actual implementation in Rust terms.
47
48// The next three functions are a tiny modification to the implementation found here:
49// https://www.hackertouch.com/quick-sort-in-rust.html
50fn qsort<T: PartialEq + PartialOrd>(arr: &mut [T]) {
51    let len = arr.len();
52    _quicksort(arr, 0, (len - 1) as isize);
53}
54
55fn _quicksort<T: PartialEq + PartialOrd>(arr: &mut [T], low: isize, high: isize) {
56    if low < high {
57        let p = partition(arr, low, high);
58        _quicksort(arr, low, p - 1);
59        _quicksort(arr, p + 1, high);
60    }
61}
62
63fn partition<T: PartialEq + PartialOrd>(arr: &mut [T], low: isize, high: isize) -> isize {
64    let pivot = high as usize;
65    let mut store_index = low - 1;
66    let mut last_index = high;
67
68    loop {
69        store_index += 1;
70        while arr[store_index as usize] < arr[pivot] {
71            store_index += 1;
72        }
73        last_index -= 1;
74        while last_index >= 0 && arr[last_index as usize] > arr[pivot] {
75            last_index -= 1;
76        }
77        if store_index >= last_index {
78            break;
79        } else {
80            arr.swap(store_index as usize, last_index as usize);
81        }
82    }
83    arr.swap(store_index as usize, pivot);
84    store_index
85}
86
87#[cfg(test)]
88mod tests {
89    use super::*;
90
91    #[test]
92    fn test_qsort() {
93        let expected = vec![
94            "A".to_string(),
95            "B".to_string(),
96            "C".to_string(),
97            "D".to_string(),
98        ];
99
100        let mut unsort1 = vec![
101            "B".to_string(),
102            "A".to_string(),
103            "C".to_string(),
104            "D".to_string(),
105        ];
106
107        let mut unsort2 = vec![
108            "D".to_string(),
109            "C".to_string(),
110            "B".to_string(),
111            "A".to_string(),
112        ];
113
114        let mut unsort3 = vec![
115            "C".to_string(),
116            "B".to_string(),
117            "D".to_string(),
118            "A".to_string(),
119        ];
120
121        // sanity check:
122        assert_eq!(&expected, &expected);
123        assert_ne!(&expected, &unsort1);
124        assert_ne!(&expected, &unsort2);
125        assert_ne!(&expected, &unsort3);
126
127        qsort(&mut unsort1);
128        qsort(&mut unsort2);
129        qsort(&mut unsort3);
130
131        assert_eq!(&expected, &unsort1);
132        assert_eq!(&expected, &unsort2);
133        assert_eq!(&expected, &unsort3);
134
135        let expected = [1, 2, 3];
136        let mut unsort1 = [3, 2, 1];
137        let mut unsort2 = [2, 3, 1];
138
139        // sanity check:
140        assert_eq!(&expected, &expected);
141        assert_ne!(&expected, &unsort1);
142        assert_ne!(&expected, &unsort2);
143
144        qsort(&mut unsort1);
145        qsort(&mut unsort2);
146
147        assert_eq!(&expected, &unsort1);
148        assert_eq!(&expected, &unsort2);
149    }
150}
wasm_quicksort_example/lib.rs

wasm_quicksort_example/
lib.rs
