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

   1 /* -*-c-*-
   2  *
   3  * $Id: trackword.c,v 1.4 2004/04/08 01:36:19 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 /*----- Header files ------------------------------------------------------*/
  30
  31 #include "anag.h"
  32
  33 /*----- Data structures ---------------------------------------------------*/
  34
  35 #define NDIR 9
  36
  37 typedef struct tcell {
  38   struct tcell *hop[NDIR];
  39   char ch;
  40   unsigned char f;
  41 } tcell;
  42
  43 typedef struct node_track {
  44   node n;
  45   unsigned x;
  46   unsigned y;
  47   tcell *c;
  48 } node_track;
  49
  50 /*----- Utility functions -------------------------------------------------*/
  51
  52 /* --- @isqrt@ --- *
  53  *
  54  * Arguments:   @long a@ = the target value
  55  *
  56  * Returns:     %$\lfloor \sqrt{a} \rfloor$%
  57  *
  58  * Use:         Computes an integer square root.  This algorithm is
  59  *              Newton-Raphson with integers.  I've stolen this more-or-less
  60  *              wholesale fom the multiprecision integer square-root function
  61  *              in Catacomb.
  62  */
  63
  64 long isqrt(long a)
  65 {
  66   long i, q;
  67
  68   /* --- Initial guess is half the input length --- */
  69
  70   for (i = q = a; q; q >>= 2)
  71     i >>= 1;
  72
  73   /* --- Do the main series iteration --- */
  74
  75   for (;;) {
  76     q = i * i - a;
  77     if (!q || (q < 0 && -q <= 2 * i))
  78       return (i);
  79     q /= 2 * i;
  80     if (!q)
  81       i--;
  82     else
  83       i -= q;
  84   }
  85 }
  86
  87 /*----- Main code ---------------------------------------------------------*/
  88
  89 /* --- @track@ --- *
  90  *
  91  * Arguments:   @tcell *c@ = pointer to start cell
  92  *              @const char *p@ = string to match
  93  *
  94  * Returns:     Nonzero for a match, zero if no match was found.
  95  *
  96  * Use:         Searches for a match in a trackword.
  97  */
  98
  99 static int track(tcell *c, const char *p)
 100 {
 101   tcell **cc;
 102
 103   if (*p++ != c->ch)
 104     return (0);
 105   if (!*p)
 106     return (1);
 107   c->f = 1;
 108
 109   for (cc = c->hop; *cc; cc++) {
 110     if ((*cc)->f)
 111       continue;
 112     if (track(*cc, p)) {
 113       c->f = 0;
 114       return (1);
 115     }
 116   }
 117   c->f = 0;
 118   return (0);
 119 }
 120
 121 /* --- Node matcher --- */
 122
 123 static int n_track(node *nn, const char *p, size_t sz)
 124 {
 125   node_track *n = (node_track *)nn;
 126   tcell *c;
 127
 128   if (!*p)
 129     return (1);
 130   for (c = n->c; c->ch; c++) {
 131     if (track(c, p))
 132       return (1);
 133   }
 134   return (0);
 135 }
 136
 137 /* --- Node creation --- */
 138
 139 node *trackword(const char *const *av)
 140 {
 141   node_track *n;
 142   unsigned x, y;
 143   unsigned i, j;
 144   const char *p = av[0], *q, *l;
 145   size_t sz = strlen(p);
 146   tcell *c, **cc, **ccc;
 147
 148   /* --- Work out the dimensions --- */
 149
 150   x = strcspn(p, "/");
 151   if (!p[x]) {
 152     x = isqrt(sz);
 153     if (x * x != sz)
 154       die("bad trackword `%s': not square, and no line markers", p);
 155     y = x;
 156   }
 157
 158   if (!x)
 159     die("bad trackword `%s': no columns", p);
 160
 161   y = 0;
 162   l = p + sz;
 163   q = p;
 164   for (;;) {
 165     if (*q == '/')
 166       q++;
 167     if (!*q)
 168       break;
 169     if (l - q < x)
 170       die("bad trackword `%s': inconsistent line lengths", p);
 171     q += x;
 172     y++;
 173   }
 174
 175   if (!y)
 176     die("bad trackword `%s': no rows", p);
 177
 178   /* --- Build the match node --- */
 179
 180   n = xmalloc(sizeof(*n));
 181   n->n.func = n_track;
 182   n->x = x; n->y = y;
 183   n->c = xmalloc((x * y + 1) * sizeof(tcell));
 184
 185   q = p;
 186   c = n->c;
 187   for (j = 0; j < y; j++) {
 188     if (*q == '/')
 189       q++;
 190     for (i = 0; i < x; i++) {
 191       c->ch = *q++;
 192       c->f = 0;
 193       cc = c->hop;
 194
 195 #define NOK (j > 0)
 196 #define SOK (j < y - 1)
 197 #define WOK (i > 0)
 198 #define EOK (i < x - 1)
 199
 200       if (NOK) *cc++ = c - x;
 201       if (SOK) *cc++ = c + x;
 202       if (WOK) *cc++ = c - 1;
 203       if (EOK) *cc++ = c + 1;
 204
 205       if (NOK && WOK) *cc++ = c - x - 1;
 206       if (NOK && EOK) *cc++ = c - x + 1;
 207       if (SOK && WOK) *cc++ = c + x - 1;
 208       if (SOK && EOK) *cc++ = c + x + 1;
 209
 210 #undef NOK
 211 #undef SOK
 212 #undef WOK
 213 #undef EOK
 214
 215       *cc++ = 0;
 216       c++;
 217     }
 218   }
 219   c->ch = 0;
 220
 221   /* --- Now prune out bogus links --- */
 222
 223   for (c = n->c; c->ch; c++) {
 224     ccc = c->hop;
 225     for (cc = c->hop; *cc; cc++) {
 226       if (isalpha((unsigned char)(*cc)->ch)) {
 227         *ccc++ = *cc;
 228       }
 229     }
 230     *ccc++ = 0;
 231   }
 232
 233   /* --- Done --- */
 234
 235   return (&n->n);
 236 }
 237
 238 /*----- That's all, folks -------------------------------------------------*/