From: mdw <mdw>
Date: Wed, 7 Feb 2001 09:08:44 +0000 (+0000)
Subject: Optimize the graph by removing edges to non-matching cells.  Make all of
X-Git-Tag: 1.0.0~8
X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/anag/commitdiff_plain/c088671a6a6d980bd7329c9f36ccb438f6ddfafe

Optimize the graph by removing edges to non-matching cells.  Make all of
the graph links be contiguous so the main loop can give up earlier.
---

diff --git a/trackword.c b/trackword.c
index 68e90e5..55e0710 100644
--- a/trackword.c
+++ b/trackword.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: trackword.c,v 1.2 2001/02/04 19:52:53 mdw Exp $
+ * $Id: trackword.c,v 1.3 2001/02/07 09:08:44 mdw Exp $
  *
  * Matches trackwords
  *
@@ -29,6 +29,10 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: trackword.c,v $
+ * Revision 1.3  2001/02/07 09:08:44  mdw
+ * Optimize the graph by removing edges to non-matching cells.  Make all of
+ * the graph links be contiguous so the main loop can give up earlier.
+ *
  * Revision 1.2  2001/02/04 19:52:53  mdw
  * Remove debugging.
  *
@@ -43,7 +47,7 @@
 
 /*----- Data structures ---------------------------------------------------*/
 
-enum { N, NE, E, SE, S, SW, W, NW, NDIR };
+#define NDIR 9
 
 typedef struct tcell {
   struct tcell *hop[NDIR];
@@ -109,17 +113,18 @@ long isqrt(long a)
 
 static int track(tcell *c, const char *p)
 {
-  int i;
+  tcell **cc;
 
   if (*p++ != c->ch)
     return (0);
   if (!*p)
     return (1);
   c->f = 1;
-  for (i = 0; i < NDIR; i++) {
-    if (!c->hop[i] || c->hop[i]->f)
+
+  for (cc = c->hop; *cc; cc++) {
+    if ((*cc)->f)
       continue;
-    if (track(c->hop[i], p)) {
+    if (track(*cc, p)) {
       c->f = 0;
       return (1);
     }
@@ -153,7 +158,7 @@ node *trackword(const char *const *av)
   unsigned i, j;
   const char *p = av[0], *q, *l;
   size_t sz = strlen(p);
-  tcell *c;
+  tcell *c, **cc, **ccc;
 
   /* --- Work out the dimensions --- */
 
@@ -200,32 +205,46 @@ node *trackword(const char *const *av)
     for (i = 0; i < x; i++) {
       c->ch = *q++;
       c->f = 0;
+      cc = c->hop;
 
 #define NOK (j > 0)
 #define SOK (j < y - 1)
 #define WOK (i > 0)
 #define EOK (i < x - 1)
 
-      c->hop[N] = NOK ? c - x : 0;
-      c->hop[S] = SOK ? c + x : 0;
-      c->hop[W] = WOK ? c - 1 : 0;
-      c->hop[E] = EOK ? c + 1 : 0;
+      if (NOK) *cc++ = c - x;
+      if (SOK) *cc++ = c + x;
+      if (WOK) *cc++ = c - 1;
+      if (EOK) *cc++ = c + 1;
 
-      c->hop[NW] = NOK && WOK ? c - x - 1 : 0;
-      c->hop[NE] = NOK && EOK ? c - x + 1 : 0;
-      c->hop[SW] = SOK && WOK ? c + x - 1 : 0;
-      c->hop[SE] = SOK && EOK ? c + x + 1 : 0;
+      if (NOK && WOK) *cc++ = c - x - 1;
+      if (NOK && EOK) *cc++ = c - x + 1;
+      if (SOK && WOK) *cc++ = c + x - 1;
+      if (SOK && EOK) *cc++ = c + x + 1;
 
 #undef NOK
 #undef SOK
 #undef WOK
 #undef EOK
 
+      *cc++ = 0;
       c++;
     }
   }
   c->ch = 0;
 
+  /* --- Now prune out bogus links --- */
+
+  for (c = n->c; c->ch; c++) {
+    ccc = c->hop;
+    for (cc = c->hop; *cc; cc++) {
+      if (isalpha((unsigned char)(*cc)->ch)) {
+	*ccc++ = *cc;
+      }
+    }
+    *ccc++ = 0;
+  }
+
   /* --- Done --- */
 
   return (&n->n);