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

/**
 * @class TreeNode
 * @brief Safe C++11 N-ary tree
 *
 * 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 typename T must be at least one of the following requirement:
 *	- CopyConstructible
 *	- MoveConstructible
 */
template <typename T, typename Container = std::vector<T>>
class TreeNode {
private:
	TreeNode	*m_parent = nullptr;
	Container	 m_children;

	/*
	 * This is used by move constructors and assignment. It removes the
	 * reference to the object in the old tree.
	 */
	inline void updateOther(TreeNode &&other)
	{
		if (other.m_parent) {
			auto &children = other.m_parent->m_children;
			auto finder = [&] (TreeNode &i) {
				return &other == &i;
			};

			children.erase(std::find_if(children.begin(), children.end(), finder));
		}

		other.m_parent = nullptr;
	}

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

	/**
	 * Copy constructor.
	 *
	 * @param other the other node
	 */
	TreeNode(const TreeNode &other)
		: TreeNode()
	{
		m_children = other.m_children;

		for (auto &c : m_children)
			c.m_parent = this;
	}

	/**
	 * Move constructor.
	 *
	 * @param other the other node
	 */
	TreeNode(TreeNode &&other)
		: TreeNode()
	{

		m_children = std::move(other.m_children);

		updateOther(std::move(other));

		for (auto &c : m_children)
			c.m_parent = this;
	}

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

		for (auto &c : m_children)
			c.m_parent = this;
	}

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

		updateOther(std::move(other));

		for (auto &c : m_children)
			c.m_parent = this;

		return *this;
	}

	/**
	 * Add a child node.
	 *
	 * @param child the children
	 */
	void add(const T &child)
	{
		m_children.push_back(child);
		m_children.back().m_parent = this;
	}

	/**
	 * Move a child node.
	 *
	 * @param child the child
	 */
	void add(T &&child)
	{
		m_children.push_back(std::move(child));
		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;
	}

	/**
	 * Access a children.
	 *
	 * @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 children.
	 *
	 * @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_