contest_algorithms/
caching.rs

1//! Basic Cacher struct which stores a closure and a hashmap.
2//! The hasmap stores key value pairs representing previous
3//! function calls.
4//!
5//! When the Cacher function is run, it first does a lookup
6//! to see if the value has already been calculated. If it has,
7//! it returns that value. If it hasn't, it calculates the value,
8//! adds it to the hashmap, and returns it.
9
10use std::collections::HashMap;
11
12/// The Cacher struct (Memoization) stores a function and a Hashmap.
13/// The HashMap keeps track of previous input and output for the function so
14/// that it only ever has to be called once per input. Use for expensive functions.
15pub struct Cacher<F, U, V>
16where
17    F: Fn(U) -> V,
18    U: std::cmp::Eq + std::hash::Hash + Copy,
19    V: Copy,
20{
21    calculation: F,
22    values: HashMap<U, V>,
23}
24
25impl<F, U, V> Cacher<F, U, V>
26where
27    F: Fn(U) -> V,
28    U: std::cmp::Eq + std::hash::Hash + Copy,
29    V: Copy,
30{
31    /// Constuctor for the Casher
32    /// # Examples
33    /// ```
34    /// # use contest_algorithms::caching::Cacher;
35    /// let mut squared = Cacher::new(|n: u32| n*n);
36    /// ```
37    pub fn new(calculation: F) -> Cacher<F, U, V> {
38        Cacher {
39            calculation,
40            values: HashMap::new(),
41        }
42    }
43
44    /// Performs a lookup into the HashMap to see if the value has already
45    /// been calculated. If it has, returns the value. If it has not,
46    /// calls the function, stores the value, then returns the value.
47    /// # Examples
48    /// ```
49    /// # use contest_algorithms::caching::Cacher;
50    /// let mut squared = Cacher::new(|n: u32| n*n);
51    ///
52    /// // This is where we call the function
53    /// let sixteen = squared.call(4);
54    /// ```
55    // TODO: whenever Rust's Entry API gains the ability to take ownership of
56    // arg only when necessary, this method should follow the same practice.
57    // Also, Cacher should implement Fn(U)->V once this is possible.
58    pub fn call(&mut self, arg: U) -> V {
59        let calc = &self.calculation;
60        *self.values.entry(arg).or_insert_with_key(|&key| calc(key))
61    }
62
63    /// Calls the function without performing a lookup and replaces
64    /// the old return value with the new one, and returns it.
65    /// Potentially useful if the function reads from a file or RNG
66    /// whose state may have changed.
67    // TODO: if there's state, FnMut seems more appropriate.
68    pub fn call_and_replace(&mut self, arg: U) -> V {
69        let new_val = (self.calculation)(arg);
70        self.values.insert(arg, new_val);
71        new_val
72    }
73}
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_cacher_basically_works() {
81        let mut word_len = Cacher::new(|word: &str| word.len());
82        let hello = word_len.call("hello");
83
84        // Test function returns correctly
85        assert_eq!(hello, 5);
86
87        // Test HashMap is correct length
88        assert_eq!(word_len.values.len(), 1);
89
90        // Test HashMap has correct value after one insert
91        let mut test_map = HashMap::new();
92        test_map.insert("hello", 5);
93        assert_eq!(word_len.values, test_map);
94
95        // Test HashMap has correct value after duplicate insert
96        word_len.call("hello");
97        assert_eq!(word_len.values, test_map);
98
99        // Test HashMap has correct values after unique input
100        word_len.call("wazzup");
101        test_map.insert("wazzup", 6);
102        assert_eq!(word_len.values, test_map);
103    }
104
105    #[test]
106    fn test_cacher_speed() {
107        // Simulate a function that takes 1 second to complete
108        let mut func = Cacher::new(|x| {
109            std::thread::sleep(std::time::Duration::from_millis(100));
110            x * x
111        });
112
113        // Would take 10 minutes without caching
114        for _ in 0..6000 {
115            assert_eq!(25, func.call(5));
116        }
117    }
118
119    #[test]
120    fn test_call_and_replace() {
121        use std::time::Instant;
122
123        let mut func = Cacher::new(|_param: usize| Instant::now());
124        let first_instant = func.call(0);
125        let lookup_instant = func.call(0);
126
127        assert_eq!(first_instant, lookup_instant);
128        assert_eq!(1, func.values.len());
129
130        let second_instant = func.call_and_replace(0);
131        assert_eq!(1, func.values.len());
132        assert_ne!(second_instant, lookup_instant);
133    }
134}
contest_algorithms/caching.rs

contest_algorithms/
caching.rs
