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<T>(xs: Vec<T>) -> Vec<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 = vec![T::default(); output.len()];
    for f in T::FILTERS {
        mem::swap(&mut input, &mut output);

        let mut counts = [0; 256];
        for x in &input {
            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;
        }
    }
    output
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn basic_rand() {
        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
        let xs: Vec<u32> = (0..1_000_000).map(|_| r.next_u32()).collect();

        let xs = radix_sort(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 xs: Vec<i32> = (0..1_000_000).map(|_| r.next_u32() as i32).collect();

        let xs = radix_sort(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 xs = black_box(xs.clone());
            black_box(radix_sort(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 xs = black_box(xs.clone());
            black_box(radix_sort(xs));
        });
    }
}