jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2020, the SerenityOS developers.
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/StringView.h>
10#include <AK/Trie.h>
11
12TEST_CASE(normal_behavior)
13{
14 Trie<char, DeprecatedString> dictionary('/', "");
15 constexpr StringView data[] { "test"sv, "example"sv, "foo"sv, "foobar"sv };
16 constexpr size_t total_chars = 18; // root (1), 'test' (4), 'example' (7), 'foo' (3), 'foobar' (3, "foo" already stored).
17 for (auto& view : data) {
18 auto it = view.begin();
19 MUST(dictionary.insert(it, view.end(), view, [](auto& parent, auto& it) -> Optional<DeprecatedString> { return DeprecatedString::formatted("{}{}", parent.metadata_value(), *it); }));
20 }
21
22 size_t i = 0;
23 MUST(dictionary.for_each_node_in_tree_order([&](auto&) {
24 ++i;
25 }));
26 EXPECT_EQ(i, total_chars);
27
28 for (auto& view : data) {
29 auto it = view.begin();
30 auto& node = dictionary.traverse_until_last_accessible_node(it, view.end());
31 EXPECT(it.is_end());
32 EXPECT(node.metadata().has_value());
33 EXPECT_EQ(view, node.metadata_value());
34 }
35
36 constexpr StringView test_data_with_prefix_in_dict[] { "testx"sv, "exampley"sv, "fooa"sv, "foobarb"sv, "fox"sv, "text"sv };
37 for (auto& view : test_data_with_prefix_in_dict) {
38 auto it = view.begin();
39 auto& node = dictionary.traverse_until_last_accessible_node(it, view.end());
40 EXPECT(!it.is_end());
41 EXPECT(node.metadata().has_value());
42 EXPECT(view.starts_with(node.metadata_value()));
43 }
44}
45
46TEST_CASE(iterate)
47{
48 Trie<int> bunch_of_numbers { 0 };
49 Array<int, 64> input;
50 for (size_t i = 0; i < input.size(); ++i)
51 input[i] = i;
52
53 MUST(bunch_of_numbers.insert(input.begin(), input.end()));
54
55 // Iteration order is preorder (order between adjacent nodes is not defined, but parents come before children)
56 // in this case, the tree is linear.
57 size_t i = 0;
58 bool is_root = true;
59 MUST(bunch_of_numbers.for_each_node_in_tree_order([&](auto& node) {
60 if (is_root) {
61 is_root = false;
62 return;
63 }
64 EXPECT_EQ(input[i], node.value());
65 ++i;
66 }));
67}