Mercurial > code
changeset 308:b4dcf2e0013e
TreeNode:
* Add map function
* Add flat function
* Add search functions
author | David Demelier <markand@malikania.fr> |
---|---|
date | Wed, 21 Jan 2015 11:15:31 +0100 |
parents | e2a8cbf2dd79 |
children | 9ce6d771b4fc |
files | C++/Tests/TreeNode/main.cpp C++/TreeNode.h |
diffstat | 2 files changed, 186 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/C++/Tests/TreeNode/main.cpp Wed Dec 10 10:39:38 2014 +0100 +++ b/C++/Tests/TreeNode/main.cpp Wed Jan 21 11:15:31 2015 +0100 @@ -18,6 +18,7 @@ #include <chrono> #include <iostream> +#include <iterator> #include <string> #include <gtest/gtest.h> @@ -1379,6 +1380,118 @@ ASSERT_EQ("b", root[1].name()); } +TEST(Misc, map) +{ + Object root("root"); + std::vector<Object> list; + + root.appendNew("a"); + root.appendNew("b"); + + root[0].appendNew("c"); + + root.map([&] (const auto &o) { + list.push_back(o); + }); + + ASSERT_EQ(4, list.size()); + ASSERT_EQ("root", list[0].name()); + ASSERT_EQ("a", list[1].name()); + ASSERT_EQ("c", list[2].name()); + ASSERT_EQ("b", list[3].name()); +} + +TEST(Misc, flat) +{ + Object root("root"); + std::vector<Object> list; + + root.appendNew("a"); + root.appendNew("b"); + + root[0].appendNew("c"); + root.flat(std::back_inserter(list)); + + ASSERT_EQ(4, list.size()); + ASSERT_EQ("root", list[0].name()); + ASSERT_EQ("a", list[1].name()); + ASSERT_EQ("c", list[2].name()); + ASSERT_EQ("b", list[3].name()); +} + +/* -------------------------------------------------------- + * Search + * -------------------------------------------------------- */ + +TEST(Search, returnsValue) +{ + Object root("root"); + + root.appendNew("a"); + root.appendNew("b"); + + root[0].appendNew("c"); + + auto dummy = [] (Object &) {}; + + ASSERT_TRUE(root.search([] (const auto &v) { return v.name() == "a"; }, dummy)); + ASSERT_TRUE(root.search([] (const auto &v) { return v.name() == "b"; }, dummy)); + ASSERT_TRUE(root.search([] (const auto &v) { return v.name() == "c"; }, dummy)); + ASSERT_FALSE(root.search([] (const auto &v) { return v.name() == "notavail"; }, dummy)); +} + +TEST(Search, returns) +{ + Object root("root"); + + root.appendNew("a"); + root.appendNew("b"); + + root[0].appendNew("c"); + + try { + auto &a = root.search([] (const auto &o) { + return o.name() == "a"; + }); + auto &b = root.search([] (const auto &o) { + return o.name() == "b"; + }); + auto &c = root.search([] (const auto &o) { + return o.name() == "c"; + }); + + ASSERT_EQ("a", a.name()); + ASSERT_EQ("b", b.name()); + ASSERT_EQ("c", c.name()); + + ASSERT_TRUE(&a == &root[0]); + ASSERT_TRUE(&b == &root[1]); + ASSERT_TRUE(&c == &root[0][0]); + } catch (const std::exception &ex) { + FAIL() << ex.what(); + } +} + +TEST(Search, returnsFirst) +{ + Object root("root"); + + root.appendNew("a"); + root.appendNew("a"); + root.appendNew("a"); + + try { + auto &value = root.search([] (const auto &v) { + return v.name() == "a"; + }); + + ASSERT_EQ("a", value.name()); + ASSERT_TRUE(&value == &root[0]); + } catch (const std::exception &ex) { + FAIL() << ex.what(); + } +} + /* -------------------------------------------------------- * Test inheritance * -------------------------------------------------------- */
--- a/C++/TreeNode.h Wed Dec 10 10:39:38 2014 +0100 +++ b/C++/TreeNode.h Wed Jan 21 11:15:31 2015 +0100 @@ -424,6 +424,79 @@ } /** + * Iterate over all the nodes. The first node is also passed through + * the callback. + * + * @param callback the callback + */ + template <typename Callback> + void map(Callback callback) + { + callback(static_cast<T &>(*this)); + + for (auto &v : m_children) + v->get().map(callback); + } + + /** + * Convert the tree to a flat list by appending to the output iterator. + * + * @param dest the destination iterator + */ + template <typename OutputIt> + void flat(OutputIt dest) + { + map([&] (const auto &value) { + *dest++ = value; + }); + } + + /** + * Iterate all values and call the function when found. + * + * @param predicate the predicate + * @param callable the callable to call when found + * @return true if found + */ + template <typename UnaryPredicate, typename Callable> + bool search(UnaryPredicate predicate, Callable callable) + { + if (predicate(static_cast<const T &>(*this))) { + callable(static_cast<T &>(*this)); + return true; + } + + for (auto &v : m_children) { + if (v->get().search(predicate, callable)) + return true; + } + + return false; + } + + /** + * Search and return the first value matching the predicate. + * + * @param predicate the predicate + * @return the reference to the node + * @throw std::out_of_range if not found + */ + template <typename UnaryPredicate> + T &search(UnaryPredicate predicate) + { + T *value{nullptr}; + + search(predicate, [&] (auto &ptr) { + value = &ptr; + }); + + if (value == nullptr) + throw std::out_of_range("node not found"); + + return *value; + } + + /** * Access a child. * * @param index the index