Debian Codegraph @

tests/test_walk.c

raw
1 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * libdatrie - Double-Array Trie Library
4 * Copyright (C) 2013 Theppitak Karoonboonyanan <[email protected]>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21 /*
22 * test_walk.c - Test for datrie walking operations
23 * Created: 2013-10-16
24 * Author: Theppitak Karoonboonyanan <[email protected]>
25 */
26
27 #include <datrie/trie.h>
28 #include "utils.h"
29 #include <stdio.h>
30 #include <wchar.h>
31
32 /*
33 * Sample trie in http://linux.thai.net/~thep/datrie/datrie.html
34 *
35 * +---o-> (3) -o-> (4) -l-> [5]
36 * |
37 * | +---i-> (7) -z-> (8) -e-> [9]
38 * | |
39 * (1) -p-> (2) -r-> (6) -e-> (10) -v-> (11) -i-> (12) -e-> (13) -w-> [14]
40 * | |
41 * | +---p-> (15) -a-> (16) -r-> (17) -e-> [18]
42 * |
43 * +---o-> (19) -d-> (20) -u-> (21) -c-> (22) -e-> [23]
44 * |
45 * +---g-> (24) -r-> (25) -e-> (26) -s-> (27) -s-> [28]
46 *
47 */
48 DictRec walk_dict[] = {
49 {(AlphaChar *)L"pool", TRIE_DATA_UNREAD},
50 {(AlphaChar *)L"prize", TRIE_DATA_UNREAD},
51 {(AlphaChar *)L"preview", TRIE_DATA_UNREAD},
52 {(AlphaChar *)L"prepare", TRIE_DATA_UNREAD},
53 {(AlphaChar *)L"produce", TRIE_DATA_UNREAD},
54 {(AlphaChar *)L"progress", TRIE_DATA_UNREAD},
55 {(AlphaChar *)NULL, TRIE_DATA_ERROR},
56 };
57
58 static Bool
59 is_walkables_include (AlphaChar c, const AlphaChar *walkables, int n_elm)
60 {
61 while (n_elm > 0) {
62 if (walkables[--n_elm] == c)
63 return TRUE;
64 }
65 return FALSE;
66 }
67
68 static void
69 print_walkables (const AlphaChar *walkables, int n_elm)
70 {
71 int i;
72
73 printf ("{");
74 for (i = 0; i < n_elm; i++) {
75 if (i > 0) {
76 printf (", ");
77 }
78 printf ("'%lc'", walkables[i]);
79 }
80 printf ("}");
81 }
82
83 #define ALPHABET_SIZE 256
84
85 int
86 main (void)
87 {
88 Trie *test_trie;
89 DictRec *dict_p;
90 TrieState *s, *t, *u;
91 AlphaChar walkables[ALPHABET_SIZE];
92 int n;
93 Bool is_failed;
94 TrieData data;
95
96 msg_step ("Preparing trie");
97 test_trie = en_trie_new ();
98 if (!test_trie) {
99 fprintf (stderr, "Fail to create test trie\n");
100 goto err_trie_not_created;
101 }
102
103 /* store */
104 for (dict_p = walk_dict; dict_p->key; dict_p++) {
105 if (!trie_store (test_trie, dict_p->key, dict_p->data)) {
106 printf ("Failed to add key '%ls', data %d.\n",
107 (wchar_t *)dict_p->key, dict_p->data);
108 goto err_trie_created;
109 }
110 }
111
112 printf (
113 "Now the trie structure is supposed to be:\n"
114 "\n"
115 );
116 printf (
117 " +---o-> (3) -o-> (4) -l-> [5]\n"
118 " |\n"
119 " | +---i-> (7) -z-> (8) -e-> [9]\n"
120 " | |\n"
121 "(1) -p-> (2) -r-> (6) -e-> (10) -v-> (11) -i-> (12) -e-> (13) -w-> [14]\n"
122 " | |\n"
123 " | +---p-> (15) -a-> (16) -r-> (17) -e-> [18]\n"
124 " |\n"
125 " +---o-> (19) -d-> (20) -u-> (21) -c-> (22) -e-> [23]\n"
126 " |\n"
127 " +---g-> (24) -r-> (25) -e-> (26) -s-> (27) -s-> [28]\n"
128 "\n"
129 );
130
131 /* walk */
132 msg_step ("Test walking");
133 s = trie_root (test_trie);
134 if (!s) {
135 printf ("Failed to get trie root state\n");
136 goto err_trie_created;
137 }
138
139 msg_step ("Test walking with 'p'");
140 if (!trie_state_is_walkable (s, L'p')) {
141 printf ("Trie state is not walkable with 'p'\n");
142 goto err_trie_state_s_created;
143 }
144 if (!trie_state_walk (s, L'p')) {
145 printf ("Failed to walk with 'p'\n");
146 goto err_trie_state_s_created;
147 }
148
149 msg_step ("Now at (2), walkable chars should be {'o', 'r'}");
150 is_failed = FALSE;
151 n = trie_state_walkable_chars (s, walkables, ALPHABET_SIZE);
152 if (2 != n) {
153 printf ("Walkable chars should be exactly 2, got %d\n", n);
154 is_failed = TRUE;
155 }
156 if (!is_walkables_include (L'o', walkables, n)) {
157 printf ("Walkable chars do not include 'o'\n");
158 is_failed = TRUE;
159 }
160 if (!is_walkables_include (L'r', walkables, n)) {
161 printf ("Walkable chars do not include 'r'\n");
162 is_failed = TRUE;
163 }
164 if (is_failed) {
165 printf ("Walkables = ");
166 print_walkables (walkables, n);
167 printf ("\n");
168 goto err_trie_state_s_created;
169 }
170
171 msg_step ("Try walking from (2) with 'o' to (3)");
172 t = trie_state_clone (s);
173 if (!t) {
174 printf ("Failed to clone trie state\n");
175 goto err_trie_state_s_created;
176 }
177 if (!trie_state_walk (t, L'o')) {
178 printf ("Failed to walk from (2) with 'o' to (3)\n");
179 goto err_trie_state_t_created;
180 }
181 if (!trie_state_is_single (t)) {
182 printf ("(3) should be single, but isn't.\n");
183 goto err_trie_state_t_created;
184 }
185
186 msg_step ("Try walking from (3) with 'o' to (4)");
187 if (!trie_state_walk (t, L'o')) {
188 printf ("Failed to walk from (3) with 'o' to (4)\n");
189 goto err_trie_state_t_created;
190 }
191 if (!trie_state_is_single (t)) {
192 printf ("(4) should be single, but isn't.\n");
193 goto err_trie_state_t_created;
194 }
195
196 msg_step ("Try walking from (4) with 'l' to (5)");
197 if (!trie_state_walk (t, L'l')) {
198 printf ("Failed to walk from (4) with 'l' to (5)\n");
199 goto err_trie_state_t_created;
200 }
201 if (!trie_state_is_terminal (t)) {
202 printf ("(5) should be terminal, but isn't.\n");
203 goto err_trie_state_t_created;
204 }
205
206 /* get key & data */
207 msg_step ("Try getting data from (5)");
208 data = trie_state_get_data (t);
209 if (TRIE_DATA_ERROR == data) {
210 printf ("Failed to get data from (5)\n");
211 goto err_trie_state_t_created;
212 }
213 if (TRIE_DATA_UNREAD != data) {
214 printf ("Mismatched data from (5), expected %d, got %d\n",
215 TRIE_DATA_UNREAD, data);
216 goto err_trie_state_t_created;
217 }
218
219 /* walk s from (2) with 'r' to (6) */
220 msg_step ("Try walking from (2) with 'r' to (6)");
221 if (!trie_state_walk (s, L'r')) {
222 printf ("Failed to walk from (2) with 'r' to (6)\n");
223 goto err_trie_state_t_created;
224 }
225
226 msg_step ("Now at (6), walkable chars should be {'e', 'i', 'o'}");
227 is_failed = FALSE;
228 n = trie_state_walkable_chars (s, walkables, ALPHABET_SIZE);
229 if (3 != n) {
230 printf ("Walkable chars should be exactly 3, got %d\n", n);
231 is_failed = TRUE;
232 }
233 if (!is_walkables_include (L'e', walkables, n)) {
234 printf ("Walkable chars do not include 'e'\n");
235 is_failed = TRUE;
236 }
237 if (!is_walkables_include (L'i', walkables, n)) {
238 printf ("Walkable chars do not include 'i'\n");
239 is_failed = TRUE;
240 }
241 if (!is_walkables_include (L'o', walkables, n)) {
242 printf ("Walkable chars do not include 'o'\n");
243 is_failed = TRUE;
244 }
245 if (is_failed) {
246 printf ("Walkables = ");
247 print_walkables (walkables, n);
248 printf ("\n");
249 goto err_trie_state_t_created;
250 }
251
252 /* walk from s (6) with "ize" */
253 msg_step ("Try walking from (6) with 'i' to (7)");
254 trie_state_copy (t, s);
255 if (!trie_state_walk (t, L'i')) {
256 printf ("Failed to walk from (6) with 'i' to (7)\n");
257 goto err_trie_state_t_created;
258 }
259 msg_step ("Try walking from (7) with 'z' to (8)");
260 if (!trie_state_walk (t, L'z')) {
261 printf ("Failed to walk from (7) with 'z' to (8)\n");
262 goto err_trie_state_t_created;
263 }
264 if (!trie_state_is_single (t)) {
265 printf ("(7) should be single, but isn't.\n");
266 goto err_trie_state_t_created;
267 }
268 msg_step ("Try walking from (8) with 'e' to (9)");
269 if (!trie_state_walk (t, L'e')) {
270 printf ("Failed to walk from (8) with 'e' to (9)\n");
271 goto err_trie_state_t_created;
272 }
273 if (!trie_state_is_terminal (t)) {
274 printf ("(9) should be terminal, but isn't.\n");
275 goto err_trie_state_t_created;
276 }
277
278 msg_step ("Try getting data from (9)");
279 data = trie_state_get_data (t);
280 if (TRIE_DATA_ERROR == data) {
281 printf ("Failed to get data from (9)\n");
282 goto err_trie_state_t_created;
283 }
284 if (TRIE_DATA_UNREAD != data) {
285 printf ("Mismatched data from (9), expected %d, got %d\n",
286 TRIE_DATA_UNREAD, data);
287 goto err_trie_state_t_created;
288 }
289
290 /* walk from u = s (6) with 'e' to (10) */
291 msg_step ("Try walking from (6) with 'e' to (10)");
292 u = trie_state_clone (s);
293 if (!u) {
294 printf ("Failed to clone trie state\n");
295 goto err_trie_state_t_created;
296 }
297 if (!trie_state_walk (u, L'e')) {
298 printf ("Failed to walk from (6) with 'e' to (10)\n");
299 goto err_trie_state_u_created;
300 }
301
302 /* walkable chars from (10) should be {'p', 'v'} */
303 msg_step ("Now at (10), walkable chars should be {'p', 'v'}");
304 is_failed = FALSE;
305 n = trie_state_walkable_chars (u, walkables, ALPHABET_SIZE);
306 if (2 != n) {
307 printf ("Walkable chars should be exactly 2, got %d\n", n);
308 is_failed = TRUE;
309 }
310 if (!is_walkables_include (L'p', walkables, n)) {
311 printf ("Walkable chars do not include 'p'\n");
312 is_failed = TRUE;
313 }
314 if (!is_walkables_include (L'v', walkables, n)) {
315 printf ("Walkable chars do not include 'v'\n");
316 is_failed = TRUE;
317 }
318 if (is_failed) {
319 printf ("Walkables = ");
320 print_walkables (walkables, n);
321 printf ("\n");
322 goto err_trie_state_u_created;
323 }
324
325 /* walk from u (10) with "view" */
326 msg_step ("Try walking from (10) with 'v' to (11)");
327 trie_state_copy (t, u);
328 if (!trie_state_walk (t, L'v')) {
329 printf ("Failed to walk from (10) with 'v' to (11)\n");
330 goto err_trie_state_u_created;
331 }
332 if (!trie_state_is_single (t)) {
333 printf ("(11) should be single, but isn't.\n");
334 goto err_trie_state_u_created;
335 }
336 msg_step ("Try walking from (11) with 'i' to (12)");
337 if (!trie_state_walk (t, L'i')) {
338 printf ("Failed to walk from (11) with 'i' to (12)\n");
339 goto err_trie_state_u_created;
340 }
341 msg_step ("Try walking from (12) with 'e' to (13)");
342 if (!trie_state_walk (t, L'e')) {
343 printf ("Failed to walk from (12) with 'e' to (13)\n");
344 goto err_trie_state_u_created;
345 }
346 msg_step ("Try walking from (13) with 'w' to (14)");
347 if (!trie_state_walk (t, L'w')) {
348 printf ("Failed to walk from (13) with 'w' to (14)\n");
349 goto err_trie_state_u_created;
350 }
351 if (!trie_state_is_terminal (t)) {
352 printf ("(14) should be terminal, but isn't.\n");
353 goto err_trie_state_u_created;
354 }
355
356 msg_step ("Try getting data from (14)");
357 data = trie_state_get_data (t);
358 if (TRIE_DATA_ERROR == data) {
359 printf ("Failed to get data from (14)\n");
360 goto err_trie_state_u_created;
361 }
362 if (TRIE_DATA_UNREAD != data) {
363 printf ("Mismatched data from (14), expected %d, got %d\n",
364 TRIE_DATA_UNREAD, data);
365 goto err_trie_state_u_created;
366 }
367
368 /* walk from u (10) with "pare" */
369 msg_step ("Try walking from (10) with 'p' to (15)");
370 trie_state_copy (t, u);
371 if (!trie_state_walk (t, L'p')) {
372 printf ("Failed to walk from (10) with 'p' to (15)\n");
373 goto err_trie_state_u_created;
374 }
375 if (!trie_state_is_single (t)) {
376 printf ("(15) should be single, but isn't.\n");
377 goto err_trie_state_u_created;
378 }
379 msg_step ("Try walking from (15) with 'a' to (16)");
380 if (!trie_state_walk (t, L'a')) {
381 printf ("Failed to walk from (15) with 'a' to (16)\n");
382 goto err_trie_state_u_created;
383 }
384 msg_step ("Try walking from (16) with 'r' to (17)");
385 if (!trie_state_walk (t, L'r')) {
386 printf ("Failed to walk from (16) with 'r' to (17)\n");
387 goto err_trie_state_u_created;
388 }
389 msg_step ("Try walking from (17) with 'e' to (18)");
390 if (!trie_state_walk (t, L'e')) {
391 printf ("Failed to walk from (17) with 'e' to (18)\n");
392 goto err_trie_state_u_created;
393 }
394 if (!trie_state_is_terminal (t)) {
395 printf ("(18) should be terminal, but isn't.\n");
396 goto err_trie_state_u_created;
397 }
398
399 msg_step ("Try getting data from (18)");
400 data = trie_state_get_data (t);
401 if (TRIE_DATA_ERROR == data) {
402 printf ("Failed to get data from (18)\n");
403 goto err_trie_state_u_created;
404 }
405 if (TRIE_DATA_UNREAD != data) {
406 printf ("Mismatched data from (18), expected %d, got %d\n",
407 TRIE_DATA_UNREAD, data);
408 goto err_trie_state_u_created;
409 }
410
411 trie_state_free (u);
412
413 /* walk s from (6) with 'o' to (19) */
414 msg_step ("Try walking from (6) with 'o' to (19)");
415 if (!trie_state_walk (s, L'o')) {
416 printf ("Failed to walk from (6) with 'o' to (19)\n");
417 goto err_trie_state_t_created;
418 }
419
420 msg_step ("Now at (19), walkable chars should be {'d', 'g'}");
421 is_failed = FALSE;
422 n = trie_state_walkable_chars (s, walkables, ALPHABET_SIZE);
423 if (2 != n) {
424 printf ("Walkable chars should be exactly 2, got %d\n", n);
425 is_failed = TRUE;
426 }
427 if (!is_walkables_include (L'd', walkables, n)) {
428 printf ("Walkable chars do not include 'd'\n");
429 is_failed = TRUE;
430 }
431 if (!is_walkables_include (L'g', walkables, n)) {
432 printf ("Walkable chars do not include 'g'\n");
433 is_failed = TRUE;
434 }
435 if (is_failed) {
436 printf ("Walkables = ");
437 print_walkables (walkables, n);
438 printf ("\n");
439 goto err_trie_state_t_created;
440 }
441
442 /* walk from s (19) with "duce" */
443 msg_step ("Try walking from (19) with 'd' to (20)");
444 trie_state_copy (t, s);
445 if (!trie_state_walk (t, L'd')) {
446 printf ("Failed to walk from (19) with 'd' to (20)\n");
447 goto err_trie_state_t_created;
448 }
449 if (!trie_state_is_single (t)) {
450 printf ("(20) should be single, but isn't.\n");
451 goto err_trie_state_t_created;
452 }
453 msg_step ("Try walking from (20) with 'u' to (21)");
454 if (!trie_state_walk (t, L'u')) {
455 printf ("Failed to walk from (20) with 'u' to (21)\n");
456 goto err_trie_state_t_created;
457 }
458 msg_step ("Try walking from (21) with 'c' to (22)");
459 if (!trie_state_walk (t, L'c')) {
460 printf ("Failed to walk from (21) with 'c' to (22)\n");
461 goto err_trie_state_t_created;
462 }
463 msg_step ("Try walking from (22) with 'e' to (23)");
464 if (!trie_state_walk (t, L'e')) {
465 printf ("Failed to walk from (22) with 'e' to (23)\n");
466 goto err_trie_state_t_created;
467 }
468 if (!trie_state_is_terminal (t)) {
469 printf ("(23) should be terminal, but isn't.\n");
470 goto err_trie_state_t_created;
471 }
472
473 msg_step ("Try getting data from (23)");
474 data = trie_state_get_data (t);
475 if (TRIE_DATA_ERROR == data) {
476 printf ("Failed to get data from (23)\n");
477 goto err_trie_state_t_created;
478 }
479 if (TRIE_DATA_UNREAD != data) {
480 printf ("Mismatched data from (23), expected %d, got %d\n",
481 TRIE_DATA_UNREAD, data);
482 goto err_trie_state_t_created;
483 }
484
485 trie_state_free (t);
486
487 /* walk from s (19) with "gress" */
488 msg_step ("Try walking from (19) with 'g' to (24)");
489 if (!trie_state_walk (s, L'g')) {
490 printf ("Failed to walk from (19) with 'g' to (24)\n");
491 goto err_trie_state_s_created;
492 }
493 if (!trie_state_is_single (s)) {
494 printf ("(24) should be single, but isn't.\n");
495 goto err_trie_state_s_created;
496 }
497 msg_step ("Try walking from (24) with 'r' to (25)");
498 if (!trie_state_walk (s, L'r')) {
499 printf ("Failed to walk from (24) with 'r' to (25)\n");
500 goto err_trie_state_s_created;
501 }
502 msg_step ("Try walking from (25) with 'e' to (26)");
503 if (!trie_state_walk (s, L'e')) {
504 printf ("Failed to walk from (25) with 'e' to (26)\n");
505 goto err_trie_state_s_created;
506 }
507 msg_step ("Try walking from (26) with 's' to (27)");
508 if (!trie_state_walk (s, L's')) {
509 printf ("Failed to walk from (26) with 's' to (27)\n");
510 goto err_trie_state_s_created;
511 }
512 msg_step ("Try walking from (27) with 's' to (28)");
513 if (!trie_state_walk (s, L's')) {
514 printf ("Failed to walk from (27) with 's' to (28)\n");
515 goto err_trie_state_s_created;
516 }
517 if (!trie_state_is_terminal (s)) {
518 printf ("(28) should be terminal, but isn't.\n");
519 goto err_trie_state_s_created;
520 }
521
522 msg_step ("Try getting data from (28)");
523 data = trie_state_get_data (s);
524 if (TRIE_DATA_ERROR == data) {
525 printf ("Failed to get data from (28)\n");
526 goto err_trie_state_s_created;
527 }
528 if (TRIE_DATA_UNREAD != data) {
529 printf ("Mismatched data from (28), expected %d, got %d\n",
530 TRIE_DATA_UNREAD, data);
531 goto err_trie_state_s_created;
532 }
533
534 trie_state_free (s);
535 trie_free (test_trie);
536 return 0;
537
538 err_trie_state_u_created:
539 trie_state_free (u);
540 err_trie_state_t_created:
541 trie_state_free (t);
542 err_trie_state_s_created:
543 trie_state_free (s);
544 err_trie_created:
545 trie_free (test_trie);
546 err_trie_not_created:
547 return 1;
548 }
549
550 /*
551 vi:ts=4:ai:expandtab
552 */