a/sort/
key.rs

1//! The key types of the sorts that do not compare elements: [`counting`](super::counting) and
2//! [`radix`](super::radix) 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
10pub(super) mod sealed {
11    /// What the sorts need to know about a key type.
12    pub trait Key: Copy + Ord {
13        /// The key as an unsigned integer of the same width that orders as the key does; as a
14        /// key itself, it is its own bits.
15        type Bits: Bits + super::IntegerKey;
16        /// The key as [`Self::Bits`]: its bits, with the sign bit flipped for a signed type.
17        fn bits(self) -> Self::Bits;
18        /// `self − min`, for `min <= self`.
19        fn distance(self, min: Self) -> u128;
20        /// `self − min`, for `min <= self` and a distance that fits in `usize`.
21        fn offset(self, min: Self) -> usize;
22        /// `min + offset`, or any value of the type if that is not one.
23        fn nth(min: Self, offset: usize) -> Self;
24    }
25
26    /// An unsigned integer, read as digits of a few bits.
27    pub trait Bits: Copy + Ord {
28        const ZERO: Self;
29        /// The width in bits.
30        const BITS: u32;
31        fn or(self, other: Self) -> Self;
32        fn xor(self, other: Self) -> Self;
33        fn leading_zeros(self) -> u32;
34        fn trailing_zeros(self) -> u32;
35        /// The bits from `shift` on, masked by `mask`.
36        fn digit(self, shift: u32, mask: usize) -> usize;
37        /// `n`, which is less than `2^BITS`.
38        fn of(n: usize) -> Self;
39    }
40}
41
42macro_rules! bits {
43    ($($u:ty),*) => {$(
44        impl sealed::Bits for $u {
45            const ZERO: Self = 0;
46            const BITS: u32 = <$u>::BITS;
47            #[inline(always)]
48            fn or(self, other: Self) -> Self {
49                self | other
50            }
51            #[inline(always)]
52            fn xor(self, other: Self) -> Self {
53                self ^ other
54            }
55            #[inline(always)]
56            fn leading_zeros(self) -> u32 {
57                <$u>::leading_zeros(self)
58            }
59            #[inline(always)]
60            fn trailing_zeros(self) -> u32 {
61                <$u>::trailing_zeros(self)
62            }
63            #[inline(always)]
64            fn digit(self, shift: u32, mask: usize) -> usize {
65                (self >> shift) as usize & mask
66            }
67            #[inline(always)]
68            fn of(n: usize) -> Self {
69                n as $u
70            }
71        }
72    )*};
73}
74
75bits!(u8, u16, u32, u64, u128, usize);
76
77macro_rules! integer_key {
78    ($($t:ty => $u:ty, $sign:expr);* $(;)?) => {$(
79        impl sealed::Key for $t {
80            type Bits = $u;
81            #[inline(always)]
82            fn bits(self) -> $u {
83                (self as $u) ^ $sign
84            }
85            #[inline(always)]
86            fn distance(self, min: Self) -> u128 {
87                (self as $u).wrapping_sub(min as $u) as u128
88            }
89            #[inline(always)]
90            fn offset(self, min: Self) -> usize {
91                (self as $u).wrapping_sub(min as $u) as usize
92            }
93            #[inline(always)]
94            fn nth(min: Self, offset: usize) -> Self {
95                (min as $u).wrapping_add(offset as $u) as $t
96            }
97        }
98        impl IntegerKey for $t {}
99    )*};
100}
101
102integer_key! {
103    u8 => u8, 0; u16 => u16, 0; u32 => u32, 0; u64 => u64, 0; u128 => u128, 0;
104    usize => usize, 0;
105    i8 => u8, 1 << 7; i16 => u16, 1 << 15; i32 => u32, 1 << 31; i64 => u64, 1 << 63;
106    i128 => u128, 1 << 127; isize => usize, 1 << (usize::BITS - 1);
107}
108
109impl sealed::Key for char {
110    type Bits = u32;
111    #[inline(always)]
112    fn bits(self) -> u32 {
113        self as u32
114    }
115    #[inline(always)]
116    fn distance(self, min: Self) -> u128 {
117        u128::from(self as u32 - min as u32)
118    }
119    #[inline(always)]
120    fn offset(self, min: Self) -> usize {
121        (self as u32).wrapping_sub(min as u32) as usize
122    }
123    #[inline(always)]
124    fn nth(min: Self, offset: usize) -> Self {
125        // An offset into the surrogates, which no element has, gives `min`.
126        char::from_u32((min as u32).wrapping_add(offset as u32)).unwrap_or(min)
127    }
128}
129impl IntegerKey for char {}
130
131impl sealed::Key for bool {
132    type Bits = u8;
133    #[inline(always)]
134    fn bits(self) -> u8 {
135        self as u8
136    }
137    #[inline(always)]
138    fn distance(self, min: Self) -> u128 {
139        u128::from(self as u8 - min as u8)
140    }
141    #[inline(always)]
142    fn offset(self, min: Self) -> usize {
143        usize::from(self).wrapping_sub(usize::from(min))
144    }
145    #[inline(always)]
146    fn nth(min: Self, offset: usize) -> Self {
147        usize::from(min) + offset != 0
148    }
149}
150impl IntegerKey for bool {}
a/sort/key.rs

a/sort/
key.rs
