3 * $Id: trackword.c,v 1.2 2001/02/04 19:52:53 mdw Exp $
7 * (c) 2001 Mark Wooding
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Anag: a simple wordgame helper.
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.
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.
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.
29 /*----- Revision history --------------------------------------------------*
31 * $Log: trackword.c,v $
32 * Revision 1.2 2001/02/04 19:52:53 mdw
35 * Revision 1.1 2001/02/04 17:14:42 mdw
40 /*----- Header files ------------------------------------------------------*/
44 /*----- Data structures ---------------------------------------------------*/
46 enum { N, NE, E, SE, S, SW, W, NW, NDIR };
48 typedef struct tcell {
49 struct tcell *hop[NDIR];
54 typedef struct node_track {
61 /*----- Utility functions -------------------------------------------------*/
65 * Arguments: @long a@ = the target value
67 * Returns: %$\lfloor \sqrt{a} \rfloor$%
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
79 /* --- Initial guess is half the input length --- */
81 for (i = q = a; q; q >>= 2)
84 /* --- Do the main series iteration --- */
88 if (!q || (q < 0 && -q <= 2 * i))
98 /*----- Main code ---------------------------------------------------------*/
102 * Arguments: @tcell *c@ = pointer to start cell
103 * @const char *p@ = string to match
105 * Returns: Nonzero for a match, zero if no match was found.
107 * Use: Searches for a match in a trackword.
110 static int track(tcell *c, const char *p)
119 for (i = 0; i < NDIR; i++) {
120 if (!c->hop[i] || c->hop[i]->f)
122 if (track(c->hop[i], p)) {
131 /* --- Node matcher --- */
133 static int n_track(node *nn, const char *p, size_t sz)
135 node_track *n = (node_track *)nn;
140 for (c = n->c; c->ch; c++) {
147 /* --- Node creation --- */
149 node *trackword(const char *const *av)
154 const char *p = av[0], *q, *l;
155 size_t sz = strlen(p);
158 /* --- Work out the dimensions --- */
164 die("bad trackword `%s': not square, and no line markers", p);
169 die("bad trackword `%s': no columns", p);
180 die("bad trackword `%s': inconsistent line lengths", p);
186 die("bad trackword `%s': no rows", p);
188 /* --- Build the match node --- */
190 n = xmalloc(sizeof(*n));
193 n->c = xmalloc((x * y + 1) * sizeof(tcell));
197 for (j = 0; j < y; j++) {
200 for (i = 0; i < x; i++) {
205 #define SOK (j < y - 1)
207 #define EOK (i < x - 1)
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;
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;
234 /*----- That's all, folks -------------------------------------------------*/