any equivalence class is always the element with the smallest index.
This is slower (the previous behaviour, suggested by Jonas Koelker,
was to choose the new root element to maximise performance), but
still more than acceptably fast and more useful.
git-svn-id: svn://svn.tartarus.org/sgt/puzzles@8792
cda61777-01e9-0310-a592-
d414129be87e
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.
+ *
+ * (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;