diff options
| -rw-r--r-- | bridges.c | 4 | ||||
| -rw-r--r-- | divvy.c | 4 | ||||
| -rw-r--r-- | dominosa.c | 12 | ||||
| -rw-r--r-- | dsf.c | 26 | ||||
| -rw-r--r-- | filling.c | 8 | ||||
| -rw-r--r-- | galaxies.c | 6 | ||||
| -rw-r--r-- | grid.c | 2 | ||||
| -rw-r--r-- | keen.c | 44 | ||||
| -rw-r--r-- | loopy.c | 60 | ||||
| -rw-r--r-- | map.c | 2 | ||||
| -rw-r--r-- | net.c | 2 | ||||
| -rw-r--r-- | palisade.c | 6 | ||||
| -rw-r--r-- | pearl.c | 4 | ||||
| -rw-r--r-- | puzzles.h | 44 | ||||
| -rw-r--r-- | range.c | 2 | ||||
| -rw-r--r-- | signpost.c | 2 | ||||
| -rw-r--r-- | singles.c | 2 | ||||
| -rw-r--r-- | slant.c | 6 | ||||
| -rw-r--r-- | solo.c | 2 | ||||
| -rw-r--r-- | tents.c | 2 | ||||
| -rw-r--r-- | tracks.c | 6 | ||||
| -rw-r--r-- | unfinished/separate.c | 2 | ||||
| -rw-r--r-- | unfinished/slide.c | 6 |
23 files changed, 133 insertions, 121 deletions
@@ -1774,8 +1774,8 @@ static game_state *new_state(const game_params *params) 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; @@ -611,7 +611,7 @@ DSF *divvy_rectangle_attempt(int w, int h, int k, random_state *rs) 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 @@ DSF *divvy_rectangle_attempt(int w, int h, int k, random_state *rs) * 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)]) @@ -1429,12 +1429,12 @@ static bool deduce_forcing_chain(struct solver_scratch *sc) 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 @@ static bool deduce_forcing_chain(struct solver_scratch *sc) 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 @@ static bool deduce_forcing_chain(struct solver_scratch *sc) */ 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); } @@ -34,7 +34,7 @@ void dsf_copy(DSF *to, DSF *from) 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 @@ DSF *snew_dsf(int size) 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,24 +58,29 @@ void dsf_free(DSF *dsf) 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) { 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,17 +115,17 @@ int edsf_canonify(DSF *dsf, int index, bool *inverse_return) 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; 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 @@ void edsf_merge(DSF *dsf, int v1, int v2, bool inverse) 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); } @@ -409,7 +409,7 @@ static void make_board(int *board, int w, int h, random_state *rs) { * 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 @@ static bool solver(const int *orig, int w, int h, char **solution) { 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 @@ static DSF *make_dsf(DSF *dsf, int *board, const int w, const int h) { int i; if (!dsf) - dsf = snew_dsf(w * h); + dsf = dsf_new(w * h); else dsf_reinit(dsf); @@ -1809,7 +1809,7 @@ static solver_ctx *new_solver(game_state *state) 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 @@ static bool check_complete(const game_state *state, DSF *dsf, int *colours) } *sqdata; if (!dsf) { - dsf = snew_dsf(w*h); + dsf = dsf_new(w*h); free_dsf = true; } else { dsf_reinit(dsf); @@ -3960,7 +3960,7 @@ static void game_print(drawing *dr, const game_state *state, int sz) /* * Get the completion information. */ - dsf = snew_dsf(w * h); + dsf = dsf_new(w * h); colours = snewn(w * h, int); check_complete(state, dsf, colours); @@ -404,7 +404,7 @@ static void grid_trim_vigorously(grid *g) * 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] && @@ -708,11 +708,11 @@ static int solver(int w, DSF *dsf, long *clues, digit *soln, int maxdiff) 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 @@ done 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 @@ done * 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 @@ done 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 @@ done * 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 @@ done } 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 @@ done 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 @@ static const char *validate_desc(const game_params *params, const char *desc) /* * 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 @@ static const char *validate_desc(const game_params *params, const char *desc) * 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 @@ static game_state *new_game(midend *me, const game_params *params, 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 @@ static game_state *new_game(midend *me, const game_params *params, 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 @@ static bool check_errors(const game_state *state, long *errors) 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 @@ static bool check_errors(const game_state *state, long *errors) } 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 @@ static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, 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 @@ static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, 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 @@ static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, 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 @@ static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, * 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 @@ static void game_print(drawing *dr, const game_state *state, int tilesize) */ 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); @@ -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 @@ static solver_state *new_solver_state(const game_state *state, int diff) { 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 @@ static solver_state *new_solver_state(const game_state *state, int diff) { 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 @@ static solver_state *dup_solver_state(const solver_state *sstate) { 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 @@ static solver_state *dup_solver_state(const solver_state *sstate) { } 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 @@ static bool merge_lines(solver_state *sstate, int i, int j, bool inverse 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 @@ static bool check_completion(game_state *state) * 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 @@ static bool check_completion(game_state *state) * 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 @@ static bool face_setall_identical(solver_state *sstate, int face_index, 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 @@ static int parity_deductions(solver_state *sstate, 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 @@ static int parity_deductions(solver_state *sstate, 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 @@ static int linedsf_deductions(solver_state *sstate) 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 @@ static int linedsf_deductions(solver_state *sstate) 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]; @@ -1725,7 +1725,7 @@ static const char *parse_edge_list(const game_params *params, bool state; const char *p = *desc; const char *err = NULL; - DSF *dsf = snew_dsf(wh); + DSF *dsf = dsf_new(wh); pos = -1; state = false; @@ -547,7 +547,7 @@ static int net_solver(int w, int h, unsigned char *tiles, * 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 @@ -527,7 +527,7 @@ static bool is_solved(const game_params *params, clue *clues, { 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 @@ static bool solver(const game_params *params, clue *clues, borderflag *borders) 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 @@ static void game_redraw(drawing *dr, game_drawstate *ds, { 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) { @@ -350,7 +350,7 @@ static int pearl_solve(int w, int h, char *clues, char *result, * 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 @@ static bool check_completion(game_state *state, bool mark) * 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++) { @@ -427,30 +427,34 @@ char *button2label(int button); * 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); - -/* 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 - * 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); +/* 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); + +/* Merge two elements and their classes. Not legal on a flip dsf. */ +void dsf_merge(DSF *dsf, int n1, int n2); + +/* 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); @@ -1476,7 +1476,7 @@ static bool find_errors(const game_state *state, bool *report) /* * 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 && @@ -461,7 +461,7 @@ static game_state *blank_game(int w, int h) 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); @@ -498,7 +498,7 @@ static int check_rowcol(game_state *state, int starti, int di, int sz, unsigned 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) { @@ -312,10 +312,10 @@ static struct solver_scratch *new_scratch(int w, int h) { 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 @@ static void slant_generate(int w, int h, signed char *soln, random_state *rs) * 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 @@ -3915,7 +3915,7 @@ static const char *spec_to_dsf(const char **pdesc, DSF **pdsf, int pos = 0; DSF *dsf; - *pdsf = dsf = snew_dsf(area); + *pdsf = dsf = dsf_new(area); while (*desc && *desc != ',') { int c; @@ -2224,7 +2224,7 @@ static int *find_errors(const game_state *state, char *grid) * 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++) { @@ -1374,7 +1374,7 @@ static int solve_check_loop(game_state *state) /* 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 @@ static int solve_bridge_sub(game_state *state, int x, int y, int d, 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 @@ static bool check_completion(game_state *state, bool mark) } } - dsf = snew_dsf(w*h); + dsf = dsf_new(w*h); for (x = 0; x < w; x++) { for (y = 0; y < h; y++) { diff --git a/unfinished/separate.c b/unfinished/separate.c index 088f0ac..cc2a6c1 100644 --- a/unfinished/separate.c +++ b/unfinished/separate.c @@ -228,7 +228,7 @@ static struct solver_scratch *solver_scratch_new(int w, int h, int k) 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); diff --git a/unfinished/slide.c b/unfinished/slide.c index f1a057e..e091def 100644 --- a/unfinished/slide.c +++ b/unfinished/slide.c @@ -294,7 +294,7 @@ static char *board_text_format(int w, int h, unsigned char *data, 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 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, 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 @@ static void game_redraw(drawing *dr, game_drawstate *ds, * 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++) { |