diff options
| -rw-r--r-- | AK/Tests/TestTrie.cpp | 7 | ||||
| -rw-r--r-- | AK/Trie.h | 15 |
2 files changed, 22 insertions, 0 deletions
diff --git a/AK/Tests/TestTrie.cpp b/AK/Tests/TestTrie.cpp index cae1b5b63f..853b9ff18a 100644 --- a/AK/Tests/TestTrie.cpp +++ b/AK/Tests/TestTrie.cpp @@ -71,10 +71,17 @@ TEST_CASE(iterate) for (size_t i = 0; i < input.size(); ++i) input[i] = i; + bunch_of_numbers.insert(input.begin(), input.end()); + // Iteration order is preorder (order between adjacent nodes is not defined, but parents come before children) // in this case, the tree is linear. size_t i = 0; + bool is_root = true; for (auto& node : bunch_of_numbers) { + if (is_root) { + is_root = false; + continue; + } EXPECT_EQ(input[i], node.value()); ++i; } @@ -183,6 +183,21 @@ public: return static_cast<BaseType&>(*last_root_node); } + template<typename It, typename ProvideMetadataFunction> + BaseType& insert( + const It& begin, const It& end, MetadataType metadata, ProvideMetadataFunction provide_missing_metadata) requires(!IsSame<MetadataType, decltype(nullptr)>::value) + { + auto it = begin; + return insert(it, end, move(metadata), move(provide_missing_metadata)); + } + + template<typename It> + BaseType& insert(const It& begin, const It& end) requires(IsSame<MetadataType, decltype(nullptr)>::value) + { + auto it = begin; + return insert(it, end); + } + ConstIterator begin() const { return ConstIterator(*this); } ConstIterator end() const { return ConstIterator::end(); } |