"""
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