asciimath_parser/prefix_map/
hash.rs

1use super::PrefixMap;
2use std::borrow::Borrow;
3use std::cmp::min;
4use std::collections::HashMap;
5use std::collections::hash_map::RandomState;
6use std::hash::{BuildHasher, Hash};
7
8/// A prefix map that uses length buckets and hashmaps for lookups
9///
10/// For asciimath, the default hasher makes this the third fastest prefix map. If the `qp-trie`
11/// feature isn't enabled, this will be the default. Finding the longest prefix takes
12/// `O(len_search_key)`, but if all keys are long and roughly the same length this may be faster
13/// than `QpTriePrefixMap`.
14///
15/// # Example
16/// ```
17/// use asciimath_parser::prefix_map::HashPrefixMap;
18/// use asciimath_parser::{ASCIIMATH_TOKENS};
19///
20/// let token_map = HashPrefixMap::from_iter(ASCIIMATH_TOKENS);
21/// ```
22#[derive(Debug, Clone)]
23pub struct HashPrefixMap<K, V, S = RandomState>(Box<[HashMap<K, V, S>]>);
24
25impl<K, V, S> HashPrefixMap<K, V, S>
26where
27    K: Borrow<str> + Hash + Eq,
28    S: BuildHasher + Default,
29{
30    /// Create from an iterator and custom hasher
31    pub fn from_iter_hasher<T, I>(iter: T) -> Self
32    where
33        T: IntoIterator<IntoIter = I>,
34        I: Iterator<Item = (K, V)>,
35    {
36        let mut bins = Vec::new();
37        for (key, val) in iter {
38            let len = key.borrow().len();
39            bins.extend((bins.len()..=len).map(|_| HashMap::default()));
40            bins[len].insert(key, val);
41        }
42        HashPrefixMap(bins.into())
43    }
44}
45
46impl<K, V> FromIterator<(K, V)> for HashPrefixMap<K, V>
47where
48    K: Borrow<str> + Hash + Eq,
49{
50    fn from_iter<I>(iter: I) -> Self
51    where
52        I: IntoIterator<Item = (K, V)>,
53    {
54        Self::from_iter_hasher(iter)
55    }
56}
57
58impl<K, V, S> PrefixMap<V> for HashPrefixMap<K, V, S>
59where
60    K: Borrow<str> + Hash + Eq,
61    S: BuildHasher,
62{
63    fn get_longest_prefix<P: AsRef<str>>(&self, inp: P) -> Option<(usize, &V)> {
64        let inp = inp.as_ref();
65        for (len, map) in self.0[..min(self.0.len(), inp.len() + 1)]
66            .iter()
67            .enumerate()
68            .rev()
69        {
70            if inp.is_char_boundary(len)
71                && let Some(val) = map.get(&inp[..len])
72            {
73                return Some((len, val));
74            }
75        }
76        None
77    }
78}
79
80#[cfg(test)]
81mod tests {
82    use super::{HashPrefixMap, PrefixMap};
83
84    #[test]
85    fn correct_prefixes() {
86        let map = HashPrefixMap::from_iter([("a", 0), ("abc", 1), ("bc", 2), ("bc", 3)]);
87        assert_eq!(map.get_longest_prefix("abcd"), Some((3, &1)));
88        assert_eq!(map.get_longest_prefix("ab"), Some((1, &0)));
89        assert_eq!(map.get_longest_prefix("bcd"), Some((2, &3)));
90        assert_eq!(map.get_longest_prefix("bd"), None);
91        assert_eq!(map.get_longest_prefix("💖"), None);
92    }
93
94    #[test]
95    fn works_for_perverse() {
96        let map = HashPrefixMap::from_iter([("", 0), (" 3", 1)]);
97        assert_eq!(map.get_longest_prefix(" 3 "), Some((2, &1)));
98        assert_eq!(map.get_longest_prefix("ab"), Some((0, &0)));
99    }
100}
asciimath_parser/prefix_map/hash.rs

asciimath_parser/prefix_map/
hash.rs
