/*
 * 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 <deque>
#include <memory>
#include <stdexcept>

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:
		static_assert(sizeof (char) != sizeof (long), "buy a new compiler");

		template <typename Value>
		static constexpr auto check(Value *u) -> decltype(*u == *u, char(0));

		static constexpr long check(...);

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

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

} // !namespace

/**
 * @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 {
private:
	using Container	= std::deque<std::unique_ptr<T>>;

	TreeNode	*m_parent { nullptr };
	Container	 m_children;

public:
	/**
	 * Default constructor.
	 */
	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(std::make_unique<T>(*c));
			m_children.back()->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->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(std::make_unique<T>(*c));
			m_children.back()->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->m_parent = this;

		other.m_children.clear();

		return *this;
	}

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

	/**
	 * Move to the beginning.
	 *
	 * @param child the children
	 */
	void push(T &&child)
	{
		m_children.push_front(std::make_unique<T>(std::move(child)));
		m_children.front()->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<T>(std::forward<Args>(args)...));
		m_children.front()->m_parent = this;
	}

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

	/**
	 * Move a child node to the end
	 *
	 * @param child the children
	 */
	void append(T &&child)
	{
		m_children.push_back(std::make_unique<T>(std::move(child)));
		m_children.back()->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<T>(std::forward<Args>(args)...));
		m_children.back()->m_parent = this;
	}

	/**
	 * Count the number of children in this node.
	 *
	 * @return the number of children
	 */
	unsigned countChildren() const
	{
		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
	{
		return m_parent == nullptr;
	}

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

	/**
	 * Find a child in this. The type must have operator==.
	 *
	 * @param child the child
	 * @return the index or -1 if not found
	 */
	template <typename Value>
	int indexOf(const Value &child, typename std::enable_if<TypeTraits<Value>::equalityComparable>::type * = nullptr) const
	{
		for (int i = 0; i < (int)m_children.size(); ++i)
			if (*m_children[i] == child)
				return i;

		return -1;
	}

	/**
	 * 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));
	}

	/**
	 * 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));
	}
};

#endif // !_TREE_NODE_H_