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

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