Author: Ronan Lamy <[email protected]>
Branch: ssa-flow
Changeset: r74530:4ee0a64a020b
Date: 2014-11-15 02:59 +0000
http://bitbucket.org/pypy/pypy/changeset/4ee0a64a020b/
Log: UnionFind: ensure meaningful result when absorb() isn't commutative
diff --git a/rpython/tool/algo/test/test_unionfind.py
b/rpython/tool/algo/test/test_unionfind.py
--- a/rpython/tool/algo/test/test_unionfind.py
+++ b/rpython/tool/algo/test/test_unionfind.py
@@ -18,6 +18,17 @@
uf.find(2)
for i in xrange(2, 20, 2):
uf.union(i, 2)
- assert len(state) == 2 # we have exactly 2 partitions
+ 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]
diff --git a/rpython/tool/algo/unionfind.py b/rpython/tool/algo/unionfind.py
--- a/rpython/tool/algo/unionfind.py
+++ b/rpython/tool/algo/unionfind.py
@@ -72,19 +72,16 @@
if rep1 is rep2:
return new1 or new2, rep1, info1
- w1 = self.weight[rep1]
- w2 = self.weight[rep2]
-
- w = w1 + w2
-
- if w1 < w2:
- rep1, rep2, info1, info2, = rep2, rep1, info2, info1
-
if info1 is not None:
info1.absorb(info2)
+ w1 = self.weight[rep1]
+ w2 = self.weight[rep2]
+ w = w1 + w2
+ if w1 < w2:
+ rep1, rep2 = rep2, rep1
+
self.link_to_parent[rep2] = rep1
-
del self.weight[rep2]
del self.root_info[rep2]
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
