fn-memo 1.2.0

A library for creating the memoization of a function.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

use crate::FnMemo;
use recur_fn::RecurFn;
use std::cell::UnsafeCell;
use std::collections::HashMap;
use std::hash::Hash;

/// The cache for single-thread memoization.
pub trait Cache {
    type Arg;
    type Output;

    /// Create an empty cache.
    fn new() -> Self;
    /// Gets the cached result of `arg`.
    /// If it is not cached, returns `None`.
    fn get(&self, arg: &Self::Arg) -> Option<&Self::Output>;
    /// Caches the `arg` with `result`.
    fn cache(&mut self, arg: Self::Arg, result: Self::Output);
    /// Clears the cache.
    fn clear(&mut self);
}

/// Use `HashMap` as `Cache`.
impl<Arg: Clone + Eq + Hash, Output: Clone> Cache for HashMap<Arg, Output> {
    type Arg = Arg;
    type Output = Output;

    fn new() -> Self {
        HashMap::new()
    }
    fn get(&self, arg: &Arg) -> Option<&Output> {
        HashMap::get(self, arg);
        self.get(arg)
    }

    fn cache(&mut self, arg: Arg, result: Output) {
        self.insert(arg, result);
    }

    fn clear(&mut self) {
        self.clear();
    }
}

/// Use `Vec` as `Cache` for sequences.
impl<Output: Clone> Cache for Vec<Option<Output>> {
    type Arg = usize;
    type Output = Output;

    fn new() -> Self {
        Vec::new()
    }

    fn get(&self, arg: &usize) -> Option<&Output> {
        self.as_slice().get(*arg)?.as_ref()
    }

    fn cache(&mut self, arg: usize, result: Output) {
        if arg >= self.len() {
            self.resize(arg + 1, None);
        }
        self[arg] = Some(result);
    }

    fn clear(&mut self) {
        self.clear();
    }
}

/// The implementation of `FnMemo` for single-thread.
pub struct Memo<C, F> {
    cache: UnsafeCell<C>,
    f: F,
}

impl<C: Cache, F: RecurFn<C::Arg, C::Output>> Memo<C, F>
where
    C::Arg: Clone,
    C::Output: Clone,
{
    /// Constructs a `Memo` using `C` as cache, caching function `f`.
    pub fn new(f: F) -> Memo<C, F> {
        Memo {
            cache: UnsafeCell::new(C::new()),
            f,
        }
    }
}

impl<C: Cache, F: RecurFn<C::Arg, C::Output>> FnMemo<C::Arg, C::Output> for Memo<C, F>
where
    C::Arg: Clone,
    C::Output: Clone,
{
    fn call(&self, arg: C::Arg) -> C::Output {
        if let Some(result) = unsafe { &*self.cache.get() }.get(&arg) {
            return result.clone();
        }

        let result = self.f.body(|arg| self.call(arg), arg.clone());
        unsafe { &mut *self.cache.get() }.cache(arg, result.clone());
        result
    }

    fn clear_cache(&self) {
        unsafe { &mut *self.cache.get() }.clear()
    }
}

/// Creates a memoization of `f` using `HashMap` as cache.
pub fn memoize<Arg, Output, F>(f: F) -> impl FnMemo<Arg, Output>
where
    Arg: Clone + Eq + Hash,
    Output: Clone,
    F: RecurFn<Arg, Output>,
{
    Memo::<std::collections::HashMap<_, _>, _>::new(f)
}

/// Creates a memoization of the sequence `f` using `Vec` as cache.
pub fn memoize_seq<Output, F>(f: F) -> impl FnMemo<usize, Output>
where
    Output: Clone,
    F: RecurFn<usize, Output>,
{
    Memo::<Vec<_>, _>::new(f)
}