/*
 * TreeNode.h -- C++11 pointer-free N-ary tree
 *
 * Copyright (c) 2013, 2014 David Demelier <markand@malikania.fr>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifndef _TREE_NODE_H_
#define _TREE_NODE_H_

/**
 * @file TreeNode.h
 * @brief N-ary tree without pointers
 */

#include <algorithm>
#include <deque>
#include <memory>
#include <stdexcept>
#include <type_traits>

namespace {

/**
 * @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:
		using Yes	= char [2];
		using No	= char [1];

		static_assert(sizeof (char) != sizeof (long), "buy a new compiler");

		template <typename Value>
		static constexpr Yes &check(Value *u, decltype(*u == *u) * = nullptr);

		static constexpr No &check(...);

		static constexpr const bool value = sizeof (check((U *)0)) == sizeof (Yes);
	};

public:
	static constexpr const bool equalityComparable = HasEqualsTo<T>::value;
};

} // !namespace

/**
 * @class TreeNodeItem
 * @brief Children object
 * @see TreeNodeItemProxy
 */
template <typename T>
class TreeNodeItem {
public:
	/**
	 * Get the real object as a reference.
	 */
	virtual T &value() = 0;

	/**
	 * Do a real polymorphic copy of the children object.
	 *
	 * @return a copy of the object
	 */
	virtual std::unique_ptr<TreeNodeItem<T>> clone() const = 0;
};

/**
 * @class TreeNodeItemProxy
 * @brief Implements polymorphic copy for the given value
 */
template <typename T, typename Value>
class TreeNodeItemProxy final : public TreeNodeItem<T> {
private:
	Value m_value;

	TreeNodeItemProxy(const TreeNodeItemProxy &) = delete;
	TreeNodeItemProxy &operator=(const TreeNodeItemProxy &) = delete;
	TreeNodeItemProxy(TreeNodeItemProxy &&) = delete;
	TreeNodeItemProxy &operator=(TreeNodeItemProxy &&) = delete;

public:
	inline TreeNodeItemProxy(Value &&value)
		: m_value(std::move(value))
	{
	}

	inline TreeNodeItemProxy(const Value &value)
		: m_value(value)
	{
	}

	template <typename... Args>
	inline TreeNodeItemProxy(Args&&... args)
		: m_value(std::forward<Args>(args)...)
	{
	}

	T &value() override
	{
		return m_value;
	}

	std::unique_ptr<TreeNodeItem<T>> clone() const override
	{
		return std::make_unique<TreeNodeItemProxy<T, Value>>(m_value);
	}
};

/**
 * @class TreeNode
 * @brief Safe C++11 N-ary tree
 *
 * This class use a std::deque as the container, it allocate object on the heap to avoid useless
 * copy and move when adding new elements.
 */
template <typename T>
class TreeNode {
public:
	using Container	= std::deque<std::unique_ptr<TreeNodeItem<T>>>;

	TreeNode	*m_parent{nullptr};
	Container	 m_children;

public:
	/**
	 * Default constructor.
	 */
	TreeNode() = default;

	/**
	 * Default destructor.
	 */
	virtual ~TreeNode() = default;

	/**
	 * Copy constructor.
	 *
	 * @param other the other node
	 */
	TreeNode(const TreeNode &other)
		: m_parent(nullptr)
	{
		for (const auto &c : other.m_children) {
			m_children.push_back(c->clone());
			m_children.back()->value().m_parent = this;
		}
	}

	/**
	 * Move constructor.
	 *
	 * @param other the other node
	 */
	TreeNode(TreeNode &&other)
		: m_parent(nullptr)
		, m_children(std::move(other.m_children))
	{
		// Update children to update to *this
		for (auto &c : m_children)
			c->value().m_parent = this;

		other.m_children.clear();
	}

	/**
	 * Copy assignment operator.
	 *
	 * @param other the other node
	 */
	TreeNode &operator=(const TreeNode &other)
	{
		m_children.clear();

		for (const auto &c : other.m_children) {
			m_children.push_back(c->clone());
			m_children.back()->value().m_parent = this;
		}

		return *this;
	}

