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;