1
2
3 __all__ = ['Equivalence']
4 __docformat__ = "restructuredtext en"
5 __author__ = 'George Sakkis <george.sakkis AT gmail DOT com>'
6
7 from collections import defaultdict
8
9
11 '''Representation of a general equivalence relation.
12
13 An `Equivalence` instance can be used to maintain a partition of objects
14 into equivalence sets. Two objects ``x`` and ``y`` are considered
15 equivalent either implicitly through a key function or explicitly. For the
16 implicit case, ``x`` and ``y`` are equivalent if ``key(x) == key(y)`` for
17 some provided function ``key`` (by default the identity function ``lambda x:x``).
18 For the explicit case, ``x`` and ``y`` are considered equivalent after a call
19 to `merge(x,y)`, regardless of their keys.
20
21 This class makes sure that the equivalence properties (reflexivity, symmetry,
22 transitivity) are maintained, provided that ``key(x)`` remains fixed for a
23 given object ``x`` (i.e. ``key`` is deterministic and does not depend on
24 mutable state of ``x``).
25 '''
26
28 '''Initialize a new equivalence relation.
29
30 :param key: A callable that takes a single argument and returns its
31 equivalence key (default: identity function).
32 '''
33 self._keyfunc = key
34
35 self._key2pkey = {}
36
37
38 self._pkey2keys = defaultdict(set)
39
40 self._pkey2members = defaultdict(set)
41
43 '''Update this equivalence with the given objects.'''
44 for obj in objects:
45 self._pkey2members[self.partition_key(obj)].add(obj)
46
47 - def merge(self, *objects):
48 '''Merge all the given objects into the same equivalence set.'''
49 objects = iter(objects)
50 try: obj = objects.next()
51 except StopIteration: return
52 new_pkey = self.partition_key(obj)
53 partition_members = self._pkey2members[new_pkey]
54 partition_members.add(obj)
55 key2pkey = self._key2pkey
56 partition_keys = self._pkey2keys[new_pkey]
57 for obj in objects:
58 partition_members.add(obj)
59 old_pkey = self.partition_key(obj)
60 if old_pkey != new_pkey:
61 key2pkey[old_pkey] = new_pkey
62 partition_keys.add(old_pkey)
63 for key in self._pkey2keys.pop(old_pkey, ()):
64 key2pkey[key] = new_pkey
65 partition_keys.add(key)
66 partition_members.update(self._pkey2members.pop(old_pkey, ()))
67 if not partition_keys:
68 del self._pkey2members[new_pkey]
69
71 '''Checks whether all objects are equivalent.
72
73 An object doesn't have to be inserted first (through `update` or `merge`)
74 in order to appear as an argument. In this case, its ``key`` is used to
75 determine the partition it would belong if it was inserted.
76
77 :rtype: bool
78 '''
79 if not objects:
80 raise ValueError('No objects given')
81 return len(set(self.partition_key(obj) for obj in objects)) == 1
82
84 '''Returns the partitioning of `objects` into equivalence groups.
85
86 :type objects: Iterable or None
87 :param objects: If not None, it must be an iterable of objects to be
88 partitioned. Otherwise, it defaults to the set of objects already
89 inserted in the equivalence (through `update` and `merge`).
90
91 :returns: A list of partitions, each partition being a list of objects.
92 :rtype: list of lists
93 '''
94 if not objects:
95 objects = (obj for members in self._pkey2members.itervalues()
96 for obj in members)
97 key2partition = defaultdict(list)
98 for obj in objects:
99 key2partition[self.partition_key(obj)].append(obj)
100 return key2partition.values()
101
103 '''Return the set of objects in the equivalence that are equivalent to
104 `obj`.
105
106 :rtype: set
107 '''
108 return self._pkey2members.get(self.partition_key(obj)) or set()
109
111 '''Return the key of the equivalence partition `obj` belongs to.'''
112 key = self._keyfunc(obj) if self._keyfunc else obj
113 return self._key2pkey.get(key,key)
114