radix_sort.rs

#!/usr/bin/env run-cargo-script

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;

macro_rules! array {
    [$x: tt; $n: tt] => {array!(@go ($n, $x) -> ())};
    (@end $x: tt) => {$x};
    (@go (1, $($x: tt), *) -> ($($xs: tt)*)) => {array!(@end [$($x,)* $($xs)*]) };
    (@go (2, $($x: tt), *) -> ($($xs: tt)*)) => {array!(@go (1, $($x), *) -> ($($x,)* $($xs)*))};
    (@go (3, $($x: tt), *) -> ($($xs: tt)*)) => {array!(@go (2, $($x), *) -> ($($x,)* $($xs)*))};
    (@go (6, $($x: tt), *) -> ($($xs: tt)*)) => {array!(@go (3, $($x,)* $($x), *) -> ($($xs)*))};
    (@go (12, $($x: tt), *) -> ($($xs: tt)*)) => {array!(@go (6, $($x,)* $($x), *) -> ($($xs)*))};
    (@go (24, $($x: tt), *) -> ($($xs: tt)*)) => {array!(@go (12, $($x,)* $($x), *) -> ($($xs)*))};
    (@go (25, $($x: tt), *) -> ($($xs: tt)*)) => {array!(@go (24, $($x), *) -> ($($x,)* $($xs)*))};
    (@go (50, $($x: tt), *) -> ($($xs: tt)*)) => {array!(@go (25, $($x,)* $($x), *) -> ($($xs)*))};
    (@go (100, $($x: tt), *) -> ($($xs: tt)*)) => {array!(@go (50, $($x,)* $($x), *) -> ($($xs)*))};
}


fn main() {
    let mut sc = Scanner::new();
    let n = sc.parse();
    let a = sc.vec(n);
    for x in solve(a) {
        println!("{}", x);
    }
}


fn solve(mut a: Vec<u32>) -> Vec<u32> {
    for &x in a.iter() {
        assert!(1 <= x && x <= 100000000);
    }
    a.radix_sort();
    a
}


trait RadixSort {
    fn radix_sort(&mut self);
}

impl RadixSort for [u32] {
    fn radix_sort(&mut self) {
        let buckets_a = array![{ Vec::with_capacity(100) }; 100];
        let buckets_b = array![{ Vec::with_capacity(100) }; 100];
        let mut buckets1 = buckets_a;

        for &x in self.iter() {
            buckets1[(x - 1) as usize % 100].push(x);
        }

        let mut buckets2 = buckets_b;
        for v in buckets1.iter() {
            for &x in v {
                buckets2[((x - 1) / 100) as usize % 100].push(x);
            }
        }

        let mut buckets3 = buckets1;
        for v in buckets3.iter_mut() {
            v.clear();
        }
        for v in buckets2.iter() {
            for &x in v {
                buckets3[((x - 1) / 10000) as usize % 100].push(x);
            }
        }

        let mut buckets4 = buckets2;
        for v in buckets4.iter_mut() {
            v.clear();
        }
        for v in buckets3.iter() {
            for &x in v {
                buckets4[((x - 1) / 1000000) as usize % 100].push(x);
            }
        }

        let mut i = 0;
        for v in buckets4.iter() {
            for &x in v {
                self[i] = x;
                i += 1;
            }
        }
    }
}


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

    #[test]
    fn test() {
        let a = vec![1000000, 23, 323, 382, 2010, 30204, 302, 5982, 3877779, 3292, 9328829];
        assert_sorted(solve(a));
    }

    fn assert_sorted(a: Vec<u32>) {
        let mut x = a[0];
        for &e in a.iter() {
            assert!(x <= e);
            x = e;
        }
    }
}



struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }

    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T>
        where <T as FromStr>::Err: Debug
    {
        (0..n).map(|_| self.parse()).collect()
    }
}