GnuCash  4.11-243-g1cac132214+
QuickFill.c
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 
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 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
81 destroy_helper (gpointer key, gpointer value, gpointer data)
82 {
83  gnc_quickfill_destroy (value);
84  return TRUE;
85 }
86 
87 void
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
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 *
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 *
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 *
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 *
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
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 *
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
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
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
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
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
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 \********************************************************************/
void gnc_quickfill_insert(QuickFill *qf, const char *text, QuickFillSort sort)
Add the string "text" to the collection of searchable strings.
Definition: QuickFill.c:229
QuickFill * gnc_quickfill_get_char_match(QuickFill *qf, gunichar uc)
Return the subnode of the tree whose strings all hold &#39;wc&#39; as the next letter.
Definition: QuickFill.c:135
utility functions for the GnuCash UI
#define DEBUG(format, args...)
Print a debugging message.
Definition: qoflog.h:264
#define PWARN(format, args...)
Log a warning.
Definition: qoflog.h:250
QuickFill * gnc_quickfill_get_string_len_match(QuickFill *qf, const char *str, int len)
Same as gnc_quickfill_get_string_match(), except that the string length is explicitly specified...
Definition: QuickFill.c:150
QuickFill * gnc_quickfill_get_string_match(QuickFill *qf, const char *str)
Return a subnode in the tree whose strings all match the string &#39;str&#39; as the next substring...
Definition: QuickFill.c:179
All type declarations for the whole Gnucash engine.
const char * gnc_quickfill_string(QuickFill *qf)
For the given node &#39;qf&#39;, return the best-guess matching string.
Definition: QuickFill.c:123
QuickFill is used to auto-complete typed user entries.
QuickFill * gnc_quickfill_get_unique_len_match(QuickFill *qf, int *length)
Walk a &#39;unique&#39; part of the QuickFill tree.
Definition: QuickFill.c:199