chiark - git - mdw - anag/blob - trackword.c

   1 /* -*-c-*-
   2  *
   3  * Matches trackwords
   4  *
   5  * (c) 2001 Mark Wooding
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Anag: a simple wordgame helper.
  11  *
  12  * Anag is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU General Public License as published by
  14  * the Free Software Foundation; either version 2 of the License, or
  15  * (at your option) any later version.
  16  *
  17  * Anag is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with Anag; if not, write to the Free Software Foundation,
  24  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  25  */
  26
  27 /*----- Header files ------------------------------------------------------*/
  28
  29 #include "anag.h"
  30
  31 /*----- Data structures ---------------------------------------------------*/
  32
  33 #define NDIR 9
  34
  35 typedef struct tcell {
  36   struct tcell *hop[NDIR];
  37   char ch;
  38   unsigned char f;
  39 } tcell;
  40
  41 typedef struct node_track {
  42   node n;
  43   unsigned x;
  44   unsigned y;
  45   tcell *c;
  46 } node_track;
  47
  48 /*----- Utility functions -------------------------------------------------*/
  49
  50 /* --- @isqrt@ --- *
  51  *
  52  * Arguments:   @long a@ = the target value
  53  *
  54  * Returns:     %$\lfloor \sqrt{a} \rfloor$%
  55  *
  56  * Use:         Computes an integer square root.  This algorithm is
  57  *              Newton-Raphson with integers.  I've stolen this more-or-less
  58  *              wholesale fom the multiprecision integer square-root function
  59  *              in Catacomb.
  60  */
  61
  62 long isqrt(long a)
  63 {
  64   long i, q;
  65
  66   /* --- Initial guess is half the input length --- */
  67
  68   for (i = q = a; q; q >>= 2)
  69     i >>= 1;
  70
  71   /* --- Do the main series iteration --- */
  72
  73   for (;;) {
  74     q = i * i - a;
  75     if (!q || (q < 0 && -q <= 2 * i))
  76       return (i);
  77     q /= 2 * i;
  78     if (!q)
  79       i--;
  80     else
  81       i -= q;
  82   }
  83 }
  84
  85 /*----- Main code ---------------------------------------------------------*/
  86
  87 /* --- @track@ --- *
  88  *
  89  * Arguments:   @tcell *c@ = pointer to start cell
  90  *              @const char *p@ = string to match
  91  *
  92  * Returns:     Nonzero for a match, zero if no match was found.
  93  *
  94  * Use:         Searches for a match in a trackword.
  95  */
  96
  97 static int track(tcell *c, const char *p)
  98 {
  99   tcell **cc;
 100
 101   if (*p++ != c->ch)
 102     return (0);
 103   if (!*p)
 104     return (1);
 105   c->f = 1;
 106
 107   for (cc = c->hop; *cc; cc++) {
 108     if ((*cc)->f)
 109       continue;
 110     if (track(*cc, p)) {
 111       c->f = 0;
 112       return (1);
 113     }
 114   }
 115   c->f = 0;
 116   return (0);
 117 }
 118
 119 /* --- Node matcher --- */
 120
 121 static int n_track(node *nn, const char *p, size_t sz)
 122 {
 123   node_track *n = (node_track *)nn;
 124   tcell *c;
 125
 126   if (!*p)
 127     return (1);
 128   for (c = n->c; c->ch; c++) {
 129     if (track(c, p))
 130       return (1);
 131   }
 132   return (0);
 133 }
 134
 135 /* --- Node creation --- */
 136
 137 node *trackword(const char *const *av)
 138 {
 139   node_track *n;
 140   unsigned x, y;
 141   unsigned i, j;
 142   const char *p = av[0], *q, *l;
 143   size_t sz = strlen(p);
 144   tcell *c, **cc, **ccc;
 145
 146   /* --- Work out the dimensions --- */
 147
 148   x = strcspn(p, "/");
 149   if (!p[x]) {
 150     x = isqrt(sz);
 151     if (x * x != sz)
 152       die("bad trackword `%s': not square, and no line markers", p);
 153     y = x;
 154   }
 155
 156   if (!x)
 157     die("bad trackword `%s': no columns", p);
 158
 159   y = 0;
 160   l = p + sz;
 161   q = p;
 162   for (;;) {
 163     if (*q == '/')
 164       q++;
 165     if (!*q)
 166       break;
 167     if (l - q < x)
 168       die("bad trackword `%s': inconsistent line lengths", p);
 169     q += x;
 170     y++;
 171   }
 172
 173   if (!y)
 174     die("bad trackword `%s': no rows", p);
 175
 176   /* --- Build the match node --- */
 177
 178   n = xmalloc(sizeof(*n));
 179   n->n.func = n_track;
 180   n->x = x; n->y = y;
 181   n->c = xmalloc((x * y + 1) * sizeof(tcell));
 182
 183   q = p;
 184   c = n->c;
 185   for (j = 0; j < y; j++) {
 186     if (*q == '/')
 187       q++;
 188     for (i = 0; i < x; i++) {
 189       c->ch = *q++;
 190       c->f = 0;
 191       cc = c->hop;
 192
 193 #define NOK (j > 0)
 194 #define SOK (j < y - 1)
 195 #define WOK (i > 0)
 196 #define EOK (i < x - 1)
 197
 198       if (NOK) *cc++ = c - x;
 199       if (SOK) *cc++ = c + x;
 200       if (WOK) *cc++ = c - 1;
 201       if (EOK) *cc++ = c + 1;
 202
 203       if (NOK && WOK) *cc++ = c - x - 1;
 204       if (NOK && EOK) *cc++ = c - x + 1;
 205       if (SOK && WOK) *cc++ = c + x - 1;
 206       if (SOK && EOK) *cc++ = c + x + 1;
 207
 208 #undef NOK
 209 #undef SOK
 210 #undef WOK
 211 #undef EOK
 212
 213       *cc++ = 0;
 214       c++;
 215     }
 216   }
 217   c->ch = 0;
 218
 219   /* --- Now prune out bogus links --- */
 220
 221   for (c = n->c; c->ch; c++) {
 222     ccc = c->hop;
 223     for (cc = c->hop; *cc; cc++) {
 224       if (isalpha((unsigned char)(*cc)->ch)) {
 225         *ccc++ = *cc;
 226       }
 227     }
 228     *ccc++ = 0;
 229   }
 230
 231   /* --- Done --- */
 232
 233   return (&n->n);
 234 }
 235
 236 /*----- That's all, folks -------------------------------------------------*/