1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
from rpython.tool.algo.unionfind import UnionFind
def test_cleanup():
state = []
class ReferencedByExternalState(object):
def __init__(self, obj):
state.append(self)
self.obj = obj
def absorb(self, other):
state.remove(other)
uf = UnionFind(ReferencedByExternalState)
uf.find(1)
for i in xrange(1, 10, 2):
uf.union(i, 1)
uf.find(2)
for i in xrange(2, 20, 2):
uf.union(i, 2)
assert len(state) == 2 # we have exactly 2 partitions
def test_asymmetric_absorb():
class Info(object):
def __init__(self, obj):
self.values = [obj]
def absorb(self, other):
self.values += other.values
uf = UnionFind(Info)
uf.union(2, 3)
uf.union(1, 2)
assert uf[1].values == uf[2].values == uf[3].values == [1, 2, 3]
|
