asciimath_parser/prefix_map/
linear.rs

1use super::PrefixMap;
2use std::borrow::Borrow;
3
4/// A very simple prefix map
5///
6/// This prefix map stores prefix in descending order by length. While very simple, it was still
7/// reasonably fast only requires keys with equality. This might be a good choice on machines with
8/// limited memory especially if you're parsing a very small subset of asciimath. Finding the
9/// longest prefix takes `O(num_prefixes)`.
10#[derive(Debug, Clone, PartialEq, Eq)]
11pub struct LinearPrefixMap<K, V>(Box<[(K, V)]>);
12
13impl<K, V> LinearPrefixMap<K, V>
14where
15    K: Borrow<str> + Eq,
16{
17    /// Create from a vector of entries
18    pub fn from_vec<B>(inp: B) -> Self
19    where
20        B: Into<Vec<(K, V)>>,
21    {
22        let mut res = inp.into();
23        res.sort_by(|(left, _), (right, _)| {
24            let left = left.borrow();
25            let right = right.borrow();
26            left.len()
27                .cmp(&right.len())
28                .reverse()
29                .then_with(|| left.as_bytes().cmp(right.as_bytes()))
30        });
31        super::remove_ordered_dups(&mut res);
32        LinearPrefixMap(res.into())
33    }
34}
35
36impl<K, V> FromIterator<(K, V)> for LinearPrefixMap<K, V>
37where
38    K: Borrow<str> + Eq,
39{
40    fn from_iter<I>(iter: I) -> Self
41    where
42        I: IntoIterator<Item = (K, V)>,
43    {
44        Self::from_vec(iter.into_iter().collect::<Vec<_>>())
45    }
46}
47
48impl<K: Borrow<str>, V> PrefixMap<V> for LinearPrefixMap<K, V> {
49    fn get_longest_prefix<P: AsRef<str>>(&self, inp: P) -> Option<(usize, &V)> {
50        let inp = inp.as_ref();
51        for (tag, val) in &self.0 {
52            let tag = tag.borrow();
53            if inp.starts_with(tag) {
54                return Some((tag.len(), val));
55            }
56        }
57        None
58    }
59}
60
61#[cfg(test)]
62mod tests {
63    use super::{LinearPrefixMap, PrefixMap};
64
65    #[test]
66    fn correct_prefixes() {
67        let map = LinearPrefixMap::from_vec([("a", 0), ("abc", 1), ("bc", 2), ("bc", 3)]);
68        assert_eq!(map.get_longest_prefix("abcd"), Some((3, &1)));
69        assert_eq!(map.get_longest_prefix("ab"), Some((1, &0)));
70        assert_eq!(map.get_longest_prefix("bcd"), Some((2, &3)));
71        assert_eq!(map.get_longest_prefix("bd"), None);
72        assert_eq!(map.get_longest_prefix("💖"), None);
73    }
74
75    #[test]
76    fn works_for_perverse() {
77        let map = LinearPrefixMap::from_vec([("", 0), (" 3", 1)]);
78        assert_eq!(map.get_longest_prefix(" 3 "), Some((2, &1)));
79        assert_eq!(map.get_longest_prefix("ab"), Some((0, &0)));
80    }
81}
asciimath_parser/prefix_map/linear.rs

asciimath_parser/prefix_map/
linear.rs
