i_key_sort 0.10.1

Counting sort algorithm.
Documentation 
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

use crate::sort::key::{KeyFn, SortKey};
use crate::sort::min_max::MinMax;

#[derive(Debug, Clone)]
pub(crate) struct BinLayout<K> {
    pub(crate) min_key: K,
    pub(crate) max_key: K,
    pub(crate) power: usize,
    bin_width_is_one: bool,
}

pub(crate) const BIN_SORT_MIN: usize = 64;
pub(crate) const MAX_BINS_POWER: u32 = 8;

pub(crate) const MAX_BINS_COUNT: usize = 1 << MAX_BINS_POWER;

impl<K: SortKey> BinLayout<K> {
    #[inline(always)]
    pub(super) fn bin_width_is_one(&self) -> bool {
        self.bin_width_is_one
    }

    #[inline(always)]
    pub fn index(&self, value: K) -> usize {
        debug_assert!(value >= self.min_key, "value must be >= min_key");
        let offset = value.difference(self.min_key);
        offset >> self.power
    }

    #[inline(always)]
    pub fn count(&self) -> usize {
        self.index(self.max_key) + 1
    }

    #[inline(always)]
    pub(crate) fn new(min_key: K, max_key: K, max_bins_count: usize) -> BinLayout<K> {
        let length = max_key.difference(min_key);
        if length < max_bins_count {
            return Self {
                min_key,
                max_key,
                power: 0,
                bin_width_is_one: true,
            };
        }

        let scale = length.saturating_add(1).ilog2_ceil();
        let power = scale.saturating_sub(max_bins_count.ilog2()) as usize;

        Self {
            min_key,
            max_key,
            power,
            bin_width_is_one: false,
        }
    }

    #[inline(always)]
    pub fn with_keys<T, F: KeyFn<T, K>>(array: &[T], key: F) -> Option<Self> {
        if array.is_empty() {
            return None;
        }

        let (min_key, max_key) = array.min_max(key);

        if min_key == max_key {
            return None;
        }

        Some(Self::new(min_key, max_key, MAX_BINS_COUNT))
    }
}

trait Log2 {
    fn ilog2_ceil(&self) -> u32;
}

impl Log2 for usize {
    #[inline(always)]
    fn ilog2_ceil(&self) -> u32 {
        let floor = self.ilog2();
        if self.is_power_of_two() {
            floor
        } else {
            floor + 1
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::sort::bin_layout::{BinLayout, Log2, MAX_BINS_COUNT};

    #[test]
    fn test_0() {
        let layout = BinLayout::<i32>::new(0i32, 3i32, MAX_BINS_COUNT);
        assert_eq!(layout.power, 0);
    }

    #[test]
    fn test_1() {
        let layout = BinLayout::<i32>::new(0, 255, MAX_BINS_COUNT);

        assert_eq!(layout.power, 0);
    }

    #[test]
    fn test_2() {
        let layout = BinLayout::<i32>::new(0, 256, MAX_BINS_COUNT);

        assert_eq!(layout.power, 1);
    }

    #[test]
    fn test_log2_0() {
        assert_eq!(1usize.ilog2_ceil(), 0);
        assert_eq!(2usize.ilog2_ceil(), 1);
        assert_eq!(3usize.ilog2_ceil(), 2);
        assert_eq!(4usize.ilog2_ceil(), 2);
        assert_eq!(5usize.ilog2_ceil(), 3);
    }
}