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