a/sort/
key.rs

1//! The key types of the sorts that do not compare elements: [`counting`](super::counting),
2//! [`radix`](super::radix) and [`bucket`](super::bucket) sort.
3
4/// A key the sorts that do not compare elements can sort by: a primitive integer, `char` or
5/// `bool`.
6///
7/// It is sealed: it cannot be implemented outside this crate.
8pub trait IntegerKey: sealed::Key {}
9
10/// A key bucket sort can sort by: a primitive integer, `char`, `bool`, `f32` or `f64`.
11///
12/// Floats are ordered as [`f64::total_cmp`] orders them: negative NaNs, −∞, the negative
13/// numbers, −0, +0, the positive numbers, +∞, positive NaNs.
14///
15/// It is sealed: it cannot be implemented outside this crate.
16pub trait BucketKey: sealed::Bucket {}
17
18pub(super) mod sealed {
19    /// What the sorts need to know about a key type.
20    pub trait Key: Copy + Ord {
21        /// The key as an unsigned integer of the same width that orders as the key does; as a
22        /// key itself, it is its own bits.
23        type Bits: Bits + super::IntegerKey;
24        /// The key as [`Self::Bits`]: its bits, with the sign bit flipped for a signed type.
25        fn bits(self) -> Self::Bits;
26        /// `self − min`, for `min <= self`.
27        fn distance(self, min: Self) -> u128;
28        /// `self − min`, for `min <= self` and a distance that fits in `usize`.
29        fn offset(self, min: Self) -> usize;
30        /// `min + offset`, or any value of the type if that is not one.
31        fn nth(min: Self, offset: usize) -> Self;
32    }
33
34    /// An unsigned integer, read as digits of a few bits.
35    pub trait Bits: Copy + Ord {
36        const ZERO: Self;
37        /// The width in bits.
38        const BITS: u32;
39        fn or(self, other: Self) -> Self;
40        fn xor(self, other: Self) -> Self;
41        fn leading_zeros(self) -> u32;
42        fn trailing_zeros(self) -> u32;
43        /// The bits from `shift` on, masked by `mask`.
44        fn digit(self, shift: u32, mask: usize) -> usize;
45        /// `n`, which is less than `2^BITS`.
46        fn of(n: usize) -> Self;
47        fn wrapping_sub(self, other: Self) -> Self;
48        fn shr(self, shift: u32) -> Self;
49        /// The low 64 bits.
50        fn low64(self) -> u64;
51    }
52
53    /// What bucket sort needs to know about a key type.
54    pub trait Bucket: Copy {
55        /// The key as an unsigned integer of the same size and alignment that orders as the key
56        /// does.
57        type Bits: Bits + super::IntegerKey;
58        /// Whether a key's bytes, read as [`Self::Bits`], already are [`Self::ordered`].
59        const IDENTITY: bool;
60        /// Whether the key is a float, whose buckets are cut by value.
61        const FLOAT: bool;
62        /// The key as [`Self::Bits`].
63        fn ordered(self) -> Self::Bits;
64        /// The key whose [`Self::ordered`] bits are `bits`.
65        fn from_ordered(bits: Self::Bits) -> Self;
66        /// The value of the float whose [`Self::ordered`] bits are `bits`; `0.0` for other keys.
67        fn value(bits: Self::Bits) -> f64;
68        /// [`Self::value`] as an `f32`, exact for an `f32` key.
69        fn value32(bits: Self::Bits) -> f32;
70    }
71}
72
73macro_rules! bits {
74    ($($u:ty),*) => {$(
75        impl sealed::Bits for $u {
76            const ZERO: Self = 0;
77            const BITS: u32 = <$u>::BITS;
78            #[inline(always)]
79            fn or(self, other: Self) -> Self {
80                self | other
81            }
82            #[inline(always)]
83            fn xor(self, other: Self) -> Self {
84                self ^ other
85            }
86            #[inline(always)]
87            fn leading_zeros(self) -> u32 {
88                <$u>::leading_zeros(self)
89            }
90            #[inline(always)]
91            fn trailing_zeros(self) -> u32 {
92                <$u>::trailing_zeros(self)
93            }
94            #[inline(always)]
95            fn digit(self, shift: u32, mask: usize) -> usize {
96                (self >> shift) as usize & mask
97            }
98            #[inline(always)]
99            fn of(n: usize) -> Self {
100                n as $u
101            }
102            #[inline(always)]
103            fn wrapping_sub(self, other: Self) -> Self {
104                <$u>::wrapping_sub(self, other)
105            }
106            #[inline(always)]
107            fn shr(self, shift: u32) -> Self {
108                self >> shift
109            }
110            #[inline(always)]
111            fn low64(self) -> u64 {
112                self as u64
113            }
114        }
115    )*};
116}
117
118bits!(u8, u16, u32, u64, u128, usize);
119
120macro_rules! integer_key {
121    ($($t:ty => $u:ty, $sign:expr);* $(;)?) => {$(
122        impl sealed::Key for $t {
123            type Bits = $u;
124            #[inline(always)]
125            fn bits(self) -> $u {
126                (self as $u) ^ $sign
127            }
128            #[inline(always)]
129            fn distance(self, min: Self) -> u128 {
130                (self as $u).wrapping_sub(min as $u) as u128
131            }
132            #[inline(always)]
133            fn offset(self, min: Self) -> usize {
134                (self as $u).wrapping_sub(min as $u) as usize
135            }
136            #[inline(always)]
137            fn nth(min: Self, offset: usize) -> Self {
138                (min as $u).wrapping_add(offset as $u) as $t
139            }
140        }
141        impl IntegerKey for $t {}
142        impl sealed::Bucket for $t {
143            type Bits = $u;
144            const IDENTITY: bool = {
145                let sign: $u = $sign;
146                sign == 0
147            };
148            const FLOAT: bool = false;
149            #[inline(always)]
150            fn ordered(self) -> $u {
151                sealed::Key::bits(self)
152            }
153            #[inline(always)]
154            fn from_ordered(bits: $u) -> Self {
155                (bits ^ $sign) as $t
156            }
157            #[inline(always)]
158            fn value(_: $u) -> f64 {
159                0.0
160            }
161            #[inline(always)]
162            fn value32(_: $u) -> f32 {
163                0.0
164            }
165        }
166        impl BucketKey for $t {}
167    )*};
168}
169
170integer_key! {
171    u8 => u8, 0; u16 => u16, 0; u32 => u32, 0; u64 => u64, 0; u128 => u128, 0;
172    usize => usize, 0;
173    i8 => u8, 1 << 7; i16 => u16, 1 << 15; i32 => u32, 1 << 31; i64 => u64, 1 << 63;
174    i128 => u128, 1 << 127; isize => usize, 1 << (usize::BITS - 1);
175}
176
177impl sealed::Key for char {
178    type Bits = u32;
179    #[inline(always)]
180    fn bits(self) -> u32 {
181        self as u32
182    }
183    #[inline(always)]
184    fn distance(self, min: Self) -> u128 {
185        u128::from(self as u32 - min as u32)
186    }
187    #[inline(always)]
188    fn offset(self, min: Self) -> usize {
189        (self as u32).wrapping_sub(min as u32) as usize
190    }
191    #[inline(always)]
192    fn nth(min: Self, offset: usize) -> Self {
193        // An offset into the surrogates, which no element has, gives `min`.
194        char::from_u32((min as u32).wrapping_add(offset as u32)).unwrap_or(min)
195    }
196}
197impl IntegerKey for char {}
198
199impl sealed::Bucket for char {
200    type Bits = u32;
201    const IDENTITY: bool = true;
202    const FLOAT: bool = false;
203    #[inline(always)]
204    fn ordered(self) -> u32 {
205        self as u32
206    }
207    #[inline(always)]
208    fn from_ordered(bits: u32) -> Self {
209        char::from_u32(bits).unwrap_or_default()
210    }
211    #[inline(always)]
212    fn value(_: u32) -> f64 {
213        0.0
214    }
215    #[inline(always)]
216    fn value32(_: u32) -> f32 {
217        0.0
218    }
219}
220impl BucketKey for char {}
221
222impl sealed::Key for bool {
223    type Bits = u8;
224    #[inline(always)]
225    fn bits(self) -> u8 {
226        self as u8
227    }
228    #[inline(always)]
229    fn distance(self, min: Self) -> u128 {
230        u128::from(self as u8 - min as u8)
231    }
232    #[inline(always)]
233    fn offset(self, min: Self) -> usize {
234        usize::from(self).wrapping_sub(usize::from(min))
235    }
236    #[inline(always)]
237    fn nth(min: Self, offset: usize) -> Self {
238        usize::from(min) + offset != 0
239    }
240}
241impl IntegerKey for bool {}
242
243impl sealed::Bucket for bool {
244    type Bits = u8;
245    const IDENTITY: bool = true;
246    const FLOAT: bool = false;
247    #[inline(always)]
248    fn ordered(self) -> u8 {
249        self as u8
250    }
251    #[inline(always)]
252    fn from_ordered(bits: u8) -> Self {
253        bits != 0
254    }
255    #[inline(always)]
256    fn value(_: u8) -> f64 {
257        0.0
258    }
259    #[inline(always)]
260    fn value32(_: u8) -> f32 {
261        0.0
262    }
263}
264impl BucketKey for bool {}
265
266macro_rules! float_key {
267    ($($f:ty => $u:ty, $i:ty);* $(;)?) => {$(
268        impl sealed::Bucket for $f {
269            type Bits = $u;
270            const IDENTITY: bool = false;
271            const FLOAT: bool = true;
272            /// The bits with the sign bit flipped for a positive float and every bit flipped for
273            /// a negative one, which order as [`f64::total_cmp`] does.
274            #[inline(always)]
275            fn ordered(self) -> $u {
276                let u = self.to_bits();
277                u ^ ((((u as $i) >> (<$u>::BITS - 1)) as $u) | (1 << (<$u>::BITS - 1)))
278            }
279            #[inline(always)]
280            fn from_ordered(bits: $u) -> Self {
281                let flip = ((((!bits) as $i) >> (<$u>::BITS - 1)) as $u) | (1 << (<$u>::BITS - 1));
282                <$f>::from_bits(bits ^ flip)
283            }
284            #[inline(always)]
285            fn value(bits: $u) -> f64 {
286                f64::from(<Self as sealed::Bucket>::from_ordered(bits))
287            }
288            #[inline(always)]
289            fn value32(bits: $u) -> f32 {
290                <Self as sealed::Bucket>::from_ordered(bits) as f32
291            }
292        }
293        impl BucketKey for $f {}
294    )*};
295}
296
297float_key! { f32 => u32, i32; f64 => u64, i64 }
a/sort/key.rs

a/sort/
key.rs
