# HG changeset patch
# User David Demelier <markand@malikania.fr>
# Date 1403794140 -7200
# Node ID 0e3ccc204bc213d62dbbd69998707d0d0c89b59a
# Parent  99f8b9aedfb34409ff86c60d34f775173b465f49
TreeNode: be more flexible

diff -r 99f8b9aedfb3 -r 0e3ccc204bc2 C++/TreeNode.h
--- a/C++/TreeNode.h	Wed Jun 25 12:58:29 2014 +0200
+++ b/C++/TreeNode.h	Thu Jun 26 16:49:00 2014 +0200
@@ -26,8 +26,147 @@
 
 #include <algorithm>
 #include <stdexcept>
+#include <type_traits>
 #include <vector>
 
+namespace
+{
+
+/**
+ * @class ContainerTraits
+ * @brief Check capabilities
+ *
+ * This class checks for several functions in the container to disable or enable functions
+ * depending on the container.
+ *
+ * Provides the following static members:
+ *
+ *	pushCopy	- Set to true if we can push to the beginning by lvalue
+ *	pushMove	- Set to true if we can push to the beginning by rvalue
+ *	appendCopy	- Set to true if we can append to the end by lvalue
+ *	appendMove	- Set to true if we can append to the end by rvalue
+ *	at		- Set to true if container has at (also require typedef size_type)
+ *	constAt		- Set to true if container has const at (also require typedef size_type)
+ */
+template <typename Container, typename Type>
+class ContainerTraits
+{
+private:
+	typedef char Yes[2];
+	typedef char No[1];
+
+	template <typename U, void (U::*)(const Type &)>
+	struct InsertCopy;
+
+	template <typename U, void (U::*)(Type &&)>
+	struct InsertMove;
+
+	template <typename U, const Type &(U::*)(typename U::size_type) const>
+	struct ConstAt;
+
+	template <typename U, Type &(U::*)(typename U::size_type)>
+	struct At;
+
+	/*
+	 * Container::push_front(const T &)
+	 */
+
+	template <typename U>
+	static Yes &testPushCopy(InsertCopy<U, &U::push_front> *);
+	template <typename U>
+	static No &testPushCopy(...);
+
+	/*
+	 * Container::push_front(T &&)
+	 */
+
+	template <typename U>
+	static Yes &testPushMove(InsertMove<U, &U::push_front> *);
+	template <typename U>
+	static No &testPushMove(...);
+
+	/*
+	 * Container::push_back(const T &)
+	 */
+
+	template <typename U>
+	static Yes &testAppendCopy(InsertCopy<U, &U::push_back> *);
+	template <typename U>
+	static No &testAppendCopy(...);
+
+	/*
+	 * Container::push_back(T &&)
+	 */
+
+	template <typename U>
+	static Yes &testAppendMove(InsertMove<U, &U::push_back> *);
+	template <typename U>
+	static No &testAppendMove(...);
+
+
+	/*
+	 * Container::at(size_type)
+	 */
+
+	template <typename U>
+	static Yes &testConstAt(ConstAt<U, &U::at> *);
+	template <typename U>
+	static No &testConstAt(...);
+
+	/*
+	 * Container::at(size_type)
+	 */
+
+	template <typename U>
+	static Yes &testAt(At<U, &U::at> *);
+	template <typename U>
+	static No &testAt(...);
+
+public:
+	static const bool pushCopy = sizeof (testPushCopy<Container>(nullptr)) == sizeof (Yes);
+	static const bool pushMove = sizeof (testPushMove<Container>(nullptr)) == sizeof (Yes);
+	static const bool appendCopy = sizeof (testAppendCopy<Container>(nullptr)) == sizeof( Yes);
+	static const bool appendMove = sizeof (testAppendMove<Container>(nullptr)) == sizeof (Yes);
+	static const bool constAt = sizeof (testConstAt<Container>(nullptr)) == sizeof (Yes);
+	static const bool at = sizeof (testAt<Container>(nullptr)) == sizeof (Yes);
+};
+
+/**
+ * @class TypeTraits
+ * @brief Some checks on the type
+ *
+ * Provides the following members depending on the type:
+ *
+ *	equalityComparable	- If == comparison can be performed
+ */
+template <typename T>
+class TypeTraits {
+private:
+	/**
+	 * @class HasEqualsTo
+	 * @brief Check if the type is comparable
+	 *
+	 * Sets to true if the type T can is equality comparable.
+	 */
+	template <typename U>
+	class HasEqualsTo {
+	public:
+		static_assert(sizeof (char) != sizeof (long), "buy a new compiler");
+
+		template <typename Value>
+		static auto check(Value *u) -> decltype(*u == *u, char(0));
+
+		static long check(...);
+
+		static const bool value = sizeof (check((U*)0)) == sizeof (char);
+	};
+
+public:
+	static const bool equalityComparable = HasEqualsTo<T>::value;
+};
+
+} // !namespace
+
 /**
  * @class TreeNode
  * @brief Safe C++11 N-ary tree
@@ -35,52 +174,76 @@
  * This class template can be used to implement N-ary trees without any pointers. It uses
  * move semantics and copy constructs to avoid usage of pointers.
  *
+ * The container must have at least the following types:
+ *	size_type			- Typedef for indexation
+ *
+ * And the following functions:
+ *	T &at(size_type)		- Indexation at specified index
+ *	const T &at(size_type) const	- Indexation at specified index (const version)
+ *
  * The typename T must be at least one of the following requirement:
- *	- CopyConstructible
- *	- MoveConstructible
+ *	CopyConstructible
+ *	MoveConstructible
+ *	Comparable with operator==
+
  */
 template <typename T, typename Container = std::vector<T>>
