[anag] / trackword.c

/* -*-c-*-
 *
 * $Id: trackword.c,v 1.1 2001/02/04 17:14:42 mdw Exp $
 *
 * Matches trackwords
 *
 * (c) 2001 Mark Wooding
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Anag: a simple wordgame helper.
 *
 * Anag is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * Anag is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with Anag; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: trackword.c,v $
 * Revision 1.1  2001/02/04 17:14:42  mdw
 * Initial checkin
 *
 */

/*----- Header files ------------------------------------------------------*/

#include "anag.h"

/*----- Data structures ---------------------------------------------------*/

enum { N, NE, E, SE, S, SW, W, NW, NDIR };

typedef struct tcell {
  struct tcell *hop[NDIR];
  char ch;
  unsigned char f;
} tcell;

typedef struct node_track {
  node n;
  unsigned x;
  unsigned y;
  tcell *c;
} node_track;

/*----- Utility functions -------------------------------------------------*/

/* --- @isqrt@ --- *
 *
 * Arguments:   @long a@ = the target value
 *
 * Returns:     %$\lfloor \sqrt{a} \rfloor$%
 *
 * Use:         Computes an integer square root.  This algorithm is
 *              Newton-Raphson with integers.  I've stolen this more-or-less
 *              wholesale fom the multiprecision integer square-root function
 *              in Catacomb.
 */

long isqrt(long a)
{
  long i, q;

  /* --- Initial guess is half the input length --- */

  for (i = q = a; q; q >>= 2)
    i >>= 1;

  /* --- Do the main series iteration --- */

  for (;;) {
    q = i * i - a;
    if (!q || (q < 0 && -q <= 2 * i))
      return (i);
    q /= 2 * i;
    if (!q)
      i--;
    else
      i -= q;
  }
}

/*----- Main code ---------------------------------------------------------*/

/* --- @track@ --- *
 *
 * Arguments:   @tcell *c@ = pointer to start cell
 *              @const char *p@ = string to match
 *
 * Returns:     Nonzero for a match, zero if no match was found.
 *
 * Use:         Searches for a match in a trackword.
 */

static int track(tcell *c, const char *p)
{
  int i;

  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)
      continue;
    if (track(c->hop[i], p)) {
      c->f = 0;
      return (1);
    }
  }
  c->f = 0;
  return (0);
}

/* --- Node matcher --- */

static int n_track(node *nn, const char *p, size_t sz)
{
  node_track *n = (node_track *)nn;
  tcell *c;

  if (!*p)
    return (1);
  for (c = n->c; c->ch; c++) {
    if (track(c, p))
      return (1);
  }
  return (0);
}

/* --- Node creation --- */

node *trackword(const char *const *av)
{
  node_track *n;
  unsigned x, y;
  unsigned i, j;
  const char *p = av[0], *q, *l;
  size_t sz = strlen(p);
  tcell *c;

  /* --- Work out the dimensions --- */

  x = strcspn(p, "/");
  if (!p[x]) {
    x = isqrt(sz);
    if (x * x != sz)
      die("bad trackword `%s': not square, and no line markers", p);
    y = x;
  }

  if (!x)
    die("bad trackword `%s': no columns", p);

  y = 0;
  l = p + sz;
  q = p;
  for (;;) {
    if (*q == '/')
      q++;
    if (!*q)
      break;
    if (l - q < x)
      die("bad trackword `%s': inconsistent line lengths", p);
    q += x;
    y++;
  }

  if (!y)
    die("bad trackword `%s': no rows", p);

  /* --- Build the match node --- */

  n = xmalloc(sizeof(*n));
  n->n.func = n_track;
  n->x = x; n->y = y;
  n->c = xmalloc((x * y + 1) * sizeof(tcell));

  q = p;
  c = n->c;
  for (j = 0; j < y; j++) {
    if (*q == '/')
      q++;
    for (i = 0; i < x; i++) {
      c->ch = *q++;
      c->f = 0;

#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;

      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;

#undef NOK
#undef SOK
#undef WOK
#undef EOK

      c++;
    }
  }
  c->ch = 0;

  /* --- Done --- */

  c = n->c;
  for (j = 0; j < y; j++) {
    for (i = 0; i < x; i++) {
      printf("%c ", c->ch);
      c++;
    }
    fputc('\n', stdout);
  }

  return (&n->n);
}

/*----- That's all, folks -------------------------------------------------*/