Merge lp:~desrt/indicator-appmenu/hud-performance into lp:indicator-appmenu/0.4
- hud-performance
- Merge into trunk.0.4
Proposed by
Allison Karlitskaya
Status: | Merged | ||||||||
---|---|---|---|---|---|---|---|---|---|
Approved by: | Charles Kerr | ||||||||
Approved revision: | 213 | ||||||||
Merged at revision: | 197 | ||||||||
Proposed branch: | lp:~desrt/indicator-appmenu/hud-performance | ||||||||
Merge into: | lp:indicator-appmenu/0.4 | ||||||||
Diff against target: |
2576 lines (+1367/-705) 34 files modified
configure.ac (+1/-1) data/Makefile.am (+5/-13) data/com.canonical.indicator.appmenu.gschema.xml (+18/-0) data/com.canonical.indicator.appmenu.gschema.xml.in (+0/-15) data/com.canonical.indicator.appmenu.hud.gschema.xml (+16/-0) data/com.canonical.indicator.appmenu.hud.gschema.xml.in (+0/-14) data/com.canonical.indicator.appmenu.hud.search.gschema.xml (+72/-0) data/com.canonical.indicator.appmenu.hud.search.gschema.xml.in (+0/-90) po/POTFILES.in (+4/-4) src/Makefile.am (+2/-2) src/distance.c (+0/-415) src/distance.h (+0/-33) src/hudappindicatorsource.c (+4/-4) src/huddbusmenucollector.c (+3/-3) src/huddebugsource.c (+3/-3) src/hudindicatorsource.c (+3/-3) src/huditem.c (+11/-0) src/huditem.h (+2/-1) src/hudmenumodelcollector.c (+3/-3) src/hudquery.c (+9/-1) src/hudresult.c (+13/-40) src/hudresult.h (+12/-12) src/hudsettings.c (+4/-15) src/hudsettings.h (+1/-4) src/hudsource.c (+3/-3) src/hudsource.h (+13/-13) src/hudsourcelist.c (+3/-3) src/hudtoken.c (+394/-0) src/hudtoken.h (+40/-0) src/hudwindowsource.c (+9/-4) tests/Makefile.am (+18/-0) tests/hud-performance.c (+279/-0) tests/test-distance.c (+58/-6) tests/word-list.h (+364/-0) |
||||||||
To merge this branch: | bzr merge lp:~desrt/indicator-appmenu/hud-performance | ||||||||
Related bugs: |
|
Reviewer | Review Type | Date Requested | Status |
---|---|---|---|
Ted Gould (community) | Approve | ||
Review via email: mp+100480@code.launchpad.net |
Commit message
Description of the change
Improve hud-service performance and search result quality by substantially reworking the core distance algorithm and the needle/haystack assignment algorithm.
To post a comment you must log in.
- 212. By Allison Karlitskaya
-
Adjustments for Ted's review comments.
- 213. By Allison Karlitskaya
-
HudWindowSource: fix a couple of leaks
- don't leak icon name while changing windows (fixes lp:972354)
- don't leak the collector on finalize (which never happens)
Preview Diff
[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1 | === modified file 'configure.ac' |
2 | --- configure.ac 2012-03-28 23:37:14 +0000 |
3 | +++ configure.ac 2012-04-03 12:30:26 +0000 |
4 | @@ -222,7 +222,7 @@ |
5 | |
6 | GETTEXT_PACKAGE=indicator-appmenu |
7 | |
8 | -IT_PROG_INTLTOOL([0.41.0]) |
9 | +IT_PROG_INTLTOOL([0.50.2]) |
10 | |
11 | AM_GNU_GETTEXT([external]) |
12 | AM_GNU_GETTEXT_VERSION([0.17]) |
13 | |
14 | === modified file 'data/Makefile.am' |
15 | --- data/Makefile.am 2012-01-24 14:24:30 +0000 |
16 | +++ data/Makefile.am 2012-04-03 12:30:26 +0000 |
17 | @@ -1,13 +1,8 @@ |
18 | - |
19 | -gsettings_in_files = \ |
20 | - com.canonical.indicator.appmenu.gschema.xml.in \ |
21 | - com.canonical.indicator.appmenu.hud.gschema.xml.in \ |
22 | - com.canonical.indicator.appmenu.hud.search.gschema.xml.in |
23 | - |
24 | gsettings_SCHEMAS = \ |
25 | - $(gsettings_in_files:.xml.in=.xml) |
26 | + com.canonical.indicator.appmenu.gschema.xml \ |
27 | + com.canonical.indicator.appmenu.hud.gschema.xml \ |
28 | + com.canonical.indicator.appmenu.hud.search.gschema.xml |
29 | |
30 | -@INTLTOOL_XML_NOMERGE_RULE@ |
31 | @GSETTINGS_RULES@ |
32 | |
33 | dbus_servicesdir = $(DBUSSERVICEDIR) |
34 | @@ -18,10 +13,7 @@ |
35 | |
36 | EXTRA_DIST = \ |
37 | $(dbus_services_DATA:.service=.service.in) \ |
38 | - $(gsettings_in_files) |
39 | + $(gsettings_SCHEMAS) |
40 | |
41 | CLEANFILES = \ |
42 | - $(dbus_services_DATA) \ |
43 | - $(gsettings_SCHEMAS:.xml=.valid) \ |
44 | - $(gsettings_SCHEMAS) |
45 | - |
46 | + $(dbus_services_DATA) |
47 | |
48 | === added file 'data/com.canonical.indicator.appmenu.gschema.xml' |
49 | --- data/com.canonical.indicator.appmenu.gschema.xml 1970-01-01 00:00:00 +0000 |
50 | +++ data/com.canonical.indicator.appmenu.gschema.xml 2012-04-03 12:30:26 +0000 |
51 | @@ -0,0 +1,18 @@ |
52 | +<?xml version='1.0' encoding='UTF-8'?> |
53 | + |
54 | +<schemalist> |
55 | + <enum id='menu-enum'> |
56 | + <value value='0' nick='global'/> |
57 | + <value value='1' nick='locally-integrated'/> |
58 | + </enum> |
59 | + |
60 | + <schema path='/com/canonical/indicator/appmenu/' id='com.canonical.indicator.appmenu' gettext-domain='indicator-appmenu'> |
61 | + <key name='menu-mode' enum='menu-enum'> |
62 | + <default>'global'</default> |
63 | + <summary>Where the menus displayed</summary> |
64 | + <description> |
65 | + Controls the menu display location. TODO: add more |
66 | + </description> |
67 | + </key> |
68 | + </schema> |
69 | +</schemalist> |
70 | |
71 | === removed file 'data/com.canonical.indicator.appmenu.gschema.xml.in' |
72 | --- data/com.canonical.indicator.appmenu.gschema.xml.in 2012-01-17 17:38:12 +0000 |
73 | +++ data/com.canonical.indicator.appmenu.gschema.xml.in 1970-01-01 00:00:00 +0000 |
74 | @@ -1,15 +0,0 @@ |
75 | -<schemalist> |
76 | - <enum id="menu-enum"> |
77 | - <value nick="global" value="0" /> |
78 | - <value nick="locally-integrated" value="1" /> |
79 | - </enum> |
80 | - <schema id="com.canonical.indicator.appmenu" path="/com/canonical/indicator/appmenu/" gettext-domain="indicator-appmenu"> |
81 | - <key name="menu-mode" enum="menu-enum"> |
82 | - <default>'global'</default> |
83 | - <_summary>Where the menus displayed</_summary> |
84 | - <_description> |
85 | - Controls the menu display location. TODO: add more |
86 | - </_description> |
87 | - </key> |
88 | - </schema> |
89 | -</schemalist> |
90 | |
91 | === added file 'data/com.canonical.indicator.appmenu.hud.gschema.xml' |
92 | --- data/com.canonical.indicator.appmenu.hud.gschema.xml 1970-01-01 00:00:00 +0000 |
93 | +++ data/com.canonical.indicator.appmenu.hud.gschema.xml 2012-04-03 12:30:26 +0000 |
94 | @@ -0,0 +1,16 @@ |
95 | +<?xml version='1.0' encoding='UTF-8'?> |
96 | + |
97 | +<schemalist> |
98 | + <schema path='/com/canonical/indicator/appmenu/hud/' id='com.canonical.indicator.appmenu.hud' gettext-domain='indicator-appmenu'> |
99 | + <key type='b' name='store-usage-data'> |
100 | + <default>true</default> |
101 | + <summary>Whether to store usage data</summary> |
102 | + <description> |
103 | + When the HUD executes operations it stores the execution in order to |
104 | + make the future results better. Some users could choose to not want |
105 | + this data to be stored. If that is the case they should disable this |
106 | + property. |
107 | + </description> |
108 | + </key> |
109 | + </schema> |
110 | +</schemalist> |
111 | |
112 | === removed file 'data/com.canonical.indicator.appmenu.hud.gschema.xml.in' |
113 | --- data/com.canonical.indicator.appmenu.hud.gschema.xml.in 2012-01-17 17:38:12 +0000 |
114 | +++ data/com.canonical.indicator.appmenu.hud.gschema.xml.in 1970-01-01 00:00:00 +0000 |
115 | @@ -1,14 +0,0 @@ |
116 | -<schemalist> |
117 | - <schema id="com.canonical.indicator.appmenu.hud" path="/com/canonical/indicator/appmenu/hud/" gettext-domain="indicator-appmenu"> |
118 | - <key name="store-usage-data" type="b"> |
119 | - <default>true</default> |
120 | - <_summary>Whether to store usage data</_summary> |
121 | - <_description> |
122 | - When the HUD executes operations it stores the execution in |
123 | - order to make the future results better. Some users could choose |
124 | - to not want this data to be stored. If that is the case they |
125 | - should disable this property. |
126 | - </_description> |
127 | - </key> |
128 | - </schema> |
129 | -</schemalist> |
130 | |
131 | === added file 'data/com.canonical.indicator.appmenu.hud.search.gschema.xml' |
132 | --- data/com.canonical.indicator.appmenu.hud.search.gschema.xml 1970-01-01 00:00:00 +0000 |
133 | +++ data/com.canonical.indicator.appmenu.hud.search.gschema.xml 2012-04-03 12:30:26 +0000 |
134 | @@ -0,0 +1,72 @@ |
135 | +<?xml version='1.0' encoding='UTF-8'?> |
136 | + |
137 | +<schemalist> |
138 | + <schema path='/com/canonical/indicator/appmenu/hud/search/' |
139 | + id='com.canonical.indicator.appmenu.hud.search' |
140 | + gettext-domain='indicator-appmenu'> |
141 | + <key type='u' name='indicator-penalty'> |
142 | + <default>50</default> |
143 | + <summary>The penalty given to a menu item being in an indicator</summary> |
144 | + <description> |
145 | + In order to have the application's menu items appear higher in the search results a slight penalty is |
146 | + given to the indicator menu items. This value represents the percentage of that penalty so a value of |
147 | + '50' is a 50% additional to the calculated distance. |
148 | + </description> |
149 | + </key> |
150 | + |
151 | + <key type='u' name='add-penalty'> |
152 | + <default>10</default> |
153 | + <summary>Penalty for extra characters added to the search</summary> |
154 | + <description> |
155 | + The penalty for each extra character in the search string that does not appear in the text of a menu |
156 | + item. |
157 | + |
158 | + This penalty would be applied if the user typed "fiile" when searching against the menu item "File", for |
159 | + example. |
160 | + </description> |
161 | + </key> |
162 | + |
163 | + <key type='u' name='drop-penalty'> |
164 | + <default>10</default> |
165 | + <summary>Penalty applied if a character is dropped</summary> |
166 | + <description> |
167 | + The penalty for each character dropped from the search string, as compared with the text of a menu item. |
168 | + This only applies to missing characters that are not at the end of the search term. |
169 | + |
170 | + This penalty would be applied if the user typed "fle" when searching against the menu item "File", for |
171 | + example. |
172 | + </description> |
173 | + </key> |
174 | + |
175 | + <key type='u' name='end-drop-penalty'> |
176 | + <default>1</default> |
177 | + <summary>Penalty applied if a character is dropped from the end</summary> |
178 | + <description> |
179 | + The penalty for each missing character at the end of a search term. |
180 | + |
181 | + This penalty would be applied if the user typed "fil" when searching against the menu item "File", for |
182 | + example. |
183 | + </description> |
184 | + </key> |
185 | + |
186 | + <key type='u' name='swap-penalty'> |
187 | + <default>15</default> |
188 | + <summary>Penalty applied when the characters are not the same</summary> |
189 | + <description> |
190 | + The penalty for each substituted character in the search term. |
191 | + |
192 | + The penalty would be applied if the user typed "fike" when searching against the menu item "File", for |
193 | + example. |
194 | + </description> |
195 | + </key> |
196 | + |
197 | + <key type='u' name='max-distance'> |
198 | + <default>30</default> |
199 | + <summary>The highest distance value that is shown in the results</summary> |
200 | + <description> |
201 | + After the distances are calculated (including the indicator penalty) then all values above this max are |
202 | + dropped. This means that the history for those entries aren't looked up as well. |
203 | + </description> |
204 | + </key> |
205 | + </schema> |
206 | +</schemalist> |
207 | |
208 | === removed file 'data/com.canonical.indicator.appmenu.hud.search.gschema.xml.in' |
209 | --- data/com.canonical.indicator.appmenu.hud.search.gschema.xml.in 2012-03-03 13:39:53 +0000 |
210 | +++ data/com.canonical.indicator.appmenu.hud.search.gschema.xml.in 1970-01-01 00:00:00 +0000 |
211 | @@ -1,90 +0,0 @@ |
212 | -<schemalist> |
213 | - <schema id="com.canonical.indicator.appmenu.hud.search" path="/com/canonical/indicator/appmenu/hud/search/" gettext-domain="indicator-appmenu"> |
214 | - <key name="indicator-penalty" type="u"> |
215 | - <default>50</default> |
216 | - <_summary>The penalty given to a menu item being in an indicator</_summary> |
217 | - <_description> |
218 | - In order to have the application's menu items appear higher |
219 | - in the search results a slight penalty is given to the indicator |
220 | - menu items. This value represents then percentage of that penalty |
221 | - so a value of '50' is a 50% additional to the calculated distance. |
222 | - </_description> |
223 | - </key> |
224 | - <key name="add-penalty" type="u"> |
225 | - <default>10</default> |
226 | - <_summary>Penalty for extra characters added to the search</_summary> |
227 | - <_description> |
228 | - Penalty applied for extra characters that are added on the end of |
229 | - the string that are not related to the source string. |
230 | - </_description> |
231 | - </key> |
232 | - <key name="add-penalty-pre" type="u"> |
233 | - <default>1</default> |
234 | - <_summary>Penalty for extra characters added to the search before the length of the search string</_summary> |
235 | - <_description> |
236 | - Extra characters that occur before the length of the search string |
237 | - could cover them get this penalty. In the case of "return" and |
238 | - a search string of "turn" the 'r' and the 'e' would get hit with |
239 | - this penalty. |
240 | - </_description> |
241 | - </key> |
242 | - <key name="drop-penalty" type="u"> |
243 | - <default>10</default> |
244 | - <_summary>Penalty applied if a character is dropped</_summary> |
245 | - <_description> |
246 | - The penalty applied for characters that were dropped off the end |
247 | - of the search string compared to the tested string. This is mostly |
248 | - used for seeding and creating a max gradient on the edge of the |
249 | - matrix, as mostly dropped single characters are covered by the |
250 | - 'drop-penalty-end' value. |
251 | - </_description> |
252 | - </key> |
253 | - <key name="drop-penalty-end" type="u"> |
254 | - <default>10</default> |
255 | - <_summary>Penalty applied if a character is dropped after the search string length</_summary> |
256 | - <_description> |
257 | - Drop penalty that is added to characters that are longer than the |
258 | - current search string. So for a search string of "add" and a source |
259 | - string of "added" there would be drop end penalties for both 'e' and |
260 | - 'd'. |
261 | - </_description> |
262 | - </key> |
263 | - <key name="transpose-penalty" type="u"> |
264 | - <default>10</default> |
265 | - <_summary>Penalty applied when characters are transposed</_summary> |
266 | - <_description> |
267 | - When two characters are transposed this penalty is applied. This is |
268 | - for values like "ea" when the correct value is "ae". This penalty should |
269 | - be less than twice the swap penalty to have any effect. |
270 | - </_description> |
271 | - </key> |
272 | - <key name="swap-penalty" type="u"> |
273 | - <default>10</default> |
274 | - <_summary>Penalty applied when the characters are not the same</_summary> |
275 | - <_description> |
276 | - When two characters don't match at all this is the penalty |
277 | - that is given. This should probably be the highest penalty |
278 | - in the set of all the values. |
279 | - </_description> |
280 | - </key> |
281 | - <key name="swap-penalty-case" type="u"> |
282 | - <default>1</default> |
283 | - <_summary>The swap penalty when the swap is a case change</_summary> |
284 | - <_description> |
285 | - While not strictly a swap, this value allows for penalizing |
286 | - the search slightly when the only difference between the |
287 | - characters is in its case. For instance, 'c' vs. 'C'. |
288 | - </_description> |
289 | - </key> |
290 | - <key name="max-distance" type="u"> |
291 | - <default>30</default> |
292 | - <_summary>The highest distance value that is shown in the results</_summary> |
293 | - <_description> |
294 | - After the distances are calculated (including the indicator |
295 | - penalty) then all values above this max are dropped. This |
296 | - means that the history for those entries aren't looked up |
297 | - as well. |
298 | - </_description> |
299 | - </key> |
300 | - </schema> |
301 | -</schemalist> |
302 | |
303 | === modified file 'po/POTFILES.in' |
304 | --- po/POTFILES.in 2012-03-16 14:48:19 +0000 |
305 | +++ po/POTFILES.in 2012-04-03 12:30:26 +0000 |
306 | @@ -1,7 +1,6 @@ |
307 | -data/com.canonical.indicator.appmenu.gschema.xml.in |
308 | -data/com.canonical.indicator.appmenu.hud.gschema.xml.in |
309 | -data/com.canonical.indicator.appmenu.hud.search.gschema.xml.in |
310 | -src/distance.c |
311 | +data/com.canonical.indicator.appmenu.gschema.xml |
312 | +data/com.canonical.indicator.appmenu.hud.gschema.xml |
313 | +data/com.canonical.indicator.appmenu.hud.search.gschema.xml |
314 | src/dump-app-info.c |
315 | src/gdk-get-func.c |
316 | src/hudappindicatorsource.c |
317 | @@ -18,6 +17,7 @@ |
318 | src/hudsource.c |
319 | src/hudsourcelist.c |
320 | src/hudstringlist.c |
321 | +src/hudtoken.c |
322 | src/hud-verify-app-info.c |
323 | src/hudwindowsource.c |
324 | src/indicator-appmenu.c |
325 | |
326 | === modified file 'src/Makefile.am' |
327 | --- src/Makefile.am 2012-03-21 17:27:26 +0000 |
328 | +++ src/Makefile.am 2012-04-03 12:30:26 +0000 |
329 | @@ -99,8 +99,6 @@ |
330 | libhud_service_a_SOURCES = \ |
331 | create-db.h \ |
332 | create-db.c \ |
333 | - distance.h \ |
334 | - distance.c \ |
335 | dump-app-info.h \ |
336 | dump-app-info.c \ |
337 | shared-values.h \ |
338 | @@ -124,6 +122,8 @@ |
339 | hudsourcelist.c \ |
340 | hudsource.h \ |
341 | hudsource.c \ |
342 | + hudtoken.h \ |
343 | + hudtoken.c \ |
344 | hudquery.h \ |
345 | hudquery.c \ |
346 | hudstringlist.h \ |
347 | |
348 | === removed file 'src/distance.c' |
349 | --- src/distance.c 2012-03-29 15:26:51 +0000 |
350 | +++ src/distance.c 1970-01-01 00:00:00 +0000 |
351 | @@ -1,415 +0,0 @@ |
352 | -/* |
353 | -Functions to calculate the distance between two strings. |
354 | - |
355 | -Copyright 2011 Canonical Ltd. |
356 | - |
357 | -Authors: |
358 | - Ted Gould <ted@canonical.com> |
359 | - |
360 | -This program is free software: you can redistribute it and/or modify it |
361 | -under the terms of the GNU General Public License version 3, as published |
362 | -by the Free Software Foundation. |
363 | - |
364 | -This program is distributed in the hope that it will be useful, but |
365 | -WITHOUT ANY WARRANTY; without even the implied warranties of |
366 | -MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR |
367 | -PURPOSE. See the GNU General Public License for more details. |
368 | - |
369 | -You should have received a copy of the GNU General Public License along |
370 | -with this program. If not, see <http://www.gnu.org/licenses/>. |
371 | -*/ |
372 | - |
373 | -#include "distance.h" |
374 | - |
375 | -#include <glib-object.h> |
376 | -#include <glib/gprintf.h> |
377 | -#include <glib/gi18n.h> |
378 | -#include <gio/gio.h> |
379 | - |
380 | -#include "hudsettings.h" |
381 | - |
382 | -#define ADD_PENALTY hud_settings.add_penalty |
383 | -#define PRE_ADD_PENALTY hud_settings.add_penalty_pre |
384 | -#define DROP_PENALTY hud_settings.drop_penalty |
385 | -#define END_DROP_PENALTY hud_settings.drop_penalty_end |
386 | -#define TRANSPOSE_PENALTY hud_settings.transpose_penalty |
387 | -#define SWAP_PENALTY hud_settings.swap_penalty |
388 | -#define SWAP_CASE_PENALTY hud_settings.swap_penalty_case |
389 | - |
390 | -/* Figure out how far off we are from a set of characters, basically |
391 | - whether they match or not */ |
392 | -static guint |
393 | -swap_cost (gunichar a, gunichar b) |
394 | -{ |
395 | - if (a == b) |
396 | - return 0; |
397 | - if (g_unichar_toupper(a) == g_unichar_toupper(b)) |
398 | - return SWAP_CASE_PENALTY; /* Some penalty, but close */ |
399 | - return SWAP_PENALTY; |
400 | -} |
401 | - |
402 | -#define MATRIX_VAL(needle_loc, haystack_loc) (penalty_matrix[(needle_loc + 1) + (haystack_loc + 1) * (len_needle + 1)]) |
403 | - |
404 | -/* A function to print out the matrix for debugging purposes. It is |
405 | - mostly used in the test suite, though it could be used else where if |
406 | - needed */ |
407 | -static void |
408 | -dumpmatrix (const gchar * needle, guint len_needle, const gchar * haystack, guint len_haystack, guint * penalty_matrix) |
409 | -{ |
410 | -#ifndef DUMP_MATRIX |
411 | - return; |
412 | -#endif |
413 | - gint i, j; |
414 | - |
415 | - g_printf("\n"); |
416 | - /* Character Column */ |
417 | - g_printf(" "); |
418 | - /* Base val column */ |
419 | - g_printf(" "); |
420 | - for (i = 0; i < len_needle; i++) { |
421 | - g_printf("%c ", needle[i]); |
422 | - } |
423 | - g_printf("\n"); |
424 | - |
425 | - /* Character Column */ |
426 | - g_printf(" "); |
427 | - for (i = -1; i < (gint)len_needle; i++) { |
428 | - g_printf("%u ", MATRIX_VAL(i, -1)); |
429 | - } |
430 | - g_printf("\n"); |
431 | - |
432 | - for (j = 0; j < len_haystack; j++) { |
433 | - g_printf("%c ", haystack[j]); |
434 | - for (i = -1; i < (gint)len_needle; i++) { |
435 | - g_printf("%u ", MATRIX_VAL(i, j)); |
436 | - } |
437 | - g_printf("\n"); |
438 | - } |
439 | - g_printf("\n"); |
440 | - |
441 | - return; |
442 | -} |
443 | - |
444 | -/* Looks at two individual tokens, builds a matrix and calculates the |
445 | - distance between them by moving through the matrix. |
446 | - If you believe, you can see the matrix, otherwise it looks just like |
447 | - an array. */ |
448 | -static guint |
449 | -calculate_token_distance (const gchar * needle, const gchar * haystack) |
450 | -{ |
451 | - // g_debug("Comparing token '%s' to token '%s'", needle, haystack); |
452 | - |
453 | - guint len_needle = 0; |
454 | - guint len_haystack = 0; |
455 | - |
456 | - if (needle != NULL) { |
457 | - len_needle = g_utf8_strlen(needle, -1); |
458 | - } |
459 | - |
460 | - if (haystack != NULL) { |
461 | - len_haystack = g_utf8_strlen(haystack, -1); |
462 | - } |
463 | - |
464 | - /* Handle the cases of very short or NULL strings quickly */ |
465 | - if (len_needle == 0) { |
466 | - return DROP_PENALTY * len_haystack; |
467 | - } |
468 | - |
469 | - if (len_haystack == 0) { |
470 | - return ADD_PENALTY * len_needle; |
471 | - } |
472 | - |
473 | - /* Allocate the matrix of penalties */ |
474 | - guint * penalty_matrix = g_malloc0(sizeof(guint) * (len_needle + 1) * (len_haystack + 1)); |
475 | - gint len_difference; |
476 | - gint penalty; |
477 | - int i; |
478 | - |
479 | - /* Take the first row and first column and make them additional letter penalties */ |
480 | - penalty = 0; |
481 | - for (i = 0; i < len_needle + 1; i++) { |
482 | - MATRIX_VAL(i - 1, -1) = penalty; |
483 | - penalty += ADD_PENALTY; |
484 | - } |
485 | - |
486 | - len_difference = len_haystack - len_needle; |
487 | - penalty = 0; |
488 | - for (i = 0; i < len_difference; i++) { |
489 | - MATRIX_VAL(-1, i - 1) = penalty; |
490 | - penalty += PRE_ADD_PENALTY; |
491 | - } |
492 | - for (; i < len_haystack + 1; i++) { |
493 | - MATRIX_VAL(-1, i - 1) = penalty; |
494 | - penalty += DROP_PENALTY; |
495 | - } |
496 | - |
497 | - /* Now go through the matrix building up the penalties */ |
498 | - int ineedle, ihaystack; |
499 | - gchar * needle_head, * haystack_head; |
500 | - for (needle_head = (gchar *)needle, ineedle = 0; |
501 | - needle_head[0] != '\0'; |
502 | - needle_head = g_utf8_next_char(needle_head), ineedle++) { |
503 | - for (haystack_head = (gchar *)haystack, ihaystack = 0; |
504 | - haystack_head[0] != '\0'; |
505 | - haystack_head = g_utf8_next_char(haystack_head), ihaystack++) { |
506 | - gunichar needle_let = g_utf8_get_char(needle_head); |
507 | - gunichar haystack_let = g_utf8_get_char(haystack_head); |
508 | - |
509 | - guint subst_pen = MATRIX_VAL(ineedle - 1, ihaystack - 1) + swap_cost(needle_let, haystack_let); |
510 | - guint drop_pen = MATRIX_VAL(ineedle - 1, ihaystack); |
511 | - if (ineedle < ihaystack) { |
512 | - drop_pen += DROP_PENALTY; |
513 | - } else { |
514 | - drop_pen += END_DROP_PENALTY; |
515 | - } |
516 | - |
517 | - guint add_pen = MATRIX_VAL(ineedle, ihaystack - 1); |
518 | - if (len_haystack - len_needle - ineedle > 0) { |
519 | - add_pen += PRE_ADD_PENALTY; |
520 | - } else { |
521 | - add_pen += ADD_PENALTY; |
522 | - } |
523 | - guint transpose_pen = drop_pen + 1; /* ensures won't be chosen */ |
524 | - |
525 | - if (ineedle > 0 && ihaystack > 0 && needle_let == haystack[ihaystack - 1] && haystack_let == needle[ineedle - 1]) { |
526 | - transpose_pen = MATRIX_VAL(ineedle - 2, ihaystack - 2) + TRANSPOSE_PENALTY; |
527 | - } |
528 | - |
529 | - MATRIX_VAL(ineedle, ihaystack) = MIN(MIN(subst_pen, drop_pen), MIN(add_pen, transpose_pen)); |
530 | - } |
531 | - } |
532 | - |
533 | - dumpmatrix(needle, len_needle, haystack, len_haystack, penalty_matrix); |
534 | - |
535 | - guint retval = penalty_matrix[(len_needle + 1) * (len_haystack + 1) - 1]; |
536 | - g_free(penalty_matrix); |
537 | - |
538 | - return retval; |
539 | -} |
540 | - |
541 | -/* Looks through the array of paths and tries to find a minimum path |
542 | - looking up from the needle specified. This way we can look through |
543 | - all the possible paths */ |
544 | -guint |
545 | -minimize_distance_recurse (guint needle, guint num_needles, guint haystack, guint num_haystacks, guint * distances, guint * matches) |
546 | -{ |
547 | - gint i; |
548 | - |
549 | - /* Put where we are in the array so that we don't forget */ |
550 | - matches[needle] = haystack; |
551 | - |
552 | - /* First check to see if we've already used this entry */ |
553 | - for (i = needle - 1; i >= 0; i--) { |
554 | - if (matches[i] == haystack) { |
555 | - return G_MAXUINT; |
556 | - } |
557 | - } |
558 | - |
559 | - /* If we're the last needle, we can return our distance */ |
560 | - if (needle + 1 >= num_needles) { |
561 | - return distances[(needle * num_haystacks) + haystack]; |
562 | - } |
563 | - |
564 | - guint * local_match = g_new0(guint, num_needles); |
565 | - for (i = 0; i < num_needles && i < needle + 1; i++) { |
566 | - local_match[i] = matches[i]; |
567 | - } |
568 | - |
569 | - /* Now look where we can get the minimum with the other needles */ |
570 | - guint min = G_MAXUINT; |
571 | - for (i = 0; i < num_haystacks; i++) { |
572 | - guint local = minimize_distance_recurse(needle + 1, num_needles, i, num_haystacks, distances, local_match); |
573 | - |
574 | - if (local < min) { |
575 | - min = local; |
576 | - |
577 | - int j; |
578 | - for (j = needle + 1; j < num_needles; j++) { |
579 | - matches[j] = local_match[j]; |
580 | - } |
581 | - } |
582 | - } |
583 | - |
584 | - g_free(local_match); |
585 | - |
586 | - /* Return the min of everyone else plus our distance */ |
587 | - if (min < G_MAXUINT) { |
588 | - min += distances[(needle * num_haystacks) + haystack]; |
589 | - } |
590 | - |
591 | - return min; |
592 | -} |
593 | - |
594 | -/* Figuring out the lowest path through the distance array |
595 | - where we don't use the same haystack tokens */ |
596 | -guint |
597 | -minimize_distance (guint num_needles, guint num_haystacks, guint * distances, guint * matches) |
598 | -{ |
599 | - guint final_distance = G_MAXUINT; |
600 | - guint * local_matches = g_new0(guint, num_needles); |
601 | - |
602 | - guint haystack_token; |
603 | - for (haystack_token = 0; haystack_token < num_haystacks; haystack_token++) { |
604 | - guint distance = minimize_distance_recurse(0, num_needles, haystack_token, num_haystacks, distances, local_matches); |
605 | - |
606 | - if (distance < final_distance) { |
607 | - final_distance = distance; |
608 | - |
609 | - guint match_cnt; |
610 | - for (match_cnt = 0; match_cnt < num_needles; match_cnt++) { |
611 | - matches[match_cnt] = local_matches[match_cnt]; |
612 | - } |
613 | - } |
614 | - } |
615 | - |
616 | - g_free(local_matches); |
617 | - |
618 | - return final_distance; |
619 | -} |
620 | - |
621 | -/* Dups a specific token in the array of strv arrays */ |
622 | -gchar * |
623 | -find_token (guint token_number, GStrv * haystacks, guint num_haystacks) |
624 | -{ |
625 | - guint haystack; |
626 | - |
627 | - for (haystack = 0; haystack < num_haystacks; haystack++) { |
628 | - guint strvlen = g_strv_length(haystacks[haystack]); |
629 | - |
630 | - if (token_number < strvlen) { |
631 | - return g_strdup(haystacks[haystack][token_number]); |
632 | - } |
633 | - |
634 | - token_number -= strvlen; |
635 | - } |
636 | - |
637 | - return NULL; |
638 | -} |
639 | - |
640 | -/* Normalize a set of strings so that we can compare them |
641 | - without worry about accents and the such */ |
642 | -static GStrv |
643 | -normalize_gstrv (GStrv inlist) |
644 | -{ |
645 | - /* The identity property */ |
646 | - if (inlist == NULL) return NULL; |
647 | - |
648 | - guint length = g_strv_length(inlist); |
649 | - GStrv out = g_new0(gchar *, length + 1); |
650 | - gint i; |
651 | - |
652 | - for (i = 0; i < length; i++) { |
653 | - out[i] = g_utf8_normalize(inlist[i], -1, G_NORMALIZE_ALL); |
654 | - } |
655 | - |
656 | - return out; |
657 | -} |
658 | - |
659 | -#define SEPARATORS " .->" |
660 | - |
661 | -guint |
662 | -calculate_distance (const gchar * needle, GStrv haystacks, GStrv * matches) |
663 | -{ |
664 | - g_return_val_if_fail(needle != NULL || haystacks != NULL, G_MAXUINT); |
665 | - guint final_distance = G_MAXUINT; |
666 | - |
667 | - if (needle == NULL || !g_utf8_validate(needle, -1, NULL)) { |
668 | - return DROP_PENALTY * g_utf8_strlen(haystacks[0], 1024); |
669 | - } |
670 | - if (haystacks == NULL) { |
671 | - return ADD_PENALTY * g_utf8_strlen(needle, 1024); |
672 | - } |
673 | - |
674 | - /* Check to make sure we have valid haystacks */ |
675 | - gint i; |
676 | - guint num_haystacks = g_strv_length(haystacks); |
677 | - |
678 | - for (i = 0; i < num_haystacks; i++) { |
679 | - if (!g_utf8_validate(haystacks[i], -1, NULL)) { |
680 | - return ADD_PENALTY * g_utf8_strlen(needle, 1024); |
681 | - } |
682 | - } |
683 | - |
684 | - /* Tokenize all the haystack strings */ |
685 | - guint num_haystack_tokens = 0; |
686 | - GStrv * haystacks_array = g_new0(GStrv, num_haystacks); |
687 | - |
688 | - for (i = 0; i < num_haystacks; i++) { |
689 | - GStrv split = g_strsplit_set(haystacks[i], SEPARATORS, 0); |
690 | - haystacks_array[i] = normalize_gstrv(split); |
691 | - g_strfreev(split); |
692 | - num_haystack_tokens += g_strv_length(haystacks_array[i]); |
693 | - } |
694 | - |
695 | - /* Tokenize our needles the same way */ |
696 | - GStrv needle_split = g_strsplit_set(needle, SEPARATORS, 0); |
697 | - GStrv needle_tokens = normalize_gstrv(needle_split); |
698 | - g_strfreev(needle_split); |
699 | - guint num_needle_tokens = g_strv_length(needle_tokens); |
700 | - |
701 | - /* If we can't even find a set that works, let's just cut |
702 | - our losses here */ |
703 | - if (num_needle_tokens > num_haystack_tokens) { |
704 | - goto cleanup_tokens; |
705 | - } |
706 | - |
707 | - /* We need a place to store all the distances */ |
708 | - guint * distances = g_new0(guint, num_haystack_tokens * num_needle_tokens); |
709 | - |
710 | - /* Calculate all the distance combinations */ |
711 | - gint needle_token; |
712 | - for (needle_token = 0; needle_tokens[needle_token] != NULL; needle_token++) { |
713 | - gchar * ineedle = needle_tokens[needle_token]; |
714 | - |
715 | - guint haystacks_cnt; |
716 | - guint haystack_token_cnt = 0; |
717 | - for (haystacks_cnt = 0; haystacks_cnt < num_haystacks; haystacks_cnt++) { |
718 | - guint haystack_cnt; |
719 | - for (haystack_cnt = 0; haystacks_array[haystacks_cnt][haystack_cnt] != NULL; haystack_cnt++) { |
720 | - gchar * ihaystack = haystacks_array[haystacks_cnt][haystack_cnt]; |
721 | - guint distance = calculate_token_distance(ineedle, ihaystack); |
722 | - |
723 | - distances[(needle_token * num_haystack_tokens) + haystack_token_cnt] = distance; |
724 | - haystack_token_cnt++; |
725 | - } |
726 | - } |
727 | - } |
728 | - |
729 | - /* Now, try to find a path through the array that results in the |
730 | - lowest total value */ |
731 | - guint * final_matches = g_new0(guint, num_needle_tokens); |
732 | - |
733 | - final_distance = minimize_distance(num_needle_tokens, num_haystack_tokens, distances, final_matches); |
734 | - |
735 | - /* Set up an array for matches so that we can enter |
736 | - the items as we go */ |
737 | - if (matches != NULL) { |
738 | - GStrv match_array = NULL; |
739 | - match_array = g_new0(gchar *, num_needle_tokens + 1); |
740 | - match_array[num_needle_tokens] = NULL; |
741 | - |
742 | - /* Copy the strings that we care about */ |
743 | - int i; |
744 | - for (i = 0; i < num_needle_tokens; i++) { |
745 | - match_array[i] = find_token(final_matches[i], haystacks_array, num_haystacks); |
746 | - } |
747 | - |
748 | - *matches = match_array; |
749 | - } |
750 | - |
751 | - g_free(final_matches); |
752 | - g_free(distances); |
753 | - |
754 | -cleanup_tokens: |
755 | - g_strfreev(needle_tokens); |
756 | - for (i = 0; i < num_haystacks; i++) { |
757 | - g_strfreev(haystacks_array[i]); |
758 | - } |
759 | - g_free(haystacks_array); |
760 | - |
761 | - if (final_distance != G_MAXUINT) { |
762 | - return final_distance / num_needle_tokens; |
763 | - } else { |
764 | - return G_MAXUINT; |
765 | - } |
766 | -} |
767 | |
768 | === removed file 'src/distance.h' |
769 | --- src/distance.h 2012-03-05 04:46:53 +0000 |
770 | +++ src/distance.h 1970-01-01 00:00:00 +0000 |
771 | @@ -1,33 +0,0 @@ |
772 | -/* |
773 | -Functions to calculate the distance between two strings. |
774 | - |
775 | -Copyright 2011 Canonical Ltd. |
776 | - |
777 | -Authors: |
778 | - Ted Gould <ted@canonical.com> |
779 | - |
780 | -This program is free software: you can redistribute it and/or modify it |
781 | -under the terms of the GNU General Public License version 3, as published |
782 | -by the Free Software Foundation. |
783 | - |
784 | -This program is distributed in the hope that it will be useful, but |
785 | -WITHOUT ANY WARRANTY; without even the implied warranties of |
786 | -MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR |
787 | -PURPOSE. See the GNU General Public License for more details. |
788 | - |
789 | -You should have received a copy of the GNU General Public License along |
790 | -with this program. If not, see <http://www.gnu.org/licenses/>. |
791 | -*/ |
792 | - |
793 | -#ifndef __DISTANCE_H__ |
794 | -#define __DISTANCE_H__ |
795 | - |
796 | -#include <glib-object.h> |
797 | - |
798 | -G_BEGIN_DECLS |
799 | - |
800 | -guint calculate_distance (const gchar * needle, GStrv haystack, GStrv * matched); |
801 | - |
802 | -G_END_DECLS |
803 | - |
804 | -#endif /* __DISTANCE_H__ */ |
805 | |
806 | === modified file 'src/hudappindicatorsource.c' |
807 | --- src/hudappindicatorsource.c 2012-03-23 15:35:01 +0000 |
808 | +++ src/hudappindicatorsource.c 2012-04-03 12:30:26 +0000 |
809 | @@ -371,9 +371,9 @@ |
810 | } |
811 | |
812 | static void |
813 | -hud_app_indicator_source_search (HudSource *hud_source, |
814 | - GPtrArray *results_array, |
815 | - const gchar *search_string) |
816 | +hud_app_indicator_source_search (HudSource *hud_source, |
817 | + GPtrArray *results_array, |
818 | + HudTokenList *search_tokens) |
819 | { |
820 | HudAppIndicatorSource *source = HUD_APP_INDICATOR_SOURCE (hud_source); |
821 | GSequenceIter *iter; |
822 | @@ -382,7 +382,7 @@ |
823 | |
824 | while (!g_sequence_iter_is_end (iter)) |
825 | { |
826 | - hud_source_search (g_sequence_get (iter), results_array, search_string); |
827 | + hud_source_search (g_sequence_get (iter), results_array, search_tokens); |
828 | iter = g_sequence_iter_next (iter); |
829 | } |
830 | } |
831 | |
832 | === modified file 'src/huddbusmenucollector.c' |
833 | --- src/huddbusmenucollector.c 2012-03-26 15:25:33 +0000 |
834 | +++ src/huddbusmenucollector.c 2012-04-03 12:30:26 +0000 |
835 | @@ -290,9 +290,9 @@ |
836 | } |
837 | |
838 | static void |
839 | -hud_dbusmenu_collector_search (HudSource *source, |
840 | - GPtrArray *results_array, |
841 | - const gchar *search_string) |
842 | +hud_dbusmenu_collector_search (HudSource *source, |
843 | + GPtrArray *results_array, |
844 | + HudTokenList *search_string) |
845 | { |
846 | HudDbusmenuCollector *collector = HUD_DBUSMENU_COLLECTOR (source); |
847 | GHashTableIter iter; |
848 | |
849 | === modified file 'src/huddebugsource.c' |
850 | --- src/huddebugsource.c 2012-03-23 15:35:01 +0000 |
851 | +++ src/huddebugsource.c 2012-04-03 12:30:26 +0000 |
852 | @@ -105,9 +105,9 @@ |
853 | } |
854 | |
855 | static void |
856 | -hud_debug_source_search (HudSource *hud_source, |
857 | - GPtrArray *results_array, |
858 | - const gchar *search_string) |
859 | +hud_debug_source_search (HudSource *hud_source, |
860 | + GPtrArray *results_array, |
861 | + HudTokenList *search_string) |
862 | { |
863 | HudDebugSource *source = HUD_DEBUG_SOURCE (hud_source); |
864 | |
865 | |
866 | === modified file 'src/hudindicatorsource.c' |
867 | --- src/hudindicatorsource.c 2012-03-23 15:35:01 +0000 |
868 | +++ src/hudindicatorsource.c 2012-04-03 12:30:26 +0000 |
869 | @@ -146,9 +146,9 @@ |
870 | } |
871 | |
872 | static void |
873 | -hud_indicator_source_search (HudSource *hud_source, |
874 | - GPtrArray *results_array, |
875 | - const gchar *search_string) |
876 | +hud_indicator_source_search (HudSource *hud_source, |
877 | + GPtrArray *results_array, |
878 | + HudTokenList *search_string) |
879 | { |
880 | HudIndicatorSource *source = HUD_INDICATOR_SOURCE (hud_source); |
881 | gint i; |
882 | |
883 | === modified file 'src/huditem.c' |
884 | --- src/huditem.c 2012-03-23 15:35:01 +0000 |
885 | +++ src/huditem.c 2012-04-03 12:30:26 +0000 |
886 | @@ -19,6 +19,7 @@ |
887 | #include "huditem.h" |
888 | |
889 | #include "usage-tracker.h" |
890 | +#include "hudtoken.h" |
891 | |
892 | /** |
893 | * SECTION:huditem |
894 | @@ -52,6 +53,7 @@ |
895 | |
896 | gchar *desktop_file; |
897 | |
898 | + HudTokenList *token_list; |
899 | HudStringList *tokens; |
900 | gchar *usage_tag; |
901 | gchar *app_icon; |
902 | @@ -68,8 +70,10 @@ |
903 | HudItem *item = HUD_ITEM (object); |
904 | |
905 | g_hash_table_remove (hud_item_table, &item->priv->id); |
906 | + hud_token_list_free (item->priv->token_list); |
907 | hud_string_list_unref (item->priv->tokens); |
908 | g_free (item->priv->desktop_file); |
909 | + g_free (item->priv->app_icon); |
910 | g_free (item->priv->usage_tag); |
911 | |
912 | G_OBJECT_CLASS (hud_item_parent_class) |
913 | @@ -156,6 +160,7 @@ |
914 | item->priv->app_icon = g_strdup (app_icon); |
915 | item->priv->enabled = enabled; |
916 | item->priv->id = hud_item_next_id++; |
917 | + item->priv->token_list = hud_token_list_new_from_string_list (tokens); |
918 | |
919 | g_hash_table_insert (hud_item_table, &item->priv->id, item); |
920 | |
921 | @@ -330,3 +335,9 @@ |
922 | { |
923 | return g_hash_table_lookup (hud_item_table, &id); |
924 | } |
925 | + |
926 | +HudTokenList * |
927 | +hud_item_get_token_list (HudItem *item) |
928 | +{ |
929 | + return item->priv->token_list; |
930 | +} |
931 | |
932 | === modified file 'src/huditem.h' |
933 | --- src/huditem.h 2012-03-23 15:35:01 +0000 |
934 | +++ src/huditem.h 2012-04-03 12:30:26 +0000 |
935 | @@ -21,7 +21,7 @@ |
936 | |
937 | #include <glib-object.h> |
938 | |
939 | -#include "hudstringlist.h" |
940 | +#include "hudtoken.h" |
941 | |
942 | #define HUD_TYPE_ITEM (hud_item_get_type ()) |
943 | #define HUD_ITEM(inst) (G_TYPE_CHECK_INSTANCE_CAST ((inst), \ |
944 | @@ -74,5 +74,6 @@ |
945 | gboolean hud_item_get_enabled (HudItem *item); |
946 | guint64 hud_item_get_id (HudItem *item); |
947 | HudItem * hud_item_lookup (guint64 id); |
948 | +HudTokenList * hud_item_get_token_list (HudItem *item); |
949 | |
950 | #endif /* __HUD_ITEM_H__ */ |
951 | |
952 | === modified file 'src/hudmenumodelcollector.c' |
953 | --- src/hudmenumodelcollector.c 2012-03-23 15:35:42 +0000 |
954 | +++ src/hudmenumodelcollector.c 2012-04-03 12:30:26 +0000 |
955 | @@ -346,9 +346,9 @@ |
956 | } |
957 | |
958 | static void |
959 | -hud_menu_model_collector_search (HudSource *source, |
960 | - GPtrArray *results_array, |
961 | - const gchar *search_string) |
962 | +hud_menu_model_collector_search (HudSource *source, |
963 | + GPtrArray *results_array, |
964 | + HudTokenList *search_string) |
965 | { |
966 | HudMenuModelCollector *collector = HUD_MENU_MODEL_COLLECTOR (source); |
967 | GPtrArray *items; |
968 | |
969 | === modified file 'src/hudquery.c' |
970 | --- src/hudquery.c 2012-03-23 15:35:42 +0000 |
971 | +++ src/hudquery.c 2012-04-03 12:30:26 +0000 |
972 | @@ -51,6 +51,7 @@ |
973 | |
974 | HudSource *source; |
975 | gchar *search_string; |
976 | + HudTokenList *token_list; |
977 | gint num_results; |
978 | guint refresh_id; |
979 | |
980 | @@ -100,16 +101,21 @@ |
981 | hud_query_refresh (HudQuery *query) |
982 | { |
983 | guint max_usage = 0; |
984 | + guint64 start_time; |
985 | + |
986 | + start_time = g_get_monotonic_time (); |
987 | |
988 | g_ptr_array_set_size (query->results, 0); |
989 | |
990 | if (query->search_string[0] != '\0') |
991 | - hud_source_search (query->source, query->results, query->search_string); |
992 | + hud_source_search (query->source, query->results, query->token_list); |
993 | |
994 | g_ptr_array_foreach (query->results, hud_query_find_max_usage, &max_usage); |
995 | g_ptr_array_sort_with_data (query->results, hud_query_compare_results, GINT_TO_POINTER (max_usage)); |
996 | if (query->results->len > query->num_results) |
997 | g_ptr_array_set_size (query->results, query->num_results); |
998 | + |
999 | + g_debug ("query took %dus\n", (int) (g_get_monotonic_time () - start_time)); |
1000 | } |
1001 | |
1002 | static gboolean |
1003 | @@ -148,6 +154,7 @@ |
1004 | hud_source_unuse (query->source); |
1005 | |
1006 | g_object_unref (query->source); |
1007 | + hud_token_list_free (query->token_list); |
1008 | g_free (query->search_string); |
1009 | g_ptr_array_unref (query->results); |
1010 | |
1011 | @@ -206,6 +213,7 @@ |
1012 | query->source = g_object_ref (source); |
1013 | query->results = g_ptr_array_new_with_free_func (g_object_unref); |
1014 | query->search_string = g_strdup (search_string); |
1015 | + query->token_list = hud_token_list_new_from_string (query->search_string); |
1016 | query->num_results = num_results; |
1017 | |
1018 | hud_source_use (query->source); |
1019 | |
1020 | === modified file 'src/hudresult.c' |
1021 | --- src/hudresult.c 2012-03-12 16:27:09 +0000 |
1022 | +++ src/hudresult.c 2012-04-03 12:30:26 +0000 |
1023 | @@ -21,7 +21,7 @@ |
1024 | #include <string.h> |
1025 | |
1026 | #include "hudsettings.h" |
1027 | -#include "distance.h" |
1028 | +#include "hudtoken.h" |
1029 | |
1030 | /** |
1031 | * SECTION:hudresult |
1032 | @@ -48,46 +48,19 @@ |
1033 | HudItem *item; |
1034 | |
1035 | guint distance; |
1036 | - gchar **matched; |
1037 | + const gchar **matched; |
1038 | gchar *description; |
1039 | }; |
1040 | |
1041 | G_DEFINE_TYPE (HudResult, hud_result, G_TYPE_OBJECT) |
1042 | |
1043 | -static guint |
1044 | -calculate_distance_from_list (const gchar *search_string, |
1045 | - HudStringList *list, |
1046 | - GStrv *matched) |
1047 | -{ |
1048 | - HudStringList *iter; |
1049 | - const gchar **strv; |
1050 | - guint distance; |
1051 | - gint i = 0; |
1052 | - |
1053 | - for (iter = list; iter; iter = hud_string_list_get_tail (iter)) |
1054 | - i++; |
1055 | - |
1056 | - strv = g_new (const char *, i + 1); |
1057 | - strv[i] = NULL; |
1058 | - |
1059 | - for (iter = list; iter; iter = hud_string_list_get_tail (iter)) |
1060 | - strv[--i] = hud_string_list_get_head (iter); |
1061 | - |
1062 | - distance = calculate_distance (search_string, (char **) strv, matched); |
1063 | - |
1064 | - g_free (strv); |
1065 | - |
1066 | - |
1067 | - return distance; |
1068 | -} |
1069 | - |
1070 | static void |
1071 | hud_result_finalize (GObject *object) |
1072 | { |
1073 | HudResult *result = HUD_RESULT (object); |
1074 | |
1075 | g_object_unref (result->item); |
1076 | - g_strfreev (result->matched); |
1077 | + g_free (result->matched); |
1078 | g_free (result->description); |
1079 | |
1080 | G_OBJECT_CLASS (hud_result_parent_class) |
1081 | @@ -126,16 +99,16 @@ |
1082 | * Returns: a new #HudResult, or %NULL in event of a poor match |
1083 | **/ |
1084 | HudResult * |
1085 | -hud_result_get_if_matched (HudItem *item, |
1086 | - const gchar *search_string, |
1087 | - guint penalty) |
1088 | +hud_result_get_if_matched (HudItem *item, |
1089 | + HudTokenList *search_tokens, |
1090 | + guint penalty) |
1091 | { |
1092 | if (!hud_item_get_enabled (item)) |
1093 | return NULL; |
1094 | |
1095 | /* ignore the penalty in the max-distance calculation */ |
1096 | - if (calculate_distance_from_list (search_string, hud_item_get_tokens (item), NULL) <= hud_settings.max_distance) |
1097 | - return hud_result_new (item, search_string, penalty); |
1098 | + if (hud_token_list_distance (hud_item_get_token_list (item), search_tokens, NULL) <= hud_settings.max_distance) |
1099 | + return hud_result_new (item, search_tokens, penalty); |
1100 | else |
1101 | return NULL; |
1102 | } |
1103 | @@ -212,18 +185,18 @@ |
1104 | * Returns: the new #HudResult |
1105 | **/ |
1106 | HudResult * |
1107 | -hud_result_new (HudItem *item, |
1108 | - const gchar *search_string, |
1109 | - guint penalty) |
1110 | +hud_result_new (HudItem *item, |
1111 | + HudTokenList *search_tokens, |
1112 | + guint penalty) |
1113 | { |
1114 | HudResult *result; |
1115 | |
1116 | g_return_val_if_fail (HUD_IS_ITEM (item), NULL); |
1117 | - g_return_val_if_fail (search_string != NULL, NULL); |
1118 | + g_return_val_if_fail (search_tokens != NULL, NULL); |
1119 | |
1120 | result = g_object_new (HUD_TYPE_RESULT, NULL); |
1121 | result->item = g_object_ref (item); |
1122 | - result->distance = calculate_distance_from_list (search_string, hud_item_get_tokens (item), &result->matched); |
1123 | + result->distance = hud_token_list_distance (hud_item_get_token_list (item), search_tokens, &result->matched); |
1124 | hud_result_format_description (result); |
1125 | |
1126 | result->distance += (result->distance * penalty) / 100; |
1127 | |
1128 | === modified file 'src/hudresult.h' |
1129 | --- src/hudresult.h 2012-03-05 04:46:53 +0000 |
1130 | +++ src/hudresult.h 2012-04-03 12:30:26 +0000 |
1131 | @@ -31,18 +31,18 @@ |
1132 | |
1133 | GType hud_result_get_type (void); |
1134 | |
1135 | -HudResult * hud_result_new (HudItem *item, |
1136 | - const gchar *search_string, |
1137 | - guint penalty); |
1138 | - |
1139 | -HudResult * hud_result_get_if_matched (HudItem *item, |
1140 | - const gchar *search_string, |
1141 | - guint penalty); |
1142 | - |
1143 | -HudItem * hud_result_get_item (HudResult *result); |
1144 | -guint hud_result_get_distance (HudResult *result, |
1145 | - guint max_usage); |
1146 | -const gchar * hud_result_get_html_description (HudResult *result); |
1147 | +HudResult * hud_result_new (HudItem *item, |
1148 | + HudTokenList *search_tokens, |
1149 | + guint penalty); |
1150 | + |
1151 | +HudResult * hud_result_get_if_matched (HudItem *item, |
1152 | + HudTokenList *search_tokens, |
1153 | + guint penalty); |
1154 | + |
1155 | +HudItem * hud_result_get_item (HudResult *result); |
1156 | +guint hud_result_get_distance (HudResult *result, |
1157 | + guint max_usage); |
1158 | +const gchar * hud_result_get_html_description (HudResult *result); |
1159 | |
1160 | |
1161 | #endif /* __HUD_RESULT_H__ */ |
1162 | |
1163 | === modified file 'src/hudsettings.c' |
1164 | --- src/hudsettings.c 2012-03-07 04:11:28 +0000 |
1165 | +++ src/hudsettings.c 2012-04-03 12:30:26 +0000 |
1166 | @@ -53,20 +53,14 @@ |
1167 | * matching result |
1168 | * @add_penalty: the penalty incurred by a character in the search term |
1169 | * that does not exist in the item being matched |
1170 | - * @add_penalty_pre: the penalty incurred by a character in the search |
1171 | - * term that does not exist in the item being matched when that |
1172 | - * character comes at the beginning of the term |
1173 | * @drop_penalty: the penalty incurred by a character missing from the |
1174 | * search string as compared to the item being matched |
1175 | - * @drop_penalty_end: the penalty incurred by a character missing from |
1176 | + * @end_drop_penalty: the penalty incurred by a character missing from |
1177 | * the search string as compared to the item being matched when the |
1178 | * character is at the end of the item (ie: the search term is a |
1179 | * prefix of the item) |
1180 | - * @transpose_penalty: the penalty incurred for transposed characters |
1181 | * @swap_penalty: the penalty incurred for the substitution of one |
1182 | * character for another |
1183 | - * @swap_penalty_case: the penalty incurred for the substitution of one |
1184 | - * character for another when the characters differ only in case |
1185 | * |
1186 | * This structure contains the value of several tunable parameters that |
1187 | * affect the behaviour of various components of the HUD. |
1188 | @@ -101,19 +95,14 @@ |
1189 | hud_settings.indicator_penalty = g_settings_get_uint (settings, "indicator-penalty"); |
1190 | hud_settings.max_distance = g_settings_get_uint (settings, "max-distance"); |
1191 | hud_settings.add_penalty = g_settings_get_uint (settings, "add-penalty"); |
1192 | - hud_settings.add_penalty_pre = g_settings_get_uint (settings, "add-penalty-pre"); |
1193 | hud_settings.drop_penalty = g_settings_get_uint (settings, "drop-penalty"); |
1194 | - hud_settings.drop_penalty_end = g_settings_get_uint (settings, "drop-penalty-end"); |
1195 | - hud_settings.transpose_penalty = g_settings_get_uint (settings, "transpose-penalty"); |
1196 | + hud_settings.end_drop_penalty = g_settings_get_uint (settings, "end-drop-penalty"); |
1197 | hud_settings.swap_penalty = g_settings_get_uint (settings, "swap-penalty"); |
1198 | - hud_settings.swap_penalty_case = g_settings_get_uint (settings, "swap-penalty-case"); |
1199 | |
1200 | g_debug ("indicator penalty: %u, max distance: %u", |
1201 | hud_settings.indicator_penalty, hud_settings.max_distance); |
1202 | - g_debug ("penalties: add:%u add-pre:%u drop:%u drop-end:%u trans:%u swap:%u swap-case:%u", |
1203 | - hud_settings.add_penalty, hud_settings.add_penalty_pre, hud_settings.drop_penalty, |
1204 | - hud_settings.drop_penalty_end, hud_settings.transpose_penalty, hud_settings.swap_penalty, |
1205 | - hud_settings.swap_penalty_case); |
1206 | + g_debug ("penalties: add:%u drop:%u end-drop:%u swap:%u", hud_settings.add_penalty, |
1207 | + hud_settings.drop_penalty, hud_settings.end_drop_penalty, hud_settings.swap_penalty); |
1208 | } |
1209 | |
1210 | /** |
1211 | |
1212 | === modified file 'src/hudsettings.h' |
1213 | --- src/hudsettings.h 2012-03-07 04:11:28 +0000 |
1214 | +++ src/hudsettings.h 2012-04-03 12:30:26 +0000 |
1215 | @@ -31,12 +31,9 @@ |
1216 | guint max_distance; |
1217 | |
1218 | guint add_penalty; |
1219 | - guint add_penalty_pre; |
1220 | guint drop_penalty; |
1221 | - guint drop_penalty_end; |
1222 | - guint transpose_penalty; |
1223 | + guint end_drop_penalty; |
1224 | guint swap_penalty; |
1225 | - guint swap_penalty_case; |
1226 | }; |
1227 | |
1228 | extern HudSettings hud_settings; |
1229 | |
1230 | === modified file 'src/hudsource.c' |
1231 | --- src/hudsource.c 2012-03-15 18:25:50 +0000 |
1232 | +++ src/hudsource.c 2012-04-03 12:30:26 +0000 |
1233 | @@ -144,9 +144,9 @@ |
1234 | * function may have changed, at which point you should call it again. |
1235 | **/ |
1236 | void |
1237 | -hud_source_search (HudSource *source, |
1238 | - GPtrArray *results_array, |
1239 | - const gchar *search_string) |
1240 | +hud_source_search (HudSource *source, |
1241 | + GPtrArray *results_array, |
1242 | + HudTokenList *search_string) |
1243 | { |
1244 | g_debug ("search on %s %p", G_OBJECT_TYPE_NAME (source), source); |
1245 | |
1246 | |
1247 | === modified file 'src/hudsource.h' |
1248 | --- src/hudsource.h 2012-03-15 18:25:50 +0000 |
1249 | +++ src/hudsource.h 2012-04-03 12:30:26 +0000 |
1250 | @@ -36,22 +36,22 @@ |
1251 | { |
1252 | GTypeInterface g_iface; |
1253 | |
1254 | - void (* use) (HudSource *source); |
1255 | - void (* unuse) (HudSource *source); |
1256 | - void (* search) (HudSource *source, |
1257 | - GPtrArray *results_array, |
1258 | - const gchar *search_string); |
1259 | + void (* use) (HudSource *source); |
1260 | + void (* unuse) (HudSource *source); |
1261 | + void (* search) (HudSource *source, |
1262 | + GPtrArray *results_array, |
1263 | + HudTokenList *search_tokens); |
1264 | }; |
1265 | |
1266 | GType hud_source_get_type (void); |
1267 | |
1268 | -void hud_source_use (HudSource *source); |
1269 | -void hud_source_unuse (HudSource *source); |
1270 | - |
1271 | -void hud_source_search (HudSource *source, |
1272 | - GPtrArray *results_array, |
1273 | - const gchar *search_string); |
1274 | - |
1275 | -void hud_source_changed (HudSource *source); |
1276 | +void hud_source_use (HudSource *source); |
1277 | +void hud_source_unuse (HudSource *source); |
1278 | + |
1279 | +void hud_source_search (HudSource *source, |
1280 | + GPtrArray *results_array, |
1281 | + HudTokenList *search_tokens); |
1282 | + |
1283 | +void hud_source_changed (HudSource *source); |
1284 | |
1285 | #endif /* __HUD_SOURCE_H__ */ |
1286 | |
1287 | === modified file 'src/hudsourcelist.c' |
1288 | --- src/hudsourcelist.c 2012-03-15 18:25:50 +0000 |
1289 | +++ src/hudsourcelist.c 2012-04-03 12:30:26 +0000 |
1290 | @@ -83,9 +83,9 @@ |
1291 | } |
1292 | |
1293 | static void |
1294 | -hud_source_list_search (HudSource *source, |
1295 | - GPtrArray *results_array, |
1296 | - const gchar *search_string) |
1297 | +hud_source_list_search (HudSource *source, |
1298 | + GPtrArray *results_array, |
1299 | + HudTokenList *search_string) |
1300 | { |
1301 | HudSourceList *list = HUD_SOURCE_LIST (source); |
1302 | GSList *node; |
1303 | |
1304 | === added file 'src/hudtoken.c' |
1305 | --- src/hudtoken.c 1970-01-01 00:00:00 +0000 |
1306 | +++ src/hudtoken.c 2012-04-03 12:30:26 +0000 |
1307 | @@ -0,0 +1,394 @@ |
1308 | +/* |
1309 | + * Copyright © 2012 Canonical Ltd. |
1310 | + * |
1311 | + * This program is free software: you can redistribute it and/or modify it |
1312 | + * under the terms of the GNU General Public License version 3, as |
1313 | + * published by the Free Software Foundation. |
1314 | + * |
1315 | + * This program is distributed in the hope that it will be useful, but |
1316 | + * WITHOUT ANY WARRANTY; without even the implied warranties of |
1317 | + * MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR |
1318 | + * PURPOSE. See the GNU General Public License for more details. |
1319 | + * |
1320 | + * You should have received a copy of the GNU General Public License along |
1321 | + * with this program. If not, see <http://www.gnu.org/licenses/>. |
1322 | + * |
1323 | + * Author: Ryan Lortie <desrt@desrt.ca> |
1324 | + */ |
1325 | + |
1326 | +#include "hudtoken.h" |
1327 | + |
1328 | +#include "hudsettings.h" |
1329 | + |
1330 | +#include <string.h> |
1331 | + |
1332 | +struct _HudToken |
1333 | +{ |
1334 | + guint length; |
1335 | + gchar *original; |
1336 | + gunichar *str; |
1337 | +}; |
1338 | + |
1339 | +/* This is actually one greater than the max-length. |
1340 | + * Should be power-of-two for best performance. |
1341 | + */ |
1342 | +#define TOKEN_LENGTH_LIMIT 32 |
1343 | + |
1344 | +#if 0 |
1345 | +static void |
1346 | +hud_token_distance_debug (const HudToken *haystack, |
1347 | + const HudToken *needle, |
1348 | + guint d[TOKEN_LENGTH_LIMIT][TOKEN_LENGTH_LIMIT]) |
1349 | +{ |
1350 | + gint i, j; |
1351 | + |
1352 | + g_print (" "); |
1353 | + for (j = 0; j <= haystack->length; j++) |
1354 | + g_print ("%6lc", (wchar_t) (j ? haystack->str[j - 1] : ' ')); |
1355 | + g_print ("\n"); |
1356 | + |
1357 | + for (i = 0; i <= needle->length; i++) |
1358 | + { |
1359 | + g_print ("%lc", (wchar_t) (i ? needle->str[i - 1] : ' ')); |
1360 | + for (j = 0; j <= haystack->length; j++) |
1361 | + g_print ("%6u", d[i][j]); |
1362 | + g_print ("\n"); |
1363 | + } |
1364 | +} |
1365 | +#endif |
1366 | + |
1367 | +#define MIN3(a,b,c) (MIN(MIN((a),(b)),(c))) |
1368 | + |
1369 | +/* Keeping in mind the fact that we're matching single words against |
1370 | + * single words, we can expect the extremely vast majority of cases to |
1371 | + * see needle and haystack both be less than 32 characters in length. |
1372 | + * |
1373 | + * For the common case we can avoid memory allocation by using a static |
1374 | + * array. By making the array a constant factor-of-two size we can |
1375 | + * replace multiplication by a variable with bitshift by a constant. |
1376 | + * |
1377 | + * Tokens longer than this are expected to be so unlikely that we |
1378 | + * simply deal with them by truncation during the normalisation phase. |
1379 | + */ |
1380 | +guint |
1381 | +hud_token_distance (const HudToken *haystack, |
1382 | + const HudToken *needle) |
1383 | +{ |
1384 | + static guint d[TOKEN_LENGTH_LIMIT][TOKEN_LENGTH_LIMIT]; |
1385 | + gunichar h, n; |
1386 | + gint result; |
1387 | + gint i, j; |
1388 | + |
1389 | + g_assert (haystack->length < TOKEN_LENGTH_LIMIT && needle->length < TOKEN_LENGTH_LIMIT); |
1390 | + g_assert (haystack->str[haystack->length] == 0); |
1391 | + g_assert (needle->str[needle->length] == 0); |
1392 | + |
1393 | + /* This function only performs memory writes to 'd' and calls no other |
1394 | + * functions. No pointer to 'd' is ever leaked. Hopefully the |
1395 | + * compiler is clever enough to therefore realise that no other memory |
1396 | + * will be modified during the running of this function and optimise |
1397 | + * aggressively. |
1398 | + */ |
1399 | + |
1400 | + /* By convention we refer to "add" and "drop" in terms of "mistakes |
1401 | + * the user made". The user's token is the one in "needle". To give |
1402 | + * examples against the menu item "preferences", if the user typed: |
1403 | + * |
1404 | + * - "prefereces": this has a dropped character |
1405 | + * |
1406 | + * - "prefferences": this has an added character |
1407 | + * |
1408 | + * - "prefefences": this has a swap |
1409 | + * |
1410 | + * We organise the matrix with each column (j) corresponding to a |
1411 | + * character in the menu item text ('haystack') and each row (i) |
1412 | + * corresponding to a character in the search token ('needle'). |
1413 | + * |
1414 | + * We modify the Levenshtein algorithm in the following ways: |
1415 | + * |
1416 | + * - configurable penalties for various mistakes (add, drop, |
1417 | + * swap). This is done by replacing additions of '1' with |
1418 | + * additions of these configurable values. |
1419 | + * |
1420 | + * - a lower penalties for drops that occur at the end of the token |
1421 | + * that the user typed. For example, "prefer" would be given a |
1422 | + * lower penalty for those 5 missing letters than would occur if |
1423 | + * they were not missing from the end. |
1424 | + * |
1425 | + * This is done by special-casing the last row (i == nlen) in the |
1426 | + * matrix, corresponding to the last character in the search |
1427 | + * token. In this case, we calculate drops at a lower penalty. |
1428 | + * |
1429 | + * Implementing the first of these two changes is a simple tweak: |
1430 | + * instead of adding '1', add the configurable value. |
1431 | + * |
1432 | + * Implementing the second one is somewhat more difficult: we could |
1433 | + * modify the core algorithm, but that would violate the 'pureness' of |
1434 | + * the dynamic programming approach. |
1435 | + * |
1436 | + * Instead, we wait until the 'pure' algorithm is done then instead of |
1437 | + * only considering the result for the full menu item text (ie: the |
1438 | + * number in the bottom right corner) we consider all prefixes of the |
1439 | + * menu item text by scanning the entire bottom row (and adding a |
1440 | + * penalty according to the number of characters removed). |
1441 | + */ |
1442 | + |
1443 | + /* http://en.wikipedia.org/wiki/Levenshtein_distance#Computing_Levenshtein_distance */ |
1444 | + for (i = 0; i <= needle->length; i++) |
1445 | + d[i][0] = i * hud_settings.add_penalty; |
1446 | + |
1447 | + for (j = 0; j <= haystack->length; j++) |
1448 | + d[0][j] = j * hud_settings.drop_penalty; |
1449 | + |
1450 | + for (i = 1; (n = needle->str[i - 1]); i++) |
1451 | + for (j = 1; (h = haystack->str[j - 1]); j++) |
1452 | + if (n == h) |
1453 | + d[i][j] = d[i - 1][j - 1]; |
1454 | + |
1455 | + else |
1456 | + d[i][j] = MIN3(d[i - 1][j - 1] + hud_settings.swap_penalty, |
1457 | + d[i ][j - 1] + hud_settings.drop_penalty, |
1458 | + d[i - 1][j ] + hud_settings.add_penalty); |
1459 | + |
1460 | + /* Noe we consider all prefixes of the menu item text to discover |
1461 | + * which one gives us the best score. |
1462 | + * |
1463 | + * If we end up picking a result from a column other than the |
1464 | + * rightmost, it will have had the correct multiple of the end-drop |
1465 | + * penalty added to it by the time we're done. |
1466 | + */ |
1467 | + result = d[--i][0]; |
1468 | + for (j = 1; j <= haystack->length; j++) |
1469 | + result = MIN (d[i][j], result + hud_settings.end_drop_penalty); |
1470 | + |
1471 | + return result; |
1472 | +} |
1473 | + |
1474 | +HudToken * |
1475 | +hud_token_new (const gchar *str, |
1476 | + gssize length) |
1477 | +{ |
1478 | + HudToken *token; |
1479 | + gchar *normal; |
1480 | + gchar *folded; |
1481 | + glong items; |
1482 | + |
1483 | + token = g_slice_new (HudToken); |
1484 | + |
1485 | + token->original = g_strndup (str, length); |
1486 | + normal = g_utf8_normalize (str, length, G_NORMALIZE_ALL); |
1487 | + folded = g_utf8_casefold (normal, -1); |
1488 | + token->str = g_utf8_to_ucs4_fast (folded, -1, &items); |
1489 | + token->length = items; |
1490 | + g_free (folded); |
1491 | + g_free (normal); |
1492 | + |
1493 | + if (!(token->length < TOKEN_LENGTH_LIMIT)) |
1494 | + { |
1495 | + token->length = 31; |
1496 | + token->str[31] = 0; |
1497 | + } |
1498 | + |
1499 | + return token; |
1500 | +} |
1501 | + |
1502 | +void |
1503 | +hud_token_free (HudToken *token) |
1504 | +{ |
1505 | + g_free (token->original); |
1506 | + g_free (token->str); |
1507 | + g_slice_free (HudToken, token); |
1508 | +} |
1509 | + |
1510 | +static const gchar * |
1511 | +hud_token_get_original (HudToken *token) |
1512 | +{ |
1513 | + return token->original; |
1514 | +} |
1515 | + |
1516 | +struct _HudTokenList |
1517 | +{ |
1518 | + HudToken **tokens; |
1519 | + gint length; |
1520 | +}; |
1521 | + |
1522 | +static HudTokenList * |
1523 | +hud_token_list_new_consume_array (GPtrArray *array) |
1524 | +{ |
1525 | + HudTokenList *list; |
1526 | + |
1527 | + list = g_slice_new (HudTokenList); |
1528 | + list->tokens = (HudToken **) array->pdata; |
1529 | + list->length = array->len; |
1530 | + |
1531 | + g_ptr_array_free (array, FALSE); |
1532 | + |
1533 | + return list; |
1534 | +} |
1535 | + |
1536 | +#define SEPARATORS " .->" |
1537 | +static void |
1538 | +hud_token_list_add_string_to_array (GPtrArray *array, |
1539 | + const gchar *string) |
1540 | +{ |
1541 | + while (*string) |
1542 | + { |
1543 | + /* strip separators */ |
1544 | + string += strspn (string, SEPARATORS); |
1545 | + |
1546 | + if (*string) |
1547 | + { |
1548 | + gint length; |
1549 | + |
1550 | + /* consume a token */ |
1551 | + length = strcspn (string, SEPARATORS); |
1552 | + g_ptr_array_add (array, hud_token_new (string, length)); |
1553 | + string += length; |
1554 | + } |
1555 | + } |
1556 | +} |
1557 | + |
1558 | +static void |
1559 | +hud_token_list_add_string_list_to_array (GPtrArray *array, |
1560 | + HudStringList *list) |
1561 | +{ |
1562 | + if (list == NULL) |
1563 | + return; |
1564 | + |
1565 | + hud_token_list_add_string_list_to_array (array, hud_string_list_get_tail (list)); |
1566 | + hud_token_list_add_string_to_array (array, hud_string_list_get_head (list)); |
1567 | +} |
1568 | + |
1569 | +HudTokenList * |
1570 | +hud_token_list_new_from_string (const gchar *string) |
1571 | +{ |
1572 | + GPtrArray *array; |
1573 | + |
1574 | + array = g_ptr_array_new (); |
1575 | + hud_token_list_add_string_to_array (array, string); |
1576 | + return hud_token_list_new_consume_array (array); |
1577 | +} |
1578 | + |
1579 | +HudTokenList * |
1580 | +hud_token_list_new_from_string_list (HudStringList *string_list) |
1581 | +{ |
1582 | + GPtrArray *array; |
1583 | + |
1584 | + array = g_ptr_array_new (); |
1585 | + hud_token_list_add_string_list_to_array (array, string_list); |
1586 | + return hud_token_list_new_consume_array (array); |
1587 | +} |
1588 | + |
1589 | +void |
1590 | +hud_token_list_free (HudTokenList *list) |
1591 | +{ |
1592 | + gint i; |
1593 | + |
1594 | + for (i = 0; i < list->length; i++) |
1595 | + hud_token_free (list->tokens[i]); |
1596 | + |
1597 | + g_free (list->tokens); |
1598 | + |
1599 | + g_slice_free (HudTokenList, list); |
1600 | +} |
1601 | + |
1602 | +guint |
1603 | +hud_token_list_distance (HudTokenList *haystack, |
1604 | + HudTokenList *needle, |
1605 | + const gchar ***matches) |
1606 | +{ |
1607 | + static guint d[32][32]; |
1608 | + gint i, j; |
1609 | + |
1610 | + if (needle->length > haystack->length) |
1611 | + return G_MAXUINT; |
1612 | + |
1613 | + /* Simply refuse to deal with ridiculous situations. |
1614 | + * |
1615 | + * This only happens when the user has more than 32 words in their |
1616 | + * search or the same happens in a menu item. |
1617 | + */ |
1618 | + if (haystack->length > 32 || needle->length > 32) |
1619 | + return G_MAXUINT; |
1620 | + |
1621 | + /* unroll the handling of the first needle term */ |
1622 | + { |
1623 | + guint cost; |
1624 | + |
1625 | + /* unroll the handling of the first haystack term */ |
1626 | + cost = hud_token_distance (haystack->tokens[0], needle->tokens[0]); |
1627 | + d[0][0] = cost; |
1628 | + |
1629 | + for (j = 0; j < haystack->length; j++) |
1630 | + { |
1631 | + guint take_cost; |
1632 | + |
1633 | + take_cost = hud_token_distance (haystack->tokens[j], needle->tokens[0]); |
1634 | + cost = MIN (take_cost, cost + 1); |
1635 | + d[0][j] = cost; |
1636 | + } |
1637 | + } |
1638 | + |
1639 | + /* if we have only one needle, this loop won't run at all */ |
1640 | + for (i = 1; i < needle->length; i++) |
1641 | + { |
1642 | + guint cost; |
1643 | + |
1644 | + /* unroll the handling of the first haystack term */ |
1645 | + cost = d[i - 1][i - 1] + hud_token_distance (haystack->tokens[i], needle->tokens[i]); |
1646 | + d[i][i] = cost; |
1647 | + |
1648 | + for (j = i + 1; j < haystack->length; j++) |
1649 | + { |
1650 | + guint prev_cost; |
1651 | + |
1652 | + prev_cost = d[i - 1][j - 1]; |
1653 | + /* Only do checking of additional terms of it's possible that |
1654 | + * we'll come in under the max distance AND beat the cost of |
1655 | + * just dropping the term. |
1656 | + * |
1657 | + * hud_token_distance() could return zero so we need to try it |
1658 | + * if: |
1659 | + * |
1660 | + * - prev_cost is less than or equal to the max distance |
1661 | + * (because then our result could equal the max distance) |
1662 | + * |
1663 | + * - prev_cost is less than or equal to the last cost |
1664 | + * Even if it's equal, skipping has a cost and a perfect |
1665 | + * match has no cost, so we need to try the match. |
1666 | + */ |
1667 | + if (prev_cost <= hud_settings.max_distance && prev_cost <= cost) |
1668 | + { |
1669 | + guint take_cost; |
1670 | + |
1671 | + take_cost = prev_cost + hud_token_distance (haystack->tokens[j], needle->tokens[i]); |
1672 | + cost = MIN (take_cost, cost + 1); |
1673 | + } |
1674 | + else |
1675 | + cost = cost + 1; |
1676 | + |
1677 | + d[i][j] = cost; |
1678 | + } |
1679 | + } |
1680 | + |
1681 | + /* Discover which terms were matched */ |
1682 | + if (matches) |
1683 | + { |
1684 | + *matches = g_new (const gchar *, needle->length + 1); |
1685 | + |
1686 | + j = haystack->length - 1; |
1687 | + |
1688 | + for (i = needle->length - 1; i >= 0; i--) |
1689 | + { |
1690 | + while (j > i && d[i][j-1] == d[i][j] - 1) |
1691 | + j--; |
1692 | + |
1693 | + (*matches)[i] = hud_token_get_original (haystack->tokens[j]); |
1694 | + j--; |
1695 | + } |
1696 | + |
1697 | + (*matches)[needle->length] = NULL; |
1698 | + } |
1699 | + |
1700 | + return d[needle->length - 1][haystack->length - 1]; |
1701 | +} |
1702 | |
1703 | === added file 'src/hudtoken.h' |
1704 | --- src/hudtoken.h 1970-01-01 00:00:00 +0000 |
1705 | +++ src/hudtoken.h 2012-04-03 12:30:26 +0000 |
1706 | @@ -0,0 +1,40 @@ |
1707 | +/* |
1708 | + * Copyright © 2012 Canonical Ltd. |
1709 | + * |
1710 | + * This program is free software: you can redistribute it and/or modify it |
1711 | + * under the terms of the GNU General Public License version 3, as |
1712 | + * published by the Free Software Foundation. |
1713 | + * |
1714 | + * This program is distributed in the hope that it will be useful, but |
1715 | + * WITHOUT ANY WARRANTY; without even the implied warranties of |
1716 | + * MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR |
1717 | + * PURPOSE. See the GNU General Public License for more details. |
1718 | + * |
1719 | + * You should have received a copy of the GNU General Public License along |
1720 | + * with this program. If not, see <http://www.gnu.org/licenses/>. |
1721 | + * |
1722 | + * Author: Ryan Lortie <desrt@desrt.ca> |
1723 | + */ |
1724 | + |
1725 | +#ifndef __HUD_TOKEN_H__ |
1726 | +#define __HUD_TOKEN_H__ |
1727 | + |
1728 | +#include "hudstringlist.h" |
1729 | + |
1730 | +typedef struct _HudTokenList HudTokenList; |
1731 | +typedef struct _HudToken HudToken; |
1732 | + |
1733 | +HudToken * hud_token_new (const gchar *token, |
1734 | + gssize length); |
1735 | +void hud_token_free (HudToken *token); |
1736 | +guint hud_token_distance (const HudToken *haystack, |
1737 | + const HudToken *needle); |
1738 | + |
1739 | +HudTokenList * hud_token_list_new_from_string (const gchar *string); |
1740 | +HudTokenList * hud_token_list_new_from_string_list (HudStringList *string_list); |
1741 | +void hud_token_list_free (HudTokenList *list); |
1742 | +guint hud_token_list_distance (HudTokenList *haystack, |
1743 | + HudTokenList *needle, |
1744 | + const gchar ***matches); |
1745 | + |
1746 | +#endif /* __HUD_TOKEN_H__ */ |
1747 | |
1748 | === modified file 'src/hudwindowsource.c' |
1749 | --- src/hudwindowsource.c 2012-03-23 15:35:01 +0000 |
1750 | +++ src/hudwindowsource.c 2012-04-03 12:30:26 +0000 |
1751 | @@ -67,7 +67,7 @@ |
1752 | BamfWindow *active_window; |
1753 | BamfApplication *active_application; |
1754 | const gchar *active_desktop_file; |
1755 | - const gchar *active_icon; |
1756 | + gchar *active_icon; |
1757 | HudSource *active_collector; |
1758 | gint use_count; |
1759 | }; |
1760 | @@ -255,6 +255,7 @@ |
1761 | g_clear_object (&source->active_collector); |
1762 | g_clear_object (&source->active_application); |
1763 | g_clear_object (&source->active_window); |
1764 | + g_free (source->active_icon); |
1765 | source->active_window = g_object_ref (window); |
1766 | source->active_application = g_object_ref (application); |
1767 | source->active_desktop_file = desktop_file; |
1768 | @@ -296,9 +297,9 @@ |
1769 | } |
1770 | |
1771 | static void |
1772 | -hud_window_source_search (HudSource *hud_source, |
1773 | - GPtrArray *results_array, |
1774 | - const gchar *search_string) |
1775 | +hud_window_source_search (HudSource *hud_source, |
1776 | + GPtrArray *results_array, |
1777 | + HudTokenList *search_string) |
1778 | { |
1779 | HudWindowSource *source = HUD_WINDOW_SOURCE (hud_source); |
1780 | |
1781 | @@ -311,9 +312,13 @@ |
1782 | { |
1783 | HudWindowSource *source = HUD_WINDOW_SOURCE (object); |
1784 | |
1785 | + g_assert_cmpint (source->use_count, ==, 0); |
1786 | + |
1787 | /* bamf matcher signals already disconnected in dispose */ |
1788 | + g_clear_object (&source->active_collector); |
1789 | g_clear_object (&source->active_application); |
1790 | g_clear_object (&source->active_window); |
1791 | + g_free (source->active_icon); |
1792 | |
1793 | G_OBJECT_CLASS (hud_window_source_parent_class) |
1794 | ->finalize (object); |
1795 | |
1796 | === modified file 'tests/Makefile.am' |
1797 | --- tests/Makefile.am 2012-03-27 16:38:41 +0000 |
1798 | +++ tests/Makefile.am 2012-04-03 12:30:26 +0000 |
1799 | @@ -391,6 +391,24 @@ |
1800 | |
1801 | DISTCLEANFILES += test-dbus-message-count.bustle |
1802 | |
1803 | +################### |
1804 | +# Test Performance |
1805 | +################### |
1806 | + |
1807 | +check_PROGRAMS += \ |
1808 | + hud-performance |
1809 | + |
1810 | +hud_performance_CFLAGS = \ |
1811 | + -I$(top_builddir)/src \ |
1812 | + -I$(top_srcdir)/src \ |
1813 | + $(HUD_CFLAGS) |
1814 | +hud_performance_LDADD = \ |
1815 | + ../src/libhud-service.a \ |
1816 | + $(HUD_LIBS) |
1817 | +hud_performance_SOURCES = \ |
1818 | + hud-performance.c \ |
1819 | + word-list.h |
1820 | + |
1821 | ######################### |
1822 | # Footer |
1823 | ######################### |
1824 | |
1825 | === added file 'tests/hud-performance.c' |
1826 | --- tests/hud-performance.c 1970-01-01 00:00:00 +0000 |
1827 | +++ tests/hud-performance.c 2012-04-03 12:30:26 +0000 |
1828 | @@ -0,0 +1,279 @@ |
1829 | +/* |
1830 | + * Copyright © 2012 Canonical Ltd. |
1831 | + * |
1832 | + * This program is free software: you can redistribute it and/or modify it |
1833 | + * under the terms of the GNU General Public License version 3, as |
1834 | + * published by the Free Software Foundation. |
1835 | + * |
1836 | + * This program is distributed in the hope that it will be useful, but |
1837 | + * WITHOUT ANY WARRANTY; without even the implied warranties of |
1838 | + * MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR |
1839 | + * PURPOSE. See the GNU General Public License for more details. |
1840 | + * |
1841 | + * You should have received a copy of the GNU General Public License along |
1842 | + * with this program. If not, see <http://www.gnu.org/licenses/>. |
1843 | + * |
1844 | + * Author: Ryan Lortie <desrt@desrt.ca> |
1845 | + */ |
1846 | + |
1847 | +#include "hudsettings.h" |
1848 | +#include "hudquery.h" |
1849 | +#include "hudtoken.h" |
1850 | +#include "hudsource.h" |
1851 | + |
1852 | +#include <glib-object.h> |
1853 | + |
1854 | +#include "word-list.h" |
1855 | + |
1856 | +/* Max nested depth of menu items */ |
1857 | +#define MAX_DEPTH 6 |
1858 | + |
1859 | +/* Max number of items per submenu */ |
1860 | +#define MAX_ITEMS 20 |
1861 | + |
1862 | +/* Max number of words per label. |
1863 | + * NB: keep MAX_WORDS * MAX_DEPTH under 32 |
1864 | + */ |
1865 | +#define MAX_WORDS 4 |
1866 | + |
1867 | +/* Longest word in the word-list (upper bound) */ |
1868 | +#define MAX_LETTERS 20 |
1869 | + |
1870 | +/* hardcode some parameters for reasons of determinism. |
1871 | + */ |
1872 | +HudSettings hud_settings = { |
1873 | + .indicator_penalty = 50, |
1874 | + .add_penalty = 10, |
1875 | + .drop_penalty = 10, |
1876 | + .end_drop_penalty = 1, |
1877 | + .swap_penalty = 15, |
1878 | + .max_distance = 30 |
1879 | +}; |
1880 | + |
1881 | +typedef struct |
1882 | +{ |
1883 | + GObject object; |
1884 | + |
1885 | + GHashTable *items; |
1886 | +} RandomSource; |
1887 | + |
1888 | +typedef GObjectClass RandomSourceClass; |
1889 | + |
1890 | +static void random_source_iface_init (HudSourceInterface *iface); |
1891 | +G_DEFINE_TYPE_WITH_CODE (RandomSource, random_source, G_TYPE_OBJECT, |
1892 | + G_IMPLEMENT_INTERFACE (HUD_TYPE_SOURCE, random_source_iface_init)) |
1893 | + |
1894 | +static void |
1895 | +random_source_search (HudSource *hud_source, |
1896 | + GPtrArray *results_array, |
1897 | + HudTokenList *search_tokens) |
1898 | +{ |
1899 | + RandomSource *source = (RandomSource *) hud_source; |
1900 | + GHashTableIter iter; |
1901 | + gpointer item; |
1902 | + |
1903 | + g_hash_table_iter_init (&iter, source->items); |
1904 | + while (g_hash_table_iter_next (&iter, &item, NULL)) |
1905 | + { |
1906 | + HudResult *result; |
1907 | + |
1908 | + result = hud_result_get_if_matched (item, search_tokens, 0); |
1909 | + if (result) |
1910 | + g_ptr_array_add (results_array, result); |
1911 | + } |
1912 | +} |
1913 | + |
1914 | +static void |
1915 | +random_source_ignore_use (HudSource *source) |
1916 | +{ |
1917 | +} |
1918 | + |
1919 | +static gchar * |
1920 | +make_word (GRand *rand, |
1921 | + gchar *buffer) |
1922 | +{ |
1923 | + const gchar *word; |
1924 | + gint choice; |
1925 | + gint len; |
1926 | + |
1927 | + choice = g_rand_int_range (rand, 0, G_N_ELEMENTS (word_list)); |
1928 | + word = word_list[choice]; |
1929 | + |
1930 | + while (*word) |
1931 | + *buffer++ = *word++; |
1932 | + |
1933 | + return buffer; |
1934 | +} |
1935 | + |
1936 | +static gchar * |
1937 | +make_words (GRand *rand, |
1938 | + gint n_words) |
1939 | +{ |
1940 | + gchar *buffer; |
1941 | + gchar *ptr; |
1942 | + gint i; |
1943 | + |
1944 | + buffer = g_malloc ((MAX_LETTERS + 1) * n_words); |
1945 | + |
1946 | + ptr = buffer; |
1947 | + for (i = 0; i < n_words; i++) |
1948 | + { |
1949 | + if (i) |
1950 | + *ptr++ = ' '; |
1951 | + |
1952 | + ptr = make_word (rand, ptr); |
1953 | + } |
1954 | + |
1955 | + *ptr = '\0'; |
1956 | + |
1957 | + return buffer; |
1958 | +} |
1959 | + |
1960 | +static HudStringList * |
1961 | +random_source_make_name (GRand *rand, |
1962 | + HudStringList *context) |
1963 | +{ |
1964 | + HudStringList *name; |
1965 | + gchar *label; |
1966 | + |
1967 | + label = make_words (rand, g_rand_int_range (rand, 1, MAX_WORDS + 1)); |
1968 | + name = hud_string_list_cons (label, context); |
1969 | + g_free (label); |
1970 | + |
1971 | + return name; |
1972 | +} |
1973 | + |
1974 | +static void |
1975 | +random_source_populate_table (GRand *rand, |
1976 | + GHashTable *items, |
1977 | + HudStringList *context, |
1978 | + gint depth) |
1979 | +{ |
1980 | + gint n_items; |
1981 | + gint i; |
1982 | + |
1983 | + n_items = g_rand_int_range (rand, 1, MAX_ITEMS + 1); |
1984 | + |
1985 | + for (i = 0; i < n_items; i++) |
1986 | + { |
1987 | + HudStringList *name; |
1988 | + gboolean is_submenu; |
1989 | + HudItem *item; |
1990 | + |
1991 | + name = random_source_make_name (rand, context); |
1992 | + |
1993 | + if (depth != MAX_DEPTH) |
1994 | + /* Decrease the chances of a particular item being a submenu as we |
1995 | + * go deeper into the menu structure. |
1996 | + */ |
1997 | + is_submenu = g_rand_int_range (rand, 0, depth + 1) == 0; |
1998 | + else |
1999 | + /* At the maximum depth, prevent any items from being submenus. */ |
2000 | + is_submenu = FALSE; |
2001 | + |
2002 | + item = hud_item_new (name, NULL, NULL, !is_submenu); |
2003 | + g_hash_table_add (items, item); |
2004 | + |
2005 | + if (is_submenu) |
2006 | + random_source_populate_table (rand, items, name, depth + 1); |
2007 | + |
2008 | + hud_string_list_unref (name); |
2009 | + } |
2010 | +} |
2011 | + |
2012 | +static void |
2013 | +random_source_finalize (GObject *object) |
2014 | +{ |
2015 | + RandomSource *source = (RandomSource *) object; |
2016 | + |
2017 | + g_hash_table_unref (source->items); |
2018 | + |
2019 | + G_OBJECT_CLASS (random_source_parent_class) |
2020 | + ->finalize (object); |
2021 | +} |
2022 | + |
2023 | +static void |
2024 | +random_source_init (RandomSource *source) |
2025 | +{ |
2026 | + source->items = g_hash_table_new_full (NULL, NULL, g_object_unref, NULL); |
2027 | +} |
2028 | + |
2029 | +static void |
2030 | +random_source_iface_init (HudSourceInterface *iface) |
2031 | +{ |
2032 | + iface->use = random_source_ignore_use; |
2033 | + iface->unuse = random_source_ignore_use; |
2034 | + iface->search = random_source_search; |
2035 | +} |
2036 | + |
2037 | +static void |
2038 | +random_source_class_init (RandomSourceClass *class) |
2039 | +{ |
2040 | + class->finalize = random_source_finalize; |
2041 | +} |
2042 | + |
2043 | +static HudSource * |
2044 | +random_source_new (GRand *rand) |
2045 | +{ |
2046 | + RandomSource *source; |
2047 | + |
2048 | + source = g_object_new (random_source_get_type (), NULL); |
2049 | + random_source_populate_table (rand, source->items, NULL, 0); |
2050 | + |
2051 | + return HUD_SOURCE (source); |
2052 | +} |
2053 | + |
2054 | +void |
2055 | +test_query_performance (void) |
2056 | +{ |
2057 | + HudSource *source; |
2058 | + HudQuery *query; |
2059 | + GRand *rand; |
2060 | + gint i; |
2061 | + |
2062 | + rand = g_rand_new_with_seed (1234); |
2063 | + source = random_source_new (rand); |
2064 | + |
2065 | + for (i = 1; i <= 6; i++) |
2066 | + { |
2067 | + guint64 start_time; |
2068 | + gchar *search; |
2069 | + gint j; |
2070 | + |
2071 | + g_print ("\n"); |
2072 | + |
2073 | + search = make_words (rand, i); |
2074 | + |
2075 | + /* simulate the user typing it in, one character at a time */ |
2076 | + for (j = 1; search[j - 1]; j++) |
2077 | + { |
2078 | + gchar *part_search = g_strndup (search, j); |
2079 | + |
2080 | + start_time = g_get_monotonic_time (); |
2081 | + query = hud_query_new (source, part_search, 1u<<30); |
2082 | + g_print ("%-60s: %dus (%d hits)\n", part_search, |
2083 | + (int) (g_get_monotonic_time () - start_time), |
2084 | + hud_query_get_n_results (query)); |
2085 | + hud_query_close (query); |
2086 | + g_object_unref (query); |
2087 | + g_free (part_search); |
2088 | + } |
2089 | + |
2090 | + g_free (search); |
2091 | + } |
2092 | + |
2093 | + g_object_unref (source); |
2094 | + g_rand_free (rand); |
2095 | +} |
2096 | + |
2097 | +int |
2098 | +main (int argc, char **argv) |
2099 | +{ |
2100 | + g_type_init (); |
2101 | + |
2102 | + g_test_init (&argc, &argv, NULL); |
2103 | + if (g_test_perf ()) |
2104 | + g_test_add_func ("/hud/query-performance", test_query_performance); |
2105 | + |
2106 | + return g_test_run (); |
2107 | +} |
2108 | |
2109 | === modified file 'tests/test-distance.c' |
2110 | --- tests/test-distance.c 2012-03-12 18:52:56 +0000 |
2111 | +++ tests/test-distance.c 2012-04-03 12:30:26 +0000 |
2112 | @@ -23,7 +23,7 @@ |
2113 | #include <glib-object.h> |
2114 | |
2115 | #include "hudsettings.h" |
2116 | -#include "distance.h" |
2117 | +#include "hudtoken.h" |
2118 | |
2119 | /* hardcode some parameters so the test doesn't fail if the user |
2120 | * has bogus things in GSettings. |
2121 | @@ -31,15 +31,54 @@ |
2122 | HudSettings hud_settings = { |
2123 | .indicator_penalty = 50, |
2124 | .add_penalty = 10, |
2125 | - .add_penalty_pre = 1, |
2126 | .drop_penalty = 10, |
2127 | - .drop_penalty_end = 10, |
2128 | - .transpose_penalty = 10, |
2129 | - .swap_penalty = 10, |
2130 | - .swap_penalty_case = 1, |
2131 | + .end_drop_penalty = 1, |
2132 | + .swap_penalty = 15, |
2133 | .max_distance = 30 |
2134 | }; |
2135 | |
2136 | +static guint |
2137 | +calculate_distance (const gchar *search, GStrv teststrings, gchar ***matches) |
2138 | +{ |
2139 | + HudStringList *list = NULL; |
2140 | + HudTokenList *haystack; |
2141 | + HudTokenList *needle; |
2142 | + guint distance; |
2143 | + gint i; |
2144 | + |
2145 | + if (search == NULL || teststrings == NULL) { |
2146 | + return G_MAXINT; |
2147 | + } |
2148 | + |
2149 | + for (i = 0; teststrings[i]; i++) { |
2150 | + HudStringList *tmp; |
2151 | + |
2152 | + tmp = hud_string_list_cons (teststrings[i], list); |
2153 | + hud_string_list_unref (list); |
2154 | + list = tmp; |
2155 | + } |
2156 | + |
2157 | + haystack = hud_token_list_new_from_string_list (list); |
2158 | + hud_string_list_unref (list); |
2159 | + |
2160 | + needle = hud_token_list_new_from_string (search); |
2161 | + distance = hud_token_list_distance (haystack, needle, (const gchar ***) matches); |
2162 | + |
2163 | + if (matches) { |
2164 | + /* These are owned by the tokenlists, so make copies |
2165 | + * before freeing. |
2166 | + */ |
2167 | + for (i = 0; (*matches)[i]; i++) { |
2168 | + (*matches)[i] = g_strdup ((*matches)[i]); |
2169 | + } |
2170 | + } |
2171 | + |
2172 | + hud_token_list_free (haystack); |
2173 | + hud_token_list_free (needle); |
2174 | + |
2175 | + return distance; |
2176 | +} |
2177 | + |
2178 | /* Ensure the base calculation works */ |
2179 | static void |
2180 | test_distance_base (void) |
2181 | @@ -185,6 +224,18 @@ |
2182 | return; |
2183 | } |
2184 | |
2185 | +/* Check to make sure 'Save' matches better than 'Save As...' for "save" */ |
2186 | +static void |
2187 | +test_distance_extra_terms (void) |
2188 | +{ |
2189 | + const gchar *save_as[] = { "File", "Save", "As...", NULL }; |
2190 | + const gchar *save[] = { "File", "Save", NULL }; |
2191 | + |
2192 | + g_assert_cmpint (calculate_distance ("save", (GStrv) save, NULL), |
2193 | + <, |
2194 | + calculate_distance ("save", (GStrv) save_as, NULL)); |
2195 | +} |
2196 | + |
2197 | /* Build the test suite */ |
2198 | static void |
2199 | test_distance_suite (void) |
2200 | @@ -196,6 +247,7 @@ |
2201 | g_test_add_func ("/hud/distance/duplicates", test_distance_dups); |
2202 | g_test_add_func ("/hud/distance/variety", test_distance_variety); |
2203 | g_test_add_func ("/hud/distance/french_pref", test_distance_french_pref); |
2204 | + g_test_add_func ("/hud/distance/extra_terms", test_distance_extra_terms); |
2205 | return; |
2206 | } |
2207 | |
2208 | |
2209 | === added file 'tests/word-list.h' |
2210 | --- tests/word-list.h 1970-01-01 00:00:00 +0000 |
2211 | +++ tests/word-list.h 2012-04-03 12:30:26 +0000 |
2212 | @@ -0,0 +1,364 @@ |
2213 | +const gchar *word_list[] = { |
2214 | + "sap", "sat", "sad", "rat", "rap", "ram", "rag", "nap", "Nat", "mat", |
2215 | + "map", "mad", "lap", "lag", "lad", "fat", "fan", "fad", "fin", "fit", |
2216 | + "lid", "lip", "lit", "mid", "mitt", "nit", "nip", "rid", "rig", "rim", |
2217 | + "rip", "Sid", "sin", "sip", "log", "mom", "mop", "nod", "rod", "Ron", |
2218 | + "rot", "sod", "fun", "mud", "mum", "nut", "rug", "rut", "sum", "sun", |
2219 | + "fed", "led", "leg", "met", "Ned", "net", "bag", "bad", "bam", "bat", |
2220 | + "cap", "cab", "dad", "Dan", "gas", "gag", "ham", "hat", "jab", "jam", |
2221 | + "pan", "pat", "tab", "tag", "tan", "tap", "bid", "dig", "dip", "hid", |
2222 | + "hit", "hip", "Jim", "jig", "kin", "kid", "pin", "pit", "pig", "tin", |
2223 | + "tip", "Tim", "cop", "con", "Don", "dog", "hop", "hog", "job", "jog", |
2224 | + "pot", "pop", "top", "Tom", "bug", "bud", "bum", "cup", "cub", "dud", |
2225 | + "dug", "Gus", "gun", "hum", "jug", "pup", "tub", "tug", "beg", "bed", |
2226 | + "bet", "hen", "jet", "Ken", "pen", "pet", "peg", "pep", "the", "of", |
2227 | + "and", "a", "to", "in", "is", "you", "that", "it", "he", "was", "for", |
2228 | + "on", "are", "as", "with", "his", "they", "I", "at", "be", "this", |
2229 | + "have", "from", "or", "one", "had", "by", "word", "but", "not", |
2230 | + "what", "all", "were", "we", "when", "your", "can", "said", "there", |
2231 | + "use", "an", "each", "which", "she", "do", "how", "their", "if", |
2232 | + "will", "up", "other", "about", "out", "many", "then", "them", |
2233 | + "these", "so", "some", "her", "would", "make", "like", "him", "into", |
2234 | + "time", "has", "look", "two", "more", "write", "go", "see", "number", |
2235 | + "no", "way", "could", "people", "my", "than", "first", "water", |
2236 | + "been", "call", "who", "oil", "its", "now", "find", "long", "down", |
2237 | + "day", "did", "get", "come", "made", "may", "part", "over", "new", |
2238 | + "sound", "take", "only", "little", "work", "know", "place", "year", |
2239 | + "live", "me", "back", "give", "most", "very", "after", "thing", "our", |
2240 | + "just", "name", "good", "sentence", "man", "think", "say", "great", |
2241 | + "where", "help", "through", "much", "before", "line", "right", "too", |
2242 | + "mean", "old", "any", "same", "tell", "boy", "follow", "came", "want", |
2243 | + "show", "also", "around", "farm", "three", "small", "set", "put", |
2244 | + "end", "does", "another", "well", "large", "must", "big", "even", |
2245 | + "such", "because", "turn", "here", "why", "ask", "went", "men", |
2246 | + "read", "need", "land", "different", "home", "us", "move", "try", |
2247 | + "kind", "hand", "picture", "again", "change", "off", "play", "spell", |
2248 | + "air", "away", "animal", "house", "point", "page", "letter", "mother", |
2249 | + "answer", "found", "study", "still", "learn", "should", "America", |
2250 | + "world", "high", "every", "near", "add", "food", "between", "own", |
2251 | + "below", "country", "plant", "last", "school", "father", "keep", |
2252 | + "tree", "never", "start", "city", "earth", "eye", "light", "thought", |
2253 | + "head", "under", "story", "saw", "left", "don't", "few", "while", |
2254 | + "along", "might", "chose", "something", "seem", "next", "hard", |
2255 | + "open", "example", "begin", "life", "always", "those", "both", |
2256 | + "paper", "together", "got", "group", "often", "run", "important", |
2257 | + "until", "children", "side", "feet", "car", "mile", "night", "walk", |
2258 | + "white", "sea", "began", "grow", "took", "river", "four", "carry", |
2259 | + "state", "once", "book", "hear", "stop", "without", "second", "late", |
2260 | + "miss", "idea", "enough", "eat", "face", "watch", "far", "Indian", |
2261 | + "really", "almost", "let", "above", "girl", "sometimes", "mountain", |
2262 | + "cut", "young", "talk", "soon", "list", "song", "being", "leave", |
2263 | + "family", "it's", "am", "ate", "best", "better", "black", "blue", |
2264 | + "bring", "brown", "buy", "clean", "cold", "done", "draw", "drink", |
2265 | + "eight", "fall", "fast", "five", "fly", "full", "funny", "gave", |
2266 | + "giving", "goes", "green", "hold", "hot", "hurt", "jump", "laugh", |
2267 | + "myself", "pick", "please", "pretty", "pull", "ran", "red", "ride", |
2268 | + "round", "seven", "shall", "sing", "sit", "six", "sleep", "ten", |
2269 | + "thank", "today", "upon", "warm", "wash", "wish", "yellow", "yes", |
2270 | + "act", "ant", "bake", "band", "bank", "bell", "belt", "Ben", "bend", |
2271 | + "bent", "Bess", "bike", "bit", "bite", "blast", "bled", "blend", |
2272 | + "blimp", "blink", "bliss", "block", "blond", "blot", "bluff", "blunt", |
2273 | + "bone", "brag", "brand", "brass", "brat", "bred", "bride", "brig", |
2274 | + "brim", "broke", "brunt", "brute", "bump", "bun", "bunt", "bust", |
2275 | + "camp", "cane", "can't", "cape", "cast", "cat", "clad", "clam", |
2276 | + "clamp", "clan", "clap", "clasp", "class", "cliff", "cling", "clink", |
2277 | + "clip", "close", "clot", "club", "clump", "clung", "cone", "crab", |
2278 | + "craft", "cram", "cramp", "crib", "crime", "crisp", "crop", "crust", |
2279 | + "cure", "cute", "dam", "damp", "den", "dent", "dim", "dime", "dine", |
2280 | + "dire", "dive", "dope", "draft", "drag", "drank", "dress", "drift", |
2281 | + "drill", "drip", "drop", "drove", "drug", "drum", "dump", "dust", |
2282 | + "eve", "fact", "fade", "fell", "felt", "file", "fill", "film", "fine", |
2283 | + "fire", "fist", "flag", "flap", "flat", "fled", "fling", "flip", |
2284 | + "flop", "flung", "flunk", "frame", "frank", "frill", "frisk", "frog", |
2285 | + "frost", "froze", "fume", "gasp", "gaze", "glad", "gland", "glass", |
2286 | + "glint", "globe", "glum", "golf", "grab", "grade", "gram", "gramp", |
2287 | + "grand", "grant", "grape", "grasp", "grass", "grill", "grim", "grin", |
2288 | + "grip", "gripe", "grump", "grunt", "gulp", "gust", "gut", "hate", |
2289 | + "held", "hide", "hint", "hire", "hole", "honk", "hope", "hose", "hug", |
2290 | + "hung", "hunt", "hut", "ink", "Jan", "Jane", "joke", "junk", "kept", |
2291 | + "kit", "kite", "lamp", "lick", "lift", "lime", "limp", "lock", "luck", |
2292 | + "lump", "Mack", "mask", "mass", "mast", "mate", "melt", "mend", |
2293 | + "Mick", "Mike", "milk", "mill", "mint", "mist", "mite", "mope", |
2294 | + "mule", "mute", "neck", "nest", "nine", "nose", "note", "pane", |
2295 | + "pant", "pass", "past", "pest", "Pete", "pike", "pile", "pill", |
2296 | + "pine", "plan", "plane", "plank", "plate", "plop", "plot", "plug", |
2297 | + "plum", "plump", "plus", "poke", "pole", "pomp", "pond", "pope", |
2298 | + "prank", "press", "pride", "prime", "print", "prize", "prop", "punk", |
2299 | + "pure", "raft", "ripe", "robe", "rock", "rode", "romp", "rope", |
2300 | + "rose", "Runs", "runt", "rust", "sack", "sake", "Sam", "sand", "sank", |
2301 | + "save", "scab", "scale", "scalp", "scan", "scare", "scat", "scope", |
2302 | + "scram", "scrap", "script", "self", "sell", "send", "sent", "sick", |
2303 | + "site", "size", "skate", "skid", "skill", "skim", "skin", "skip", |
2304 | + "skit", "skunk", "slam", "slang", "slant", "slap", "slat", "slate", |
2305 | + "slave", "sled", "slept", "slide", "slim", "sling", "slip", "slob", |
2306 | + "slope", "slot", "slug", "slum", "slump", "smack", "smell", "smile", |
2307 | + "smog", "smoke", "smug", "snack", "snag", "snake", "snap", "sniff", |
2308 | + "snip", "snipe", "snub", "snug", "sock", "soft", "span", "spank", |
2309 | + "spat", "sped", "spend", "spent", "spill", "spin", "spine", "spit", |
2310 | + "spite", "splat", "splint", "split", "spoke", "spot", "spun", "spunk", |
2311 | + "stab", "stack", "stale", "stamp", "stand", "stem", "step", "stiff", |
2312 | + "sting", "stink", "stomp", "stone", "stove", "strand", "strap", |
2313 | + "strip", "stripe", "struck", "strung", "stuck", "stump", "stun", |
2314 | + "suck", "sung", "swam", "swang", "swell", "swift", "swim", "swing", |
2315 | + "swung", "tack", "tam", "tame", "tape", "tent", "test", "tide", |
2316 | + "tile", "till", "tilt", "trade", "tramp", "trap", "trend", "trick", |
2317 | + "trim", "trip", "trot", "trunk", "trust", "twang", "twig", "twin", |
2318 | + "twist", "van", "vane", "wave", "weld", "wet", "win", "wind", "wine", |
2319 | + "wire", "yoke", "absent", "admit", "album", "ball", "bang", "banging", |
2320 | + "basket", "bathtub", "bedbug", "bench", "bib", "bill", "blank", |
2321 | + "blasted", "blended", "blush", "bobsled", "box", "branch", "brave", |
2322 | + "brush", "bunch", "bus", "camping", "care", "case", "catnip", "cave", |
2323 | + "chest", "chill", "chin", "chip", "chipmunk", "chop", "chunk", |
2324 | + "clock", "cloth", "contest", "crack", "crash", "crashing", "crept", |
2325 | + "cross", "crush", "cuff", "dash", "deck", "dentist", "dish", |
2326 | + "disrupt", "disrupted", "dot", "drinking", "dusted", "expanded", |
2327 | + "fang", "fib", "finishing", "fish", "fix", "flute", "fog", "fox", |
2328 | + "Fran", "fuss", "gift", "goblin", "gum", "hall", "hang", "Hank", |
2329 | + "himself", "hotrod", "huff", "hunted", "index", "insisted", |
2330 | + "insisting", "insulted", "invent", "invented", "Jack", "jumping", |
2331 | + "king", "kiss", "lane", "lapdog", "lasted", "lending", "loft", "lost", |
2332 | + "lug", "lunch", "lung", "mall", "mascot", "math", "mess", "mob", |
2333 | + "mug", "napkin", "pack", "Pam", "path", "picnic", "pigpen", "pinball", |
2334 | + "pinch", "planted", "plastic", "problem", "public", "publishing", |
2335 | + "puff", "punishing", "quake", "rake", "rash", "rented", "rest", |
2336 | + "rested", "rich", "ring", "ringing", "rub", "safe", "sale", "sang", |
2337 | + "sash", "shack", "shed", "shelf", "shell", "shifted", "shine", "ship", |
2338 | + "shop", "shrimp", "shrinking", "shrunk", "shut", "sink", "sinking", |
2339 | + "sits", "splash", "splashing", "squinted", "standing", "Steve", |
2340 | + "stub", "stuff", "stunt", "sub", "sunfish", "sunk", "sunlit", |
2341 | + "sunset", "suntan", "swishing", "talented", "tall", "tank", "throne", |
2342 | + "thud", "tick", "tilted", "tiptop", "toss", "trusted", "twisted", |
2343 | + "upset", "vent", "vest", "wag", "wall", "wax", "whiff", "whip", |
2344 | + "whiplash", "wig", "wing", "wink", "wipe", "wise", "yell", "zap", |
2345 | + "zigzag", "called", "circle", "friend", "Mr.", "Mrs.", "nothing", |
2346 | + "says", "Ann", "Beth", "Bing", "Blanch", "bong", "Buck", "burnt", |
2347 | + "Burt", "Carmen", "Cass", "caterpillar", "Chad", "cheer", "chomp", |
2348 | + "Chuck", "chuckle", "chug", "Clark", "click", "climb", "clown", |
2349 | + "cluck", "coal", "complain", "croak", "crunch", "Curtis", "curve", |
2350 | + "darts", "dinner", "diver", "doctor", "doll", "door", "Doris", |
2351 | + "Ellen", "fellow", "fiddle", "firm", "fishing", "Fitch", "foam", |
2352 | + "forever", "forgot", "forth", "front", "Gert", "gobble", "gone", |
2353 | + "gosh", "granddad", "grandpa", "grinned", "grumble", "hatch", "Herb", |
2354 | + "hill", "horse", "hush", "insect", "Jeff", "jiggle", "Jill", "Jill's", |
2355 | + "Josh", "jumble", "kick", "Kim", "Kirk", "larch", "library", "lived", |
2356 | + "lives", "market", "Mitch", "mix", "napper", "nibble", "Nick", "Norm", |
2357 | + "Oh", "onto", "owner", "patch", "peck", "perfect", "ping", "Pip", |
2358 | + "pong", "quick", "quill", "quilt", "Quinn", "quit", "reward", "Rex", |
2359 | + "Rick", "Rivera", "roam", "ruff", "Sanchez", "served", "Seth", |
2360 | + "sister", "Sloan", "smash", "snort", "snuggle", "soup", "sparkle", |
2361 | + "sprinkle", "squirt", "stick", "sudden", "sunburn", "surprise", |
2362 | + "swimmer", "Tad", "tadpole", "Ted", "Tess", "Texas", "tickle", "toad", |
2363 | + "Todd", "turf", "twinkle", "twitch", "umbrella", "uncle", "wham", |
2364 | + "whirl", "whisper", "whistle", "wiggle", "window", "Winkle", |
2365 | + "writing", "yet", "York", "zing", "zip", "able", "ace", "added", |
2366 | + "afraid", "afternoon", "age", "ahead", "annoy", "anything", "anyway", |
2367 | + "anywhere", "ape", "applaud", "arm", "artist", "attack", "attic", |
2368 | + "auto", "avoid", "awesome", "awful", "awning", "babble", "baby", |
2369 | + "baffle", "bald", "ballplayer", "bark", "base", "baseball", "basin", |
2370 | + "basketball", "batch", "bath", "battle", "beach", "bead", "beam", |
2371 | + "bean", "beanstalk", "beast", "beat", "bedtime", "bee", "beef", |
2372 | + "beehive", "beet", "begging", "behind", "bird", "birthday", "bleach", |
2373 | + "blew", "blind", "bloom", "blow", "blown", "bluebird", "blueprint", |
2374 | + "blur", "boast", "boat", "bob", "body", "boil", "bold", "bonnet", |
2375 | + "bonus", "boost", "boot", "born", "bottle", "bowl", "brace", "braid", |
2376 | + "brain", "brainstorm", "brake", "brawl", "bread", "breakfast", |
2377 | + "breath", "brick", "bright", "broil", "broiler", "broom", "bruise", |
2378 | + "bubble", "buddy", "built", "bundle", "bunk", "bunny", "burn", |
2379 | + "burst", "buses", "butterfly", "button", "buzz", "cabin", "cage", |
2380 | + "cake", "camel", "candle", "candy", "careful", "cart", "catch", |
2381 | + "cattle", "cell", "cent", "chain", "chalk", "champ", "charge", |
2382 | + "chart", "chase", "chat", "check", "cheerful", "cheese", "chess", |
2383 | + "chew", "chick", "child", "chime", "chirp", "choice", "chore", |
2384 | + "church", "churn", "claim", "classmate", "clay", "clerk", "clever", |
2385 | + "clue", "clutch", "coach", "coat", "coax", "coil", "coin", "collect", |
2386 | + "colorful", "cool", "core", "cork", "corn", "cowboy", "cozy", "crate", |
2387 | + "crawl", "cream", "crew", "crinkle", "crow", "cruise", "cry", |
2388 | + "cuddle", "cupcake", "curb", "curl", "dab", "daddy", "dangle", |
2389 | + "Danny", "dark", "dart", "date", "dawn", "daylight", "dead", "deaf", |
2390 | + "dealt", "decent", "deep", "delight", "desk", "die", "dimple", "dirt", |
2391 | + "ditch", "doghouse", "double", "dragon", "dragonfly", "drain", |
2392 | + "dread", "dream", "drew", "driveway", "droop", "dry", "duck", "due", |
2393 | + "dunk", "dusk", "easel", "easy", "egg", "elbow", "enjoy", "ever", |
2394 | + "evergreen", "everyone", "everything", "everywhere", "explore", |
2395 | + "fabric", "fail", "faithful", "fame", "fault", "fawn", "feast", |
2396 | + "feed", "feel", "fence", "fern", "fetch", "fifty", "fight", "finish", |
2397 | + "firefighter", "flagpole", "flash", "flashlight", "flaunt", "flaw", |
2398 | + "flight", "float", "flow", "fluffy", "foal", "foil", "fold", "fool", |
2399 | + "forest", "forget", "fork", "form", "fort", "fraud", "fray", "free", |
2400 | + "fresh", "Friday", "fried", "fright", "frozen", "fruit", "fry", "fur", |
2401 | + "game", "garden", "gate", "gel", "gem", "germ", "giggle", "ginger", |
2402 | + "giraffe", "gleam", "glean", "glow", "gluestick", "goat", "going", |
2403 | + "gold", "goose", "Grace", "graceful", "grain", "grapefruit", |
2404 | + "grasshopper", "grateful", "gray", "grew", "groan", "grown", |
2405 | + "grown-up", "growth", "gumball", "habit", "hail", "handwriting", |
2406 | + "happen", "happy", "harm", "harmful", "harp", "haul", "haunt", "hawk", |
2407 | + "hay", "health", "heat", "heavy", "heel", "hello", "helpful", |
2408 | + "herself", "hi", "hidden", "highway", "hoist", "homemade", "homework", |
2409 | + "hoot", "hopeful", "hopscotch", "horn", "host", "houseboat", |
2410 | + "housefly", "huddle", "human", "humid", "hummingbird", "hump", |
2411 | + "hungry", "hunk", "hurdle", "hurl", "ice", "inch", "inside", |
2412 | + "instead", "itch", "Jake", "jar", "jaw", "Jean", "jeep", "jelly", |
2413 | + "jellyfish", "Jen", "jerk", "Jimmy", "jingle", "Jo", "Joan", "join", |
2414 | + "joint", "joy", "juggle", "juice", "jungle", "kickball", "kingfish", |
2415 | + "kits", "kitten", "kitty", "knack", "knee", "kneecap", "kneel", |
2416 | + "knelt", "knew", "knife", "knight", "knit", "knob", "knock", |
2417 | + "knockout", "knot", "knothole", "known", "lace", "lack", "lake", |
2418 | + "latch", "launch", "law", "lawn", "lay", "lazy", "leap", "leather", |
2419 | + "Lee", "lemon", "less", "lie", "lighthouse", "limit", "link", |
2420 | + "lipstick", "living", "load", "loaf", "loop", "loose", "lot", "low", |
2421 | + "lunchbox", "Mabel", "mail", "main", "mane", "march", "mark", "match", |
2422 | + "Matt", "meant", "meat", "meet", "mice", "middle", "mild", "mind", |
2423 | + "mine", "mitten", "moan", "model", "moist", "mold", "moment", |
2424 | + "Monday", "moo", "mood", "motel", "mow", "munch", "music", "muzzle", |
2425 | + "nab", "nail", "nanny", "Nate", "neat", "necktie", "nerve", |
2426 | + "newscast", "newspaper", "nice", "nickname", "nighttime", "nips", |
2427 | + "noise", "noon", "north", "nowhere", "oak", "oat", "oatmeal", |
2428 | + "object", "oink", "ooze", "outside", "ox", "pace", "paddle", "pail", |
2429 | + "pain", "painful", "paint", "pal", "pancake", "paperback", "park", |
2430 | + "pause", "paw", "pawn", "pay", "peace", "peaceful", "peach", "peak", |
2431 | + "peddle", "peep", "pencil", "pennies", "penny", "perch", "piano", |
2432 | + "pie", "pillow", "pilot", "pink", "pipe", "pitch", "ploy", "poison", |
2433 | + "pony", "pooch", "poodle", "pool", "popcorn", "porch", "port", "post", |
2434 | + "poster", "potpie", "pretzel", "price", "proof", "pupil", "puppy", |
2435 | + "purple", "purse", "puzzle", "quack", "queen", "quicksand", "rabbit", |
2436 | + "race", "rack", "rage", "rail", "rain", "rainbow", "ranch", "rang", |
2437 | + "rattle", "raw", "ray", "reach", "ready", "recycle", "refund", |
2438 | + "renew", "restful", "return", "ribbon", "rice", "riddle", "rind", |
2439 | + "rink", "rise", "road", "roast", "rob", "robin", "robot", "room", |
2440 | + "roost", "row", "Roy", "royal", "ruled", "rumble", "runway", "rush", |
2441 | + "saddle", "sag", "sail", "sailboat", "salad", "sample", "sandbox", |
2442 | + "sandpaper", "sandy", "Saturday", "sauce", "saucer", "scarf", "scold", |
2443 | + "scorch", "score", "scrape", "scratch", "scream", "screen", "screw", |
2444 | + "scrub", "seal", "seat", "serve", "settle", "shade", "shadow", |
2445 | + "shake", "shaking", "shameful", "shape", "share", "shark", "sharp", |
2446 | + "sheep", "shipwreck", "shirt", "shore", "short", "shrink", "shrub", |
2447 | + "shrug", "shy", "sidewalk", "sigh", "sight", "silence", "silly", |
2448 | + "simple", "sips", "sir", "siren", "sky", "slice", "slick", "slight", |
2449 | + "slow", "slur", "sly", "smart", "smiling", "smooth", "snail", "sneak", |
2450 | + "snooze", "snore", "snow", "snowball", "snowflake", "snowman", "soak", |
2451 | + "soap", "sofa", "soil", "someone", "somewhere", "sore", "sort", "soy", |
2452 | + "space", "spark", "speak", "splendid", "splotch", "spoil", "spool", |
2453 | + "spoon", "sport", "sprain", "sprawl", "spray", "spread", "spring", |
2454 | + "sprint", "spruce", "spur", "squawk", "stage", "star", "startle", |
2455 | + "stay", "steam", "steep", "stern", "stiffer", "stir", "stool", |
2456 | + "store", "stork", "storm", "strain", "strange", "straw", "stray", |
2457 | + "stream", "street", "stretch", "strict", "strike", "string", "strong", |
2458 | + "stung", "sue", "suit", "suitcase", "sunblock", "Sunday", "sunflower", |
2459 | + "sunny", "sunrise", "sunshine", "surf", "sway", "sweat", "sweep", |
2460 | + "sweet", "swerve", "swimming", "swirl", "switch", "tablet", "tail", |
2461 | + "taps", "tattle", "taught", "tea", "teach", "teacher", "team", |
2462 | + "tease", "teeth", "tennis", "thankful", "thick", "thigh", "thimble", |
2463 | + "thin", "thinner", "thinnest", "third", "thirst", "thorn", "thread", |
2464 | + "threat", "thrill", "throat", "throw", "Thursday", "tie", "tiger", |
2465 | + "tight", "tired", "toast", "toil", "told", "tool", "tooth", "topcoat", |
2466 | + "torch", "torn", "tot", "tow", "toy", "trace", "traffic", "train", |
2467 | + "trash", "travel", "tray", "tread", "treetop", "trouble", "truck", |
2468 | + "trumpet", "Tuesday", "tugboat", "tulip", "tumble", "tummy", "turtle", |
2469 | + "tusk", "twirl", "ugly", "unzip", "useful", "value", "vanish", "verb", |
2470 | + "verse", "vine", "visit", "visitor", "voice", "void", "vote", |
2471 | + "waddle", "wage", "wagon", "wait", "wake", "waves", "wealth", |
2472 | + "weather", "weave", "web", "Wednesday", "weed", "week", "weekend", |
2473 | + "wettest", "whack", "whale", "whatever", "wheat", "wheel", "whenever", |
2474 | + "whisk", "whiz", "wide", "wife", "wild", "windmill", "wonderful", |
2475 | + "wore", "worn", "wrap", "wreath", "wreck", "wrench", "wriggle", |
2476 | + "wrinkle", "wrist", "wristwatch", "written", "wrong", "wrote", "yak", |
2477 | + "yard", "yardstick", "yarn", "yawn", "yum", "Zack", "zebra", "zoo", |
2478 | + "zoom", "ban", "bar", "winter", "bay", "wear", "bye", "mitten", "aid", |
2479 | + "aim", "arc", "art", "ash", "axe", "cog", "cot", "cow", "dew", "ear", |
2480 | + "eel", "elf", "elk", "elm", "era", "fee", "fig", "fir", "flu", "gap", |
2481 | + "guy", "icy", "inn", "ivy", "Jay", "key", "nag", "oar", "odd", "owe", |
2482 | + "owl", "pea", "pod", "rib", "sew", "ski", "sob", "son", "sow", "spa", |
2483 | + "spy", "tar", "tax", "toe", "vet", "war", "won", "yap", "zen", "ax", |
2484 | + "bait", "barn", "bawl", "beak", "birth", "blab", "blade", "blame", |
2485 | + "blaze", "bleed", "bless", "blip", "blurb", "blurt", "bog", "bond", |
2486 | + "boo", "books", "booth", "bow", "boys", "brad", "bran", "brawn", |
2487 | + "brisk", "brook", "broth", "brother", "card", "cash", "cask", "caw", |
2488 | + "cheap", "cheek", "chow", "clack", "clang", "clash", "claw", "cloak", |
2489 | + "clod", "coast", "cob", "cod", "code", "cook", "coop", "cord", "cost", |
2490 | + "count", "coy", "crane", "crick", "crock", "crook", "crown", "crude", |
2491 | + "crumb", "cube", "cue", "dear", "disk", "dock", "doze", "drake", |
2492 | + "drape", "drawn", "drive", "dude", "east", "Ed", "faint", "flake", |
2493 | + "flame", "flesh", "flick", "flirt", "flit", "flock", "floor", "flour", |
2494 | + "flown", "flush", "fond", "foot", "fowl", "Fred", "fret", "frizz", |
2495 | + "frying", "fuse", "gang", "glade", "glaze", "glee", "glen", "glide", |
2496 | + "glob", "gloss", "goal", "gown", "grate", "greet", "grit", "grouch", |
2497 | + "growl", "gruff", "heal", "heap", "hem", "hike", "hood", "hoof", |
2498 | + "hook", "hoop", "howl", "huge", "husk", "imp", "intern", "jail", |
2499 | + "jib", "June", "jut", "laid", "lame", "leak", "lend", "lent", "lien", |
2500 | + "lint", "loan", "loin", "lone", "loot", "lop", "lord", "loud", "lurk", |
2501 | + "lute", "maid", "maze", "meal", "mirth", "mock", "mole", "moon", |
2502 | + "mouse", "mouth", "murk", "musk", "nook", "nurse", "pad", "paid", |
2503 | + "peek", "peel", "pelt", "perk", "plain", "plants", "player", "plod", |
2504 | + "plow", "plums", "pork", "prance", "pray", "prayer", "present", |
2505 | + "prim", "prince", "probe", "prod", "program", "proud", "prowl", "pry", |
2506 | + "punt", "raid", "rant", "real", "rent", "risk", "Rome", "roof", |
2507 | + "rude", "rung", "scald", "scar", "scoop", "scoot", "scout", "scowl", |
2508 | + "scuff", "scum", "seek", "seen", "shawl", "sheet", "shirk", "shook", |
2509 | + "shoot", "shot", "shout", "shown", "sift", "silk", "sixth", "skips", |
2510 | + "skirt", "skull", "slash", "slaw", "slay", "slid", "slit", "slop", |
2511 | + "smear", "smith", "smock", "smoky", "snare", "snatch", "sneeze", |
2512 | + "snob", "snoop", "snuff", "soot", "sour", "south", "speck", "speech", |
2513 | + "speed", "spike", "spry", "spud", "spurn", "spurt", "stain", "stall", |
2514 | + "Stan", "steal", "stood", "sulk", "swamp", "swan", "swap", "swarm", |
2515 | + "swat", "swatch", "swept", "swig", "swine", "swish", "swoop", "sworn", |
2516 | + "swum", "tale", "task", "tend", "tenth", "term", "thumb", "tint", |
2517 | + "tock", "town", "toys", "track", "trail", "tram", "trek", "tribe", |
2518 | + "trod", "Troy", "tune", "tweed", "tweet", "twelve", "twenty", "twice", |
2519 | + "twine", "twitter", "urge", "urn", "uses", "vase", "vow", "wade", |
2520 | + "wed", "wept", "west", "whine", "whir", "wick", "wilt", "woke", |
2521 | + "wood", "woof", "wool", "wove", "wow", "zest", "zone", "against", |
2522 | + "American", "among", "asked", "course", "days", "didn't", "during", |
2523 | + "eyes", "general", "given", "however", "later", "order", "possible", |
2524 | + "president", "rather", "since", "states", "system", "things", |
2525 | + "though", "toward", "united", "used", "years", "color", "suddenly", |
2526 | + "zipper", "ah", "ho", "Ma", "Pa", "TV", "ago", "baa", "God", "hoe", |
2527 | + "I'd", "I'm", "sis", "ill", "O.K", "ache", "aunt", "bare", "bear", |
2528 | + "boom", "busy", "dare", "lose", "love", "none", "rule", "sure", |
2529 | + "tire", "tube", "copy", "edge", "else", "fizz", "glue", "hair", |
2530 | + "half", "hour", "I'll", "I've", "July", "kill", "lady", "lamb", |
2531 | + "leaf", "liar", "lion", "mama", "mash", "meow", "mush", "obey", |
2532 | + "okay", "ouch", "oven", "papa", "pour", "push", "roll", "shoe", |
2533 | + "soda", "tiny", "worm", "TRUE", "U.S.", "agree", "alive", "apple", |
2534 | + "April", "awake", "blood", "break", "chair", "cloud", "cough", |
2535 | + "cover", "dance", "erase", "phone", "piece", "whole", "whose", |
2536 | + "adult", "angry", "belly", "death", "eagle", "empty", "extra", |
2537 | + "hurry", "maybe", "money", "movie", "nasty", "party", "pizza", |
2538 | + "quiet", "sorry", "stair", "sugar", "table", "taste", "threw", |
2539 | + "touch", "towel", "truth", "waist", "waste", "woman", "women", |
2540 | + "won't", "worse", "anyone", "arrive", "asleep", "August", "avenue", |
2541 | + "behave", "bridge", "carpet", "cereal", "choose", "cookie", "corner", |
2542 | + "crayon", "danger", "minute", "banana", "bucket", "carrot", "dollar", |
2543 | + "finger", "flower", "gentle", "handle", "listen", "mirror", "monkey", |
2544 | + "nickel", "nobody", "orange", "parent", "person", "pocket", "potato", |
2545 | + "puppet", "rocket", "search", "secret", "seesaw", "shovel", "shower", |
2546 | + "silent", "spider", "sponge", "squash", "squeak", "sticky", "summer", |
2547 | + "supper", "they'd", "ticket", "tiptoe", "tissue", "tomato", "tongue", |
2548 | + "turkey", "unfair", "wonder", "U.S.A.", "airport", "anybody", |
2549 | + "balloon", "bedroom", "bicycle", "brownie", "cartoon", "ceiling", |
2550 | + "channel", "chicken", "garbage", "promise", "squeeze", "address", |
2551 | + "blanket", "earache", "excited", "good-bye", "grandma", "grocery", |
2552 | + "indoors", "January", "kitchen", "lullaby", "monster", "morning", |
2553 | + "naughty", "October", "pajamas", "pretend", "quarter", "shampoo", |
2554 | + "stomach", "there's", "they'll", "they're", "they've", "tonight", |
2555 | + "unhappy", "airplane", "alphabet", "bathroom", "favorite", "medicine", |
2556 | + "December", "dinosaur", "elephant", "February", "football", |
2557 | + "forehead", "headache", "hospital", "lollipop", "November", |
2558 | + "outdoors", "question", "railroad", "remember", "sandwich", |
2559 | + "scissors", "shoulder", "softball", "tomorrow", "upstairs", |
2560 | + "vacation", "restroom", "astronaut", "beautiful", "bumblebee", |
2561 | + "cardboard", "chocolate", "Christmas", "classroom", "cranberry", |
2562 | + "drugstore", "furniture", "milkshake", "nightmare", "telephone", |
2563 | + "difficult", "everybody", "hamburger", "September", "spaceship", |
2564 | + "spaghetti", "stoplight", "underwear", "yesterday", "automobile", |
2565 | + "blackboard", "downstairs", "photograph", "strawberry", "television", |
2566 | + "toothbrush", "toothpaste", "baby-sitter", "grandfather", |
2567 | + "grandmother", "kindergarten", "refrigerator", "Thanksgiving", |
2568 | + "hide-and-seek", "pumpkin", "salt", "melted", "handed", "printed", |
2569 | + "landed", "wanted", "filled", "showed", "hugged", "tugged", "planned", |
2570 | + "jogged", "spilled", "smelled", "grilled", "slammed", "rushed", |
2571 | + "spelled", "saved", "baked", "named", "lined", "smiled", "closed", |
2572 | + "helped", "jumped", "looked", "clapped", "tapped", "kicked", |
2573 | + "dropped", "zipped", "wished", "pitched", "missed", "walked", |
2574 | + "worked", "she'll", "you'll", "he'll", "we're", "she's", "he's", |
2575 | + "you're", "we're" |
2576 | +}; |
A couple of non-critical comments:
* Next time please use move for things like the schemas as then diffs are tracked on them which makes reviewing them much easier.
* I think the "magic 32" should probably be a #define just so that if someone changes it it will be changed everywhere. For instance, changing it in _new() could cause an assert failure further down the road.
* A comment on hud_token_ list_distance_ slow () on why the assert isn't insane would be good :-)
* Love the test :-)