Tracks: use the new findloop for loop detection.

[sgt-puzzles.git] / tracks.c

diff --git a/tracks.c b/tracks.c
index cecfe7c6616d49530fdb111a34cf59eb0b4f43a1..d633a9ca1caef0399983ec706a7942abe9be25d6 100644 (file)
--- a/tracks.c
+++ b/tracks.c
@@ -1490,11 +1490,10 @@ static void debug_state(game_state *state, const char *what) {
     sfree(sstring);
 }
 
-static void dsf_update_completion(game_state *state, int *loopclass,
-                                  int ax, int ay, char dir,
-                                  int *dsf)
+static void dsf_update_completion(game_state *state, int ax, int ay,
+                                  char dir, int *dsf)
 {
-    int w = state->p.w, ai = ay*w+ax, bx, by, bi, ac, bc;
+    int w = state->p.w, ai = ay*w+ax, bx, by, bi;
 
     if (!(S_E_DIRS(state, ax, ay, E_TRACK) & dir)) return;
     bx = ax + DX(dir);
@@ -1503,22 +1502,47 @@ static void dsf_update_completion(game_state *state, int *loopclass,
     if (!INGRID(state, bx, by)) return;
     bi = by*w+bx;
 
-    ac = dsf_canonify(dsf, ai);
-    bc = dsf_canonify(dsf, bi);
+    dsf_merge(dsf, ai, bi);
+}
 
-    if (ac == bc) {
-        /* loop detected */
-        *loopclass = ac;
-    } else {
-        dsf_merge(dsf, ai, bi);
+struct tracks_neighbour_ctx {
+    game_state *state;
+    int i, n, neighbours[4];
+};
+static int tracks_neighbour(int vertex, void *vctx)
+{
+    struct tracks_neighbour_ctx *ctx = (struct tracks_neighbour_ctx *)vctx;
+    if (vertex >= 0) {
+        game_state *state = ctx->state;
+        int w = state->p.w, x = vertex % w, y = vertex / w;
+        int dirs = S_E_DIRS(state, x, y, E_TRACK);
+        int j;
+
+        ctx->i = ctx->n = 0;
+
+        for (j = 0; j < 4; j++) {
+            int dir = 1<<j;
+            if (dirs & dir) {
+                int nx = x + DX(dir), ny = y + DY(dir);
+                if (INGRID(state, nx, ny))
+                    ctx->neighbours[ctx->n++] = ny * w + nx;
+            }
+        }
     }
+
+    if (ctx->i < ctx->n)
+        return ctx->neighbours[ctx->i++];
+    else
+        return -1;
 }
 
 static int check_completion(game_state *state, int mark)
 {
     int w = state->p.w, h = state->p.h, x, y, i, target, ret = TRUE;
     int ntrack, nnotrack, ntrackcomplete;
-    int *dsf, loopclass, pathclass;
+    int *dsf, pathclass;
+    struct findloopstate *fls;
+    struct tracks_neighbour_ctx ctx;
 
     if (mark) {
         for (i = 0; i < w+h; i++) {
@@ -1585,28 +1609,35 @@ static int check_completion(game_state *state, int mark)
 
     dsf = snewn(w*h, int);
     dsf_init(dsf, w*h);
-    loopclass = -1;
 
     for (x = 0; x < w; x++) {
         for (y = 0; y < h; y++) {
-            dsf_update_completion(state, &loopclass, x, y, R, dsf);
-            dsf_update_completion(state, &loopclass, x, y, D, dsf);
+            dsf_update_completion(state, x, y, R, dsf);
+            dsf_update_completion(state, x, y, D, dsf);
         }
     }
-    if (loopclass != -1) {
+
+    fls = findloop_new_state(w*h);
+    ctx.state = state;
+    if (findloop_run(fls, w*h, tracks_neighbour, &ctx)) {
         debug(("loop detected, not complete"));
         ret = FALSE; /* no loop allowed */
         if (mark) {
             for (x = 0; x < w; x++) {
                 for (y = 0; y < h; y++) {
-                    /* TODO this will only highlight the first loop found */
-                    if (dsf_canonify(dsf, y*w + x) == loopclass) {
-                        state->sflags[y*w+x] |= S_ERROR;
-                    }
+                    int u, v;
+
+                    u = y*w + x;
+                    for (v = tracks_neighbour(u, &ctx); v >= 0;
+                         v = tracks_neighbour(-1, &ctx))
+                        if (findloop_is_loop_edge(fls, u, v))
+                            state->sflags[y*w+x] |= S_ERROR;
                 }
             }
         }
     }
+    findloop_free_state(fls);
+
     if (mark) {
         pathclass = dsf_canonify(dsf, state->numbers->row_s*w);
         if (pathclass == dsf_canonify(dsf, (h-1)*w + state->numbers->col_s)) {