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;
pub trait Cache {
type Arg;
type Output;
fn new() -> Self;
fn get(&self, arg: &Self::Arg) -> Option<&Self::Output>;
fn cache(&mut self, arg: Self::Arg, result: Self::Output);
fn clear(&mut self);
}
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();
}
}
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();
}
}
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,
{
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()
}
}
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)
}
pub fn memoize_seq<Output, F>(f: F) -> impl FnMemo<usize, Output>
where
Output: Clone,
F: RecurFn<usize, Output>,
{
Memo::<Vec<_>, _>::new(f)
}