chiark - git - mdw - anag/blob - anagram.c

   1 /* -*-c-*-
   2  *
   3  * Matches anagrams and subgrams
   4  *
   5  * (c) 2001 Mark Wooding
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   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.
  16  *
  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.
  21  *
  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
  27 /*----- Header files ------------------------------------------------------*/
  28
  29 #include "anag.h"
  30
  31 /*----- Data structures ---------------------------------------------------*/
  32
  33 typedef struct node_gram {
  34   node n;
  35   size_t sz;
  36   unsigned f[UCHAR_MAX + 1];
  37 } node_gram;
  38
  39 /*----- Main code ---------------------------------------------------------*/
  40
  41 /* --- @compile@ --- *
  42  *
  43  * Arguments:   @node_gram *n@ = pointer to node to fill in
  44  *              @const char *p@ = pointer to string to compile from
  45  *
  46  * Returns:     The length of the string.
  47  *
  48  * Use:         Fills in an anagram node with letter frequencies.
  49  */
  50
  51 static size_t compile(node_gram *n, const char *p)
  52 {
  53   size_t len = 0;
  54   unsigned i;
  55   memset(n->f, 0, sizeof(n->f));
  56   while (*p) {
  57     i = (unsigned char)*p++;
  58     n->f[i]++;
  59     len++;
  60   }
  61   return (len);
  62 }
  63
  64 /* --- Node matcher --- */
  65
  66 static int n_gram(node *nn, const char *p, size_t sz)
  67 {
  68   node_gram *n = (node_gram *)nn;
  69   unsigned f[UCHAR_MAX];
  70   const char *q;
  71   unsigned i;
  72
  73   if (n->sz && sz != n->sz)
  74     return (0);
  75   memcpy(f, n->f, sizeof(f));
  76   q = p + sz;
  77   while (p < q) {
  78     i = (unsigned char)*p++;
  79     if (f[i])
  80       f[i]--;
  81     else if (f['.'])
  82       f['.']--;
  83     else
  84       return (0);
  85   }
  86   return (1);
  87 }
  88
  89 /* --- Node creation --- */
  90
  91 node *anagram(const char *const *av)
  92 {
  93   node_gram *n = xmalloc(sizeof(*n));
  94   n->n.func = n_gram;
  95   n->sz = compile(n, av[0]);
  96   return (&n->n);
  97 }
  98
  99 node *subgram(const char *const *av)
 100 {
 101   node_gram *n = xmalloc(sizeof(*n));
 102   n->n.func = n_gram;
 103   n->sz = 0;
 104   compile(n, av[0]);
 105   return (&n->n);
 106 }
 107
 108 /*----- That's all, folks -------------------------------------------------*/