Commit | Line | Data |
---|---|---|
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 | |
35 | typedef struct tcell { | |
36 | struct tcell *hop[NDIR]; | |
37 | char ch; | |
38 | unsigned char f; | |
39 | } tcell; | |
40 | ||
41 | typedef 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 | ||
62 | long isqrt(long a) | |
63 | { | |
64 | long i, q; | |
65 | ||
904ac13a MW |
66 | /* Initial guess is half the input length. */ |
67 | for (i = q = a; q; q >>= 2) i >>= 1; | |
6e403221 | 68 | |
904ac13a | 69 | /* Do the main series iteration. */ |
6e403221 | 70 | for (;;) { |
904ac13a MW |
71 | q = i*i - a; |
72 | if (q > -2*i && q <= 0) return (i); | |
73 | q /= 2*i; | |
74 | if (!q) i--; | |
75 | else i -= q; | |
6e403221 | 76 | } |
77 | } | |
78 | ||
79 | /*----- Main code ---------------------------------------------------------*/ | |
80 | ||
81 | /* --- @track@ --- * | |
82 | * | |
83 | * Arguments: @tcell *c@ = pointer to start cell | |
84 | * @const char *p@ = string to match | |
85 | * | |
86 | * Returns: Nonzero for a match, zero if no match was found. | |
87 | * | |
88 | * Use: Searches for a match in a trackword. | |
89 | */ | |
90 | ||
91 | static int track(tcell *c, const char *p) | |
92 | { | |
c088671a | 93 | tcell **cc; |
6e403221 | 94 | |
904ac13a MW |
95 | if (*p++ != c->ch) return (0); |
96 | if (!*p) return (1); | |
c088671a | 97 | |
904ac13a | 98 | c->f = 1; |
c088671a | 99 | for (cc = c->hop; *cc; cc++) { |
904ac13a MW |
100 | if ((*cc)->f) continue; |
101 | if (track(*cc, p)) { c->f = 0; return (1); } | |
6e403221 | 102 | } |
103 | c->f = 0; | |
904ac13a | 104 | |
6e403221 | 105 | return (0); |
106 | } | |
107 | ||
108 | /* --- Node matcher --- */ | |
109 | ||
110 | static int n_track(node *nn, const char *p, size_t sz) | |
111 | { | |
112 | node_track *n = (node_track *)nn; | |
113 | tcell *c; | |
114 | ||
904ac13a MW |
115 | if (!*p) return (1); |
116 | for (c = n->c; c->ch; c++) | |
117 | if (track(c, p)) return (1); | |
6e403221 | 118 | return (0); |
119 | } | |
120 | ||
121 | /* --- Node creation --- */ | |
122 | ||
123 | node *trackword(const char *const *av) | |
124 | { | |
125 | node_track *n; | |
126 | unsigned x, y; | |
127 | unsigned i, j; | |
128 | const char *p = av[0], *q, *l; | |
129 | size_t sz = strlen(p); | |
c088671a | 130 | tcell *c, **cc, **ccc; |
6e403221 | 131 | |
904ac13a | 132 | /* Work out the dimensions. */ |
6e403221 | 133 | x = strcspn(p, "/"); |
134 | if (!p[x]) { | |
135 | x = isqrt(sz); | |
904ac13a | 136 | if (x*x != sz) |
6e403221 | 137 | die("bad trackword `%s': not square, and no line markers", p); |
138 | y = x; | |
139 | } | |
140 | ||
904ac13a | 141 | if (!x) die("bad trackword `%s': no columns", p); |
6e403221 | 142 | |
143 | y = 0; | |
144 | l = p + sz; | |
145 | q = p; | |
146 | for (;;) { | |
904ac13a MW |
147 | if (*q == '/') q++; |
148 | if (!*q) break; | |
6e403221 | 149 | if (l - q < x) |
150 | die("bad trackword `%s': inconsistent line lengths", p); | |
151 | q += x; | |
152 | y++; | |
153 | } | |
154 | ||
904ac13a | 155 | if (!y) die("bad trackword `%s': no rows", p); |
6e403221 | 156 | |
904ac13a | 157 | /* Build the match node. */ |
6e403221 | 158 | n = xmalloc(sizeof(*n)); |
159 | n->n.func = n_track; | |
160 | n->x = x; n->y = y; | |
904ac13a | 161 | n->c = xmalloc((x*y + 1)*sizeof(tcell)); |
6e403221 | 162 | |
163 | q = p; | |
164 | c = n->c; | |
165 | for (j = 0; j < y; j++) { | |
904ac13a | 166 | if (*q == '/') q++; |
6e403221 | 167 | for (i = 0; i < x; i++) { |
168 | c->ch = *q++; | |
169 | c->f = 0; | |
c088671a | 170 | cc = c->hop; |
6e403221 | 171 | |
172 | #define NOK (j > 0) | |
173 | #define SOK (j < y - 1) | |
174 | #define WOK (i > 0) | |
175 | #define EOK (i < x - 1) | |
176 | ||
c088671a | 177 | if (NOK) *cc++ = c - x; |
178 | if (SOK) *cc++ = c + x; | |
179 | if (WOK) *cc++ = c - 1; | |
180 | if (EOK) *cc++ = c + 1; | |
6e403221 | 181 | |
c088671a | 182 | if (NOK && WOK) *cc++ = c - x - 1; |
183 | if (NOK && EOK) *cc++ = c - x + 1; | |
184 | if (SOK && WOK) *cc++ = c + x - 1; | |
185 | if (SOK && EOK) *cc++ = c + x + 1; | |
6e403221 | 186 | |
187 | #undef NOK | |
188 | #undef SOK | |
189 | #undef WOK | |
190 | #undef EOK | |
191 | ||
c088671a | 192 | *cc++ = 0; |
6e403221 | 193 | c++; |
194 | } | |
195 | } | |
196 | c->ch = 0; | |
197 | ||
904ac13a | 198 | /* Now prune out bogus links. */ |
c088671a | 199 | for (c = n->c; c->ch; c++) { |
200 | ccc = c->hop; | |
904ac13a MW |
201 | for (cc = c->hop; *cc; cc++) |
202 | if (isalpha((unsigned char)(*cc)->ch)) *ccc++ = *cc; | |
c088671a | 203 | *ccc++ = 0; |
204 | } | |
205 | ||
904ac13a | 206 | /* Done. */ |
6e403221 | 207 | return (&n->n); |
208 | } | |
209 | ||
210 | /*----- That's all, folks -------------------------------------------------*/ |