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 *
gnc_quickfill_new(void)57 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 qf = g_new (QuickFill, 1);
68
69 qf->text = NULL;
70 qf->len = 0;
71
72 qf->matches = g_hash_table_new (g_direct_hash, g_direct_equal);
73
74 return qf;
75 }
76
77 /********************************************************************\
78 \********************************************************************/
79
80 static gboolean
destroy_helper(gpointer key,gpointer value,gpointer data)81 destroy_helper (gpointer key, gpointer value, gpointer data)
82 {
83 gnc_quickfill_destroy (value);
84 return TRUE;
85 }
86
87 void
gnc_quickfill_destroy(QuickFill * qf)88 gnc_quickfill_destroy (QuickFill *qf)
89 {
90 if (qf == NULL)
91 return;
92
93 g_hash_table_foreach (qf->matches, (GHFunc)destroy_helper, NULL);
94 g_hash_table_destroy (qf->matches);
95 qf->matches = NULL;
96
97 if (qf->text)
98 g_free(qf->text);
99 qf->text = NULL;
100 qf->len = 0;
101
102 g_free (qf);
103 }
104
105 void
gnc_quickfill_purge(QuickFill * qf)106 gnc_quickfill_purge (QuickFill *qf)
107 {
108 if (qf == NULL)
109 return;
110
111 g_hash_table_foreach_remove (qf->matches, destroy_helper, NULL);
112
113 if (qf->text)
114 g_free (qf->text);
115 qf->text = NULL;
116 qf->len = 0;
117 }
118
119 /********************************************************************\
120 \********************************************************************/
121
122 const char *
gnc_quickfill_string(QuickFill * qf)123 gnc_quickfill_string (QuickFill *qf)
124 {
125 if (qf == NULL)
126 return NULL;
127
128 return qf->text;
129 }
130
131 /********************************************************************\
132 \********************************************************************/
133
134 QuickFill *
gnc_quickfill_get_char_match(QuickFill * qf,gunichar uc)135 gnc_quickfill_get_char_match (QuickFill *qf, gunichar uc)
136 {
137 guint key = g_unichar_toupper (uc);
138
139 if (NULL == qf) return NULL;
140
141 DEBUG ("xaccGetQuickFill(): index = %u\n", key);
142
143 return g_hash_table_lookup (qf->matches, GUINT_TO_POINTER (key));
144 }
145
146 /********************************************************************\
147 \********************************************************************/
148
149 QuickFill *
gnc_quickfill_get_string_len_match(QuickFill * qf,const char * str,int len)150 gnc_quickfill_get_string_len_match (QuickFill *qf,
151 const char *str, int len)
152 {
153 const char *c;
154 gunichar uc;
155
156 if (NULL == qf) return NULL;
157 if (NULL == str) return NULL;
158
159 c = str;
160 while (*c && (len > 0))
161 {
162 if (qf == NULL)
163 return NULL;
164
165 uc = g_utf8_get_char (c);
166 qf = gnc_quickfill_get_char_match (qf, uc);
167
168 c = g_utf8_next_char (c);
169 len--;
170 }
171
172 return qf;
173 }
174
175 /********************************************************************\
176 \********************************************************************/
177
178 QuickFill *
gnc_quickfill_get_string_match(QuickFill * qf,const char * str)179 gnc_quickfill_get_string_match (QuickFill *qf, const char *str)
180 {
181 if (NULL == qf) return NULL;
182 if (NULL == str) return NULL;
183
184 return gnc_quickfill_get_string_len_match (qf, str, g_utf8_strlen (str, -1));
185 }
186
187 /********************************************************************\
188 \********************************************************************/
189
190 static void
unique_len_helper(gpointer key,gpointer value,gpointer data)191 unique_len_helper (gpointer key, gpointer value, gpointer data)
192 {
193 QuickFill **qf_p = data;
194
195 *qf_p = value;
196 }
197
198 QuickFill *
gnc_quickfill_get_unique_len_match(QuickFill * qf,int * length)199 gnc_quickfill_get_unique_len_match (QuickFill *qf, int *length)
200 {
201 if (length != NULL)
202 *length = 0;
203
204 if (qf == NULL)
205 return NULL;
206
207 while (1)
208 {
209 guint count;
210
211 count = g_hash_table_size (qf->matches);
212
213 if (count != 1)
214 break;
215
216 g_hash_table_foreach (qf->matches, unique_len_helper, &qf);
217
218 if (length != NULL)
219 (*length)++;
220 }
221
222 return qf;
223 }
224
225 /********************************************************************\
226 \********************************************************************/
227
228 void
gnc_quickfill_insert(QuickFill * qf,const char * text,QuickFillSort sort)229 gnc_quickfill_insert (QuickFill *qf, const char *text, QuickFillSort sort)
230 {
231 gchar *normalized_str;
232 int len;
233
234 if (NULL == qf) return;
235 if (NULL == text) return;
236
237
238 normalized_str = g_utf8_normalize (text, -1, G_NORMALIZE_NFC);
239 len = g_utf8_strlen (text, -1);
240 quickfill_insert_recursive (qf, normalized_str, len, normalized_str, sort);
241 g_free (normalized_str);
242 }
243
244 /********************************************************************\
245 \********************************************************************/
246
247 static void
quickfill_insert_recursive(QuickFill * qf,const char * text,int len,const char * next_char,QuickFillSort sort)248 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 if (qf == NULL)
257 return;
258
259 if ((text == NULL) || (*next_char == '\0'))
260 return;
261
262
263 key_char_uc = g_utf8_get_char (next_char);
264 key = g_unichar_toupper (key_char_uc);
265
266 match_qf = g_hash_table_lookup (qf->matches, GUINT_TO_POINTER (key));
267 if (match_qf == NULL)
268 {
269 match_qf = gnc_quickfill_new ();
270 g_hash_table_insert (qf->matches, GUINT_TO_POINTER (key), match_qf);
271 }
272
273 old_text = match_qf->text;
274
275 switch (sort)
276 {
277 case QUICKFILL_ALPHA:
278 if (old_text && (g_utf8_collate (text, old_text) >= 0))
279 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 if (old_text == NULL)
286 {
287 match_qf->text = g_strdup(text);
288 match_qf->len = len;
289 break;
290 }
291
292 /* Leave prefixes in place */
293 if ((len > match_qf->len) &&
294 (strncmp(text, old_text, strlen(old_text)) == 0))
295 break;
296
297 g_free(old_text);
298 match_qf->text = g_strdup(text);
299 match_qf->len = len;
300 break;
301 }
302
303 quickfill_insert_recursive (match_qf, text, len, g_utf8_next_char (next_char), sort);
304 }
305
306 /********************************************************************\
307 \********************************************************************/
308
309 void
gnc_quickfill_remove(QuickFill * qf,const gchar * text,QuickFillSort sort)310 gnc_quickfill_remove (QuickFill *qf, const gchar *text, QuickFillSort sort)
311 {
312 gchar *normalized_str;
313
314 if (qf == NULL) return;
315 if (text == NULL) return;
316
317 normalized_str = g_utf8_normalize (text, -1, G_NORMALIZE_NFC);
318 gnc_quickfill_remove_recursive (qf, normalized_str, 0, sort);
319 g_free (normalized_str);
320 }
321
322 /********************************************************************\
323 \********************************************************************/
324
325 struct _BestText
326 {
327 gchar *text;
328 QuickFillSort sort;
329 };
330
331 static void
best_text_helper(gpointer key,gpointer value,gpointer user_data)332 best_text_helper (gpointer key, gpointer value, gpointer user_data)
333 {
334 QuickFill *qf = value;
335 struct _BestText *best = user_data;
336
337 if (best->text == NULL)
338 {
339 /* start with the first text */
340 best->text = qf->text;
341
342 }
343 else if (best->text == QUICKFILL_LIFO)
344 {
345 /* we do not track history, so ignore it */
346 return;
347
348 }
349 else if (g_utf8_collate (qf->text, best->text) < 0)
350 {
351 /* even better text */
352 best->text = qf->text;
353 }
354 }
355
356
357
358 static void
gnc_quickfill_remove_recursive(QuickFill * qf,const gchar * text,gint depth,QuickFillSort sort)359 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 child_text = NULL;
367 child_len = 0;
368
369 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 key_char = g_utf8_offset_to_pointer (text, depth);
378 key_char_uc = g_utf8_get_char (key_char);
379 key = g_unichar_toupper (key_char_uc);
380
381 match_qf = g_hash_table_lookup (qf->matches, GUINT_TO_POINTER (key));
382 if (match_qf)
383 {
384 /* remove text from child qf */
385 gnc_quickfill_remove_recursive (match_qf, text, depth + 1, sort);
386
387 if (match_qf->text == NULL)
388 {
389 /* text was the only word with a prefix up to match_qf */
390 g_hash_table_remove (qf->matches, GUINT_TO_POINTER (key));
391 gnc_quickfill_destroy (match_qf);
392
393 }
394 else
395 {
396 /* remember remaining best child string */
397 child_text = match_qf->text;
398 child_len = match_qf->len;
399 }
400 }
401 }
402
403 if (qf->text == NULL)
404 return;
405
406 if (strcmp (text, qf->text) == 0)
407 {
408 /* the currently best text is about to be removed */
409
410 gchar *best_text = NULL;
411 gint best_len = 0;
412
413 if (child_text != NULL)
414 {
415 /* other children are pretty good as well */
416 best_text = child_text;
417 best_len = child_len;
418
419 }
420 else
421 {
422 if (g_hash_table_size (qf->matches) != 0)
423 {
424 /* otherwise search for another good text */
425 struct _BestText bts;
426 bts.text = NULL;
427 bts.sort = sort;
428
429 g_hash_table_foreach (qf->matches, (GHFunc) best_text_helper, &bts);
430 best_text = bts.text;
431 best_len = (best_text == NULL) ? 0 : g_utf8_strlen (best_text, -1);
432 }
433 }
434
435 /* now replace or clear text */
436 g_free(qf->text);
437 if (best_text != NULL)
438 {
439 qf->text = g_strdup(best_text);
440 qf->len = best_len;
441 }
442 else
443 {
444 qf->text = NULL;
445 qf->len = 0;
446 }
447 }
448 }
449
450 /********************** END OF FILE ********************************* \
451 \********************************************************************/
452