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

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