Source code for libutilitaspy.data_structures.maps

"""
Provides utilities for functions, dictionaries, and associative tables.
"""

from collections import Callable, Mapping, MutableMapping, Iterable
from abc import ABCMeta
from libutilitaspy.metaclassconfig import MetaClass
from tries import Trie

__all__ = ['dictunion', 'Map']

builtin_dict = dict

def dict(obj=None):
    if isinstance(obj, Map):
        return obj.dict()
    if obj is None:
        return builtin_dict()
    return builtin_dict(obj)

[docs]def dictunion(dict1, dict2): """ Returns a dictionary containing all key, value pairs of the given dictionaries. :param dict dict1: Some dictionary :param dict dict2: Some dictionary :returns: The union of dict1 and dict2 :rtype: dict """ return dict(dict1.items() + dict2.items())
def ispair(x): """ Returns True if x is a pair and False otherwise. :param x: Any object :returns: ``type(x) is tuple and len(x) == 2`` :rtype: bool """ return type(x) is tuple and len(x) == 2 class MapImplementation(MutableMapping, Callable): __metaclass__ = ABCMeta class TableMapImplementation(MapImplementation): __metaclass__ = MetaClass def __init__(self, mapping, data_struct=dict): assert isinstance(mapping, Mapping) self.__table = data_struct() self.__preimage = {} for x in mapping: self[x] = mapping[x] # Creates a shallow copy of the dictionary, calling self.__setitem__ which builds the preimage def __getitem__(self, key): return self.__table[key] def __setitem__(self, key, value): self.__table[key] = value if value in self.__preimage: self.__preimage[value].add(key) else: self.__preimage[value] = set([key]) __call__ = __getitem__ def __delitem__(self, key): old_value = self.__table[key] self.__preimage[old_value].remove(key) del self.__table[key] def __iter__(self): return iter(self.__table) def __len__(self): return len(self.__table) def get_preimage(self, value): """Returns the set of keys x such that value is x's image in the map.""" return self.__preimage[value] class DictionaryMapImplementation(TableMapImplementation): __metaclass__ = MetaClass def __init__(self, mapping): TableMapImplementation.__init__(self, mapping, data_struct=dict) class TrieMapImplementation(TableMapImplementation): __metaclass__ = MetaClass def __init__(self, mapping): TableMapImplementation.__init__(self, mapping, data_struct=Trie) class FunctionMapImplementation(MapImplementation): __metaclass__ = MetaClass def __init__(self, function): assert isinstance(function, Callable) self.__function = function def __call__(self, x): return self.__function(x) __getitem__ = __call__ def __setitem__(self, key, value): old_function = self.__function self.__function = lambda z: value if z == key else old_function(z) def __delitem__(self, key): old_function = self.__function def new_function(z): if z == key: raise KeyError('z') else: return old_function(z) self.__function = new_function def __iter__(self): raise MapException('iter is not supported for function implementations of a map.') def __len__(self): raise MapException('len is not supported for function implementations of a map.') class MemoizedFunctionMapImplementation(MapImplementation): __metaclass__ = MetaClass def __init__(self, function): assert isinstance(function, Callable) self.__function = function self.__dictionary = {} self.__preimage = {} def __call__(self, x): if x in self.__dictionary: return self.__dictionary[x] else: y = self.__function(x) self.__dictionary[x] = y if y in self.__preimage: self.__preimage[y].add(x) else: self.__preimage[y] = set([x]) return y __getitem__ = __call__ def __setitem__(self, key, value): old_function = self.__function self.__function = lambda z: value if z == key else old_function(z) # This is unnecessary, since the key is memoized, so maybe we should remove it, because it's just adding another closure to memory. self.__dictionary[key] = value if value in self.__preimage: self.__preimage[value].add(key) else: self.__preimage[value] = set([key]) def __delitem__(self, key): old_function = self.__function def new_function(z): if z == key: raise KeyError(repr(z)) else: return old_function(z) self.__function = new_function old_value = self.__dictionary[key] self.__preimage[old_value].remove(key) del self.__dictionary[key] def __iter__(self): raise MapException('iter is not supported for function implementations of a map.') def __len__(self): raise MapException('len is not supported for function implementations of a map.') def get_preimage(self, value): """Returns the set of keys x such that value is x's image in the map.""" return self.__preimage[value]
[docs]class Map(MutableMapping, Callable): """ Map objects generalize functions, dictionaries and associative tables. A map object behaves as both. Map objects can be built from either: * a :py:class:`Mapping` object, or * a :py:class:`Callable` object For example:: m1 = Map({1: 'a', 2: 'b', 3: 'a'}) m2 = Map(lambda x: 'a' if x in (1,3) else 'b') It can be accessed with both dictionary and function call notation, e.g.:: y1 = m1[3] y2 = m1(3) Maps are mutable, even if defined by a function, e.g.:: m1[2] = 'c' m2[2] = 'd' # even though m2 was defined with a function rather than a dictionary. If built from a :py:class:`Mapping` object, the underlying :py:class:`Map` implementation can be either: * a dictionary (default), or * a :py:class:`libutilitaspy.data_structures.tries.Trie` If built from a :py:class:`Callable` object, the underlying :py:class:`Map` implementation can be either: * a function (default), or * a memoized function For example:: m1_1 = Map({1: 'a', 2: 'b', 3: 'a'}, 'dict') m1_2 = Map({1: 'a', 2: 'b', 3: 'a'}, 'trie') m2_1 = Map(lambda x: 'a' if x in (1,3) else 'b', 'func') m2_2 = Map(lambda x: 'a' if x in (1,3) else 'b', 'mem') Many combinations are possible. For example, you can create a map with a dictionary representation from a trie. .. note:: A trie representation is useful when the mapping keys are sequences of hashable objects. A memoized function representation is useful for callables which are pure functions (always return the same output on the same input), are called frequently and perform a significant amount of computation. The trade-off is that memory is used to cache previously computed results. """ __metaclass__ = MetaClass IMPLEMENTATIONS = \ { 'dict': DictionaryMapImplementation, 'func': FunctionMapImplementation, 'memfunc': MemoizedFunctionMapImplementation, 'trie': TrieMapImplementation } def __init__(self, m, imp=None): """ :param m: the mapping or callable object to make into a map. :type m: :py:class:`Mapping` or :py:class:`Callable` :param imp: The underlying implementation used :type imp: `str`: for `Mapping` objects it can be 'dict' (default) or 'trie'; for `Callable` objects it can be 'func' (default) or 'mem'. """ assert isinstance(m, Mapping) \ or isinstance(m, Callable) \ or isinstance(m, Iterable) and all(ispair(x) for x in m) self.imp = imp if isinstance(m, Mapping): if imp == 'trie': implementation_class = Map.IMPLEMENTATIONS['trie'] else: implementation_class = Map.IMPLEMENTATIONS['dict'] self.imp = 'dict' elif isinstance(m, Callable): if imp == 'mem': implementation_class = Map.IMPLEMENTATIONS['memfunc'] else: implementation_class = Map.IMPLEMENTATIONS['func'] self.imp = 'func' self.__implementation = implementation_class(m) def __call__(self, x): """ Returns the value of x in the map. """ return self.__implementation(x) def __getitem__(self, key): """Returns the value of x in the map.""" return self.__implementation[key] def __setitem__(self, key, value): """Updates the map with the given key |-> value pair.""" self.__implementation[key] = value def __mul__(self, other): """Returns the composition of the two maps, as a new Map, self first, then other.""" return Map(lambda x: other(self(x))) def __delitem__(self, item): del self.__implementation[item] def __iter__(self): return iter(self.__implementation) def __len__(self): return len(self.__implementation) def __eq__(self, other): """ Tests map equality. If the map is given by a dictionary, it tests whether all key, value pairs are equal. If it is a function it tests identity of the function objects. """ return self.__implementation == other.__implementation
[docs] def get_preimage(self, value): """ :returns: the *pre-image* of `value`, this is, the set of keys or indices or source values of the map, whose image is `value`. :rtype: set :note: This method is available if the underlying implementation is a dictionary, a trie or a memoized function, but it is not available if it is a (non-memoized) function. """ return self.__implementation.get_preimage(value)
[docs] def reflexive_closure(self): """Returns the reflexive closure of the map, i.e. the map extended with the identity map.""" return ReflexiveClosureMap(self)
def items(self): return [(key, self.__implementation[key]) for key in iter(self)] def dict(self): return dict(self.items())
class ReflexiveClosureMap(Map): """ A reflexive-closure map is a map extended with the identity map, i.e. a map m such that for any x not in the original domain, m(x) = x. """ def __init__(self, m, imp=None): Map.__init__(self, m, imp) def __call__(self, x): try: return super(ReflexiveClosureMap,self).__call__(x) except: return x def __getitem__(self, x): try: return super(ReflexiveClosureMap,self).__getitem__(x) except: return x class MapException(Exception): pass