ref: 14e1e05510ac02a5502823bafe46d98c6fab3e5c
parent: 088fdeee38599b1711ba8766d36c652f1355e36e
author: Simon Tatham <anakin@pobox.com>
date: Thu Apr 20 11:32:10 EDT 2023
Introduce a new dsf_equivalent() function. Not very interesting, but the idiom for checking equivalence via two calls to dsf_canonify is cumbersome enough to be worth abbreviating.
--- a/bridges.c
+++ b/bridges.c
@@ -1167,7 +1167,7 @@
if (!is_join) continue;
d2 = DINDEX(is_join->x, is_join->y);
- if (dsf_canonify(dsf,d1) == dsf_canonify(dsf,d2)) {+ if (dsf_equivalent(dsf, d1, d2)) {; /* we have a loop. See comment in map_hasloops. */
/* However, we still want to merge all squares joining
* this side-that-makes-a-loop. */
@@ -1291,7 +1291,7 @@
if (n > 0 && !is_max) {d1 = DINDEX(is->x, is->y);
d2 = DINDEX(is_orth->x, is_orth->y);
- if (dsf_canonify(dsf, d1) != dsf_canonify(dsf, d2))
+ if (!dsf_equivalent(dsf, d1, d2))
dsf_merge(dsf, d1, d2);
}
}
@@ -1410,7 +1410,7 @@
d1 = DINDEX(is->x, is->y);
d2 = DINDEX(is_orth->x, is_orth->y);
- if (dsf_canonify(dsf, d1) == dsf_canonify(dsf, d2)) {+ if (dsf_equivalent(dsf, d1, d2)) {/* two islands are connected already; don't join them. */
return true;
}
--- a/divvy.c
+++ b/divvy.c
@@ -632,7 +632,7 @@
dsf_merge(tmpdsf, y*w+x, (y+1)*w+x);
for (i = 0; i < wh; i++) {j = dsf_canonify(retdsf, i);
- assert(dsf_canonify(tmpdsf, j) == dsf_canonify(tmpdsf, i));
+ assert(dsf_equivalent(tmpdsf, j, i));
}
cleanup:
--- a/dsf.c
+++ b/dsf.c
@@ -58,6 +58,11 @@
return edsf_canonify(dsf, index, NULL);
}
+bool dsf_equivalent(DSF *dsf, int i1, int i2)
+{+ return edsf_canonify(dsf, i1, NULL) == edsf_canonify(dsf, i2, NULL);
+}
+
void dsf_merge(DSF *dsf, int v1, int v2)
{edsf_merge(dsf, v1, v2, false);
--- a/keen.c
+++ b/keen.c
@@ -781,7 +781,7 @@
p0 = y*w+x;
p1 = (y+1)*w+x;
}
- edge = (dsf_canonify(dsf, p0) != dsf_canonify(dsf, p1));
+ edge = !dsf_equivalent(dsf, p0, p1);
}
if (edge) {@@ -1961,13 +1961,13 @@
cw = tw = TILESIZE-1-2*GRIDEXTRA;
ch = th = TILESIZE-1-2*GRIDEXTRA;
- if (x > 0 && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, y*w+x-1))
+ if (x > 0 && dsf_equivalent(clues->dsf, y*w+x, y*w+x-1))
cx -= GRIDEXTRA, cw += GRIDEXTRA;
- if (x+1 < w && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, y*w+x+1))
+ if (x+1 < w && dsf_equivalent(clues->dsf, y*w+x, y*w+x+1))
cw += GRIDEXTRA;
- if (y > 0 && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, (y-1)*w+x))
+ if (y > 0 && dsf_equivalent(clues->dsf, y*w+x, (y-1)*w+x))
cy -= GRIDEXTRA, ch += GRIDEXTRA;
- if (y+1 < w && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, (y+1)*w+x))
+ if (y+1 < w && dsf_equivalent(clues->dsf, y*w+x, (y+1)*w+x))
ch += GRIDEXTRA;
clip(dr, cx, cy, cw, ch);
@@ -1992,13 +1992,13 @@
* Draw the corners of thick lines in corner-adjacent squares,
* which jut into this square by one pixel.
*/
- if (x > 0 && y > 0 && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y-1)*w+x-1))
+ if (x > 0 && y > 0 && !dsf_equivalent(clues->dsf, y*w+x, (y-1)*w+x-1))
draw_rect(dr, tx-GRIDEXTRA, ty-GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
- if (x+1 < w && y > 0 && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y-1)*w+x+1))
+ if (x+1 < w && y > 0 && !dsf_equivalent(clues->dsf, y*w+x, (y-1)*w+x+1))
draw_rect(dr, tx+TILESIZE-1-2*GRIDEXTRA, ty-GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
- if (x > 0 && y+1 < w && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y+1)*w+x-1))
+ if (x > 0 && y+1 < w && !dsf_equivalent(clues->dsf, y*w+x, (y+1)*w+x-1))
draw_rect(dr, tx-GRIDEXTRA, ty+TILESIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
- if (x+1 < w && y+1 < w && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y+1)*w+x+1))
+ if (x+1 < w && y+1 < w && !dsf_equivalent(clues->dsf, y*w+x, (y+1)*w+x+1))
draw_rect(dr, tx+TILESIZE-1-2*GRIDEXTRA, ty+TILESIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
/* Draw the box clue. */
--- a/palisade.c
+++ b/palisade.c
@@ -273,7 +273,7 @@
static bool connected(solver_ctx *ctx, int i, int j, int dir)
{if (j == COMPUTE_J) j = i + dx[dir] + ctx->params->w*dy[dir];
- return dsf_canonify(ctx->dsf, i) == dsf_canonify(ctx->dsf, j);
+ return dsf_equivalent(ctx->dsf, i, j);
}
static void disconnect(solver_ctx *ctx, int i, int j, int dir)
@@ -557,10 +557,10 @@
for (y = 0; y < h; y++) { for (x = 0; x < w; x++) {if (x+1 < w && (border[y*w+x] & BORDER_R) &&
- dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, y*w+(x+1)))
+ dsf_equivalent(dsf, y*w+x, y*w+(x+1)))
goto error;
if (y+1 < h && (border[y*w+x] & BORDER_D) &&
- dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, (y+1)*w+x))
+ dsf_equivalent(dsf, y*w+x, (y+1)*w+x))
goto error;
}
}
@@ -659,7 +659,7 @@
for (dir = 0; dir < 4; ++dir) {int rr = r + dy[dir], cc = c + dx[dir], ii = rr * w + cc;
if (OUT_OF_BOUNDS(cc, rr, w, h) ||
- dsf_canonify(dsf, i) != dsf_canonify(dsf, ii)) {+ !dsf_equivalent(dsf, i, ii)) {++numbers[i];
soln[i] |= BORDER(dir);
}
--- a/puzzles.h
+++ b/puzzles.h
@@ -439,6 +439,11 @@
int dsf_canonify(DSF *dsf, int val);
int dsf_size(DSF *dsf, int val);
+/* Check whether two elements are in the same equivalence class.
+ * Equivalent to, but less verbose than, calling dsf_canonify twice
+ * and seeing if their two canonical elements are the same. */
+bool dsf_equivalent(DSF *dsf, int v1, int v2);
+
/* Allow the caller to specify that two elements should be in the same
* equivalence class. If 'inverse' is true, the elements are actually opposite
* to one another in some sense. This function will fail an assertion if the
--- a/signpost.c
+++ b/signpost.c
@@ -173,7 +173,7 @@
/* can't create a new connection between cells in the same region
* as that would create a loop. */
- if (dsf_canonify(state->dsf, from) == dsf_canonify(state->dsf, to))
+ if (dsf_equivalent(state->dsf, from, to))
return false;
/* if both cells are actual numbers, can't drag if we're not