1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#![feature(test)]
#![feature(const_fn)]

extern crate test;
extern crate rand;
extern crate num;
pub mod tests;
use num::pow;

/// Items will be sorted based on the values returned by this trait
pub trait Indexed {
    fn get_index(&self) -> u64;
}

/// Sorts [source] and yield results in a new vector
pub fn sort<T: Clone + Default + Indexed> (source:&Vec<T>) -> Vec<T> {
    let radix = 8;
    let steps = (64 / radix) as usize;
    let buckets:usize = pow(2, radix);
    let mask:u64 = (buckets - 1) as u64;
    let mut shift:usize = 0;
    let mut bucket_sums = vec![0usize; buckets];
    let mut bucket_counts = vec![0usize; buckets];

    let count = source.len();
    let mut buffers = [Some(source.clone()), Some(vec![Default::default(); count])];
    for step in 0..steps {
        let (source, workspace) = {
            let mut iter = buffers.iter_mut();
            let b0 = iter.next().unwrap();
            let b1 = iter.next().unwrap();
            if step % 2 == 0 {
                (b0.as_ref().unwrap(), b1.as_mut().unwrap())
            } else {
                (b1.as_ref().unwrap(), b0.as_mut().unwrap())
            }
        };

        if step > 0 {
            for bucket in &mut bucket_counts {
                *bucket = 0;
            }
        }

        for entry in source.iter() {
            let code = entry.get_index();
            let idx = (code >> shift & mask) as usize;
            bucket_counts[idx] += 1;
        }

        bucket_sums[0] = 0;
        for i in 1..buckets {
            bucket_sums[i] = bucket_sums[i - 1] + bucket_counts[i - 1];
        }

        for entry in source.iter() {
            let entry = entry.clone();
            let code = entry.get_index();
            let idx = (code >> shift & mask) as usize;
            let sum = bucket_sums[idx];
            workspace[sum] = entry;
            bucket_sums[idx] = sum + 1;
        }

        shift = shift + radix;
    }

    buffers[steps % 2].take().unwrap()
}