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