generic_utils: add memoize decorator, OrderedSet, find
diff --git a/generic_utils.py b/generic_utils.py
index cebfb7f..d4b1892 100644
--- a/generic_utils.py
+++ b/generic_utils.py
@@ -31,6 +31,7 @@
Intended to be imported into another namespace
"""
+import functools
import sys
import of_g
@@ -73,3 +74,102 @@
@param out_str The stringified output to write
"""
of_g.loxigen_log_file.write(str(obj) + "\n")
+
+################################################################
+#
+# Memoize
+#
+################################################################
+
+def memoize(obj):
+ """ A function/method decorator that memoizes the result"""
+ cache = obj.cache = {}
+
+ @functools.wraps(obj)
+ def memoizer(*args, **kwargs):
+ key = str(args) + str(kwargs)
+ if key not in cache:
+ cache[key] = obj(*args, **kwargs)
+ return cache[key]
+ return memoizer
+
+################################################################
+#
+# OrderedSet
+#
+################################################################
+
+import collections
+
+class OrderedSet(collections.MutableSet):
+ """
+ A set implementations that retains insertion order. From the receipe
+ http://code.activestate.com/recipes/576694/
+ as referred to in the python documentation
+ """
+
+ def __init__(self, iterable=None):
+ self.end = end = []
+ end += [None, end, end] # sentinel node for doubly linked list
+ self.map = {} # key --> [key, prev, next]
+ if iterable is not None:
+ self |= iterable
+
+ def __len__(self):
+ return len(self.map)
+
+ def __contains__(self, key):
+ return key in self.map
+
+ def add(self, key):
+ if key not in self.map:
+ end = self.end
+ curr = end[1]
+ curr[2] = end[1] = self.map[key] = [key, curr, end]
+
+ def discard(self, key):
+ if key in self.map:
+ key, prev, next = self.map.pop(key)
+ prev[2] = next
+ next[1] = prev
+
+ def __iter__(self):
+ end = self.end
+ curr = end[2]
+ while curr is not end:
+ yield curr[0]
+ curr = curr[2]
+
+ def __reversed__(self):
+ end = self.end
+ curr = end[1]
+ while curr is not end:
+ yield curr[0]
+ curr = curr[1]
+
+ def pop(self, last=True):
+ if not self:
+ raise KeyError('set is empty')
+ key = self.end[1][0] if last else self.end[2][0]
+ self.discard(key)
+ return key
+
+ def __repr__(self):
+ if not self:
+ return '%s()' % (self.__class__.__name__,)
+ return '%s(%r)' % (self.__class__.__name__, list(self))
+
+ def __eq__(self, other):
+ if isinstance(other, OrderedSet):
+ return len(self) == len(other) and list(self) == list(other)
+ return set(self) == set(other)
+
+def find(iterable, func):
+ """
+ find the first item in iterable for which func returns something true'ish.
+ @raise KeyError if no item in iterable fulfills the condition
+ """
+ for i in iterable:
+ if func(i):
+ return i
+ raise KeyError("Couldn't find value that matches: %s" % repr(func))