5 * (c) 2001 Mark Wooding
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Anag: a simple wordgame helper.
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.
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.
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.
27 /*----- Header files ------------------------------------------------------*/
31 /*----- Data structures ---------------------------------------------------*/
35 typedef struct tcell {
36 struct tcell *hop[NDIR];
41 typedef struct node_track {
48 /*----- Utility functions -------------------------------------------------*/
52 * Arguments: @long a@ = the target value
54 * Returns: %$\lfloor \sqrt{a} \rfloor$%
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
66 /* --- Initial guess is half the input length --- */
68 for (i = q = a; q; q >>= 2)
71 /* --- Do the main series iteration --- */
75 if (!q || (q < 0 && -q <= 2 * i))
85 /*----- Main code ---------------------------------------------------------*/
89 * Arguments: @tcell *c@ = pointer to start cell
90 * @const char *p@ = string to match
92 * Returns: Nonzero for a match, zero if no match was found.
94 * Use: Searches for a match in a trackword.
97 static int track(tcell *c, const char *p)
107 for (cc = c->hop; *cc; cc++) {
119 /* --- Node matcher --- */
121 static int n_track(node *nn, const char *p, size_t sz)
123 node_track *n = (node_track *)nn;
128 for (c = n->c; c->ch; c++) {
135 /* --- Node creation --- */
137 node *trackword(const char *const *av)
142 const char *p = av[0], *q, *l;
143 size_t sz = strlen(p);
144 tcell *c, **cc, **ccc;
146 /* --- Work out the dimensions --- */
152 die("bad trackword `%s': not square, and no line markers", p);
157 die("bad trackword `%s': no columns", p);
168 die("bad trackword `%s': inconsistent line lengths", p);
174 die("bad trackword `%s': no rows", p);
176 /* --- Build the match node --- */
178 n = xmalloc(sizeof(*n));
181 n->c = xmalloc((x * y + 1) * sizeof(tcell));
185 for (j = 0; j < y; j++) {
188 for (i = 0; i < x; i++) {
194 #define SOK (j < y - 1)
196 #define EOK (i < x - 1)
198 if (NOK) *cc++ = c - x;
199 if (SOK) *cc++ = c + x;
200 if (WOK) *cc++ = c - 1;
201 if (EOK) *cc++ = c + 1;
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;
219 /* --- Now prune out bogus links --- */
221 for (c = n->c; c->ch; c++) {
223 for (cc = c->hop; *cc; cc++) {
224 if (isalpha((unsigned char)(*cc)->ch)) {
236 /*----- That's all, folks -------------------------------------------------*/