-class TreeNode {
+class TNewTreeNode
+{
+	static_assert(ContainerTraits<Container, T>::at, "container must have at(size_type)");
+	static_assert(ContainerTraits<Container, T>::constAt, "container must have at(size_type) const");
+
 private:
-	TreeNode	*m_parent = nullptr;
+	TNewTreeNode	*m_parent;
 	Container	 m_children;
 
+public:
 	/*
 	 * This is used by move constructors and assignment. It removes the
 	 * reference to the object in the old tree.
 	 */
-	inline void updateOther(TreeNode &&other)
+	inline void updateOther(TNewTreeNode &&other)
 	{
 		if (other.m_parent) {
-			auto &children = other.m_parent->m_children;
-			auto finder = [&] (TreeNode &i) {
+			Container &children = other.m_parent->m_children;
+
+			children.erase(std::find_if(children.begin(), children.end(), [&] (TNewTreeNode &i) {
 				return &other == &i;
-			};
-
-			children.erase(std::find_if(children.begin(), children.end(), finder));
+			}));
 		}
 
 		other.m_parent = nullptr;
 	}
 
+	/*
+	 * When reallocation of m_children occurs, we need to update the relations.
+	 */
+	inline void refreshChildren()
+	{
+		for (T &child : m_children)
+			child.m_parent = this;
+	}
+
 public:
 	/**
 	 * Default constructor.
 	 */
-	TreeNode() = default;
+	TNewTreeNode()
+		: m_parent(nullptr)
+	{
+	}
 
 	/**
 	 * Copy constructor.
 	 *
 	 * @param other the other node
 	 */
-	TreeNode(const TreeNode &other)
-		: TreeNode()
+	TNewTreeNode(const TNewTreeNode &other)
 	{
+		m_parent = nullptr;
 		m_children = other.m_children;
 
-		for (auto &c : m_children)
-			c.m_parent = this;
+		refreshChildren();
 	}
 
 	/**
@@ -88,16 +251,13 @@
 	 *
 	 * @param other the other node
 	 */
-	TreeNode(TreeNode &&other)
-		: TreeNode()
+	TNewTreeNode(TNewTreeNode &&other)
 	{
-
+		m_parent = nullptr;
 		m_children = std::move(other.m_children);
 
 		updateOther(std::move(other));
-
-		for (auto &c : m_children)
-			c.m_parent = this;
+		refreshChildren();
 	}
 
 	/**
@@ -105,13 +265,13 @@
 	 *
 	 * @param other the other node
 	 */
-	TreeNode &operator=(const TreeNode &other)
+	TNewTreeNode &operator=(const TNewTreeNode &other)
 	{
-		m_parent = nullptr;
 		m_children = other.m_children;
 
-		for (auto &c : m_children)
-			c.m_parent = this;
+		refreshChildren();
+
+		return *this;
 	}
 
 	/**
@@ -119,39 +279,62 @@
 	 *
 	 * @param other the other node
 	 */
-	TreeNode &operator=(TreeNode &&other)
+	TNewTreeNode &operator=(TNewTreeNode &&other)
 	{
-		m_parent = nullptr;
 		m_children = std::move(other.m_children);
 
 		updateOther(std::move(other));
-
-		for (auto &c : m_children)
-			c.m_parent = this;
+		refreshChildren();
 
 		return *this;
 	}
 
 	/**
-	 * Add a child node.
+	 * Add a child node to the beginning.
+	 *
+	 * @param child the children
+	 */
+	template <typename Value>
+	void push(const Value &child, typename std::enable_if<ContainerTraits<Container, Value>::pushCopy>::type * = 0)
+	{
+		m_children.push_front(child);
+		refreshChildren();
+	}
+
+	/**
+	 * Move to the beginning.
 	 *
 	 * @param child the children
 	 */
-	void add(const T &child)
+	template <typename Value>
+	void push(Value &&child, typename std::enable_if<std::is_rvalue_reference<Value&&>::value && ContainerTraits<Container, Value>::pushMove>::type * = 0)
 	{
-		m_children.push_back(child);
-		m_children.back().m_parent = this;
+		m_children.push_front(std::move(child));
+		refreshChildren();
 	}
 
 	/**
-	 * Move a child node.
+	 * Add a child node to the end
 	 *
-	 * @param child the child
+	 * @param child the children
 	 */
-	void add(T &&child)
+	template <typename Value>
+	void append(const Value &child, typename std::enable_if<ContainerTraits<Container, Value>::appendCopy>::type * = 0)
+	{
+		m_children.push_back(child);
+		refreshChildren();
+	}
+
+	/**
+	 * Move a child node to the end
+	 *
+	 * @param child the children
+	 */
+	template <typename Value>
+	void append(Value &&child, typename std::enable_if<std::is_rvalue_reference<Value &&>::value && ContainerTraits<Container, Value>::appendMove>::type * = 0)
 	{
 		m_children.push_back(std::move(child));
-		m_children.back().m_parent = this;
+		refreshChildren();
 	}
 
 	/**
@@ -218,7 +401,8 @@
 	 * @param child the child
 	 * @return the index or -1 if not found
 	 */
-	int childIndex(const T &child)
+	template <typename Value>
+	int indexOf(const Value &child, typename std::enable_if<TypeTraits<Value>::equalityComparable>::type * = 0) const
 	{
 		for (int i = 0; i < (int)m_children.size(); ++i)
 			if (m_children[i] == child)