X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=dsf.c;h=aa22392661407f04abddec745b0a6e292db12aa5;hb=a0a581c8b5422bf0c5ed3fde6aa25811e4eb89fc;hp=32179a6a4ba106484685c5200c88e472207778d7;hpb=df31d4f4195ea2cc3a1213da14717813aacbf404;p=sgt-puzzles.git

diff --git a/dsf.c b/dsf.c
index 32179a6..aa22392 100644
--- a/dsf.c
+++ b/dsf.c
@@ -161,7 +161,21 @@ void edsf_merge(int *dsf, int v1, int v2, int inverse)
         assert(!inverse);
     else {
 	assert(inverse == 0 || inverse == 1);
-	if ((dsf[v2] >> 2) > (dsf[v1] >> 2)) {
+	/*
+	 * We always make the smaller of v1 and v2 the new canonical
+	 * element. This ensures that the canonical element of any
+	 * class in this structure is always the first element in
+	 * it. 'Keen' depends critically on this property.
+	 *
+	 * (Jonas Koelker previously had this code choosing which
+	 * way round to connect the trees by examining the sizes of
+	 * the classes being merged, so that the root of the
+	 * larger-sized class became the new root. This gives better
+	 * asymptotic performance, but I've changed it to do it this
+	 * way because I like having a deterministic canonical
+	 * element.)
+	 */
+	if (v1 > v2) {
 	    int v3 = v1;
 	    v1 = v2;
 	    v2 = v3;