openkylin
/
libdatrie
mirror of https://gitee.com/openkylin/libdatrie.git
9
0
Fork 0
Code Issues Projects Releases Wiki Activity
libdatrie/tests/test_walk.c

553 lines
18 KiB
C
Raw Permalink Blame History

/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*
* libdatrie - Double-Array Trie Library
* Copyright (C) 2013 Theppitak Karoonboonyanan <theppitak@gmail.com>
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
/*
* test_walk.c - Test for datrie walking operations
* Created: 2013-10-16
* Author: Theppitak Karoonboonyanan <theppitak@gmail.com>
*/
#include <datrie/trie.h>
#include "utils.h"
#include <stdio.h>
#include <wchar.h>
/*
* Sample trie in http://linux.thai.net/~thep/datrie/datrie.html
*
* +---o-> (3) -o-> (4) -l-> [5]
* |
* | +---i-> (7) -z-> (8) -e-> [9]
* | |
* (1) -p-> (2) -r-> (6) -e-> (10) -v-> (11) -i-> (12) -e-> (13) -w-> [14]
* | |
* | +---p-> (15) -a-> (16) -r-> (17) -e-> [18]
* |
* +---o-> (19) -d-> (20) -u-> (21) -c-> (22) -e-> [23]
* |
* +---g-> (24) -r-> (25) -e-> (26) -s-> (27) -s-> [28]
*
*/
DictRec walk_dict[] = {
{(AlphaChar *)L"pool", TRIE_DATA_UNREAD},
{(AlphaChar *)L"prize", TRIE_DATA_UNREAD},
{(AlphaChar *)L"preview", TRIE_DATA_UNREAD},
{(AlphaChar *)L"prepare", TRIE_DATA_UNREAD},
{(AlphaChar *)L"produce", TRIE_DATA_UNREAD},
{(AlphaChar *)L"progress", TRIE_DATA_UNREAD},
{(AlphaChar *)NULL, TRIE_DATA_ERROR},
};
static Bool
is_walkables_include (AlphaChar c, const AlphaChar *walkables, int n_elm)
{
while (n_elm > 0) {
if (walkables[--n_elm] == c)
return TRUE;
}
return FALSE;
}
static void
print_walkables (const AlphaChar *walkables, int n_elm)
{
int i;
printf ("{");
for (i = 0; i < n_elm; i++) {
if (i > 0) {
printf (", ");
}
printf ("'%lc'", walkables[i]);
}
printf ("}");
}
#define ALPHABET_SIZE 256
int
main (void)
{
Trie *test_trie;
DictRec *dict_p;
TrieState *s, *t, *u;
AlphaChar walkables[ALPHABET_SIZE];
int n;
Bool is_failed;
TrieData data;
msg_step ("Preparing trie");
test_trie = en_trie_new ();
if (!test_trie) {
fprintf (stderr, "Fail to create test trie\n");
goto err_trie_not_created;
}
/* store */
for (dict_p = walk_dict; dict_p->key; dict_p++) {
if (!trie_store (test_trie, dict_p->key, dict_p->data)) {
printf ("Failed to add key '%ls', data %d.\n",
(wchar_t *)dict_p->key, dict_p->data);
goto err_trie_created;
}
}
printf (
"Now the trie structure is supposed to be:\n"
"\n"
);
printf (
" +---o-> (3) -o-> (4) -l-> [5]\n"
" |\n"
" | +---i-> (7) -z-> (8) -e-> [9]\n"
" | |\n"
"(1) -p-> (2) -r-> (6) -e-> (10) -v-> (11) -i-> (12) -e-> (13) -w-> [14]\n"
" | |\n"
" | +---p-> (15) -a-> (16) -r-> (17) -e-> [18]\n"
" |\n"
" +---o-> (19) -d-> (20) -u-> (21) -c-> (22) -e-> [23]\n"
" |\n"
" +---g-> (24) -r-> (25) -e-> (26) -s-> (27) -s-> [28]\n"
"\n"
);
/* walk */
msg_step ("Test walking");
s = trie_root (test_trie);
if (!s) {
printf ("Failed to get trie root state\n");
goto err_trie_created;
}
msg_step ("Test walking with 'p'");
if (!trie_state_is_walkable (s, L'p')) {
printf ("Trie state is not walkable with 'p'\n");
goto err_trie_state_s_created;
}
if (!trie_state_walk (s, L'p')) {
printf ("Failed to walk with 'p'\n");
goto err_trie_state_s_created;
}
msg_step ("Now at (2), walkable chars should be {'o', 'r'}");
is_failed = FALSE;
n = trie_state_walkable_chars (s, walkables, ALPHABET_SIZE);
if (2 != n) {
printf ("Walkable chars should be exactly 2, got %d\n", n);
is_failed = TRUE;
}
if (!is_walkables_include (L'o', walkables, n)) {
printf ("Walkable chars do not include 'o'\n");
is_failed = TRUE;
}
if (!is_walkables_include (L'r', walkables, n)) {
printf ("Walkable chars do not include 'r'\n");
is_failed = TRUE;
}
if (is_failed) {
printf ("Walkables = ");
print_walkables (walkables, n);
printf ("\n");
goto err_trie_state_s_created;
}
msg_step ("Try walking from (2) with 'o' to (3)");
t = trie_state_clone (s);
if (!t) {
printf ("Failed to clone trie state\n");
goto err_trie_state_s_created;
}
if (!trie_state_walk (t, L'o')) {
printf ("Failed to walk from (2) with 'o' to (3)\n");
goto err_trie_state_t_created;
}
if (!trie_state_is_single (t)) {
printf ("(3) should be single, but isn't.\n");
goto err_trie_state_t_created;
}
msg_step ("Try walking from (3) with 'o' to (4)");
if (!trie_state_walk (t, L'o')) {
printf ("Failed to walk from (3) with 'o' to (4)\n");
goto err_trie_state_t_created;
}
if (!trie_state_is_single (t)) {
printf ("(4) should be single, but isn't.\n");
goto err_trie_state_t_created;
}
msg_step ("Try walking from (4) with 'l' to (5)");
if (!trie_state_walk (t, L'l')) {
printf ("Failed to walk from (4) with 'l' to (5)\n");
goto err_trie_state_t_created;
}
if (!trie_state_is_terminal (t)) {
printf ("(5) should be terminal, but isn't.\n");
goto err_trie_state_t_created;
}
/* get key & data */
msg_step ("Try getting data from (5)");
data = trie_state_get_data (t);
if (TRIE_DATA_ERROR == data) {
printf ("Failed to get data from (5)\n");
goto err_trie_state_t_created;
}
if (TRIE_DATA_UNREAD != data) {
printf ("Mismatched data from (5), expected %d, got %d\n",
TRIE_DATA_UNREAD, data);
goto err_trie_state_t_created;
}
/* walk s from (2) with 'r' to (6) */
msg_step ("Try walking from (2) with 'r' to (6)");
if (!trie_state_walk (s, L'r')) {
printf ("Failed to walk from (2) with 'r' to (6)\n");
goto err_trie_state_t_created;
}
msg_step ("Now at (6), walkable chars should be {'e', 'i', 'o'}");
is_failed = FALSE;
n = trie_state_walkable_chars (s, walkables, ALPHABET_SIZE);
if (3 != n) {
printf ("Walkable chars should be exactly 3, got %d\n", n);
is_failed = TRUE;
}
if (!is_walkables_include (L'e', walkables, n)) {
printf ("Walkable chars do not include 'e'\n");
is_failed = TRUE;
}
if (!is_walkables_include (L'i', walkables, n)) {
printf ("Walkable chars do not include 'i'\n");
is_failed = TRUE;
}
if (!is_walkables_include (L'o', walkables, n)) {
printf ("Walkable chars do not include 'o'\n");
is_failed = TRUE;
}
if (is_failed) {
printf ("Walkables = ");
print_walkables (walkables, n);
printf ("\n");
goto err_trie_state_t_created;
}
/* walk from s (6) with "ize" */
msg_step ("Try walking from (6) with 'i' to (7)");
trie_state_copy (t, s);
if (!trie_state_walk (t, L'i')) {
printf ("Failed to walk from (6) with 'i' to (7)\n");
goto err_trie_state_t_created;
}
msg_step ("Try walking from (7) with 'z' to (8)");
if (!trie_state_walk (t, L'z')) {
printf ("Failed to walk from (7) with 'z' to (8)\n");
goto err_trie_state_t_created;
}
if (!trie_state_is_single (t)) {
printf ("(7) should be single, but isn't.\n");
goto err_trie_state_t_created;
}
msg_step ("Try walking from (8) with 'e' to (9)");
if (!trie_state_walk (t, L'e')) {
printf ("Failed to walk from (8) with 'e' to (9)\n");
goto err_trie_state_t_created;
}
if (!trie_state_is_terminal (t)) {
printf ("(9) should be terminal, but isn't.\n");
goto err_trie_state_t_created;
}
msg_step ("Try getting data from (9)");
data = trie_state_get_data (t);
if (TRIE_DATA_ERROR == data) {
printf ("Failed to get data from (9)\n");
goto err_trie_state_t_created;
}
if (TRIE_DATA_UNREAD != data) {
printf ("Mismatched data from (9), expected %d, got %d\n",
TRIE_DATA_UNREAD, data);
goto err_trie_state_t_created;
}
/* walk from u = s (6) with 'e' to (10) */
msg_step ("Try walking from (6) with 'e' to (10)");
u = trie_state_clone (s);
if (!u) {
printf ("Failed to clone trie state\n");
goto err_trie_state_t_created;
}
if (!trie_state_walk (u, L'e')) {
printf ("Failed to walk from (6) with 'e' to (10)\n");
goto err_trie_state_u_created;
}
/* walkable chars from (10) should be {'p', 'v'} */
msg_step ("Now at (10), walkable chars should be {'p', 'v'}");
is_failed = FALSE;
n = trie_state_walkable_chars (u, walkables, ALPHABET_SIZE);
if (2 != n) {
printf ("Walkable chars should be exactly 2, got %d\n", n);
is_failed = TRUE;
}
if (!is_walkables_include (L'p', walkables, n)) {
printf ("Walkable chars do not include 'p'\n");
is_failed = TRUE;
}
if (!is_walkables_include (L'v', walkables, n)) {
printf ("Walkable chars do not include 'v'\n");
is_failed = TRUE;
}
if (is_failed) {
printf ("Walkables = ");
print_walkables (walkables, n);
printf ("\n");
goto err_trie_state_u_created;
}
/* walk from u (10) with "view" */
msg_step ("Try walking from (10) with 'v' to (11)");
trie_state_copy (t, u);
if (!trie_state_walk (t, L'v')) {
printf ("Failed to walk from (10) with 'v' to (11)\n");
goto err_trie_state_u_created;
}
if (!trie_state_is_single (t)) {
printf ("(11) should be single, but isn't.\n");
goto err_trie_state_u_created;
}
msg_step ("Try walking from (11) with 'i' to (12)");
if (!trie_state_walk (t, L'i')) {
printf ("Failed to walk from (11) with 'i' to (12)\n");
goto err_trie_state_u_created;
}
msg_step ("Try walking from (12) with 'e' to (13)");
if (!trie_state_walk (t, L'e')) {
printf ("Failed to walk from (12) with 'e' to (13)\n");
goto err_trie_state_u_created;
}
msg_step ("Try walking from (13) with 'w' to (14)");
if (!trie_state_walk (t, L'w')) {
printf ("Failed to walk from (13) with 'w' to (14)\n");
goto err_trie_state_u_created;
}
if (!trie_state_is_terminal (t)) {
printf ("(14) should be terminal, but isn't.\n");
goto err_trie_state_u_created;
}
msg_step ("Try getting data from (14)");
data = trie_state_get_data (t);
if (TRIE_DATA_ERROR == data) {
printf ("Failed to get data from (14)\n");
goto err_trie_state_u_created;
}
if (TRIE_DATA_UNREAD != data) {
printf ("Mismatched data from (14), expected %d, got %d\n",
TRIE_DATA_UNREAD, data);
goto err_trie_state_u_created;
}
/* walk from u (10) with "pare" */
msg_step ("Try walking from (10) with 'p' to (15)");
trie_state_copy (t, u);
if (!trie_state_walk (t, L'p')) {
printf ("Failed to walk from (10) with 'p' to (15)\n");
goto err_trie_state_u_created;
}
if (!trie_state_is_single (t)) {
printf ("(15) should be single, but isn't.\n");
goto err_trie_state_u_created;
}
msg_step ("Try walking from (15) with 'a' to (16)");
if (!trie_state_walk (t, L'a')) {
printf ("Failed to walk from (15) with 'a' to (16)\n");
goto err_trie_state_u_created;
}
msg_step ("Try walking from (16) with 'r' to (17)");
if (!trie_state_walk (t, L'r')) {
printf ("Failed to walk from (16) with 'r' to (17)\n");
goto err_trie_state_u_created;
}
msg_step ("Try walking from (17) with 'e' to (18)");
if (!trie_state_walk (t, L'e')) {
printf ("Failed to walk from (17) with 'e' to (18)\n");
goto err_trie_state_u_created;
}
if (!trie_state_is_terminal (t)) {
printf ("(18) should be terminal, but isn't.\n");
goto err_trie_state_u_created;
}
msg_step ("Try getting data from (18)");
data = trie_state_get_data (t);
if (TRIE_DATA_ERROR == data) {
printf ("Failed to get data from (18)\n");
goto err_trie_state_u_created;
}
if (TRIE_DATA_UNREAD != data) {
printf ("Mismatched data from (18), expected %d, got %d\n",
TRIE_DATA_UNREAD, data);
goto err_trie_state_u_created;
}
trie_state_free (u);
/* walk s from (6) with 'o' to (19) */
msg_step ("Try walking from (6) with 'o' to (19)");
if (!trie_state_walk (s, L'o')) {
printf ("Failed to walk from (6) with 'o' to (19)\n");
goto err_trie_state_t_created;
}
msg_step ("Now at (19), walkable chars should be {'d', 'g'}");
is_failed = FALSE;
n = trie_state_walkable_chars (s, walkables, ALPHABET_SIZE);
if (2 != n) {
printf ("Walkable chars should be exactly 2, got %d\n", n);
is_failed = TRUE;
}
if (!is_walkables_include (L'd', walkables, n)) {
printf ("Walkable chars do not include 'd'\n");
is_failed = TRUE;
}
if (!is_walkables_include (L'g', walkables, n)) {
printf ("Walkable chars do not include 'g'\n");
is_failed = TRUE;
}
if (is_failed) {
printf ("Walkables = ");
print_walkables (walkables, n);
printf ("\n");
goto err_trie_state_t_created;
}
/* walk from s (19) with "duce" */
msg_step ("Try walking from (19) with 'd' to (20)");
trie_state_copy (t, s);
if (!trie_state_walk (t, L'd')) {
printf ("Failed to walk from (19) with 'd' to (20)\n");
goto err_trie_state_t_created;
}
if (!trie_state_is_single (t)) {
printf ("(20) should be single, but isn't.\n");
goto err_trie_state_t_created;
}
msg_step ("Try walking from (20) with 'u' to (21)");
if (!trie_state_walk (t, L'u')) {
printf ("Failed to walk from (20) with 'u' to (21)\n");
goto err_trie_state_t_created;
}
msg_step ("Try walking from (21) with 'c' to (22)");
if (!trie_state_walk (t, L'c')) {
printf ("Failed to walk from (21) with 'c' to (22)\n");
goto err_trie_state_t_created;
}
msg_step ("Try walking from (22) with 'e' to (23)");
if (!trie_state_walk (t, L'e')) {
printf ("Failed to walk from (22) with 'e' to (23)\n");
goto err_trie_state_t_created;
}
if (!trie_state_is_terminal (t)) {
printf ("(23) should be terminal, but isn't.\n");
goto err_trie_state_t_created;
}
msg_step ("Try getting data from (23)");
data = trie_state_get_data (t);
if (TRIE_DATA_ERROR == data) {
printf ("Failed to get data from (23)\n");
goto err_trie_state_t_created;
}
if (TRIE_DATA_UNREAD != data) {
printf ("Mismatched data from (23), expected %d, got %d\n",
TRIE_DATA_UNREAD, data);
goto err_trie_state_t_created;
}
trie_state_free (t);
/* walk from s (19) with "gress" */
msg_step ("Try walking from (19) with 'g' to (24)");
if (!trie_state_walk (s, L'g')) {
printf ("Failed to walk from (19) with 'g' to (24)\n");
goto err_trie_state_s_created;
}
if (!trie_state_is_single (s)) {
printf ("(24) should be single, but isn't.\n");
goto err_trie_state_s_created;
}
msg_step ("Try walking from (24) with 'r' to (25)");
if (!trie_state_walk (s, L'r')) {
printf ("Failed to walk from (24) with 'r' to (25)\n");
goto err_trie_state_s_created;
}
msg_step ("Try walking from (25) with 'e' to (26)");
if (!trie_state_walk (s, L'e')) {
printf ("Failed to walk from (25) with 'e' to (26)\n");
goto err_trie_state_s_created;
}
msg_step ("Try walking from (26) with 's' to (27)");
if (!trie_state_walk (s, L's')) {
printf ("Failed to walk from (26) with 's' to (27)\n");
goto err_trie_state_s_created;
}
msg_step ("Try walking from (27) with 's' to (28)");
if (!trie_state_walk (s, L's')) {
printf ("Failed to walk from (27) with 's' to (28)\n");
goto err_trie_state_s_created;
}
if (!trie_state_is_terminal (s)) {
printf ("(28) should be terminal, but isn't.\n");
goto err_trie_state_s_created;
}
msg_step ("Try getting data from (28)");
data = trie_state_get_data (s);
if (TRIE_DATA_ERROR == data) {
printf ("Failed to get data from (28)\n");
goto err_trie_state_s_created;
}
if (TRIE_DATA_UNREAD != data) {
printf ("Mismatched data from (28), expected %d, got %d\n",
TRIE_DATA_UNREAD, data);
goto err_trie_state_s_created;
}
trie_state_free (s);
trie_free (test_trie);
return 0;
err_trie_state_u_created:
trie_state_free (u);
err_trie_state_t_created:
trie_state_free (t);
err_trie_state_s_created:
trie_state_free (s);
err_trie_created:
trie_free (test_trie);
err_trie_not_created:
return 1;
}
/*
vi:ts=4:ai:expandtab
*/
Reference in New Issue View Git Blame Copy Permalink