Move stuff around

2 files changed, 0 insertions, 223 deletions

diff --git a/kattis-kth-alginda-quicksort/src/main.rs b/kattis-kth-alginda-quicksort/src/main.rs
deleted file mode 100644
index afb23f7..0000000
--- a/kattis-kth-alginda-quicksort/src/main.rs
+++ /dev/null
@@ -1,72 +0,0 @@
-// 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
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);
-        });
-    }
-}