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 71 72def longest_common_prefix(strings): 73 """ 74 Find the longest common prefix of a list of 2 or more strings. 75 76 Args: 77 strings (collection): at least 2 strings. 78 79 Returns: 80 string: The longest string that all submitted strings start with. 81 82 >>> longest_common_prefix(["abcd", "abce"]) 83 'abc' 84 85 """ 86 assert(len(strings) > 1) 87 a = min(strings) 88 b = max(strings) 89 prefix = [] 90 for a_char, b_char in zip(a, b): 91 if a_char == b_char: 92 prefix.append(a_char) 93 else: 94 break 95 return "".join(prefix) 96 97 98def longest_common_token_prefix(strings, delimiter='_'): 99 """ 100 Find the longest common token-wise prefix of a list of 2 or more strings. 101 102 Args: 103 strings (collection): at least 2 strings. 104 delimiter (character): the character to split on. 105 106 Returns: 107 string: The longest string that all submitted strings start with. 108 109 >>> longest_common_token_prefix(["xr_abc_123", "xr_abc_567"]) 110 'xr_abc_' 111 112 "1" is in the per-character longest common prefix, but 123 != 135, 113 so it's not in the per-token prefix. 114 115 >>> longest_common_token_prefix(["xr_abc_123", "xr_abc_135"]) 116 'xr_abc_' 117 118 Here, the prefix is actually the entirety of one string, so no trailing delimiter. 119 120 >>> longest_common_token_prefix(["xr_abc_123", "xr_abc"]) 121 'xr_abc' 122 123 124 No common prefix here, because it's per-token: 125 126 >>> longest_common_token_prefix(["abc_123", "ab_123"]) 127 '' 128 129 """ 130 assert(len(strings) > 1) 131 a = min(strings).split(delimiter) 132 b = max(strings).split(delimiter) 133 prefix_tokens = [] 134 for a_token, b_token in zip(a, b): 135 if a_token == b_token: 136 prefix_tokens.append(a_token) 137 else: 138 break 139 if prefix_tokens: 140 prefix = delimiter.join(prefix_tokens) 141 if len(prefix_tokens) < min(len(a), len(b)): 142 # This is truly a prefix, not just one of the strings. 143 prefix += delimiter 144 return prefix 145 return '' 146