chiark / gitweb /
Quick lick of paint before we really get started.
[anag] / anagram.c
CommitLineData
6e403221 1/* -*-c-*-
2 *
6e403221 3 * Matches anagrams and subgrams
4 *
5 * (c) 2001 Mark Wooding
6 */
7
0279756e 8/*----- Licensing notice --------------------------------------------------*
6e403221 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.
0279756e 16 *
6e403221 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.
0279756e 21 *
6e403221 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
6e403221 27/*----- Header files ------------------------------------------------------*/
28
29#include "anag.h"
30
31/*----- Data structures ---------------------------------------------------*/
32
33typedef 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
51static 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
66static 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++;
a29e0def 79 if (f[i])
80 f[i]--;
81 else if (f['.'])
82 f['.']--;
83 else
6e403221 84 return (0);
6e403221 85 }
86 return (1);
87}
88
89/* --- Node creation --- */
90
91node *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
99node *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 -------------------------------------------------*/