From a1eb38bebe6ce1668c3f96489506c3b05b9fe5cb Mon Sep 17 00:00:00 2001
From: mathiasmagnusson <mathiasmagnussons@gmail.com>
Date: Fri, 9 Dec 2022 18:00:41 +0100
Subject: Move stuff around

---
 kattis-kth/alginda-quicksort/src/radix_sort.rs | 151 +++++++++++++++++++++++++
 1 file changed, 151 insertions(+)
 create mode 100644 kattis-kth/alginda-quicksort/src/radix_sort.rs

(limited to 'kattis-kth/alginda-quicksort/src/radix_sort.rs')

diff --git a/kattis-kth/alginda-quicksort/src/radix_sort.rs b/kattis-kth/alginda-quicksort/src/radix_sort.rs
new file mode 100644
index 0000000..2f8d32a
--- /dev/null
+++ b/kattis-kth/alginda-quicksort/src/radix_sort.rs
@@ -0,0 +1,151 @@
+use std::mem;
+
+pub trait RadixFilters: 'static {
+    const FILTERS: &'static [fn(&Self) -> u8];
+}
+
+impl RadixFilters for u32 {
+    const FILTERS: &'static [fn(&Self) -> u8] = &[
+        |x| ((x & 0x000000ff) >> (8 * 0)) as _,
+        |x| ((x & 0x0000ff00) >> (8 * 1)) as _,
+        |x| ((x & 0x00ff0000) >> (8 * 2)) as _,
+        |x| ((x & 0xff000000) >> (8 * 3)) as _,
+    ];
+}
+
+impl RadixFilters for i32 {
+    const FILTERS: &'static [fn(&Self) -> u8] = &[
+        |x| ((x & 0x000000ff) >> (8 * 0)) as _,
+        |x| ((x & 0x0000ff00) >> (8 * 1)) as _,
+        |x| ((x & 0x00ff0000) >> (8 * 2)) as _,
+        |x| (((x & 0xff000000u32 as i32) ^ (1 << 31)) >> (8 * 3)) as _,
+    ];
+}
+
+impl RadixFilters for u64 {
+    const FILTERS: &'static [fn(&Self) -> u8] = &[
+        |x| ((x & 0x00000000000000ff) >> (8 * 0)) as _,
+        |x| ((x & 0x000000000000ff00) >> (8 * 1)) as _,
+        |x| ((x & 0x0000000000ff0000) >> (8 * 2)) as _,
+        |x| ((x & 0x00000000ff000000) >> (8 * 3)) as _,
+        |x| ((x & 0x000000ff00000000) >> (8 * 4)) as _,
+        |x| ((x & 0x0000ff0000000000) >> (8 * 5)) as _,
+        |x| ((x & 0x00ff000000000000) >> (8 * 6)) as _,
+        |x| ((x & 0xff00000000000000) >> (8 * 7)) as _,
+    ];
+}
+
+pub fn radix_sort_with<T>(xs: &mut [T], temp: &mut [T])
+where
+    T: Default + Copy + Clone + RadixFilters,
+{
+    // The first thing that happens it that these two are swapped so thats why this seems backwards
+    let mut output = xs;
+    let mut input = temp;
+    debug_assert!(T::FILTERS.len() % 2 == 0);
+    for f in T::FILTERS {
+        mem::swap(&mut input, &mut output);
+
+        let mut counts = [0; 256];
+        for x in input.iter() {
+            counts[f(x) as usize] += 1;
+        }
+        let mut sum = 0;
+        for c in &mut counts {
+            sum += *c;
+            *c = sum;
+        }
+        for x in input.iter_mut().rev() {
+            let fx = f(x) as usize;
+            counts[fx] -= 1;
+            output[counts[fx]] = *x;
+        }
+    }
+}
+
+pub fn radix_sort<T>(xs: &mut [T])
+where
+    T: Default + Copy + Clone + RadixFilters,
+{
+    let n = xs.len();
+    radix_sort_with(xs, vec![Default::default(); n].as_mut_slice());
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn basic_rand() {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let mut xs: Vec<u32> = (0..1_000_000).map(|_| r.next_u32()).collect();
+
+        radix_sort(&mut xs);
+        for w in xs.as_slice().windows(2) {
+            assert!(w[0] <= w[1]);
+        }
+    }
+
+    #[test]
+    fn negatives() {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let mut xs: Vec<i32> = (0..1_000_000).map(|_| r.next_u32() as i32).collect();
+
+        radix_sort(&mut xs);
+        for w in xs.as_slice().windows(2) {
+            assert!(w[0] <= w[1], "{} <= {}", w[0], w[1]);
+        }
+    }
+
+    extern crate test;
+    use rand::RngCore;
+    use test::{black_box, Bencher};
+
+    #[bench]
+    fn std_u32_x1e6(b: &mut Bencher) {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let xs: Vec<u32> = (0..1_000_000).map(|_| r.next_u32()).collect();
+
+        b.iter(|| {
+            let mut xs = black_box(xs.clone());
+            xs.sort();
+            black_box(xs);
+        });
+    }
+
+    #[bench]
+    fn radix_u32_x1e6(b: &mut Bencher) {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let xs: Vec<u32> = (0..1_000_000).map(|_| r.next_u32()).collect();
+
+        b.iter(|| {
+            let mut xs = black_box(xs.clone());
+            radix_sort(&mut xs);
+            black_box(xs);
+        });
+    }
+
+    #[bench]
+    fn std_u64_x1e6(b: &mut Bencher) {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let xs: Vec<u64> = (0..1_000_000).map(|_| r.next_u64()).collect();
+
+        b.iter(|| {
+            let mut xs = black_box(xs.clone());
+            xs.sort();
+            black_box(xs);
+        });
+    }
+
+    #[bench]
+    fn radix_u64_x1e6(b: &mut Bencher) {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let xs: Vec<u64> = (0..1_000_000).map(|_| r.next_u64()).collect();
+
+        b.iter(|| {
+            let mut xs = black_box(xs.clone());
+            radix_sort(&mut xs);
+            black_box(xs);
+        });
+    }
+}
-- 
cgit v1.2.3