Move stuff around

2 files changed, 223 insertions, 0 deletions

diff --git a/kattis-kth/alginda-quicksort/src/main.rs b/kattis-kth/alginda-quicksort/src/main.rs
new file mode 100644
index 0000000..afb23f7
--- /dev/null
+++ b/kattis-kth/alginda-quicksort/src/main.rs
@@ -0,0 +1,72 @@
+// https://kth.kattis.com/problems/kth.alginda.quicksort
+
+#![feature(test)]
+
+use std::io::{stdin, stdout, Read, Write};
+
+mod radix_sort;
+use radix_sort::radix_sort;
+
+fn main() {
+    let mut buffer = String::new();
+    stdin().lock().read_to_string(&mut buffer).unwrap();
+    let mut p = buffer.bytes();
+    let mut n = 0;
+    while let Some(b) = p.next() {
+        if b == b' ' {
+            break;
+        }
+        n *= 10;
+        n += (b - b'0') as usize;
+    }
+    let mut xs = vec![0; n];
+    for i in 0..n {
+        let mut neg = false;
+        let mut x = 0i32;
+        while let Some(b) = p.next() {
+            match b {
+                b' ' | b'\n' => break,
+                b'-' => neg = true,
+                b => {
+                    x *= 10;
+                    x += (b - b'0') as i32;
+                }
+            }
+        }
+        if neg {
+            x = -x;
+        }
+        xs[i] = x;
+    }
+
+    radix_sort(&mut xs);
+
+    let mut p = buffer.len() - 1;
+    let b = unsafe { buffer.as_mut_vec() };
+    b[p] = b'\n';
+    p -= 1;
+    for i in (0..n).rev() {
+        let x = xs[i];
+        let neg = x < 0;
+        let mut x = if neg { (-x) as u32 } else { x as u32 };
+        loop {
+            b[p] = (x % 10) as u8 + b'0';
+            p -= 1;
+            x /= 10;
+            if x == 0 {
+                break;
+            }
+        }
+        if neg {
+            b[p] = b'-';
+            p -= 1;
+        }
+        if i > 0 {
+            b[p] = b'\n';
+            p -= 1;
+        }
+    }
+    p += 1;
+
+    stdout().lock().write(&b[p..]).unwrap();
+}
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);
+        });
+    }
+}