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 deletions(-)
 delete 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
deleted file mode 100644
index 2f8d32a..0000000
--- a/kattis-kth-alginda-quicksort/src/radix_sort.rs
+++ /dev/null
@@ -1,151 +0,0 @@
-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