Mercurial > code
view C++/TreeNode.h @ 256:0080762c8983
TreeNode: support inheritance through proxies
author | David Demelier <markand@malikania.fr> |
---|---|
date | Thu, 02 Oct 2014 20:40:56 +0200 |
parents | 8196fdb0fc48 |
children | 02aea4deed32 |
line wrap: on
line source
/* * 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: 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: struct Object { std::unique_ptr<T> value; virtual std::unique_ptr<Object> clone() const = 0; }; template <typename U> struct Proxy final : public Object { inline Proxy(U &&u) { this->value = std::make_unique<U>(std::move(u)); } inline Proxy(const U &u) { this->value = std::make_unique<U>(u); } template <typename... Args> inline Proxy(Args&&... args) { this->value = std::make_unique<U>(std::forward<Args>(args)...); } std::unique_ptr<Object> clone() const override { return std::make_unique<Proxy<U>>(static_cast<const U &>(*this->value)); } }; using Container = std::deque<std::unique_ptr<Object>>; 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<Proxy<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<Proxy<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<Proxy<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<Proxy<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<Proxy<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<Proxy<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 { 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; } /** * 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(unsigned index) { if (index >= 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.get() == &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 { for (unsigned i = 0; i < m_children.size(); ++i) if (m_children[i]->value.get() == &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) { for (unsigned i = 0; i < m_children.size(); ++i) if (*m_children[i]->value == value) 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)->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_