#!/usr/bin/python
# Finite multi-mappings, like the stuff I wrote about "mvfs:
# multivalued functions" in 2003, using + and * for (commutative,
# associative) union and (non-commutative, associative) composition,
# and supporting transitive closure.
# This code only supports finite mvfs, and unlike what I'd originally
# written, it suppresses duplicates. .values() from my old post is
# called .items() to match Python usage here; .cut() and .paste() are
# not included (but they aren't sufficient anyway); "compose" is
# written "*"; and lists (or other sequences) are mapped to finite
# multimappings with list indices as the keys, not "None".
class FiniteMultiMapping(object):
def __init__(self, *pairs, **morepairs):
pairs = list(pairs) + morepairs.items()
pairs.sort()
self.mapping, previtem = {}, None
for item in pairs:
if item != previtem:
previtem = key, val = item
if not self.mapping.has_key(key): self.mapping[key] = []
self.mapping[key].append(val)
self._keys = self.mapping.keys()
self._keys.sort()
def __getitem__(self, key):
try: return self.mapping[key]
except KeyError: return []
def keys(self): return self._keys
def items(self):
return sum([[(key, val) for val in self[key]] for key in self.keys()],
[])
def __eq__(self, other):
if not hasattr(other, 'mapping') or not hasattr(other, 'items'): return
False
return self.items() == other.items()
def __ne__(self, other): return not (self == other)
def __add__(self, other):
return FiniteMultiMapping(*(self.items() + other.items()))
def __mul__(self, other):
rv = sum([[(key, val2) for val2 in other[val]] for key, val in
self.items()], [])
return FiniteMultiMapping(*rv)
def __repr__(self):
return '<ffm {%s}>' % ', '.join(['%r -> %r' % item for item in
self.items()])
def invert(self):
return FiniteMultiMapping(*[(val, key) for key, val in self.items()])
def tclosure(self):
rv = self
while 1:
nrv = rv + rv * rv
if nrv == rv: return nrv
rv = nrv
def ffm_from_list(inlist):
return FiniteMultiMapping(*[(ii, inlist[ii]) for ii in range(len(inlist))])
def ok(a, b): assert a == b, (a, b)
def test():
x = FiniteMultiMapping()
assert x[1] == []
x = FiniteMultiMapping(x=1, y=2)
assert x[1] == []
assert x['x'] == [1]
assert x.items() == [('x', 1), ('y', 2)]
# ==, !=
assert x == x
assert not (x != x)
assert x != FiniteMultiMapping()
assert not (x == FiniteMultiMapping())
assert x == FiniteMultiMapping(x=1, y=2)
assert x == FiniteMultiMapping(('y', 2), ('x', 1))
assert not (x == {'x': 1, 'y': 2})
assert x != {'x': 1, 'y': 2}
assert FiniteMultiMapping(x=5) != {'x': 5}
assert not (FiniteMultiMapping(x=5) == {'x': 5})
assert not (x == 3)
# initialization
assert FiniteMultiMapping(x=45) == FiniteMultiMapping(('x', 45))
ok(len(FiniteMultiMapping(('x', 45), ('x', 45)).items()), 1)
ok(len(FiniteMultiMapping(('x', 45), ('x', 46)).items()), 2)
# addition
assert x + {} == x
assert x + x == x
y = x + {'x': 3}
ok(y['x'], [1, 3])
ok(x['x'], [1])
# multiplication (composition)
rot13fw = FiniteMultiMapping(a='n', b='o', c='p')
rot13bw = FiniteMultiMapping(n='a', o='b', p='c')
rot13 = rot13fw + rot13bw
ok(rot13.items(), [('a', 'n'), ('b', 'o'), ('c', 'p'),
('n', 'a'), ('o', 'b'), ('p', 'c')])
bono = ffm_from_list('bonocabana')
ok(bono.items(), [(0, 'b'), (1, 'o'), (2, 'n'), (3, 'o'), (4, 'c'),
(5, 'a'), (6, 'b'), (7, 'a'), (8, 'n'), (9, 'a')])
ok(bono * rot13, ffm_from_list('obabpnonan'))
ok((bono * rot13) * rot13, bono)
ok(bono * (rot13 * rot13), bono)
ok(rot13 * rot13, FiniteMultiMapping(a='a', b='b', c='c',
n='n', o='o', p='p'))
# inversion
ok(rot13fw.invert(), rot13bw)
ok(rot13.invert(), rot13)
# transitive closure
succ = FiniteMultiMapping((0, 1), (1, 2), (2, 3))
gt = succ.tclosure()
ok(gt[0], [1, 2, 3])
ok(gt.items(), [(0, 1), (0, 2), (0, 3),
(1, 2), (1, 3),
(2, 3)])
test()
