1 files changed, 129 insertions, 81 deletions

diff --git a/apps/plugins/puzzles/src/bridges.c b/apps/plugins/puzzles/src/bridges.c
index 83086c9761..7e87764d6d 100644
--- a/apps/plugins/puzzles/src/bridges.c
+++ b/apps/plugins/puzzles/src/bridges.c
@@ -72,11 +72,15 @@
 #include <string.h>
 #include <assert.h>
 #include <ctype.h>
-#include <math.h>
+#include <limits.h>
+#ifdef NO_TGMATH_H
+#  include <math.h>
+#else
+#  include <tgmath.h>
+#endif
 
 #include "puzzles.h"
 
-/* Turn this on for hints about which lines are considered possibilities. */
 #undef DRAW_GRID
 
 /* --- structures for params, state, etc. --- */
@@ -134,8 +138,8 @@ struct game_params {
 typedef unsigned int grid_type; /* change me later if we invent > 16 bits of flags. */
 
 struct solver_state {
-    int *dsf, *comptspaces;
-    int *tmpdsf, *tmpcompspaces;
+    DSF *dsf, *tmpdsf;
+    int *comptspaces, *tmpcompspaces;
     int refcount;
 };
 
@@ -183,7 +187,7 @@ struct game_state {
 
 #define GRIDCOUNT(s,x,y,f) ((GRID(s,x,y) & (f)) ? (INDEX(s,lines,x,y)) : 0)
 
-#define WITHIN2(x,min,max) ((x) >= (min) && (x) < (max))
+#define WITHIN2(x,min,max) ((x) >= (min) && (x) <= (max))
 #define WITHIN(x,min,max) ((min) > (max) ? \
                            WITHIN2(x,max,min) : WITHIN2(x,min,max))
 
@@ -803,6 +807,8 @@ static const char *validate_params(const game_params *params, bool full)
 {
     if (params->w < 3 || params->h < 3)
         return "Width and height must be at least 3";
+    if (params->w > INT_MAX / params->h)
+        return "Width times height must not be unreasonably large";
     if (params->maxb < 1 || params->maxb > MAX_BRIDGES)
         return "Too many bridges.";
     if (full) {
@@ -1133,13 +1139,13 @@ static bool map_hasloops(game_state *state, bool mark)
 
 static void map_group(game_state *state)
 {
-    int i, wh = state->w*state->h, d1, d2;
+    int i, d1, d2;
     int x, y, x2, y2;
-    int *dsf = state->solver->dsf;
+    DSF *dsf = state->solver->dsf;
     struct island *is, *is_join;
 
     /* Initialise dsf. */
-    dsf_init(dsf, wh);
+    dsf_reinit(dsf);
 
     /* For each island, find connected islands right or down
      * and merge the dsf for the island squares as well as the
@@ -1160,7 +1166,7 @@ static void map_group(game_state *state)
                 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. */
@@ -1180,7 +1186,8 @@ static void map_group(game_state *state)
 static bool map_group_check(game_state *state, int canon, bool warn,
                             int *nislands_r)
 {
-    int *dsf = state->solver->dsf, nislands = 0;
+    DSF *dsf = state->solver->dsf;
+    int nislands = 0;
     int x, y, i;
     bool allfull = true;
     struct island *is;
@@ -1212,7 +1219,8 @@ static bool map_group_check(game_state *state, int canon, bool warn,
 
 static bool map_group_full(game_state *state, int *ngroups_r)
 {
-    int *dsf = state->solver->dsf, ngroups = 0;
+    DSF *dsf = state->solver->dsf;
+    int ngroups = 0;
     int i;
     bool anyfull = false;
     struct island *is;
@@ -1267,7 +1275,8 @@ static void map_clear(game_state *state)
 static void solve_join(struct island *is, int direction, int n, bool is_max)
 {
     struct island *is_orth;
-    int d1, d2, *dsf = is->state->solver->dsf;
+    int d1, d2;
+    DSF *dsf = is->state->solver->dsf;
     game_state *state = is->state; /* for DINDEX */
 
     is_orth = INDEX(is->state, gridi,
@@ -1281,7 +1290,7 @@ static void solve_join(struct island *is, int direction, int n, bool is_max)
     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);
     }
 }
@@ -1382,7 +1391,8 @@ static bool solve_island_stage1(struct island *is, bool *didsth_r)
 static bool solve_island_checkloop(struct island *is, int direction)
 {
     struct island *is_orth;
-    int *dsf = is->state->solver->dsf, d1, d2;
+    DSF *dsf = is->state->solver->dsf;
+    int d1, d2;
     game_state *state = is->state;
 
     if (is->state->allowloops)
@@ -1399,7 +1409,7 @@ static bool solve_island_checkloop(struct island *is, int direction)
 
     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;
     }
@@ -1457,7 +1467,8 @@ static bool solve_island_stage2(struct island *is, bool *didsth_r)
 static bool solve_island_subgroup(struct island *is, int direction)
 {
     struct island *is_join;
-    int nislands, *dsf = is->state->solver->dsf;
+    int nislands;
+    DSF *dsf = is->state->solver->dsf;
     game_state *state = is->state;
 
     debug(("..checking subgroups.\n"));
@@ -1520,7 +1531,6 @@ static bool solve_island_stage3(struct island *is, bool *didsth_r)
 {
     int i, n, x, y, missing, spc, curr, maxb;
     bool didsth = false;
-    int wh = is->state->w * is->state->h;
     struct solver_state *ss = is->state->solver;
 
     assert(didsth_r);
@@ -1544,7 +1554,7 @@ static bool solve_island_stage3(struct island *is, bool *didsth_r)
         maxb = -1;
         /* We have to squirrel the dsf away and restore it afterwards;
          * it is additive only, and can't be removed from. */
-        memcpy(ss->tmpdsf, ss->dsf, wh*sizeof(int));
+        dsf_copy(ss->tmpdsf, ss->dsf);
         for (n = curr+1; n <= curr+spc; n++) {
             solve_join(is, i, n, false);
             map_update_possibles(is->state);
@@ -1560,7 +1570,7 @@ static bool solve_island_stage3(struct island *is, bool *didsth_r)
             }
         }
         solve_join(is, i, curr, false); /* put back to before. */
-        memcpy(ss->dsf, ss->tmpdsf, wh*sizeof(int));
+        dsf_copy(ss->dsf, ss->tmpdsf);
 
         if (maxb != -1) {
             /*debug_state(is->state);*/
@@ -1629,7 +1639,7 @@ static bool solve_island_stage3(struct island *is, bool *didsth_r)
                                   is->adj.points[j].dx ? G_LINEH : G_LINEV);
         if (before[i] != 0) continue;  /* this idea is pointless otherwise */
 
-        memcpy(ss->tmpdsf, ss->dsf, wh*sizeof(int));
+        dsf_copy(ss->tmpdsf, ss->dsf);
 
         for (j = 0; j < is->adj.npoints; j++) {
             spc = island_adjspace(is, true, missing, j);
@@ -1644,7 +1654,7 @@ static bool solve_island_stage3(struct island *is, bool *didsth_r)
 
         for (j = 0; j < is->adj.npoints; j++)
             solve_join(is, j, before[j], false);
-        memcpy(ss->dsf, ss->tmpdsf, wh*sizeof(int));
+        dsf_copy(ss->dsf, ss->tmpdsf);
 
         if (got) {
             debug(("island at (%d,%d) must connect in direction (%d,%d) to"
@@ -1763,8 +1773,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 = snewn(wh, int);
+    ret->solver->dsf = dsf_new(wh);
+    ret->solver->tmpdsf = dsf_new(wh);
 
     ret->solver->refcount = 1;
 
@@ -1813,8 +1823,8 @@ static game_state *dup_game(const game_state *state)
 static void free_game(game_state *state)
 {
     if (--state->solver->refcount <= 0) {
-        sfree(state->solver->dsf);
-        sfree(state->solver->tmpdsf);
+        dsf_free(state->solver->dsf);
+        dsf_free(state->solver->tmpdsf);
         sfree(state->solver);
     }
 
@@ -2004,28 +2014,38 @@ generated:
 
 static const char *validate_desc(const game_params *params, const char *desc)
 {
-    int i, wh = params->w * params->h;
+    int i, j, wh = params->w * params->h, nislands = 0;
+    bool *last_row = snewn(params->w, bool);
 
+    memset(last_row, 0, params->w * sizeof(bool));
     for (i = 0; i < wh; i++) {
-        if (*desc >= '1' && *desc <= '9')
-            /* OK */;
-        else if (*desc >= 'a' && *desc <= 'z')
+        if ((*desc >= '1' && *desc <= '9') || (*desc >= 'A' && *desc <= 'G')) {
+            nislands++;
+            /* Look for other islands to the left and above. */
+            if ((i % params->w > 0 && last_row[i % params->w - 1]) ||
+                last_row[i % params->w]) {
+                sfree(last_row);
+                return "Game description contains joined islands";
+            }
+            last_row[i % params->w] = true;
+        } else if (*desc >= 'a' && *desc <= 'z') {
+            for (j = 0; j < *desc - 'a' + 1; j++)
+                last_row[(i + j) % params->w] = false;
             i += *desc - 'a'; /* plus the i++ */
-        else if (*desc >= 'A' && *desc <= 'G')
-            /* OK */;
-        else if (*desc == 'V' || *desc == 'W' ||
-                 *desc == 'X' || *desc == 'Y' ||
-                 *desc == 'H' || *desc == 'I' ||
-                 *desc == 'J' || *desc == 'K')
-            /* OK */;
-        else if (!*desc)
+        } else if (!*desc) {
+            sfree(last_row);
             return "Game description shorter than expected";
-        else
+        } else {
+            sfree(last_row);
             return "Game description contains unexpected character";
+        }
         desc++;
     }
+    sfree(last_row);
     if (*desc || i > wh)
         return "Game description longer than expected";
+    if (nislands < 2)
+        return "Game description has too few islands";
 
     return NULL;
 }
@@ -2105,32 +2125,47 @@ static char *ui_cancel_drag(game_ui *ui)
     ui->dragx_src = ui->dragy_src = -1;
     ui->dragx_dst = ui->dragy_dst = -1;
     ui->dragging = false;
-    return UI_UPDATE;
+    return MOVE_UI_UPDATE;
 }
 
 static game_ui *new_ui(const game_state *state)
 {
     game_ui *ui = snew(game_ui);
     ui_cancel_drag(ui);
-    ui->cur_x = state->islands[0].x;
-    ui->cur_y = state->islands[0].y;
-    ui->cur_visible = false;
+    if (state != NULL) {
+        ui->cur_x = state->islands[0].x;
+        ui->cur_y = state->islands[0].y;
+    }
+    ui->cur_visible = getenv_bool("PUZZLES_SHOW_CURSOR", false);
     ui->show_hints = false;
     return ui;
 }
 
-static void free_ui(game_ui *ui)
+static config_item *get_prefs(game_ui *ui)
 {
-    sfree(ui);
+    config_item *ret;
+
+    ret = snewn(2, config_item);
+
+    ret[0].name = "Show possible bridge locations";
+    ret[0].kw = "show-hints";
+    ret[0].type = C_BOOLEAN;
+    ret[0].u.boolean.bval = ui->show_hints;
+
+    ret[1].name = NULL;
+    ret[1].type = C_END;
+
+    return ret;
 }
 
-static char *encode_ui(const game_ui *ui)
+static void set_prefs(game_ui *ui, const config_item *cfg)
 {
-    return NULL;
+    ui->show_hints = cfg[0].u.boolean.bval;
 }
 
-static void decode_ui(game_ui *ui, const char *encoding)
+static void free_ui(game_ui *ui)
 {
+    sfree(ui);
 }
 
 static void game_changed_state(game_ui *ui, const game_state *oldstate,
@@ -2138,6 +2173,20 @@ static void game_changed_state(game_ui *ui, const game_state *oldstate,
 {
 }
 
+static const char *current_key_label(const game_ui *ui,
+                                     const game_state *state, int button)
+{
+    if (IS_CURSOR_SELECT(button)) {
+        if (!ui->cur_visible)
+            return ""; /* Actually shows cursor. */
+        if (ui->dragging || button == CURSOR_SELECT2)
+            return "Finished";
+        if (GRID(state, ui->cur_x, ui->cur_y) & G_ISLAND)
+            return "Select";
+    }
+    return "";
+}
+
 struct game_drawstate {
     int tilesize;
     int w, h;
@@ -2307,7 +2356,7 @@ static char *update_drag_dst(const game_state *state, game_ui *ui,
     /*debug(("update_drag src (%d,%d) d(%d,%d) dst (%d,%d)\n",
            ui->dragx_src, ui->dragy_src, dx, dy,
            ui->dragx_dst, ui->dragy_dst));*/
-    return UI_UPDATE;
+    return MOVE_UI_UPDATE;
 }
 
 static char *finish_drag(const game_state *state, game_ui *ui)
@@ -2342,15 +2391,15 @@ static char *interpret_move(const game_state *state, game_ui *ui,
     char buf[80], *ret;
     grid_type ggrid = INGRID(state,gx,gy) ? GRID(state,gx,gy) : 0;
     bool shift = button & MOD_SHFT, control = button & MOD_CTRL;
-    button &= ~MOD_MASK;
+    button = STRIP_BUTTON_MODIFIERS(button);
 
     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
-        if (!INGRID(state, gx, gy)) return NULL;
+        if (!INGRID(state, gx, gy)) return MOVE_UNUSED;
         ui->cur_visible = false;
         if (ggrid & G_ISLAND) {
             ui->dragx_src = gx;
             ui->dragy_src = gy;
-            return UI_UPDATE;
+            return MOVE_UI_UPDATE;
         } else
             return ui_cancel_drag(ui);
     } else if (button == LEFT_DRAG || button == RIGHT_DRAG) {
@@ -2364,7 +2413,7 @@ static char *interpret_move(const game_state *state, game_ui *ui,
             /* cancel a drag when we go back to the starting point */
             ui->dragx_dst = -1;
             ui->dragy_dst = -1;
-            return UI_UPDATE;
+            return MOVE_UI_UPDATE;
         }
     } else if (button == LEFT_RELEASE || button == RIGHT_RELEASE) {
         if (ui->dragging) {
@@ -2375,8 +2424,8 @@ static char *interpret_move(const game_state *state, game_ui *ui,
                 return ui_cancel_drag(ui);
             }
             ui_cancel_drag(ui);
-            if (!INGRID(state, gx, gy)) return NULL;
-            if (!(GRID(state, gx, gy) & G_ISLAND)) return NULL;
+            if (!INGRID(state, gx, gy)) return MOVE_UNUSED;
+            if (!(GRID(state, gx, gy) & G_ISLAND)) return MOVE_NO_EFFECT;
             sprintf(buf, "M%d,%d", gx, gy);
             return dupstr(buf);
         }
@@ -2397,9 +2446,9 @@ static char *interpret_move(const game_state *state, game_ui *ui,
         if (ui->dragging) {
             int nx = ui->cur_x, ny = ui->cur_y;
 
-            move_cursor(button, &nx, &ny, state->w, state->h, false);
+            move_cursor(button, &nx, &ny, state->w, state->h, false, NULL);
             if (nx == ui->cur_x && ny == ui->cur_y)
-                return NULL;
+                return MOVE_NO_EFFECT;
             update_drag_dst(state, ui, ds,
                              COORD(nx)+TILE_SIZE/2,
                              COORD(ny)+TILE_SIZE/2);
@@ -2451,19 +2500,19 @@ static char *interpret_move(const game_state *state, game_ui *ui,
 
                     if (!dingrid) break;
                 }
-                if (!oingrid) return UI_UPDATE;
+                if (!oingrid) return MOVE_UI_UPDATE;
             }
             /* not reached */
 
 found:
             ui->cur_x = nx;
             ui->cur_y = ny;
-            return UI_UPDATE;
+            return MOVE_UI_UPDATE;
         }
     } else if (IS_CURSOR_SELECT(button)) {
         if (!ui->cur_visible) {
             ui->cur_visible = true;
-            return UI_UPDATE;
+            return MOVE_UI_UPDATE;
         }
         if (ui->dragging || button == CURSOR_SELECT2) {
             ui_cancel_drag(ui);
@@ -2471,7 +2520,7 @@ found:
                 sprintf(buf, "M%d,%d", ui->cur_x, ui->cur_y);
                 return dupstr(buf);
             } else
-                return UI_UPDATE;
+                return MOVE_UI_UPDATE;
         } else {
             grid_type v = GRID(state, ui->cur_x, ui->cur_y);
             if (v & G_ISLAND) {
@@ -2480,7 +2529,7 @@ found:
                 ui->dragy_src = ui->cur_y;
                 ui->dragx_dst = ui->dragy_dst = -1;
                 ui->drag_is_noline = (button == CURSOR_SELECT2);
-                return UI_UPDATE;
+                return MOVE_UI_UPDATE;
             }
         }
     } else if ((button >= '0' && button <= '9') ||
@@ -2498,7 +2547,7 @@ found:
 
         if (!ui->cur_visible) {
             ui->cur_visible = true;
-            return UI_UPDATE;
+            return MOVE_UI_UPDATE;
         }
 
         for (i = 0; i < state->n_islands; ++i) {
@@ -2525,15 +2574,15 @@ found:
         if (best_x != -1 && best_y != -1) {
             ui->cur_x = best_x;
             ui->cur_y = best_y;
-            return UI_UPDATE;
+            return MOVE_UI_UPDATE;
         } else
-            return NULL;
+            return MOVE_NO_EFFECT;
     } else if (button == 'g' || button == 'G') {
         ui->show_hints = !ui->show_hints;
-        return UI_UPDATE;
+        return MOVE_UI_UPDATE;
     }
 
-    return NULL;
+    return MOVE_UNUSED;
 }
 
 static game_state *execute_move(const game_state *state, const char *move)
@@ -2557,6 +2606,8 @@ static game_state *execute_move(const game_state *state, const char *move)
                 goto badmove;
             if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
                 goto badmove;
+            /* Precisely one co-ordinate must differ between islands. */
+            if ((x1 != x2) + (y1 != y2) != 1) goto badmove;
             is1 = INDEX(ret, gridi, x1, y1);
             is2 = INDEX(ret, gridi, x2, y2);
             if (!is1 || !is2) goto badmove;
@@ -2568,6 +2619,7 @@ static game_state *execute_move(const game_state *state, const char *move)
                 goto badmove;
             if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
                 goto badmove;
+            if ((x1 != x2) + (y1 != y2) != 1) goto badmove;
             is1 = INDEX(ret, gridi, x1, y1);
             is2 = INDEX(ret, gridi, x2, y2);
             if (!is1 || !is2) goto badmove;
@@ -2636,7 +2688,7 @@ static char *solve_game(const game_state *state, const game_state *currstate,
  */
 
 static void game_compute_size(const game_params *params, int tilesize,
-                              int *x, int *y)
+                              const game_ui *ui, int *x, int *y)
 {
     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
     struct { int tilesize; } ads, *ds = &ads;
@@ -2987,9 +3039,6 @@ static void game_redraw(drawing *dr, game_drawstate *ds,
 
     /* Clear screen, if required. */
     if (!ds->started) {
-        draw_rect(dr, 0, 0,
-                  TILE_SIZE * ds->w + 2 * BORDER,
-                  TILE_SIZE * ds->h + 2 * BORDER, COL_BACKGROUND);
 #ifdef DRAW_GRID
         draw_rect_outline(dr,
                           COORD(0)-1, COORD(0)-1,
@@ -3177,22 +3226,19 @@ static int game_status(const game_state *state)
     return state->completed ? +1 : 0;
 }
 
-static bool game_timing_state(const game_state *state, game_ui *ui)
-{
-    return true;
-}
-
-static void game_print_size(const game_params *params, float *x, float *y)
+static void game_print_size(const game_params *params, const game_ui *ui,
+                            float *x, float *y)
 {
     int pw, ph;
 
     /* 10mm squares by default. */
-    game_compute_size(params, 1000, &pw, &ph);
+    game_compute_size(params, 1000, ui, &pw, &ph);
     *x = pw / 100.0F;
     *y = ph / 100.0F;
 }
 
-static void game_print(drawing *dr, const game_state *state, int ts)
+static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
+                       int ts)
 {
     int ink = print_mono_colour(dr, 0);
     int paper = print_mono_colour(dr, 1);
@@ -3266,12 +3312,14 @@ const struct game thegame = {
     free_game,
     true, solve_game,
     true, game_can_format_as_text_now, game_text_format,
+    get_prefs, set_prefs,
     new_ui,
     free_ui,
-    encode_ui,
-    decode_ui,
+    NULL, /* encode_ui */
+    NULL, /* decode_ui */
     NULL, /* game_request_keys */
     game_changed_state,
+    current_key_label,
     interpret_move,
     execute_move,
     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
@@ -3285,7 +3333,7 @@ const struct game thegame = {
     game_status,
     true, false, game_print_size, game_print,
     false,                             /* wants_statusbar */
-    false, game_timing_state,
+    false, NULL,                       /* timing_state */
     REQUIRE_RBUTTON,                   /* flags */
 };