asciimath_parser/prefix_map/
mod.rs

1//! `PrefixMaps` are string keyed maps that support finding values with a longest prefix
2//!
3//! They are used by tokenizers to find valid tokens by seeing if the prefix of the current string
4//! maps to a known token. Since this is a large part of asciimath parsing, the efficient of these
5//! maps is heavily linked to overall parsing time.
6//!
7//! In benchmarks on random-ish strings, a prefix map based off of `qp-trie` was the fastest for
8//! parsing asciimath, but using an `fnv` backed [`HashPrefixMap`] was close behind.
9//!
10//! # Benchmarks
11//!
12//! ```txt
13//! test qptrie::random_prefix  ... bench:      85,604 ns/iter (+/- 23,794)
14//! test fnv::random_prefix     ... bench:     107,734 ns/iter (+/- 15,949)
15//! test hash::random_prefix    ... bench:     163,859 ns/iter (+/- 14,000)
16//! test linear::random_prefix  ... bench:     482,320 ns/iter (+/- 42,428)
17//! test fst::random_prefix     ... bench:  22,297,830 ns/iter (+/- 820,369)
18//! ```
19//!
20//! # Example
21//!
22//! ```
23//! use asciimath_parser::prefix_map::LinearPrefixMap;
24//! use asciimath_parser::{ASCIIMATH_TOKENS, Tokenizer, parse_tokens};
25//!
26//! let token_map = LinearPrefixMap::from_vec(ASCIIMATH_TOKENS);
27//! let tokens = Tokenizer::with_tokens("sum_i x_i", &token_map, true);
28//! let parsed = parse_tokens(tokens);
29//! ```
30
31#[cfg(feature = "fst")]
32mod fst;
33mod hash;
34mod linear;
35#[cfg(feature = "qp-trie")]
36mod trie;
37
38#[cfg(feature = "fst")]
39pub use self::fst::FstPrefixMap;
40#[cfg(feature = "fnv")]
41use ::fnv::FnvBuildHasher;
42pub use hash::HashPrefixMap;
43pub use linear::LinearPrefixMap;
44#[cfg(feature = "qp-trie")]
45pub use trie::QpTriePrefixMap;
46
47/// A hash prefix map using the fnv hasher
48///
49/// This is the [second fastest tokenizer][crate::prefix_map], but requires the `fnv` feature.
50///
51/// # Example
52/// ```
53/// use asciimath_parser::prefix_map::FnvHashPrefixMap;
54/// use asciimath_parser::{ASCIIMATH_TOKENS};
55///
56/// let token_map = FnvHashPrefixMap::from_iter_hasher(ASCIIMATH_TOKENS);
57/// ```
58#[cfg(feature = "fnv")]
59pub type FnvHashPrefixMap<K, V> = HashPrefixMap<K, V, FnvBuildHasher>;
60
61/// A `PrefixMap` is a map that supports operations on the prefix of an input
62pub trait PrefixMap<V> {
63    /// Get the corresponding length and value of the key that is part of the lonest prefix of inp
64    ///
65    /// # Example
66    /// ```
67    /// use asciimath_parser::prefix_map::{HashPrefixMap, PrefixMap};
68    ///
69    /// let map = HashPrefixMap::from_iter([("a", 1), ("abc", 3)]);
70    /// assert_eq!(map.get_longest_prefix("ab"), Some((1, &1)));
71    /// ```
72    fn get_longest_prefix<P: AsRef<str>>(&self, inp: P) -> Option<(usize, &V)>;
73}
74
75/// From a vec-like, order all the entries and remove duplicates
76fn remove_ordered_dups<K, V>(inp: &mut Vec<(K, V)>)
77where
78    K: Eq,
79{
80    // NOTE this can potentially be achieved better with drain_filter once it's stabalized
81    if let Some((first, _)) = inp.first() {
82        let mut last = first;
83        let mut off = 0;
84        for ind in 1..inp.len() {
85            if &inp[ind].0 == last {
86                off += 1;
87            }
88            inp.swap(ind - off, ind);
89            last = &inp[ind - off].0;
90        }
91        inp.truncate(inp.len() - off);
92    }
93}
asciimath_parser/prefix_map/mod.rs

asciimath_parser/prefix_map/
mod.rs
