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: Fn(K, &mut dyn FnMut(K) -> V) -> V,
{
    pub fn new(compute: F) -> Cache<K, V, F> {
        let cache = HashMap::new();
        Cache { cache, compute }
    }

    pub fn get(&mut self, key: K) -> V {
        get(&mut self.cache, &self.compute, key)
    }
}

fn get<'a, K, V, F>(cache: &mut HashMap<K, V>, f: &F, key: K) -> V
where
    K: Hash + Eq + Copy,
    V: Copy,
    F: Fn(K, &mut dyn FnMut(K) -> V) -> V,
{
    if let Some(&value) = cache.get(&key) {
        return value;
    }

    let value = (f)(key, &mut |k: K| get(cache, f, k));
    cache.insert(key, value);
    value
}

fn main() {
    let mut fib = Cache::new(
        |n: usize, fib| {
            if n <= 1 {
                n
            } else {
                fib(n - 1) + fib(n - 2)
            }
        },
    );
    println!("fib80 = {}", fib.get(80));
}