Skip to content

Commit a4f8009

Browse files
lonelyenvoylonelyenvoy
committed
fix #14; implement 8 APIs on @cached wrapper; drop wrapper._get_caching_list private API; add/update test cases
1 parent 2c73051 commit a4f8009

File tree

6 files changed

+915
-63
lines changed

6 files changed

+915
-63
lines changed

‎memoization/caching/fifo_cache.py

Lines changed: 156 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -108,23 +108,170 @@ def cache_info():
108108
return CacheInfo(hits, misses, cache.__len__(), max_size, algorithm,
109109
ttl, thread_safe, order_independent, custom_key_maker is not None)
110110

111-
def get_caching_list():
111+
def cache_is_empty():
112+
"""Return True if the cache contains no elements"""
113+
return cache.__len__() == 0
114+
115+
def cache_is_full():
116+
"""Return True if the cache is full"""
117+
return full
118+
119+
def cache_contains_argument(function_arguments, alive_only=False):
112120
"""
113-
Get a list containing all (key, value) in the cache in an order determined by the algorithm - FIFO
121+
Return True if the cache contains a cached item with the specified function call arguments
122+
123+
:param function_arguments: Can be a list, a tuple or a dict.
124+
- Full arguments: use a list to represent both positional arguments and keyword
125+
arguments. The list contains two elements, a tuple (positional arguments) and
126+
a dict (keyword arguments). For example,
127+
f(1, 2, 3, a=4, b=5, c=6)
128+
can be represented by:
129+
[(1, 2, 3), {'a': 4, 'b': 5, 'c': 6}]
130+
- Positional arguments only: when the arguments does not include keyword arguments,
131+
a tuple can be used to represent positional arguments. For example,
132+
f(1, 2, 3)
133+
can be represented by:
134+
(1, 2, 3)
135+
- Keyword arguments only: when the arguments does not include positional arguments,
136+
a dict can be used to represent keyword arguments. For example,
137+
f(a=4, b=5, c=6)
138+
can be represented by:
139+
{'a': 4, 'b': 5, 'c': 6}
140+
141+
:param alive_only: Whether to check alive cache item only (default to False).
142+
143+
:return: True if the desired cached item is present, False otherwise.
114144
"""
115-
node = root[_PREV]
116-
result = []
117-
while node is not root:
118-
result.append((node[_KEY], node[_VALUE]))
119-
node = node[_PREV]
120-
return result
145+
if isinstance(function_arguments, tuple):
146+
positional_argument_tuple = function_arguments
147+
keyword_argument_dict = {}
148+
elif isinstance(function_arguments, dict):
149+
positional_argument_tuple = ()
150+
keyword_argument_dict = function_arguments
151+
elif isinstance(function_arguments, list) and len(function_arguments) == 2:
152+
positional_argument_tuple, keyword_argument_dict = function_arguments
153+
if not isinstance(positional_argument_tuple, tuple) or not isinstance(keyword_argument_dict, dict):
154+
raise TypeError('Expected function_arguments to be a list containing a positional argument tuple '
155+
'and a keyword argument dict')
156+
else:
157+
raise TypeError('Expected function_arguments to be a tuple, a dict, or a list with 2 elements')
158+
key = make_key(positional_argument_tuple, keyword_argument_dict)
159+
with lock:
160+
node = cache.get(key, sentinel)
161+
if node is not sentinel:
162+
return values_toolkit.is_cache_value_valid(node[_VALUE]) if alive_only else True
163+
return False
164+
165+
def cache_contains_key(key, alive_only=False):
166+
"""
167+
Return True if the cache contains a cache item with the specified key. This function is only recommended to use
168+
when you provide a custom key maker; otherwise, use cache_contains_argument() instead.
169+
170+
:param key: A key built by the default key maker or a custom key maker.
171+
172+
:param alive_only: Whether to check alive cache item only (default to False).
173+
174+
:return: True if the desired cached item is present, False otherwise.
175+
"""
176+
with lock:
177+
node = cache.get(key, sentinel)
178+
if node is not sentinel:
179+
return values_toolkit.is_cache_value_valid(node[_VALUE]) if alive_only else True
180+
return False
181+
182+
def cache_contains_result(return_value, alive_only=False):
183+
"""
184+
Return True if the cache contains a cache item with the specified user function return value. O(n) time
185+
complexity.
186+
187+
:param return_value: A return value coming from the user function.
188+
189+
:param alive_only: Whether to check alive cache item only (default to False).
190+
191+
:return: True if the desired cached item is present, False otherwise.
192+
"""
193+
with lock:
194+
node = root[_PREV]
195+
while node is not root:
196+
is_alive = values_toolkit.is_cache_value_valid(node[_VALUE])
197+
cache_result = values_toolkit.retrieve_result_from_cache_value(node[_VALUE])
198+
if cache_result == return_value:
199+
return is_alive if alive_only else True
200+
node = node[_PREV]
201+
return False
202+
203+
def cache_for_each(consumer):
204+
"""
205+
Perform the given action for each cache element in an order determined by the algorithm (FIFO) until all
206+
elements have been processed or the action throws an error
207+
208+
:param consumer: an action function to process the cache elements. Must have 3 arguments:
209+
def consumer(cache_key, cache_result, is_alive): ...
210+
cache_key is built by the default key maker or a custom key maker.
211+
cache_result is a return value coming from the user function.
212+
is_alive is a boolean value indicating whether the cache is still alive
213+
(if a TTL is given).
214+
"""
215+
with lock:
216+
node = root[_PREV]
217+
while node is not root:
218+
is_alive = values_toolkit.is_cache_value_valid(node[_VALUE])
219+
cache_result = values_toolkit.retrieve_result_from_cache_value(node[_VALUE])
220+
consumer(node[_KEY], cache_result, is_alive)
221+
node = node[_PREV]
222+
223+
def cache_remove_if(predicate):
224+
"""
225+
Remove all cache elements that satisfy the given predicate
226+
227+
:param predicate: a predicate function to judge whether the cache elements should be removed. Must
228+
have 3 arguments:
229+
def consumer(cache_key, cache_result, is_alive): ...
230+
cache_key is built by the default key maker or a custom key maker.
231+
cache_result is a return value coming from the user function.
232+
is_alive is a boolean value indicating whether the cache is still alive
233+
(if a TTL is given).
234+
235+
:return: True if at least one element is removed, False otherwise.
236+
"""
237+
nonlocal full
238+
removed = False
239+
with lock:
240+
node = root[_PREV]
241+
while node is not root:
242+
is_alive = values_toolkit.is_cache_value_valid(node[_VALUE])
243+
cache_result = values_toolkit.retrieve_result_from_cache_value(node[_VALUE])
244+
if predicate(node[_KEY], cache_result, is_alive):
245+
removed = True
246+
node_prev = node[_PREV]
247+
# relink pointers of node.prev.next and node.next.prev
248+
node_prev[_NEXT] = node[_NEXT]
249+
node[_NEXT][_PREV] = node_prev
250+
# clear the content of this node
251+
key = node[_KEY]
252+
node[_KEY] = node[_VALUE] = None
253+
# delete from cache
254+
del cache[key]
255+
# check whether the cache is full
256+
full = (cache.__len__() >= max_size)
257+
node = node_prev
258+
else:
259+
node = node[_PREV]
260+
return removed
121261

