use std::collections::HashMap;
use std::hash::Hash;

pub struct Cache<K, V, F> {
    cache: HashMap<K, V>,
    compute: F,
}

impl<'a, K, V, F> Cache<K, V, F>
where
    K: Hash + Eq + Copy,
    V: Copy,
    F: FnMut(K, Box<dyn FnMut(K) -> V + 'a>) -> V,
{
    pub fn new(compute: F) -> Cache<K, V, F> {
        let cache = HashMap::new();
        Cache { cache, compute }
    }

    pub fn get(&'a mut self, key: K) -> V {
        if let Some(&value) = self.cache.get(&key) {
            return value;
        }

        let value = (self.compute)(key, Box::new(|k: K| self.get(k)));
        self.cache.insert(key, value);
        value
    }
}