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

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