Branch data Line data Source code
1 : : /********************************************************************\
2 : : * QuickFill.h -- the quickfill tree data structure *
3 : : * Copyright (C) 1997 Robin D. Clark *
4 : : * Copyright (C) 1998 Linas Vepstas *
5 : : * Copyright (C) 2000 Dave Peticolas *
6 : : * *
7 : : * This program is free software; you can redistribute it and/or *
8 : : * modify it under the terms of the GNU General Public License as *
9 : : * published by the Free Software Foundation; either version 2 of *
10 : : * the License, or (at your option) any later version. *
11 : : * *
12 : : * This program is distributed in the hope that it will be useful, *
13 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of *
14 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
15 : : * GNU General Public License for more details. *
16 : : * *
17 : : * You should have received a copy of the GNU General Public License*
18 : : * along with this program; if not, contact: *
19 : : * *
20 : : * Free Software Foundation Voice: +1-617-542-5942 *
21 : : * 51 Franklin Street, Fifth Floor Fax: +1-617-542-2652 *
22 : : * Boston, MA 02110-1301, USA gnu@gnu.org *
23 : : * *
24 : : \********************************************************************/
25 : :
26 : : #include <config.h>
27 : :
28 : : #include <string.h>
29 : :
30 : : #include "QuickFill.h"
31 : : #include "gnc-engine.h"
32 : : #include "gnc-ui-util.h"
33 : :
34 : :
35 : : struct _QuickFill
36 : : {
37 : : char *text; /* the first matching text string */
38 : : int len; /* number of chars in text string */
39 : : GHashTable *matches; /* array of children in the tree */
40 : : };
41 : :
42 : :
43 : : /** PROTOTYPES ******************************************************/
44 : : static void quickfill_insert_recursive (QuickFill *qf, const char *text, int len,
45 : : const char* next_char, QuickFillSort sort);
46 : :
47 : : static void gnc_quickfill_remove_recursive (QuickFill *qf, const gchar *text,
48 : : gint depth, QuickFillSort sort);
49 : :
50 : : /* This static indicates the debugging module that this .o belongs to. */
51 : : static QofLogModule log_module = GNC_MOD_REGISTER;
52 : :
53 : : /********************************************************************\
54 : : \********************************************************************/
55 : :
56 : : QuickFill *
57 : 0 : gnc_quickfill_new (void)
58 : : {
59 : : QuickFill *qf;
60 : :
61 : : if (sizeof (guint) < sizeof (gunichar))
62 : : {
63 : : PWARN ("Can't use quickfill");
64 : : return NULL;
65 : : }
66 : :
67 : 0 : qf = g_new (QuickFill, 1);
68 : :
69 : 0 : qf->text = NULL;
70 : 0 : qf->len = 0;
71 : :
72 : 0 : qf->matches = g_hash_table_new (g_direct_hash, g_direct_equal);
73 : :
74 : 0 : return qf;
75 : : }
76 : :
77 : : /********************************************************************\
78 : : \********************************************************************/
79 : :
80 : : static gboolean
81 : 0 : destroy_helper (gpointer key, gpointer value, gpointer data)
82 : : {
83 : 0 : gnc_quickfill_destroy (value);
84 : 0 : return TRUE;
85 : : }
86 : :
87 : : void
88 : 0 : gnc_quickfill_destroy (QuickFill *qf)
89 : : {
90 : 0 : if (qf == NULL)
91 : 0 : return;
92 : :
93 : 0 : g_hash_table_foreach (qf->matches, (GHFunc)destroy_helper, NULL);
94 : 0 : g_hash_table_destroy (qf->matches);
95 : 0 : qf->matches = NULL;
96 : :
97 : 0 : if (qf->text)
98 : 0 : g_free(qf->text);
99 : 0 : qf->text = NULL;
100 : 0 : qf->len = 0;
101 : :
102 : 0 : g_free (qf);
103 : : }
104 : :
105 : : void
106 : 0 : gnc_quickfill_purge (QuickFill *qf)
107 : : {
108 : 0 : if (qf == NULL)
109 : 0 : return;
110 : :
111 : 0 : g_hash_table_foreach_remove (qf->matches, destroy_helper, NULL);
112 : :
113 : 0 : if (qf->text)
114 : 0 : g_free (qf->text);
115 : 0 : qf->text = NULL;
116 : 0 : qf->len = 0;
117 : : }
118 : :
119 : : /********************************************************************\
120 : : \********************************************************************/
121 : :
122 : : const char *
123 : 0 : gnc_quickfill_string (QuickFill *qf)
124 : : {
125 : 0 : if (qf == NULL)
126 : 0 : return NULL;
127 : :
128 : 0 : return qf->text;
129 : : }
130 : :
131 : : /********************************************************************\
132 : : \********************************************************************/
133 : :
134 : : QuickFill *
135 : 0 : gnc_quickfill_get_char_match (QuickFill *qf, gunichar uc)
136 : : {
137 : 0 : guint key = g_unichar_toupper (uc);
138 : :
139 : 0 : if (NULL == qf) return NULL;
140 : :
141 : 0 : DEBUG ("xaccGetQuickFill(): index = %u\n", key);
142 : :
143 : 0 : return g_hash_table_lookup (qf->matches, GUINT_TO_POINTER (key));
144 : : }
145 : :
146 : : /********************************************************************\
147 : : \********************************************************************/
148 : :
149 : : QuickFill *
150 : 0 : gnc_quickfill_get_string_len_match (QuickFill *qf,
151 : : const char *str, int len)
152 : : {
153 : : const char *c;
154 : : gunichar uc;
155 : :
156 : 0 : if (NULL == qf) return NULL;
157 : 0 : if (NULL == str) return NULL;
158 : :
159 : 0 : c = str;
160 : 0 : while (*c && (len > 0))
161 : : {
162 : 0 : if (qf == NULL)
163 : 0 : return NULL;
164 : :
165 : 0 : uc = g_utf8_get_char (c);
166 : 0 : qf = gnc_quickfill_get_char_match (qf, uc);
167 : :
168 : 0 : c = g_utf8_next_char (c);
169 : 0 : len--;
170 : : }
171 : :
172 : 0 : return qf;
173 : : }
174 : :
175 : : /********************************************************************\
176 : : \********************************************************************/
177 : :
178 : : QuickFill *
179 : 0 : gnc_quickfill_get_string_match (QuickFill *qf, const char *str)
180 : : {
181 : 0 : if (NULL == qf) return NULL;
182 : 0 : if (NULL == str) return NULL;
183 : :
184 : 0 : return gnc_quickfill_get_string_len_match (qf, str, g_utf8_strlen (str, -1));
185 : : }
186 : :
187 : : /********************************************************************\
188 : : \********************************************************************/
189 : :
190 : : static void
191 : 0 : unique_len_helper (gpointer key, gpointer value, gpointer data)
192 : : {
193 : 0 : QuickFill **qf_p = data;
194 : :
195 : 0 : *qf_p = value;
196 : 0 : }
197 : :
198 : : QuickFill *
199 : 0 : gnc_quickfill_get_unique_len_match (QuickFill *qf, int *length)
200 : : {
201 : 0 : if (length != NULL)
202 : 0 : *length = 0;
203 : :
204 : 0 : if (qf == NULL)
205 : 0 : return NULL;
206 : :
207 : : while (1)
208 : 0 : {
209 : : guint count;
210 : :
211 : 0 : count = g_hash_table_size (qf->matches);
212 : :
213 : 0 : if (count != 1)
214 : 0 : break;
215 : :
216 : 0 : g_hash_table_foreach (qf->matches, unique_len_helper, &qf);
217 : :
218 : 0 : if (length != NULL)
219 : 0 : (*length)++;
220 : : }
221 : :
222 : 0 : return qf;
223 : : }
224 : :
225 : : /********************************************************************\
226 : : \********************************************************************/
227 : :
228 : : void
229 : 0 : gnc_quickfill_insert (QuickFill *qf, const char *text, QuickFillSort sort)
230 : : {
231 : : gchar *normalized_str;
232 : : int len;
233 : :
234 : 0 : if (NULL == qf) return;
235 : 0 : if (NULL == text) return;
236 : :
237 : :
238 : 0 : normalized_str = g_utf8_normalize (text, -1, G_NORMALIZE_NFC);
239 : 0 : len = g_utf8_strlen (text, -1);
240 : 0 : quickfill_insert_recursive (qf, normalized_str, len, normalized_str, sort);
241 : 0 : g_free (normalized_str);
242 : : }
243 : :
244 : : /********************************************************************\
245 : : \********************************************************************/
246 : :
247 : : static void
248 : 0 : quickfill_insert_recursive (QuickFill *qf, const char *text, int len,
249 : : const char *next_char, QuickFillSort sort)
250 : : {
251 : : guint key;
252 : : char *old_text;
253 : : QuickFill *match_qf;
254 : : gunichar key_char_uc;
255 : :
256 : 0 : if (qf == NULL)
257 : 0 : return;
258 : :
259 : 0 : if ((text == NULL) || (*next_char == '\0'))
260 : 0 : return;
261 : :
262 : :
263 : 0 : key_char_uc = g_utf8_get_char (next_char);
264 : 0 : key = g_unichar_toupper (key_char_uc);
265 : :
266 : 0 : match_qf = g_hash_table_lookup (qf->matches, GUINT_TO_POINTER (key));
267 : 0 : if (match_qf == NULL)
268 : : {
269 : 0 : match_qf = gnc_quickfill_new ();
270 : 0 : g_hash_table_insert (qf->matches, GUINT_TO_POINTER (key), match_qf);
271 : : }
272 : :
273 : 0 : old_text = match_qf->text;
274 : :
275 : 0 : switch (sort)
276 : : {
277 : 0 : case QUICKFILL_ALPHA:
278 : 0 : if (old_text && (g_utf8_collate (text, old_text) >= 0))
279 : 0 : break;
280 : : /* fall through */
281 : :
282 : : case QUICKFILL_LIFO:
283 : : default:
284 : : /* If there's no string there already, just put the new one in. */
285 : 0 : if (old_text == NULL)
286 : : {
287 : 0 : match_qf->text = g_strdup(text);
288 : 0 : match_qf->len = len;
289 : 0 : break;
290 : : }
291 : :
292 : : /* Leave prefixes in place */
293 : 0 : if ((len > match_qf->len) &&
294 : 0 : (strncmp(text, old_text, strlen(old_text)) == 0))
295 : 0 : break;
296 : :
297 : 0 : g_free(old_text);
298 : 0 : match_qf->text = g_strdup(text);
299 : 0 : match_qf->len = len;
300 : 0 : break;
301 : : }
302 : :
303 : 0 : quickfill_insert_recursive (match_qf, text, len, g_utf8_next_char (next_char), sort);
304 : : }
305 : :
306 : : /********************************************************************\
307 : : \********************************************************************/
308 : :
309 : : void
310 : 0 : gnc_quickfill_remove (QuickFill *qf, const gchar *text, QuickFillSort sort)
311 : : {
312 : : gchar *normalized_str;
313 : :
314 : 0 : if (qf == NULL) return;
315 : 0 : if (text == NULL) return;
316 : :
317 : 0 : normalized_str = g_utf8_normalize (text, -1, G_NORMALIZE_NFC);
318 : 0 : gnc_quickfill_remove_recursive (qf, normalized_str, 0, sort);
319 : 0 : g_free (normalized_str);
320 : : }
321 : :
322 : : /********************************************************************\
323 : : \********************************************************************/
324 : :
325 : : struct _BestText
326 : : {
327 : : gchar *text;
328 : : QuickFillSort sort;
329 : : };
330 : :
331 : : static void
332 : 0 : best_text_helper (gpointer key, gpointer value, gpointer user_data)
333 : : {
334 : 0 : QuickFill *qf = value;
335 : 0 : struct _BestText *best = user_data;
336 : :
337 : 0 : if (best->text == NULL)
338 : : {
339 : : /* start with the first text */
340 : 0 : best->text = qf->text;
341 : :
342 : : }
343 : 0 : else if (best->text == QUICKFILL_LIFO)
344 : : {
345 : : /* we do not track history, so ignore it */
346 : 0 : return;
347 : :
348 : : }
349 : 0 : else if (g_utf8_collate (qf->text, best->text) < 0)
350 : : {
351 : : /* even better text */
352 : 0 : best->text = qf->text;
353 : : }
354 : : }
355 : :
356 : :
357 : :
358 : : static void
359 : 0 : gnc_quickfill_remove_recursive (QuickFill *qf, const gchar *text, gint depth,
360 : : QuickFillSort sort)
361 : : {
362 : : QuickFill *match_qf;
363 : : gchar *child_text;
364 : : gint child_len;
365 : :
366 : 0 : child_text = NULL;
367 : 0 : child_len = 0;
368 : :
369 : 0 : if (depth < g_utf8_strlen (text, -1))
370 : : {
371 : : /* process next letter */
372 : :
373 : : gchar *key_char;
374 : : gunichar key_char_uc;
375 : : guint key;
376 : :
377 : 0 : key_char = g_utf8_offset_to_pointer (text, depth);
378 : 0 : key_char_uc = g_utf8_get_char (key_char);
379 : 0 : key = g_unichar_toupper (key_char_uc);
380 : :
381 : 0 : match_qf = g_hash_table_lookup (qf->matches, GUINT_TO_POINTER (key));
382 : 0 : if (match_qf)
383 : : {
384 : : /* remove text from child qf */
385 : 0 : gnc_quickfill_remove_recursive (match_qf, text, depth + 1, sort);
386 : :
387 : 0 : if (match_qf->text == NULL)
388 : : {
389 : : /* text was the only word with a prefix up to match_qf */
390 : 0 : g_hash_table_remove (qf->matches, GUINT_TO_POINTER (key));
391 : 0 : gnc_quickfill_destroy (match_qf);
392 : :
393 : : }
394 : : else
395 : : {
396 : : /* remember remaining best child string */
397 : 0 : child_text = match_qf->text;
398 : 0 : child_len = match_qf->len;
399 : : }
400 : : }
401 : : }
402 : :
403 : 0 : if (qf->text == NULL)
404 : 0 : return;
405 : :
406 : 0 : if (strcmp (text, qf->text) == 0)
407 : : {
408 : : /* the currently best text is about to be removed */
409 : :
410 : 0 : gchar *best_text = NULL;
411 : 0 : gint best_len = 0;
412 : :
413 : 0 : if (child_text != NULL)
414 : : {
415 : : /* other children are pretty good as well */
416 : 0 : best_text = child_text;
417 : 0 : best_len = child_len;
418 : :
419 : : }
420 : : else
421 : : {
422 : 0 : if (g_hash_table_size (qf->matches) != 0)
423 : : {
424 : : /* otherwise search for another good text */
425 : : struct _BestText bts;
426 : 0 : bts.text = NULL;
427 : 0 : bts.sort = sort;
428 : :
429 : 0 : g_hash_table_foreach (qf->matches, (GHFunc) best_text_helper, &bts);
430 : 0 : best_text = bts.text;
431 : 0 : best_len = (best_text == NULL) ? 0 : g_utf8_strlen (best_text, -1);
432 : : }
433 : : }
434 : :
435 : : /* now replace or clear text */
436 : 0 : g_free(qf->text);
437 : 0 : if (best_text != NULL)
438 : : {
439 : 0 : qf->text = g_strdup(best_text);
440 : 0 : qf->len = best_len;
441 : : }
442 : : else
443 : : {
444 : 0 : qf->text = NULL;
445 : 0 : qf->len = 0;
446 : : }
447 : : }
448 : : }
449 : :
450 : : /********************** END OF FILE ********************************* \
451 : : \********************************************************************/
|