	/**
	 * Move assignment operator.
	 *
	 * @param other the other node
	 */
	TreeNode &operator=(TreeNode &&other)
	{
		m_children = std::move(other.m_children);

		// Update children to update to *this
		for (auto &c : m_children)
			c->value().m_parent = this;

		other.m_children.clear();

		return *this;
	}

	/**
	 * Add a child node to the beginning.
	 *
	 * @param child the children
	 */
	template <typename Value>
	inline void push(const Value &child)
	{
		m_children.push_front(std::make_unique<TreeNodeItemProxy<T, Value>>(child));
		m_children.front()->value().m_parent = this;
	}

	/**
	 * Move to the beginning.
	 *
	 * @param child the children
	 */
	template <typename Value>
	inline void push(Value &&child, typename std::enable_if<std::is_rvalue_reference<Value &&>::value>::type * = nullptr)
	{
		using Type = typename std::decay<Value>::type;

		m_children.push_front(std::make_unique<TreeNodeItemProxy<T, Type>>(std::move(child)));
		m_children.front()->value().m_parent = this;
	}

	/**
	 * Construct an element at the beginning in place.
	 *
	 * @param args the arguments
	 */
	template <typename... Args>
	void pushNew(Args&&... args)
	{
		m_children.emplace_front(std::make_unique<TreeNodeItemProxy<T, T>>(std::forward<Args>(args)...));
		m_children.front()->value().m_parent = this;
	}

	/**
	 * Add a child node to the end
	 *
	 * @param child the children
	 */
	template <typename Value>
	inline void append(const Value &child)
	{
		m_children.push_back(std::make_unique<TreeNodeItemProxy<T, Value>>(child));
		m_children.back()->value().m_parent = this;
	}

	/**
	 * Move a child node to the end
	 *
	 * @param child the children
	 */
	template <typename Value>
	inline void append(Value &&child, typename std::enable_if<std::is_rvalue_reference<Value &&>::value>::type * = nullptr)
	{
		using Type = typename std::decay<Value>::type;

		m_children.push_back(std::make_unique<TreeNodeItemProxy<T, Type>>(std::move(child)));
		m_children.back()->value().m_parent = this;
	}

	/**
	 * Construct an element at the end in place.
	 *
	 * @param args the arguments
	 */
	template <typename... Args>
	void appendNew(Args&&... args)
	{
		m_children.emplace_back(std::make_unique<TreeNodeItemProxy<T, T>>(std::forward<Args>(args)...));
		m_children.back()->value().m_parent = this;
	}

	/**
	 * Count the number of children in this node.
	 *
	 * @return the number of children
	 */
	unsigned countChildren() const noexcept
	{
		return static_cast<unsigned>(m_children.size());
	}

	/**
	 * Get the parent node.
	 *
	 * @return the parent node
	 * @throw std::out_of_range if there is no parent
	 */
	T &parent()
	{
		if (!m_parent)
			throw std::out_of_range("no parent");

		return static_cast<T &>(*m_parent);
	}

	/**
	 * Get the parent node.
	 *
	 * @return the parent node
	 * @throw std::out_of_range if there is no parent
	 */
	const T &parent() const
	{
		if (!m_parent)
			throw std::out_of_range("no parent");

		return static_cast<const T &>(*m_parent);
	}

	/**
	 * Check if the node is root (no parent).
	 *
	 * @return true if root
	 */
	bool isRoot() const noexcept
	{
		return m_parent == nullptr;
	}

	/**
	 * Check if the node is leaf (no children).
	 *
	 * @return true if leaf
	 */
	bool isLeaf() const noexcept
	{
		return m_children.size() == 0;
	}

	/**
	 * Remove a child from the node at the given index.
	 *
	 * @param index the position index
	 * @throw std::out_of_range if index is out of bounds
	 */
	void remove(int index)
	{
		if (index < 0 || index >= static_cast<int>(m_children.size()))
			throw std::out_of_range("index is out of range");

		m_children.erase(m_children.begin() + index);
	}

