mdw@git.distorted.org.uk Git - 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 unsigned countmap[UCHAR_MAX + 1];
  34
  35 typedef struct node_gram {
  36   node n;
  37   size_t sz;
  38   countmap count;
  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:     ---
  49  *
  50  * Use:         Fills in an anagram node with letter frequencies.
  51  */
  52
  53 static void compile(const char *p, countmap count)
  54 {
  55   memset(count, 0, sizeof(countmap));
  56   while (*p) count[(unsigned char)*p++]++;
  57 }
  58
  59 /* --- Node matcher --- */
  60
  61 static int n_gram(node *nn, const char *p, size_t sz)
  62 {
  63   /* A string X is a subgram of Y unless, for some character CH, X has more
  64    * characters of value CH than Y.
  65    *
  66    * Special feature: count `.' in the pattern as meaning `don't care'.
  67    */
  68
  69   node_gram *n = (node_gram *)nn;
  70   countmap count;
  71   const char *q;
  72   unsigned i;
  73
  74   if (n->sz && sz != n->sz) return (0);
  75   memcpy(count, n->count, sizeof(count));
  76   q = p + sz;
  77   while (p < q) {
  78     i = (unsigned char)*p++;
  79     if (count[i]) count[i]--;
  80     else if (count['.']) count['.']--;
  81     else return (0);
  82   }
  83   return (1);
  84 }
  85
  86 /* --- Node creation --- */
  87
  88 node *anagram(const char *const *av)
  89 {
  90   node_gram *n = xmalloc(sizeof(*n));
  91   n->n.func = n_gram;
  92   compile(av[0], n->count);
  93   n->sz = strlen(av[0]);
  94   return (&n->n);
  95 }
  96
  97 node *subgram(const char *const *av)
  98 {
  99   node_gram *n = xmalloc(sizeof(*n));
 100   n->n.func = n_gram;
 101   compile(av[0], n->count);
 102   n->sz = 0;
 103   return (&n->n);
 104 }
 105
 106 /*----- That's all, folks -------------------------------------------------*/