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

   1 /* -*-c-*-
   2  *
   3  * $Id: anagram.c,v 1.2 2004/04/08 01:36:19 mdw Exp $
   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       return (0);
  83     f[i]--;
  84   }
  85   return (1);
  86 }
  87
  88 /* --- Node creation --- */
  89
  90 node *anagram(const char *const *av)
  91 {
  92   node_gram *n = xmalloc(sizeof(*n));
  93   n->n.func = n_gram;
  94   n->sz = compile(n, av[0]);
  95   return (&n->n);
  96 }
  97
  98 node *subgram(const char *const *av)
  99 {
 100   node_gram *n = xmalloc(sizeof(*n));
 101   n->n.func = n_gram;
 102   n->sz = 0;
 103   compile(n, av[0]);
 104   return (&n->n);
 105 }
 106
 107 /*----- That's all, folks -------------------------------------------------*/