proximipy/caching/
unbounded_linear_cache.rs

1use crate::caching::approximate_cache::ApproximateCache;
2use crate::numerics::comp::ApproxComparable;
3/// A cache implementation that checks all entries one-by-one, without eviction
4/// ## Generic Types
5/// The types K and V are used for the cache keys and values respectively.
6///
7/// K should be `ApproxComparable`, i.e. the compiler should know how to
8/// decide that two K's are 'close enough' given a certain tolerance.
9///
10/// V should be `Clone` so that the user can do whatever they want with a returned
11/// value without messing with the actual cache line.
12///
13/// ## Constructors
14/// Use the ```from``` method to create a new cache. You will be asked to provide a
15/// tolerance for the search and (optionally) an initial allocated capacity in memory.
16/// ```tolerance``` indicates the searching sensitivity (see `ApproxComparable`),
17/// which is a constant w.r.t. to the queried K (for now).
18pub struct UnboundedLinearCache<K, V>
19where
20    K: ApproxComparable,
21    V: Clone,
22{
23    keys: Vec<K>,
24    values: Vec<V>,
25    tolerance: f32,
26}
27
28impl<K, V> UnboundedLinearCache<K, V>
29where
30    K: ApproxComparable,
31    V: Clone,
32{
33    pub fn new(tolerance: f32) -> Self {
34        UnboundedLinearCache {
35            keys: Vec::new(),
36            values: Vec::new(),
37            tolerance,
38        }
39    }
40
41    pub fn with_initial_capacity(tolerance: f32, capacity: usize) -> Self {
42        UnboundedLinearCache {
43            keys: Vec::with_capacity(capacity),
44            values: Vec::with_capacity(capacity),
45            tolerance,
46        }
47    }
48}
49
50impl<K, V> ApproximateCache<K, V> for UnboundedLinearCache<K, V>
51where
52    K: ApproxComparable,
53    V: Clone,
54{
55    // to find a match in an unbounded cache, iterate over all cache lines
56    // and return early if you have something
57    fn find(&mut self, to_find: &K) -> Option<V> {
58        let potential_match = self
59            .keys
60            .iter()
61            .position(|key| to_find.roughly_matches(key, self.tolerance));
62
63        potential_match.map(|i| self.values[i].clone())
64    }
65
66    // inserting a new value in a linear cache == pushing it at the end for future scans
67    fn insert(&mut self, key: K, value: V) {
68        self.keys.push(key);
69        self.values.push(value);
70    }
71
72    fn len(&self) -> usize {
73        self.keys.len()
74    }
75}
76
77#[cfg(test)]
78mod tests {
79    use crate::caching::approximate_cache::COMPTIME_CACHE_SIZE;
80
81    use super::*;
82    use quickcheck::{QuickCheck, TestResult};
83
84    const TEST_TOLERANCE: f32 = 1e-8;
85    const TEST_MAX_SIZE: usize = COMPTIME_CACHE_SIZE;
86
87    #[test]
88    fn start_always_matches_exactly() {
89        fn qc_start_always_matches_exactly(
90            start_state: Vec<(f32, u8)>,
91            key: f32,
92            value: u8,
93        ) -> TestResult {
94            let mut ulc = UnboundedLinearCache::<f32, u8>::new(TEST_TOLERANCE);
95            if !key.is_finite() || start_state.len() > TEST_MAX_SIZE {
96                return TestResult::discard();
97            }
98
99            ulc.insert(key, value);
100            for &(k, v) in start_state.iter() {
101                ulc.insert(k, v);
102            }
103
104            assert!(ulc.len() == start_state.len() + 1);
105
106            if let Some(x) = ulc.find(&key) {
107                TestResult::from_bool(x == value)
108            } else {
109                TestResult::failed()
110            }
111        }
112
113        QuickCheck::new()
114            .tests(10_000)
115            .min_tests_passed(1_000)
116            .quickcheck(
117                qc_start_always_matches_exactly as fn(Vec<(f32, u8)>, f32, u8) -> TestResult,
118            );
119    }
120
121    #[test]
122    fn middle_always_matches() {
123        fn qc_middle_always_matches(
124            start_state: Vec<(f32, u8)>,
125            key: f32,
126            value: u8,
127            end_state: Vec<(f32, u8)>,
128        ) -> TestResult {
129            let mut ulc = UnboundedLinearCache::<f32, u8>::new(TEST_TOLERANCE);
130            if !key.is_finite() || start_state.len() > TEST_MAX_SIZE {
131                return TestResult::discard();
132            }
133
134            for &(k, v) in start_state.iter() {
135                ulc.insert(k, v);
136            }
137            ulc.insert(key, value);
138            for &(k, v) in end_state.iter() {
139                ulc.insert(k, v);
140            }
141
142            assert!(ulc.len() == start_state.len() + end_state.len() + 1);
143
144            // we should match on something but we can't know on what
145            TestResult::from_bool(ulc.find(&key).is_some())
146        }
147
148        QuickCheck::new()
149            .tests(10_000)
150            .min_tests_passed(1_000)
151            .quickcheck(
152                qc_middle_always_matches
153                    as fn(Vec<(f32, u8)>, f32, u8, Vec<(f32, u8)>) -> TestResult,
154            );
155    }
156}
proximipy/caching/unbounded_linear_cache.rs

proximipy/caching/
unbounded_linear_cache.rs
