ref: c5e253a9f9d3d651227ccad56e2c7526ee1f3eba
parent: 14e1e05510ac02a5502823bafe46d98c6fab3e5c
author: Simon Tatham <anakin@pobox.com>
date: Thu Apr 20 13:27:21 EDT 2023
Reorganise the dsf API into three kinds of dsf. This is preparing to separate out the auxiliary functionality, and perhaps leave space for making more of it in future. The previous name 'edsf' was too vague: the 'e' stood for 'extended', and didn't say anything about _how_ it was extended. It's now called a 'flip dsf', since it tracks whether elements in the same class are flipped relative to each other. More importantly, clients that are going to use the flip tracking must say so when they allocate the dsf. And Keen's need to track the minimal element of an equivalence class is going to become a non-default feature, so there needs to be a new kind of dsf that specially tracks those, and Keen will have to call it. While I'm here, I've renamed the three dsf creation functions so that they start with 'dsf_' like all the rest of the dsf API.
--- a/bridges.c
+++ b/bridges.c
@@ -1774,8 +1774,8 @@
ret->completed = false;
ret->solver = snew(struct solver_state);
- ret->solver->dsf = snew_dsf(wh);
- ret->solver->tmpdsf = snew_dsf(wh);
+ ret->solver->dsf = dsf_new(wh);
+ ret->solver->tmpdsf = dsf_new(wh);
ret->solver->refcount = 1;
--- a/divvy.c
+++ b/divvy.c
@@ -611,7 +611,7 @@
assert(own[i] >= 0 && own[i] < n);
tmp[own[i]] = i;
}
- retdsf = snew_dsf(wh);
+ retdsf = dsf_new(wh);
for (i = 0; i < wh; i++) {dsf_merge(retdsf, i, tmp[own[i]]);
}
@@ -621,7 +621,7 @@
* the ominoes really are k-ominoes and we haven't
* accidentally split one into two disconnected pieces.
*/
- tmpdsf = snew_dsf(wh);
+ tmpdsf = dsf_new(wh);
for (y = 0; y < h; y++)
for (x = 0; x+1 < w; x++)
if (own[y*w+x] == own[y*w+(x+1)])
--- a/dominosa.c
+++ b/dominosa.c
@@ -1429,12 +1429,12 @@
if (!sc->dc_scratch)
sc->dc_scratch = snewn(sc->dc, int);
if (!sc->dsf_scratch)
- sc->dsf_scratch = snew_dsf(sc->pc);
+ sc->dsf_scratch = dsf_new_flip(sc->pc);
/*
* Start by identifying chains of placements which must all occur
* together if any of them occurs. We do this by making
- * dsf_scratch an edsf binding the placements into an equivalence
+ * dsf_scratch a flip dsf binding the placements into an equivalence
* class for each entire forcing chain, with the two possible sets
* of dominoes for the chain listed as inverses.
*/
@@ -1442,9 +1442,9 @@
for (si = 0; si < sc->wh; si++) {struct solver_square *sq = &sc->squares[si];
if (sq->nplacements == 2)
- edsf_merge(sc->dsf_scratch,
- sq->placements[0]->index,
- sq->placements[1]->index, true);
+ dsf_merge_flip(sc->dsf_scratch,
+ sq->placements[0]->index,
+ sq->placements[1]->index, true);
}
/*
* Now read out the whole dsf into pc_scratch, flattening its
@@ -1457,7 +1457,7 @@
*/
for (pi = 0; pi < sc->pc; pi++) {bool inv;
- int c = edsf_canonify(sc->dsf_scratch, pi, &inv);
+ int c = dsf_canonify_flip(sc->dsf_scratch, pi, &inv);
sc->pc_scratch[pi] = c * 2 + (inv ? 1 : 0);
}
--- a/dsf.c
+++ b/dsf.c
@@ -34,7 +34,7 @@
memcpy(to->p, from->p, to->size * sizeof(int));
}
-DSF *snew_dsf(int size)
+DSF *dsf_new(int size)
{DSF *ret = snew(DSF);
ret->size = size;
@@ -45,6 +45,9 @@
return ret;
}
+DSF *dsf_new_min(int size) { return dsf_new(size); }+DSF *dsf_new_flip(int size) { return dsf_new(size); }+
void dsf_free(DSF *dsf)
{ if (dsf) {@@ -55,17 +58,22 @@
int dsf_canonify(DSF *dsf, int index)
{- return edsf_canonify(dsf, index, NULL);
+ return dsf_canonify_flip(dsf, index, NULL);
}
+int dsf_minimal(DSF *dsf, int index)
+{+ return dsf_canonify_flip(dsf, index, NULL);
+}
+
bool dsf_equivalent(DSF *dsf, int i1, int i2)
{- return edsf_canonify(dsf, i1, NULL) == edsf_canonify(dsf, i2, NULL);
+ return dsf_canonify(dsf, i1) == dsf_canonify(dsf, i2);
}
void dsf_merge(DSF *dsf, int v1, int v2)
{- edsf_merge(dsf, v1, v2, false);
+ dsf_merge_flip(dsf, v1, v2, false);
}
int dsf_size(DSF *dsf, int index) {@@ -72,7 +80,7 @@
return dsf->p[dsf_canonify(dsf, index)] >> 2;
}
-int edsf_canonify(DSF *dsf, int index, bool *inverse_return)
+int dsf_canonify_flip(DSF *dsf, int index, bool *inverse_return)
{int start_index = index, canonical_index;
bool inverse = false;
@@ -107,7 +115,7 @@
return index;
}
-void edsf_merge(DSF *dsf, int v1, int v2, bool inverse)
+void dsf_merge_flip(DSF *dsf, int v1, int v2, bool inverse)
{bool i1, i2;
@@ -114,10 +122,10 @@
assert(0 <= v1 && v1 < dsf->size && "Overrun in edsf_merge");
assert(0 <= v2 && v2 < dsf->size && "Overrun in edsf_merge");
- v1 = edsf_canonify(dsf, v1, &i1);
+ v1 = dsf_canonify_flip(dsf, v1, &i1);
assert(dsf->p[v1] & 2);
inverse ^= i1;
- v2 = edsf_canonify(dsf, v2, &i2);
+ v2 = dsf_canonify_flip(dsf, v2, &i2);
assert(dsf->p[v2] & 2);
inverse ^= i2;
@@ -147,7 +155,7 @@
dsf->p[v2] = (v1 << 2) | inverse;
}
- v2 = edsf_canonify(dsf, v2, &i2);
+ v2 = dsf_canonify_flip(dsf, v2, &i2);
assert(v2 == v1);
assert(i2 == inverse);
}
--- a/filling.c
+++ b/filling.c
@@ -409,7 +409,7 @@
* contains a shuffled list of numbers {0, ..., sz-1}. */for (i = 0; i < sz; ++i) board[i] = i;
- dsf = snew_dsf(sz);
+ dsf = dsf_new(sz);
retry:
dsf_reinit(dsf);
shuffle(board, sz, sizeof (int), rs);
@@ -1089,12 +1089,12 @@
struct solver_state ss;
ss.board = memdup(orig, sz, sizeof (int));
- ss.dsf = snew_dsf(sz); /* eqv classes: connected components */
+ ss.dsf = dsf_new(sz); /* eqv classes: connected components */
ss.connected = snewn(sz, int); /* connected[n] := n.next; */
/* cyclic disjoint singly linked lists, same partitioning as dsf.
* The lists lets you iterate over a partition given any member */
ss.bm = snewn(sz, int);
- ss.bmdsf = snew_dsf(sz);
+ ss.bmdsf = dsf_new(sz);
ss.bmminsize = snewn(sz, int);
printv("trying to solve this:\n");@@ -1135,7 +1135,7 @@
int i;
if (!dsf)
- dsf = snew_dsf(w * h);
+ dsf = dsf_new(w * h);
else
dsf_reinit(dsf);
--- a/galaxies.c
+++ b/galaxies.c
@@ -1809,7 +1809,7 @@
sctx->state = state;
sctx->sz = state->sx*state->sy;
sctx->scratch = snewn(sctx->sz, space *);
- sctx->dsf = snew_dsf(sctx->sz);
+ sctx->dsf = dsf_new(sctx->sz);
sctx->iscratch = snewn(sctx->sz, int);
return sctx;
}
@@ -3081,7 +3081,7 @@
} *sqdata;
if (!dsf) {- dsf = snew_dsf(w*h);
+ dsf = dsf_new(w*h);
free_dsf = true;
} else {dsf_reinit(dsf);
@@ -3960,7 +3960,7 @@
/*
* Get the completion information.
*/
- dsf = snew_dsf(w * h);
+ dsf = dsf_new(w * h);
colours = snewn(w * h, int);
check_complete(state, dsf, colours);
--- a/grid.c
+++ b/grid.c
@@ -404,7 +404,7 @@
* Now identify connected pairs of landlocked dots, and form a dsf
* unifying them.
*/
- dsf = snew_dsf(g->num_dots);
+ dsf = dsf_new(g->num_dots);
for (i = 0; i < g->num_dots; i++)
for (j = 0; j < i; j++)
if (dots[i] && dots[j] &&
--- a/keen.c
+++ b/keen.c
@@ -708,11 +708,11 @@
ctx.clues = snewn(ctx.nboxes, long);
ctx.whichbox = snewn(a, int);
for (n = m = i = 0; i < a; i++)
- if (dsf_canonify(dsf, i) == i) {+ if (dsf_minimal(dsf, i) == i) {ctx.clues[n] = clues[i];
ctx.boxes[n] = m;
for (j = 0; j < a; j++)
- if (dsf_canonify(dsf, j) == i) {+ if (dsf_minimal(dsf, j) == i) {ctx.boxlist[m++] = (j % w) * w + (j / w); /* transpose */
ctx.whichbox[ctx.boxlist[m-1]] = n;
}
@@ -931,7 +931,7 @@
order = snewn(a, int);
revorder = snewn(a, int);
singletons = snewn(a, int);
- dsf = snew_dsf(a);
+ dsf = dsf_new_min(a);
clues = snewn(a, long);
cluevals = snewn(a, long);
soln = snewn(a, digit);
@@ -1041,11 +1041,10 @@
* integer quotient, of course), but we rule out (or try to
* avoid) some clues because they're of low quality.
*
- * Hence, we iterate once over the grid, stopping at the
- * canonical element of every >2 block and the _non_-
- * canonical element of every 2-block; the latter means that
- * we can make our decision about a 2-block in the knowledge
- * of both numbers in it.
+ * Hence, we iterate once over the grid, stopping at the first
+ * element in every >2 block and the _last_ element of every
+ * 2-block; the latter means that we can make our decision
+ * about a 2-block in the knowledge of both numbers in it.
*
* We reuse the 'singletons' array (finished with in the
* above loop) to hold information about which blocks are
@@ -1059,7 +1058,7 @@
for (i = 0; i < a; i++) {singletons[i] = 0;
- j = dsf_canonify(dsf, i);
+ j = dsf_minimal(dsf, i);
k = dsf_size(dsf, j);
if (params->multiplication_only)
singletons[j] = F_MUL;
@@ -1182,7 +1181,7 @@
* Having chosen the clue types, calculate the clue values.
*/
for (i = 0; i < a; i++) {- j = dsf_canonify(dsf, i);
+ j = dsf_minimal(dsf, i);
if (j == i) {cluevals[j] = grid[i];
} else {@@ -1210,7 +1209,7 @@
}
for (i = 0; i < a; i++) {- j = dsf_canonify(dsf, i);
+ j = dsf_minimal(dsf, i);
if (j == i) {clues[j] |= cluevals[j];
}
@@ -1256,7 +1255,7 @@
p = encode_block_structure(p, w, dsf);
*p++ = ',';
for (i = 0; i < a; i++) {- j = dsf_canonify(dsf, i);
+ j = dsf_minimal(dsf, i);
if (j == i) { switch (clues[j] & CMASK) {case C_ADD: *p++ = 'a'; break;
@@ -1307,7 +1306,7 @@
/*
* Verify that the block structure makes sense.
*/
- dsf = snew_dsf(a);
+ dsf = dsf_new_min(a);
ret = parse_block_structure(&p, w, dsf);
if (ret) {dsf_free(dsf);
@@ -1325,7 +1324,7 @@
* and DIV clues don't apply to blocks of the wrong size.
*/
for (i = 0; i < a; i++) {- if (dsf_canonify(dsf, i) == i) {+ if (dsf_minimal(dsf, i) == i) { if (*p == 'a' || *p == 'm') {/* these clues need no validation */
} else if (*p == 'd' || *p == 's') {@@ -1384,7 +1383,7 @@
state->clues = snew(struct clues);
state->clues->refcount = 1;
state->clues->w = w;
- state->clues->dsf = snew_dsf(a);
+ state->clues->dsf = dsf_new_min(a);
parse_block_structure(&p, w, state->clues->dsf);
assert(*p == ',');
@@ -1392,7 +1391,7 @@
state->clues->clues = snewn(a, long);
for (i = 0; i < a; i++) {- if (dsf_canonify(state->clues->dsf, i) == i) {+ if (dsf_minimal(state->clues->dsf, i) == i) {long clue = 0;
switch (*p) {case 'a':
@@ -1612,7 +1611,7 @@
for (i = 0; i < a; i++) {long clue;
- j = dsf_canonify(state->clues->dsf, i);
+ j = dsf_minimal(state->clues->dsf, i);
if (j == i) {cluevals[i] = state->grid[i];
} else {@@ -1646,7 +1645,7 @@
}
for (i = 0; i < a; i++) {- j = dsf_canonify(state->clues->dsf, i);
+ j = dsf_minimal(state->clues->dsf, i);
if (j == i) { if ((state->clues->clues[j] & ~CMASK) != cluevals[i]) {errs = true;
@@ -1952,6 +1951,7 @@
int tx, ty, tw, th;
int cx, cy, cw, ch;
char str[64];
+ bool draw_clue = dsf_minimal(clues->dsf, y*w+x) == y*w+x;
tx = BORDER + x * TILESIZE + 1 + GRIDEXTRA;
ty = BORDER + y * TILESIZE + 1 + GRIDEXTRA;
@@ -2002,7 +2002,7 @@
draw_rect(dr, tx+TILESIZE-1-2*GRIDEXTRA, ty+TILESIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID);
/* Draw the box clue. */
- if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) {+ if (draw_clue) {long clue = clues->clues[y*w+x];
long cluetype = clue & CMASK, clueval = clue & ~CMASK;
int size = dsf_size(clues->dsf, y*w+x);
@@ -2056,7 +2056,7 @@
pr = pl + TILESIZE - GRIDEXTRA;
pt = ty + GRIDEXTRA;
pb = pt + TILESIZE - GRIDEXTRA;
- if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) {+ if (draw_clue) {/*
* Make space for the clue text.
*/
@@ -2110,7 +2110,7 @@
* And move it down a bit if it's collided with some
* clue text.
*/
- if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) {+ if (draw_clue) {pt = max(pt, ty + GRIDEXTRA * 3 + TILESIZE/4);
}
@@ -2411,7 +2411,7 @@
*/
for (y = 0; y < w; y++)
for (x = 0; x < w; x++)
- if (dsf_canonify(state->clues->dsf, y*w+x) == y*w+x) {+ if (dsf_minimal(state->clues->dsf, y*w+x) == y*w+x) {long clue = state->clues->clues[y*w+x];
long cluetype = clue & CMASK, clueval = clue & ~CMASK;
int size = dsf_size(state->clues->dsf, y*w+x);
--- a/loopy.c
+++ b/loopy.c
@@ -25,28 +25,28 @@
* outside respectively. So if you can track this for all
* faces, you figure out the state of the line between a pair
* once their relative insideness is known.
- * + The way I envisage this working is simply to keep an edsf
+ * + The way I envisage this working is simply to keep a flip dsf
* of all _faces_, which indicates whether they're on
* opposite sides of the loop from one another. We also
- * include a special entry in the edsf for the infinite
+ * include a special entry in the dsf for the infinite
* exterior "face".
* + So, the simple way to do this is to just go through the
* edges: every time we see an edge in a state other than
* LINE_UNKNOWN which separates two faces that aren't in the
- * same edsf class, we can rectify that by merging the
+ * same dsf class, we can rectify that by merging the
* classes. Then, conversely, an edge in LINE_UNKNOWN state
- * which separates two faces that _are_ in the same edsf
+ * which separates two faces that _are_ in the same dsf
* class can immediately have its state determined.
* + But you can go one better, if you're prepared to loop
* over all _pairs_ of edges. Suppose we have edges A and B,
* which respectively separate faces A1,A2 and B1,B2.
- * Suppose that A,B are in the same edge-edsf class and that
- * A1,B1 (wlog) are in the same face-edsf class; then we can
- * immediately place A2,B2 into the same face-edsf class (as
+ * Suppose that A,B are in the same edge-dsf class and that
+ * A1,B1 (wlog) are in the same face-dsf class; then we can
+ * immediately place A2,B2 into the same face-dsf class (as
* each other, not as A1 and A2) one way round or the other.
- * And conversely again, if A1,B1 are in the same face-edsf
+ * And conversely again, if A1,B1 are in the same face-dsf
* class and so are A2,B2, then we can put A,B into the same
- * face-edsf class.
+ * face-dsf class.
* * Of course, this deduction requires a quadratic-time
* loop over all pairs of edges in the grid, so it should
* be reserved until there's nothing easier left to be
@@ -386,7 +386,7 @@
ret->solver_status = SOLVER_INCOMPLETE;
ret->diff = diff;
- ret->dotdsf = snew_dsf(num_dots);
+ ret->dotdsf = dsf_new(num_dots);
ret->looplen = snewn(num_dots, int);
for (i = 0; i < num_dots; i++) {@@ -417,7 +417,7 @@
if (diff < DIFF_HARD) {ret->linedsf = NULL;
} else {- ret->linedsf = snew_dsf(state->game_grid->num_edges);
+ ret->linedsf = dsf_new_flip(state->game_grid->num_edges);
}
return ret;
@@ -455,7 +455,7 @@
ret->solver_status = sstate->solver_status;
ret->diff = sstate->diff;
- ret->dotdsf = snew_dsf(num_dots);
+ ret->dotdsf = dsf_new(num_dots);
ret->looplen = snewn(num_dots, int);
dsf_copy(ret->dotdsf, sstate->dotdsf);
memcpy(ret->looplen, sstate->looplen,
@@ -485,7 +485,7 @@
}
if (sstate->linedsf) {- ret->linedsf = snew_dsf(num_edges);
+ ret->linedsf = dsf_new_flip(num_edges);
dsf_copy(ret->linedsf, sstate->linedsf);
} else {ret->linedsf = NULL;
@@ -1215,12 +1215,12 @@
assert(i < sstate->state->game_grid->num_edges);
assert(j < sstate->state->game_grid->num_edges);
- i = edsf_canonify(sstate->linedsf, i, &inv_tmp);
+ i = dsf_canonify_flip(sstate->linedsf, i, &inv_tmp);
inverse ^= inv_tmp;
- j = edsf_canonify(sstate->linedsf, j, &inv_tmp);
+ j = dsf_canonify_flip(sstate->linedsf, j, &inv_tmp);
inverse ^= inv_tmp;
- edsf_merge(sstate->linedsf, i, j, inverse);
+ dsf_merge_flip(sstate->linedsf, i, j, inverse);
#ifdef SHOW_WORKING
if (i != j) {@@ -1631,7 +1631,7 @@
* leave that one unhighlighted, and light the rest up in red.
*/
- dsf = snew_dsf(g->num_dots);
+ dsf = dsf_new(g->num_dots);
/* Build the dsf. */
for (i = 0; i < g->num_edges; i++) {@@ -1787,7 +1787,7 @@
* know both or neither is on that's already stored more directly.)
*
* Advanced Mode
- * Use edsf data structure to make equivalence classes of lines that are
+ * Use flip dsf data structure to make equivalence classes of lines that are
* known identical to or opposite to one another.
*/
@@ -1952,8 +1952,8 @@
continue;
/* Found two UNKNOWNS */
- can1 = edsf_canonify(sstate->linedsf, line1_index, &inv1);
- can2 = edsf_canonify(sstate->linedsf, line2_index, &inv2);
+ can1 = dsf_canonify_flip(sstate->linedsf, line1_index, &inv1);
+ can2 = dsf_canonify_flip(sstate->linedsf, line2_index, &inv2);
if (can1 == can2 && inv1 == inv2) {solver_set_line(sstate, line1_index, line_new);
solver_set_line(sstate, line2_index, line_new);
@@ -2007,9 +2007,9 @@
int can[3]; /* canonical edges */
bool inv[3]; /* whether can[x] is inverse to e[x] */
find_unknowns(state, edge_list, 3, e);
- can[0] = edsf_canonify(linedsf, e[0], inv);
- can[1] = edsf_canonify(linedsf, e[1], inv+1);
- can[2] = edsf_canonify(linedsf, e[2], inv+2);
+ can[0] = dsf_canonify_flip(linedsf, e[0], inv);
+ can[1] = dsf_canonify_flip(linedsf, e[1], inv+1);
+ can[2] = dsf_canonify_flip(linedsf, e[2], inv+2);
if (can[0] == can[1]) {if (solver_set_line(sstate, e[2], (total_parity^inv[0]^inv[1]) ?
LINE_YES : LINE_NO))
@@ -2030,10 +2030,10 @@
int can[4]; /* canonical edges */
bool inv[4]; /* whether can[x] is inverse to e[x] */
find_unknowns(state, edge_list, 4, e);
- can[0] = edsf_canonify(linedsf, e[0], inv);
- can[1] = edsf_canonify(linedsf, e[1], inv+1);
- can[2] = edsf_canonify(linedsf, e[2], inv+2);
- can[3] = edsf_canonify(linedsf, e[3], inv+3);
+ can[0] = dsf_canonify_flip(linedsf, e[0], inv);
+ can[1] = dsf_canonify_flip(linedsf, e[1], inv+1);
+ can[2] = dsf_canonify_flip(linedsf, e[2], inv+2);
+ can[3] = dsf_canonify_flip(linedsf, e[3], inv+3);
if (can[0] == can[1]) {if (merge_lines(sstate, e[2], e[3], total_parity^inv[0]^inv[1]))
diff = min(diff, DIFF_HARD);
@@ -2648,8 +2648,8 @@
if (state->lines[line2_index] != LINE_UNKNOWN)
continue;
/* Infer dline flags from linedsf */
- can1 = edsf_canonify(sstate->linedsf, line1_index, &inv1);
- can2 = edsf_canonify(sstate->linedsf, line2_index, &inv2);
+ can1 = dsf_canonify_flip(sstate->linedsf, line1_index, &inv1);
+ can2 = dsf_canonify_flip(sstate->linedsf, line2_index, &inv2);
if (can1 == can2 && inv1 != inv2) {/* These are opposites, so set dline atmostone/atleastone */
if (set_atmostone(dlines, dline_index))
@@ -2684,7 +2684,7 @@
int can;
bool inv;
enum line_state s;
- can = edsf_canonify(sstate->linedsf, i, &inv);
+ can = dsf_canonify_flip(sstate->linedsf, i, &inv);
if (can == i)
continue;
s = sstate->state->lines[can];
--- a/map.c
+++ b/map.c
@@ -1725,7 +1725,7 @@
bool state;
const char *p = *desc;
const char *err = NULL;
- DSF *dsf = snew_dsf(wh);
+ DSF *dsf = dsf_new(wh);
pos = -1;
state = false;
--- a/net.c
+++ b/net.c
@@ -547,7 +547,7 @@
* classes) by finding the representative of each tile and
* setting equivalence[one]=the_other.
*/
- equivalence = snew_dsf(w * h);
+ equivalence = dsf_new(w * h);
/*
* On a non-wrapping grid, we instantly know that all the edges
--- a/palisade.c
+++ b/palisade.c
@@ -527,7 +527,7 @@
{int w = params->w, h = params->h, wh = w*h, k = params->k;
int i, x, y;
- DSF *dsf = snew_dsf(wh);
+ DSF *dsf = dsf_new(wh);
build_dsf(w, h, border, dsf, true);
@@ -582,7 +582,7 @@
ctx.params = params;
ctx.clues = clues;
ctx.borders = borders;
- ctx.dsf = snew_dsf(wh);
+ ctx.dsf = dsf_new(wh);
solver_connected_clues_versus_region_size(&ctx); /* idempotent */
do {@@ -1172,7 +1172,7 @@
{int w = state->shared->params.w, h = state->shared->params.h, wh = w*h;
int r, c, flash = ((int) (flashtime * 5 / FLASH_TIME)) % 2;
- DSF *black_border_dsf = snew_dsf(wh), *yellow_border_dsf = snew_dsf(wh);
+ DSF *black_border_dsf = dsf_new(wh), *yellow_border_dsf = dsf_new(wh);
int k = state->shared->params.k;
if (!ds->grid) {--- a/pearl.c
+++ b/pearl.c
@@ -350,7 +350,7 @@
* We maintain a dsf of connected squares, together with a
* count of the size of each equivalence class.
*/
- dsf = snew_dsf(w*h);
+ dsf = dsf_new(w*h);
dsfsize = snewn(w*h, int);
/*
@@ -1577,7 +1577,7 @@
* same reasons, since Loopy and Pearl have basically the same
* form of expected solution.
*/
- dsf = snew_dsf(w*h);
+ dsf = dsf_new(w*h);
/* Build the dsf. */
for (x = 0; x < w; x++) {--- a/puzzles.h
+++ b/puzzles.h
@@ -427,30 +427,34 @@
* dsf.c
*/
typedef struct DSF DSF;
-DSF *snew_dsf(int size);
+DSF *dsf_new(int size);
void dsf_free(DSF *dsf);
void dsf_copy(DSF *to, DSF *from);
-/* Return the canonical element of the equivalence class containing element
- * val. If 'inverse' is non-NULL, this function will put into it a flag
- * indicating whether the canonical element is inverse to val. */
-int edsf_canonify(DSF *dsf, int val, bool *inverse);
-int dsf_canonify(DSF *dsf, int val);
-int dsf_size(DSF *dsf, int val);
+/* Basic dsf operations, return the canonical element of a class,
+ * check if two elements are in the same class, and return the size of
+ * a class. These work on all types of dsf. */
+int dsf_canonify(DSF *dsf, int n);
+bool dsf_equivalent(DSF *dsf, int n1, int n2);
+int dsf_size(DSF *dsf, int n);
-/* 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);
+/* Merge two elements and their classes. Not legal on a flip dsf. */
+void dsf_merge(DSF *dsf, int n1, int n2);
-/* 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
- * caller gives it self-contradictory data, ie if two elements are claimed to
- * be both opposite and non-opposite. */
-void edsf_merge(DSF *dsf, int v1, int v2, bool inverse);
-void dsf_merge(DSF *dsf, int v1, int v2);
+/* Special dsf that tracks the minimal element of every equivalence
+ * class, and a function to query it. */
+DSF *dsf_new_min(int size);
+int dsf_minimal(DSF *dsf, int n);
+
+/* Special dsf that tracks whether pairs of elements in the same class
+ * have flipped sense relative to each other. Merge function takes an
+ * argument saying whether n1 and n2 are opposite to each other;
+ * canonify function will report whether n is opposite to the returned
+ * element. */
+DSF *dsf_new_flip(int size);
+void dsf_merge_flip(DSF *dsf, int n1, int n2, bool flip);
+int dsf_canonify_flip(DSF *dsf, int n, bool *flip);
/* Reinitialise a dsf to the starting 'all elements distinct' state. */
void dsf_reinit(DSF *dsf);
--- a/range.c
+++ b/range.c
@@ -1476,7 +1476,7 @@
/*
* Check that all the white cells form a single connected component.
*/
- dsf = snew_dsf(n);
+ dsf = dsf_new(n);
for (r = 0; r < h-1; ++r)
for (c = 0; c < w; ++c)
if (state->grid[r*w+c] != BLACK &&
--- a/signpost.c
+++ b/signpost.c
@@ -461,7 +461,7 @@
state->flags = snewn(state->n, unsigned int);
state->next = snewn(state->n, int);
state->prev = snewn(state->n, int);
- state->dsf = snew_dsf(state->n);
+ state->dsf = dsf_new(state->n);
state->numsi = snewn(state->n+1, int);
blank_game_into(state);
--- a/singles.c
+++ b/singles.c
@@ -498,7 +498,7 @@
static bool check_complete(game_state *state, unsigned flags)
{- DSF *dsf = snew_dsf(state->n);
+ DSF *dsf = dsf_new(state->n);
int x, y, i, error = 0, nwhite, w = state->w, h = state->h;
if (flags & CC_MARK_ERRORS) {--- a/slant.c
+++ b/slant.c
@@ -312,10 +312,10 @@
{int W = w+1, H = h+1;
struct solver_scratch *ret = snew(struct solver_scratch);
- ret->connected = snew_dsf(W*H);
+ ret->connected = dsf_new(W*H);
ret->exits = snewn(W*H, int);
ret->border = snewn(W*H, bool);
- ret->equiv = snew_dsf(w*h);
+ ret->equiv = dsf_new(w*h);
ret->slashval = snewn(w*h, signed char);
ret->vbitmap = snewn(w*h, unsigned char);
return ret;
@@ -1009,7 +1009,7 @@
* Establish a disjoint set forest for tracking connectedness
* between grid points.
*/
- connected = snew_dsf(W*H);
+ connected = dsf_new(W*H);
/*
* Prepare a list of the squares in the grid, and fill them in
--- a/solo.c
+++ b/solo.c
@@ -3915,7 +3915,7 @@
int pos = 0;
DSF *dsf;
- *pdsf = dsf = snew_dsf(area);
+ *pdsf = dsf = dsf_new(area);
while (*desc && *desc != ',') {int c;
--- a/tents.c
+++ b/tents.c
@@ -2224,7 +2224,7 @@
* all the tents in any component which has a smaller tree
* count.
*/
- dsf = snew_dsf(w*h);
+ dsf = dsf_new(w*h);
/* Construct the equivalence classes. */
for (y = 0; y < h; y++) { for (x = 0; x < w-1; x++) {--- a/tracks.c
+++ b/tracks.c
@@ -1374,7 +1374,7 @@
/* TODO eventually we should pull this out into a solver struct and keep it
updated as we connect squares. For now we recreate it every time we try
this particular solver step. */
- dsf = snew_dsf(w*h);
+ dsf = dsf_new(w*h);
/* Work out the connectedness of the current loop set. */
for (x = 0; x < w; x++) {@@ -1465,7 +1465,7 @@
assert(d == D || d == R);
if (!sc->dsf)
- sc->dsf = snew_dsf(wh);
+ sc->dsf = dsf_new(wh);
dsf_reinit(sc->dsf);
for (xi = 0; xi < w; xi++) {@@ -1879,7 +1879,7 @@
}
}
- dsf = snew_dsf(w*h);
+ dsf = dsf_new(w*h);
for (x = 0; x < w; x++) { for (y = 0; y < h; y++) {--- a/unfinished/separate.c
+++ b/unfinished/separate.c
@@ -228,7 +228,7 @@
sc->h = h;
sc->k = k;
- sc->dsf = snew_dsf(wh);
+ sc->dsf = dsf_new(wh);
sc->size = snewn(wh, int);
sc->contents = snewn(wh * k, int);
sc->disconnect = snewn(wh*wh, bool);
--- a/unfinished/slide.c
+++ b/unfinished/slide.c
@@ -294,7 +294,7 @@
bool *forcefield)
{int wh = w*h;
- DSF *dsf = snew_dsf(wh);
+ DSF *dsf = dsf_new(wh);
int i, x, y;
int retpos, retlen = (w*2+2)*(h*2+1)+1;
char *ret = snewn(retlen, char);
@@ -670,7 +670,7 @@
tried_merge = snewn(wh * wh, bool);
memset(tried_merge, 0, wh*wh * sizeof(bool));
- dsf = snew_dsf(wh);
+ dsf = dsf_new(wh);
/*
* Invent a main piece at one extreme. (FIXME: vary the
@@ -2150,7 +2150,7 @@
* Build a dsf out of that board, so we can conveniently tell
* which edges are connected and which aren't.
*/
- dsf = snew_dsf(wh);
+ dsf = dsf_new(wh);
mainanchor = -1;
for (y = 0; y < h; y++)
for (x = 0; x < w; x++) {