{
int i;
- for (i = 0; i < size; i++) {
- /* Bottom bit of each element of this array stores whether that element
- * is opposite to its parent, which starts off as false */
- dsf[i] = i << 1;
- }
+ for (i = 0; i < size; i++) dsf[i] = 6;
+ /* Bottom bit of each element of this array stores whether that
+ * element is opposite to its parent, which starts off as
+ * false. Second bit of each element stores whether that element
+ * is the root of its tree or not. If it's not the root, the
+ * remaining 30 bits are the parent, otherwise the remaining 30
+ * bits are the number of elements in the tree. */
}
int *snew_dsf(int size)
edsf_merge(dsf, v1, v2, FALSE);
}
+int dsf_size(int *dsf, int index) {
+ return dsf[dsf_canonify(dsf, index)] >> 2;
+}
+
int edsf_canonify(int *dsf, int index, int *inverse_return)
{
int start_index = index, canonical_index;
/* Find the index of the canonical element of the 'equivalence class' of
* which start_index is a member, and figure out whether start_index is the
* same as or inverse to that. */
- while ((dsf[index] >> 1) != index) {
+ while ((dsf[index] & 2) == 0) {
inverse ^= (dsf[index] & 1);
- index = dsf[index] >> 1;
+ index = dsf[index] >> 2;
/* fprintf(stderr, "index = %2d, ", index); */
/* fprintf(stderr, "inverse = %d\n", inverse); */
}
* canonical member. */
index = start_index;
while (index != canonical_index) {
- int nextindex = dsf[index] >> 1;
+ int nextindex = dsf[index] >> 2;
int nextinverse = inverse ^ (dsf[index] & 1);
- dsf[index] = (canonical_index << 1) | inverse;
+ dsf[index] = (canonical_index << 2) | inverse;
inverse = nextinverse;
index = nextindex;
}
void edsf_merge(int *dsf, int v1, int v2, int inverse)
{
int i1, i2;
-
+
/* fprintf(stderr, "dsf = %p\n", dsf); */
/* fprintf(stderr, "Merge [%2d,%2d], %d\n", v1, v2, inverse); */
v1 = edsf_canonify(dsf, v1, &i1);
+ assert(dsf[v1] & 2);
inverse ^= i1;
v2 = edsf_canonify(dsf, v2, &i2);
+ assert(dsf[v2] & 2);
inverse ^= i2;
/* fprintf(stderr, "Doing [%2d,%2d], %d\n", v1, v2, inverse); */
if (v1 == v2)
assert(!inverse);
- else
- dsf[v2] = (v1 << 1) | !!inverse;
+ else {
+ assert(inverse == 0 || inverse == 1);
+ /*
+ * 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;
+ }
+ dsf[v1] += (dsf[v2] >> 2) << 2;
+ dsf[v2] = (v1 << 2) | !!inverse;
+ }
v2 = edsf_canonify(dsf, v2, &i2);
assert(v2 == v1);