1#!/usr/bin/python3 -i 2# 3# Copyright (c) 2019 Collabora, Ltd. 4# 5# SPDX-License-Identifier: Apache-2.0 6# 7# Author(s): Ryan Pavlik <ryan.pavlik@collabora.com> 8"""RecursiveMemoize serves as a base class for a function modeled 9as a dictionary computed on-the-fly.""" 10 11 12class RecursiveMemoize: 13 """Base class for functions that are recursive. 14 15 Derive and implement `def compute(self, key):` to perform the computation: 16 you may use __getitem__ (aka self[otherkey]) to access the results for 17 another key. Each value will be computed at most once. Your 18 function should never return None, since it is used as a sentinel here. 19 20 """ 21 22 def __init__(self, func, key_iterable=None, permit_cycles=False): 23 """Initialize data structures, and optionally compute/cache the answer 24 for all elements of an iterable. 25 26 If permit_cycles is False, then __getitem__ on something that's 27 currently being computed raises an exception. 28 If permit_cycles is True, then __getitem__ on something that's 29 currently being computed returns None. 30 """ 31 self._compute = func 32 self.permit_cycles = permit_cycles 33 self.d = {} 34 if key_iterable: 35 # If we were given an iterable, let's populate those. 36 for key in key_iterable: 37 _ = self[key] 38 39 def __getitem__(self, key): 40 """Access the result of computing the function on the input. 41 42 Performed lazily and cached. 43 Implement `def compute(self, key):` with the actual function, 44 which will be called on demand.""" 45 if key in self.d: 46 ret = self.d[key] 47 # Detect "we're computing this" sentinel and 48 # fail if cycles not permitted 49 if ret is None and not self.permit_cycles: 50 raise RuntimeError("Cycle detected when computing function: " + 51 "f({}) depends on itself".format(key)) 52 # return the memoized value 53 # (which might be None if we're in a cycle that's permitted) 54 return ret 55 56 # Set sentinel for "we're computing this" 57 self.d[key] = None 58 # Delegate to function to actually compute 59 ret = self._compute(key) 60 # Memoize 61 self.d[key] = ret 62 63 return ret 64 65 def get_dict(self): 66 """Return the dictionary where memoized results are stored. 67 68 DO NOT MODIFY!""" 69 return self.d 70