Mercurial > code
changeset 233:29eb8748b686
Add TreeNode, a N-ary tree implementation without pointers
author | David Demelier <markand@malikania.fr> |
---|---|
date | Tue, 24 Jun 2014 17:19:03 +0200 |
parents | 420b1710355f |
children | 99f8b9aedfb3 |
files | C++/TreeNode.h |
diffstat | 1 files changed, 240 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/C++/TreeNode.h Tue Jun 24 17:19:03 2014 +0200 @@ -0,0 +1,240 @@ +/* + * 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_ \ No newline at end of file