I haven’t tested the performance, but you could also try using a BTreeMap
:
use lazy_static::lazy_static;
use std::borrow::Borrow;
use std::collections::BTreeMap;
use std::convert::TryInto;
fn make_table<T: Ord, Ix, E>(v: impl IntoIterator<Item = T>) -> Result<BTreeMap<T, Ix>, E>
where
usize: TryInto<Ix, Error = E>,
{
v.into_iter()
.enumerate()
.map(|(i, x)| Ok((x, i.try_into()?)))
.collect()
}
fn find_index<'a, T, Ix, Q>(k: &Q, table: &'a BTreeMap<T, Ix>) -> Option<&'a Ix>
where
T: Borrow<Q> + Ord,
Q: Ord,
{
table.range(..=k).next_back().map(|(_, ix)| ix)
}
lazy_static! {
static ref TABLE1: BTreeMap<u8, u8> =
make_table([11, 13, 15, 17, 19, 23, 27, 31].iter().copied()).unwrap();
}
fn find_ix1(x: u8) -> u8 {
*find_index(&x, &TABLE1).unwrap()
}
lazy_static! {
static ref TABLE2: BTreeMap<u16, u8> = make_table(
[
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025,
1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
]
.iter()
.copied()
)
.unwrap();
}
fn find_ix2(x: u16) -> u8 {
*find_index(&x, &TABLE2).unwrap()
}
fn main() {
for &x in &[11, 12, 13, 14, 15, 29, 30, 31] {
println!("{} has ix {}", x, find_ix1(x));
}
println!("--------------");
for &x in &[1,2,1000,5000,10000,24576,24577] {
println!("{} has ix {}", x, find_ix2(x));
}
/* OUTPUT:
11 has ix 0
12 has ix 0
13 has ix 1
14 has ix 1
15 has ix 2
29 has ix 6
30 has ix 6
31 has ix 7
--------------
1 has ix 0
2 has ix 1
1000 has ix 19
5000 has ix 24
10000 has ix 26
24576 has ix 28
24577 has ix 29
*/
}