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 : \********************************************************************/
|
