Mercurial > code
view C++/modules/Treenode/TreeNode.h @ 334:0b576ee64d45
* Create brand new hierarchy
* Rename DynLib to Dynlib
* Remove some warnings
author | David Demelier <markand@malikania.fr> |
---|---|
date | Sun, 08 Mar 2015 14:26:33 +0100 |
parents | C++/TreeNode.h@b4dcf2e0013e |
children | 5f38366c7654 |
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: 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 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: class Object { public: virtual T &get() = 0; virtual std::unique_ptr<Object> clone() const = 0; }; template <typename Value> struct Proxy final : public Object { private: Value m_value; Proxy(const Proxy &) = delete; Proxy &operator=(const Proxy &) = delete; Proxy(Proxy &&) = delete; Proxy &operator=(Proxy &&) = delete; public: inline Proxy(Value &&value) : m_value(std::move(value)) { } inline Proxy(const Value &value) : m_value(value) { } template <typename... Args> inline Proxy(Args&&... args) : m_value(std::forward<Args>(args)...) { } T &get() override { return m_value; } std::unique_ptr<Object> clone() const override { return std::make_unique<Proxy<Value>>(m_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()->get().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->get().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()->get().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->get().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()->get().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()->get().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()->get().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()->get().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()->get().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()->get().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->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->get() == 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]->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) const noexcept { for (unsigned i = 0; i < m_children.size(); ++i) if (m_children[i]->get() == value) return i; return -1; } /** * 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->get().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->get().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)->get()); } /** * 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)->get()); } }; #endif // !_TREE_NODE_H_