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
|
#!/usr/bin/python3 -i
#
# Copyright (c) 2019 Collabora, Ltd.
#
# SPDX-License-Identifier: Apache-2.0
#
# Author(s): Ryan Pavlik <ryan.pavlik@collabora.com>
"""RecursiveMemoize serves as a base class for a function modeled
as a dictionary computed on-the-fly."""
class RecursiveMemoize:
"""Base class for functions that are recursive.
Derive and implement `def compute(self, key):` to perform the computation:
you may use __getitem__ (aka self[otherkey]) to access the results for
another key. Each value will be computed at most once. Your
function should never return None, since it is used as a sentinel here.
"""
def __init__(self, func, key_iterable=None, permit_cycles=False):
"""Initialize data structures, and optionally compute/cache the answer
for all elements of an iterable.
If permit_cycles is False, then __getitem__ on something that's
currently being computed raises an exception.
If permit_cycles is True, then __getitem__ on something that's
currently being computed returns None.
"""
self._compute = func
self.permit_cycles = permit_cycles
self.d = {}
if key_iterable:
# If we were given an iterable, let's populate those.
for key in key_iterable:
_ = self[key]
def __getitem__(self, key):
"""Access the result of computing the function on the input.
Performed lazily and cached.
Implement `def compute(self, key):` with the actual function,
which will be called on demand."""
if key in self.d:
ret = self.d[key]
# Detect "we're computing this" sentinel and
# fail if cycles not permitted
if ret is None and not self.permit_cycles:
raise RuntimeError("Cycle detected when computing function: " +
"f({}) depends on itself".format(key))
# return the memoized value
# (which might be None if we're in a cycle that's permitted)
return ret
# Set sentinel for "we're computing this"
self.d[key] = None
# Delegate to function to actually compute
ret = self._compute(key)
# Memoize
self.d[key] = ret
return ret
def get_dict(self):
"""Return the dictionary where memoized results are stored.
DO NOT MODIFY!"""
return self.d
|
