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

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