mdw@git.distorted.org.uk Git - anag/blob - trackword.c

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