1 /* an - Anagram generator
2 Copyright (C) 2012 Paul Martin <pm@debian.org>
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
17 */
18
19 #include <stdlib.h>
20 #include <stdbool.h>
21 #include <unicode/uchar.h>
22 #include <unicode/ustring.h>
23
24 #include "bitfield.h"
25 #include "malloc.h"
26
27
28 struct bitfield *
make_bitfield(const UChar * word,const UChar * alphabet)29 make_bitfield(const UChar *word, const UChar *alphabet)
30 {
31 int alphabetlength = u_strlen(alphabet);
32 int *freqs = safe_calloc(alphabetlength, sizeof(int));
33 struct bitfield *bf;
34 int maxfreq = 0;
35 int index;
36
37 if (freqs == NULL)
38 return NULL;
39
40 while (*word) {
41 const UChar *p = alphabet;
42 for (index = 0; *p && (*p != *word); p++, index++) {
43 }
44 if (*p) {
45 freqs[index]++;
46 if (freqs[index] > maxfreq) {
47 maxfreq = freqs[index];
48 }
49 } else {
50 /* character not in alphabet */
51 free(freqs);
52 return NULL;
53 }
54 word++;
55 }
56
57 bf = safe_calloc(1, sizeof(struct bitfield));
58 if (bf != NULL) {
59 bitpattern thisbit;
60
61 bf->depth = maxfreq;
62 bf->bits = safe_calloc(sizeof(bitpattern), maxfreq);
63 thisbit = 1;
64
65 for (index = 0; index <alphabetlength; index++) {
66 bitpattern *bits = bf->bits;
67 while (freqs[index] > 0) {
68 *bits |= thisbit;
69 bits++;
70 freqs[index]--;
71 }
72 thisbit <<= 1;
73 }
74 }
75 free(freqs);
76 return bf;
77 }
78
79 void
free_bitfield(struct bitfield * bits)80 free_bitfield(struct bitfield *bits)
81 {
82 if (bits != NULL)
83 free(bits->bits);
84 free(bits);
85 }
86
87 bool
bf_contains(struct bitfield * a,struct bitfield * b)88 bf_contains(struct bitfield *a, struct bitfield *b)
89 {
90 int i;
91
92 if ((a == NULL) || (b == NULL))
93 return false;
94 if (a->depth < b->depth)
95 return false;
96 for (i = 0; i < b->depth; i++) {
97 if ((a->bits[i] & b->bits[i]) != b->bits[i])
98 return false;
99 }
100 return true;
101 }
102
103 struct bitfield *
bf_subtract(struct bitfield * a,struct bitfield * b)104 bf_subtract(struct bitfield *a, struct bitfield *b)
105 {
106 /* assumption is that both are in normalized form */
107 int i;
108 int mindepth = a->depth > b->depth ? b->depth : a->depth;
109 struct bitfield *nbf = safe_calloc(sizeof(struct bitfield), 1);
110 nbf->bits = safe_calloc(sizeof(bitpattern), a->depth);
111 nbf->depth = a->depth;
112
113 for (i = 0; i < mindepth; i++) {
114 nbf->bits[i] = a->bits[i] & ~(a->bits[i] & b->bits[i]);
115 }
116 for (;i < a->depth ; i++ ) {
117 nbf->bits[i] = a->bits[i];
118 }
119 for (;i < b->depth ; i++ ) {
120 nbf->bits[i] = b->bits[i];
121 }
122 return bf_normalize(nbf);
123 }
124
125 struct bitfield *
bf_normalize(struct bitfield * bf)126 bf_normalize(struct bitfield *bf)
127 {
128 /* pack down the bits depthwise*/
129 if (bf != NULL) {
130 int i,j;
131 bitpattern *tbits = safe_calloc(sizeof(bitpattern), bf->depth);
132 bitpattern t;
133 for (i = 0; i < bf->depth; i++) {
134 t = 0;
135 for (j = 0; j < bf->depth; j++) {
136 t |= bf->bits[j];
137 }
138 tbits[i] = t;
139 if (t != 0) {
140 for (j = 0; (t != 0) && (j < bf->depth); j++) {
141 bitpattern p;
142
143 p = ~(t & bf->bits[j]);
144 t &= p;
145 bf->bits[j] &= p;
146 }
147 } else {
148 /* we have less depth than we started with */
149 bf->depth = i;
150 break;
151 }
152 }
153 free(bf->bits);
154 bf->bits = tbits;
155 }
156 return bf;
157 }
158
159 UChar *
make_alphabet(const UChar * source)160 make_alphabet(const UChar *source)
161 {
162 UChar *dest;
163 int sourcelen = u_strlen(source);
164 int x, y;
165
166 dest = safe_calloc(sourcelen + 1, sizeof(UChar));
167
168 u_strcpy(dest, source);
169
170 /* Very simple ripple sort as these are very short strings */
171 /* No advantage in using qsort() or similar */
172 for (x = 0; x < sourcelen - 1; x++) {
173 for (y = x + 1; y < sourcelen ; y++) {
174 if (dest[x] > dest[y]) {
175 UChar temp;
176
177 temp = dest[x];
178 dest[x] = dest[y];
179 dest[y] = temp;
180 }
181 }
182 }
183
184 x = y = 0;
185 while (dest[x]) {
186 if (dest[x] != dest[y])
187 dest[++y] = dest[x];
188 x++;
189 }
190 dest[++y] = dest[x];
191 return dest;
192 }
193