122262
# expose operations to wrapper
123263
wrapper.cache_clear = cache_clear
124264
wrapper.cache_info = cache_info
265+
wrapper.cache_is_empty = cache_is_empty
266+
wrapper.cache_is_full = cache_is_full
267+
wrapper.cache_contains_argument = cache_contains_argument
268+
wrapper.cache_contains_key = cache_contains_key
269+
wrapper.cache_contains_result = cache_contains_result
270+
wrapper.cache_for_each = cache_for_each
271+
wrapper.cache_remove_if = cache_remove_if
272+
wrapper.cache_make_key = make_key
125273
wrapper._cache = cache
126274
wrapper._fifo_root = root
127275
wrapper._root_name = '_fifo_root'
128-
wrapper._get_caching_list = get_caching_list
129276

130277
return wrapper

‎memoization/caching/lfu_cache.py

Lines changed: 170 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -79,27 +79,185 @@ def cache_info():
7979
return CacheInfo(hits, misses, cache.__len__(), max_size, algorithm,
8080
ttl, thread_safe, order_independent, custom_key_maker is not None)
8181

82-
def get_caching_list():
82+
def cache_is_empty():
83+
"""Return True if the cache contains no elements"""
84+
return cache.__len__() == 0
85+
86+
def cache_is_full():
87+
"""Return True if the cache is full"""
88+
return cache.__len__() >= max_size
89+
90+
def cache_contains_argument(function_arguments, alive_only=False):
8391
"""
84-
Get a list containing all (key, value) in the cache in an order determined by the algorithm - LFU
92+
Return True if the cache contains a cached item with the specified function call arguments
93+
94+
:param function_arguments: Can be a list, a tuple or a dict.
95+
- Full arguments: use a list to represent both positional arguments and keyword
96+
arguments. The list contains two elements, a tuple (positional arguments) and
97+
a dict (keyword arguments). For example,
98+
f(1, 2, 3, a=4, b=5, c=6)
99+
can be represented by:
100+
[(1, 2, 3), {'a': 4, 'b': 5, 'c': 6}]
101+
- Positional arguments only: when the arguments does not include keyword arguments,
102+
a tuple can be used to represent positional arguments. For example,
103+
f(1, 2, 3)
104+
can be represented by:
105+
(1, 2, 3)
106+
- Keyword arguments only: when the arguments does not include positional arguments,
107+
a dict can be used to represent keyword arguments. For example,
108+
f(a=4, b=5, c=6)
109+
can be represented by:
110+
{'a': 4, 'b': 5, 'c': 6}
111+
112+
:param alive_only: Whether to check alive cache item only (default to False).
113+
114+
:return: True if the desired cached item is present, False otherwise.
85115
"""
86-
result = []
87-
freq_node = lfu_freq_list_root.prev
88-
while freq_node != lfu_freq_list_root:
89-
cache_node = freq_node.cache_head.next
90-
while cache_node != freq_node.cache_head:
91-
result.append((cache_node.key, cache_node.value))
92-
cache_node = cache_node.next
93-
freq_node = freq_node.prev
94-
return result
116+
if isinstance(function_arguments, tuple):
117+
positional_argument_tuple = function_arguments
118+
keyword_argument_dict = {}
119+
elif isinstance(function_arguments, dict):
120+
positional_argument_tuple = ()
121+
keyword_argument_dict = function_arguments
122+
elif isinstance(function_arguments, list) and len(function_arguments) == 2:
123+
positional_argument_tuple, keyword_argument_dict = function_arguments
124+
if not isinstance(positional_argument_tuple, tuple) or not isinstance(keyword_argument_dict, dict):
125+
raise TypeError('Expected function_arguments to be a list containing a positional argument tuple '
126+
'and a keyword argument dict')
127+
else:
128+
raise TypeError('Expected function_arguments to be a tuple, a dict, or a list with 2 elements')
129+
key = make_key(positional_argument_tuple, keyword_argument_dict)
130+
with lock:
131+
cache_node = cache.get(key, sentinel)
132+
if cache_node is not sentinel:
133+
return values_toolkit.is_cache_value_valid(cache_node.value) if alive_only else True
134+
return False
135+
136+
def cache_contains_key(key, alive_only=False):
137+
"""
138+
Return True if the cache contains a cache item with the specified key. This function is only recommended to use
139+
when you provide a custom key maker; otherwise, use cache_contains_argument() instead.
140+
141+
:param key: A key built by the default key maker or a custom key maker.
142+
143+
:param alive_only: Whether to check alive cache item only (default to False).
144+
145+
:return: True if the desired cached item is present, False otherwise.
146+
"""
147+
with lock:
148+
cache_node = cache.get(key, sentinel)
149+
if cache_node is not sentinel:
150+
return values_toolkit.is_cache_value_valid(cache_node.value) if alive_only else True
151+
return False
152+
153+
def cache_contains_result(return_value, alive_only=False):
154+
"""
155+
Return True if the cache contains a cache item with the specified user function return value. O(n) time
156+
complexity.
157+
158+
:param return_value: A return value coming from the user function.
159+
160+
:param alive_only: Whether to check alive cache item only (default to False).
161+
162+
:return: True if the desired cached item is present, False otherwise.
163+
"""
164+
with lock:
165+
freq_node = lfu_freq_list_root.prev
166+
while freq_node != lfu_freq_list_root:
167+
cache_head = freq_node.cache_head
168+
cache_node = cache_head.next
169+
while cache_node != cache_head:
170+
is_alive = values_toolkit.is_cache_value_valid(cache_node.value)
171+
cache_result = values_toolkit.retrieve_result_from_cache_value(cache_node.value)
172+
if cache_result == return_value:
173+
return is_alive if alive_only else True
174+
cache_node = cache_node.next
175+
freq_node = freq_node.prev
176+
return False
177+
178+
def cache_for_each(consumer):
179+
"""
180+
Perform the given action for each cache element in an order determined by the algorithm (FIFO) until all
181+
elements have been processed or the action throws an error
182+
183+
:param consumer: an action function to process the cache elements. Must have 3 arguments:
184+
def consumer(cache_key, cache_result, is_alive): ...
185+
cache_key is built by the default key maker or a custom key maker.
186+
cache_result is a return value coming from the user function.
187+
is_alive is a boolean value indicating whether the cache is still alive
188+
(if a TTL is given).
189+
"""
190+
with lock:
191+
freq_node = lfu_freq_list_root.prev
192+
while freq_node != lfu_freq_list_root:
193+
cache_head = freq_node.cache_head
194+
cache_node = cache_head.next
195+
while cache_node != cache_head:
196+
is_alive = values_toolkit.is_cache_value_valid(cache_node.value)
197+
cache_result = values_toolkit.retrieve_result_from_cache_value(cache_node.value)
198+
consumer(cache_node.key, cache_result, is_alive)
199+
cache_node = cache_node.next
200+
freq_node = freq_node.prev
201+
202+
def cache_remove_if(predicate):
203+
"""
204+
Remove all cache elements that satisfy the given predicate
205+
206+
:param predicate: a predicate function to judge whether the cache elements should be removed. Must
207+
have 3 arguments:
208+
def consumer(cache_key, cache_result, is_alive): ...
209+
cache_key is built by the default key maker or a custom key maker.
210+
cache_result is a return value coming from the user function.
211+
is_alive is a boolean value indicating whether the cache is still alive
212+
(if a TTL is given).
213+
214+
:return: True if at least one element is removed, False otherwise.
215+
"""
216+
removed = False
217+
with lock:
218+
freq_node = lfu_freq_list_root.prev
219+
while freq_node != lfu_freq_list_root:
220+
cache_head = freq_node.cache_head
221+
cache_node = cache_head.next
222+
removed_under_this_freq_node = False
223+
while cache_node != cache_head:
224+
is_alive = values_toolkit.is_cache_value_valid(cache_node.value)
225+
cache_result = values_toolkit.retrieve_result_from_cache_value(cache_node.value)
226+
if predicate(cache_node.key, cache_result, is_alive):
227+
removed = removed_under_this_freq_node = True
228+
next_cache_node = cache_node.next
229+
del cache[cache_node.key] # delete from cache
230+
cache_node.destroy() # modify references, drop this cache node
231+
cache_node = next_cache_node
232+
else:
233+
cache_node = cache_node.next
234+
# check whether only one cache node is left
235+
if removed_under_this_freq_node and freq_node.cache_head.next == freq_node.cache_head:
236+
# Getting here means that we just deleted the only data node in the cache list
237+
# Note: there is still an empty sentinel node
238+
# We then need to destroy the sentinel node and its parent frequency node too
239+
prev_freq_node = freq_node.prev
240+
freq_node.cache_head.destroy()
241+
freq_node.destroy()
242+
freq_node = prev_freq_node
243+
else:
244+
freq_node = freq_node.prev
245+
return removed
95246

96247
# expose operations to wrapper
97248
wrapper.cache_clear = cache_clear
98249
wrapper.cache_info = cache_info
250+
wrapper.cache_is_empty = cache_is_empty
251+
wrapper.cache_is_full = cache_is_full
252+
wrapper.cache_contains_argument = cache_contains_argument
253+
wrapper.cache_contains_key = cache_contains_key
254+
wrapper.cache_contains_result = cache_contains_result
255+
wrapper.cache_for_each = cache_for_each
256+
wrapper.cache_remove_if = cache_remove_if
257+
wrapper.cache_make_key = make_key
99258
wrapper._cache = cache
100259
wrapper._lfu_root = lfu_freq_list_root
101260
wrapper._root_name = '_lfu_root'
102-
wrapper._get_caching_list = get_caching_list
103261

104262
return wrapper
105263

0 commit comments

Comments
 (0)