ryna/structures/
precedence_cache.rs

1use rustc_hash::FxHashMap;
2
3#[derive(Debug)]
4pub struct PrecedenceCache<T> {
5    inner: FxHashMap<usize, (Vec<usize>, Vec<T>)> // Needs two vecs in order to be logarithmic on lookup
6}
7
8impl<T> Default for PrecedenceCache<T> {
9    fn default() -> Self {
10        Self { inner: Default::default() }
11    }
12}
13
14impl<T> PrecedenceCache<T> {
15    pub fn new() -> Self {
16        PrecedenceCache { inner: FxHashMap::default() }
17    }
18
19    pub fn get(&self, position: usize, precedence: usize) -> Option<&T> {
20        if let Some(v) = self.inner.get(&position) {
21            let (precs, vals) = v;
22
23            // Only return if a lower precedence (or the same) has been recorded
24            return match precs.binary_search(&precedence) {
25                Err(pos) if pos > 0 => Some(&vals[pos - 1]),
26                Ok(pos) => Some(&vals[pos]),
27
28                _ => None
29            }
30        }
31
32        None
33    }
34
35    pub fn set(&mut self, position: usize, precedence: usize, v: T) {
36        let (precs, vals) = self.inner.entry(position).or_default();
37
38        if let Err(pos) = precs.binary_search(&precedence) {
39            precs.insert(pos, precedence);
40            vals.insert(pos, v);
41        }
42    }
43}
44
45#[cfg(test)]
46mod tests {
47    use super::PrecedenceCache;
48
49    #[test]
50    fn precedence_cache() {
51        let mut cache = PrecedenceCache::<&str>::new();
52
53        cache.set(0, 10, "Test 1");
54        cache.set(0, 20, "Test 2");
55        cache.set(0, 15, "Test 3");
56        cache.set(0, 5, "Test 4");
57
58        assert_eq!(cache.get(0, 10), Some(&"Test 1"));
59        assert_eq!(cache.get(0, 14), Some(&"Test 1"));
60        assert_eq!(cache.get(0, 15), Some(&"Test 3"));
61        assert_eq!(cache.get(0, 7), Some(&"Test 4"));
62        assert_eq!(cache.get(0, 2), None);
63        assert_eq!(cache.get(0, 100), Some(&"Test 2"));
64        assert_eq!(cache.get(1, 0), None);
65    }
66}
ryna/structures/precedence_cache.rs

ryna/structures/
precedence_cache.rs
