tests/test_walk.c

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