	/**
	 * Remove a child from the node, the child must exists and no comparison test is performed, only
	 * object addresses are compared.
	 *
	 * @param value the value that exists in the node
	 * @warn the removed object must not be used after the call
	 */
	void remove(T &value)
	{
		m_children.erase(std::remove_if(m_children.begin(), m_children.end(), [&] (auto &p) {
			return &p->value() == &value;
		}), m_children.end());
	}

	/**
	 * Remove a child from the node, the value is tested using operator== and therefore may not exist in the container.
	 *
	 * @param value the value that can be compared
	 * @warn the removed object must not be used after the call
	 */
	template <typename Value>
	void removeSame(const Value &value, typename std::enable_if<TypeTraits<Value>::equalityComparable>::type * = nullptr)
	{
		m_children.erase(std::remove_if(m_children.begin(), m_children.end(), [&] (auto &p) {
			return p->value() == value;
		}), m_children.end());
	}

	/**
	 * Remove all children.
	 */
	void clear()
	{
		m_children.clear();
	}

	/**
	 * Find a child in this node, the child address is used as the comparison so no equality operator is even called.
	 *
	 * @param child the child
	 * @return the index or -1 if not found
	 * @see indexOfSame
	 */
	int indexOf(const T &child) const noexcept
	{
		for (unsigned i = 0; i < m_children.size(); ++i)
			if (&m_children[i]->value() == &child)
				return i;

		return -1;
	}

	/**
	 * Find the index of a node that is equality comparable to value but may be not in the node.
	 *
	 * @param value the value to compare
	 * @return the index or -1 if not found
	 * @see indexOf
	 */
	template <typename Value>
	int indexOfSame(const Value &value, typename std::enable_if<TypeTraits<Value>::equalityComparable>::type * = nullptr) const noexcept
	{
		for (unsigned i = 0; i < m_children.size(); ++i)
			if (m_children[i]->value() == value)
				return i;

		return -1;
	}

	/**
	 * Move the other value to that node as children.
	 *
	 * Example, this is our tree:
	 *
	 *     a
	 *    / \
	 *   b   c
	 *       \
	 *        d
	 *
	 * Calling nodeB.move(nodeC) will end in the following tree:
	 *
	 *     a
	 *    / \
	 *   b   c
	 *  /
	 * d
	 *
	 * This function cannot be used accross different trees.
	 *
	 * @note moving a parent of that current not results in a loss of that node
	 * @param other the other node to move, the node is emptied but may be reused
	 * @param position position in that tree, -1 means end
	 */
	inline void move(T &other, int position = -1)
	{
		if (other.m_parent == nullptr) {
			throw std::invalid_argument("can't move root node");
		}
		if (&other == static_cast<T *>(this)) {
			throw std::invalid_argument("attempt to move node to itself");
		}

		auto it = std::find_if(other.m_parent->m_children.begin(), other.m_parent->m_children.end(), [&] (const auto &object) -> bool {
			return &object->value() == &other;
		});

		if (it == other.m_parent->m_children.end()) {
			throw std::invalid_argument("unable to find children node");
		}

		position = (position < 0) ? m_children.size() : position;

		m_children.insert(m_children.begin() + position, std::move(*it));
		other.m_parent->m_children.erase(it);
		m_children[position]->value().m_parent = this;
	}

	/**
	 * 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->value().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->value().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
	 * @return the reference to the children node
	 * @throw std::out_of_range on out of bounds
	 */
	T &operator[](int index)
	{
		return static_cast<T &>(m_children.at(index)->value());
	}

	/**
	 * Access a child.
	 *
	 * @param index the index
	 * @return the reference to the children node
	 * @throw std::out_of_range on out of bounds
	 */
	const T &operator[](int index) const
	{
		return static_cast<const T &>(m_children.at(index)->value());
	}
};

#endif // !_TREE_NODE_H_