ph_temp/
utils.rs

1//! Utility functions.
2
3use binout::{AsIs, Serializer};
4use bitm::{ArrayWithRank101111, ceiling_div};
5pub use seedable_hash::{map64_to_64, map32_to_32};
6
7pub type ArrayWithRank = ArrayWithRank101111;
8
9/// Reads `number_of_bits` bits, rounded up to multiple of 64, from `input`.
10pub fn read_bits<R: std::io::Read + ?Sized>(input: &mut R, number_of_bits: usize) -> std::io::Result<Box<[u64]>> {
11    AsIs::read_n(input, ceiling_div(number_of_bits, 64))
12}
13
14/// Checks if `phf` is valid partial (`None` results are ignored) perfect hash function. Panics if it is not.
15pub fn verify_partial_phf<K: std::fmt::Display, G: Fn(&K)->Option<usize>>(expected_range: usize, keys: impl IntoIterator<Item=K>, phf: G) {
16    use bitm::{BitVec, BitAccess};
17    let mut seen_values = Box::with_zeroed_bits(expected_range);
18    for key in keys {
19        if let Some(v) = phf(&key) {
20            assert!(v < expected_range, "f({key})={v} exceeds maximum value {}", expected_range-1);
21            assert!(!seen_values.get_bit(v as usize), "f returned the same value {v} for {key} and another key");
22            seen_values.set_bit(v);
23        }
24    }
25}
26
27/// Checks if `phf` is valid k-perfect hash function. Panics if it is not (also if `phf` returns `None` for any key).
28pub fn verify_phf<K: std::fmt::Display, G: Fn(&K)->Option<usize>>(expected_range: usize, keys: impl IntoIterator<Item=K>, phf: G) {
29    verify_partial_phf(expected_range, keys, |key| {
30        let v = phf(key);
31        assert!(v.is_some(), "f does not assign the value to the key {} which is in the input", key);
32        v
33    });
34}
35
36/// Checks if `kphf` is valid partial (`None` results are ignored) k-perfect hash function. Panics if it is not.
37pub fn verify_partial_kphf<K: std::fmt::Display, G: Fn(&K)->Option<usize>>(k: u8, expected_range: usize, keys: impl IntoIterator<Item=K>, kphf: G) {
38    if k == 1 { verify_partial_phf(expected_range, keys, kphf); return; }
39    let mut seen_values = vec![0; expected_range];
40    for key in keys {
41        if let Some(v) = kphf(&key) {
42            assert!(v < expected_range, "f({key})={v} exceeds maximum value {}", expected_range-1);
43            assert!(seen_values[v as usize] < k, "f returned the same value {v} for {key} and {k} another keys");
44            seen_values[v as usize] += 1;
45        }
46    }
47}
48
49/// Checks if `kphf` is valid partial k-perfect hash function. Panics if it is not (also if `phf` returns `None` for any key).
50pub fn verify_kphf<K: std::fmt::Display, G: Fn(&K)->Option<usize>>(k: u8, expected_range: usize, keys: impl IntoIterator<Item=K>, kphf: G) {
51    verify_partial_kphf(k, expected_range, keys, |key| {
52        let v = kphf(key);
53        assert!(v.is_some(), "f does not assign the value to the key {} which is in the input", key);
54        v
55    });
56}
57
58
59#[cfg(test)]
60pub(crate) mod tests {
61    use super::verify_phf;
62
63    pub fn test_mphf<K: std::fmt::Display+Clone, G: Fn(&K)->Option<usize>>(mphf_keys: &[K], mphf: G) {
64        verify_phf(mphf_keys.len(), mphf_keys.iter().cloned(), mphf);
65    }
66
67    pub fn test_mphf_u64<K: std::fmt::Display+Clone, G: Fn(&K)->Option<u64>>(mphf_keys: &[K], mphf: G) {
68        test_mphf(mphf_keys, |k| mphf(k).map(|v| v as usize));
69    }
70}
ph_temp/utils.rs

ph_temp/
utils.rs
