[krita] libs/global: Implement KisForest container for tree-like structures
Dmitry Kazakov
null at kde.org
Tue Jan 28 13:56:22 GMT 2020
Git commit e62259f2952506881689f57d835d4a642d6813a9 by Dmitry Kazakov.
Committed on 26/11/2019 at 10:28.
Pushed by dkazakov into branch 'master'.
Implement KisForest container for tree-like structures
Historically, we implemented tree-like structures by putting
the linked-lists inside the objects themselves (see KisNode and
KoShape). It it not very convenient in cases when you need a custom
hierarchy over existing objects, e.g. for composing.
KisForest implements a container for building tree-like structures from
arbitrary objects. The stored elements don't have to have know anything
about hierarchy and, more than that, they may be contained in multiple
different hierarchies.
See KisForestTest for examples on how to use the forest.
Ref T11969
CCBUG:392242
CC:kimageshop at kde.org
A +45 -0 libs/global/KisCppQuirks.h [License: GPL (v2+)]
A +881 -0 libs/global/KisForest.h [License: GPL (v2+)]
M +1 -0 libs/global/tests/CMakeLists.txt
A +884 -0 libs/global/tests/KisForestTest.cpp [License: GPL (v2+)]
A +55 -0 libs/global/tests/KisForestTest.h [License: GPL (v2+)]
https://invent.kde.org/kde/krita/commit/e62259f2952506881689f57d835d4a642d6813a9
diff --git a/libs/global/KisCppQuirks.h b/libs/global/KisCppQuirks.h
new file mode 100644
index 0000000000..4283839cd2
--- /dev/null
+++ b/libs/global/KisCppQuirks.h
@@ -0,0 +1,45 @@
+/*
+ * Copyright (c) 2019 Dmitry Kazakov <dimula73 at gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+#ifndef KISCPPQUIRKS_H
+#define KISCPPQUIRKS_H
+
+namespace std {
+
+#if __cplusplus < 201402L
+
+template <typename Cont>
+inline auto rbegin(Cont &cont) -> decltype(declval<Cont>().rbegin()) {
+ return cont.rbegin();
+}
+
+template <typename Cont>
+inline auto rend(Cont &cont) -> decltype(declval<Cont>().rend()) {
+ return cont.rend();
+}
+
+template <class BidirectionalIterator>
+inline reverse_iterator<BidirectionalIterator> make_reverse_iterator(BidirectionalIterator x)
+{
+ return reverse_iterator<BidirectionalIterator>(x);
+}
+
+#endif
+
+}
+
+#endif // KISCPPQUIRKS_H
diff --git a/libs/global/KisForest.h b/libs/global/KisForest.h
new file mode 100644
index 0000000000..f9c662b21f
--- /dev/null
+++ b/libs/global/KisForest.h
@@ -0,0 +1,881 @@
+/*
+ * Copyright (c) 2019 Dmitry Kazakov <dimula73 at gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+#ifndef KISFOREST_H
+#define KISFOREST_H
+
+#include <utility>
+
+#include <boost/iterator/iterator_facade.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+
+#include "KisCppQuirks.h"
+
+#include "kis_assert.h"
+#include "kis_debug.h"
+
+namespace KisForestDetail {
+
+template <typename Base>
+struct RootNodeImpl
+{
+ RootNodeImpl<Base> *parent = nullptr;
+ Base *firstChild = nullptr;
+ Base *lastChild = nullptr;
+
+ inline bool isRoot() const {
+ return !parent;
+ }
+};
+
+
+template <typename Base>
+struct BaseNode : RootNodeImpl<Base>
+{
+ Base *nextSibling = nullptr;
+ Base *prevSibling = nullptr;
+};
+
+template <typename T>
+struct Node : public BaseNode<Node<T>>
+{
+ explicit Node(T &&newValue)
+ : value(std::forward<T>(newValue))
+ {
+ }
+
+ T value;
+};
+
+template <typename T>
+using RootNode = RootNodeImpl<Node<T>>;
+
+
+/*************************************************************************/
+/* BaseIterator */
+/*************************************************************************/
+
+template <typename BaseClass, typename T, typename Tag>
+class BaseIterator :
+ public boost::iterator_facade <BaseClass,
+ T,
+ Tag>
+{
+public:
+ using value_type = T;
+
+ BaseIterator(Node<T> *node)
+ : m_node(node)
+ {
+ }
+
+ Node<T>* node() const {
+ return m_node;
+ }
+
+private:
+ friend class boost::iterator_core_access;
+
+ typename std::iterator_traits<BaseIterator>::reference dereference() const {
+ KIS_ASSERT(m_node);
+ return m_node->value;
+ }
+
+ bool equal(const BaseClass &other) const {
+ return m_node == other.m_node;
+ }
+
+protected:
+ Node<T> *m_node;
+};
+
+
+/*************************************************************************/
+/* ChildIterator */
+/*************************************************************************/
+
+/**
+ * Child iterator is used to traverse all the the children of the current node.
+ * It models \c BidirectionalIterator concept, so you can traverse with it in both
+ * directions.
+ *
+ * \code{.cpp}
+ *
+ * // Forest:
+ * //
+ * // 0 1
+ * // 2
+ * // 3 5 6
+ * // 7
+ * // 4
+ * // 8 9
+ * // 10
+ *
+ * KisForest<int>::iterator it0 = findValue(forest, 0);
+ *
+ * // iterate through all the children of '0'
+ * for (auto it = childBegin(it0); it != childEnd(it0); ++it) {
+ * qDebug() << *it;
+ * }
+ * // prints: 1,2,3,4
+ *
+ * \endcode
+ *
+ * It is also possible to convert any iterator type into child iterator
+ * via siblingCurrent() function.
+ *
+ * \code{.cpp}
+ *
+ * // Forest:
+ * //
+ * // 0 1
+ * // 2
+ * // 3 5 6
+ * // 7
+ * // 4
+ * // 8 9
+ * // 10
+ *
+ * KisForest<int>::iterator it2 = findValue(forest, 2);
+ *
+ * // iterate the children of '0' from '2' to '4'
+ * for (auto it = siblingCurrent(it2); it != siblingEnd(it2); ++it) {
+ * qDebug() << *it;
+ * }
+ * // prints: 2,3,4
+ *
+ * \endcode
+ *
+ * WARNING: converting end() iterator to other iterator types currently leads
+ * to undefined behavior.
+ */
+
+template <typename T>
+class ChildIterator :
+ public BaseIterator <ChildIterator<T>,
+ T,
+ boost::bidirectional_traversal_tag>
+{
+public:
+ ChildIterator(Node<T> *node, RootNode<T> *parent)
+ : BaseIterator<ChildIterator<T>, T, boost::bidirectional_traversal_tag>(node),
+ m_parent(parent)
+ {
+ }
+
+private:
+ friend class boost::iterator_core_access;
+ template <typename X>
+ friend ChildIterator<X> parent(const ChildIterator<X> &it);
+ template <typename X> friend class Forest;
+
+ void increment() {
+ this->m_node = this->m_node->nextSibling;
+ }
+
+ void decrement() {
+ this->m_node =
+ this->m_node ?
+ this->m_node->prevSibling :
+ m_parent ? m_parent->lastChild : nullptr;
+ }
+
+ bool equal(const ChildIterator<T> &other) const {
+ return this->m_node == other.m_node &&
+ (this->m_node || this->m_parent == other.m_parent);
+ }
+
+private:
+ RootNode<T> *m_parent;
+};
+
+template <typename Iterator,
+ typename ResultIterator = ChildIterator<typename Iterator::value_type>>
+ResultIterator siblingBegin(Iterator it)
+{
+ using RootNodeType = RootNode<typename Iterator::value_type>;
+
+ RootNodeType *parent = it.node() ? it.node()->parent : nullptr;
+ return ResultIterator(parent ? parent->firstChild : nullptr, parent);
+}
+
+
+template <typename Iterator,
+ typename ResultIterator = ChildIterator<typename Iterator::value_type>>
+ResultIterator siblingCurrent(Iterator it)
+{
+ return ResultIterator(it.node(), it.node() ? it.node()->parent : nullptr);
+}
+
+template <typename Iterator,
+ typename ResultIterator = ChildIterator<typename Iterator::value_type>>
+ResultIterator siblingEnd(Iterator it)
+{
+ return ResultIterator(nullptr, it.node() ? it.node()->parent : nullptr);
+}
+
+template <typename Iterator,
+ typename ResultIterator = ChildIterator<typename Iterator::value_type>>
+ResultIterator childBegin(Iterator it)
+{
+ return ResultIterator(it.node() ? it.node()->firstChild : nullptr, it.node());
+}
+
+template <typename Iterator,
+ typename ResultIterator = ChildIterator<typename Iterator::value_type>>
+ResultIterator childEnd(Iterator it)
+{
+ return ResultIterator(nullptr, it.node());
+}
+
+template <typename T>
+ChildIterator<T> parent(const ChildIterator<T> &it)
+{
+ Node<T> *parent = static_cast<Node<T>*>(it.m_parent && !it.m_parent->isRoot() ? it.m_parent : nullptr);
+ return ChildIterator<T>(parent, parent ? parent->parent : 0);
+}
+
+template <typename T>
+inline bool isEnd(const ChildIterator<T> &it) {
+ return !it.node();
+}
+
+
+/*************************************************************************/
+/* HierarchyIterator */
+/*************************************************************************/
+
+/**
+ * Hierarchy iterator is used to traverse from the current node to the root
+ * of the the current subtree of the forest. It models \c ForwardIterator concept.
+ *
+ * \code{.cpp}
+ *
+ * // Forest:
+ * //
+ * // 0 1
+ * // 2
+ * // 3 5 6
+ * // 7
+ * // 4
+ * // 8 9
+ * // 10
+ *
+ * KisForest<int>::iterator nodeIt = findValue(forest, 5);
+ *
+ * // print all the parent nodes for nodeIt, including nodeIt itself
+ * for (auto it = hierarchyBegin(nodeIt); it != hierarchyEnd(nodeIt); ++it) {
+ * qDebug() << *it;
+ * }
+ * // prints: 5,3,0
+ *
+ * \endcode
+ *
+ * WARNING: converting end() iterator to other iterator types currently leads
+ * to undefined behavior.
+ */
+
+template <typename T>
+class HierarchyIterator :
+ public BaseIterator <HierarchyIterator<T>,
+ T,
+ boost::forward_traversal_tag>
+{
+public:
+ HierarchyIterator(Node<T> *node)
+ : BaseIterator<HierarchyIterator<T>, T, boost::forward_traversal_tag>(node)
+ {
+ }
+
+
+private:
+ friend class boost::iterator_core_access;
+
+ void increment() {
+ RootNode<T> *parent = this->m_node->parent;
+ this->m_node =
+ static_cast<Node<T>*>(
+ parent && !parent->isRoot() ?
+ parent : nullptr);
+ }
+};
+
+template <typename Iterator,
+ typename ResultIterator = HierarchyIterator<typename Iterator::value_type>>
+ResultIterator hierarchyBegin(Iterator it)
+{
+ return ResultIterator(it.node());
+}
+
+template <typename Iterator,
+ typename ResultIterator = HierarchyIterator<typename Iterator::value_type>>
+ResultIterator hierarchyEnd(Iterator it)
+{
+ Q_UNUSED(it);
+ return ResultIterator(nullptr);
+}
+
+
+/*************************************************************************/
+/* CompositionIterator */
+/*************************************************************************/
+
+/**
+ * Composition iterator is used to traverse entire child-subtree of the node
+ * recursively in depth-first order. Every node it entered twice: first time, when
+ * subtree is entered; second time, when subtree is left. To check the current
+ * state of the iterator (Enter or Leave) use \c it.state() call.
+ *
+ * Iterator models \c ForwardIterator concept.
+ *
+ * \code{.cpp}
+ *
+ * // Forest:
+ * //
+ * // 0 1
+ * // 2
+ * // 3 5 6
+ * // 7
+ * // 4
+ * // 8 9
+ * // 10
+ *
+ * KisForest<int>::iterator it3 = findValue(forest, 3);
+ *
+ * // iterate through all the children of '3' recursively
+ * for (auto it = compositionBegin(it3); it != compositionEnd(it3); ++it) {
+ * qDebug() << *it << it.state();
+ * }
+ * // prints: (3, Enter)
+ * // (5, Enter)
+ * // (6, Enter)
+ * // (6, Leave)
+ * // (7, Enter)
+ * // (7, Leave)
+ * // (5, Leave)
+ * // (3, Leave)
+ *
+ * \endcode
+ *
+ * WARNING: converting end() iterator to other iterator types currently leads
+ * to undefined behavior.
+ */
+
+enum TraversalState {
+ Enter,
+ Leave
+};
+
+template <typename T>
+class CompositionIterator :
+ public boost::iterator_adaptor<
+ CompositionIterator<T>,
+ ChildIterator<T>,
+ boost::use_default,
+ boost::forward_traversal_tag>
+{
+ using BaseClass = boost::iterator_adaptor<
+ CompositionIterator<T>,
+ ChildIterator<T>,
+ boost::use_default,
+ boost::forward_traversal_tag>;
+
+public:
+ using traversal_state = TraversalState;
+
+ Node<T>* node() const {
+ return this->base().node();
+ }
+
+public:
+ CompositionIterator(Node<T> *node, traversal_state state = Enter)
+ : BaseClass(ChildIterator<T>(node, node ? node->parent : nullptr)),
+ m_state(state)
+ {
+ }
+
+ traversal_state state() const {
+ return m_state;
+ }
+
+
+private:
+ friend class boost::iterator_core_access;
+
+ bool tryJumpToPos(typename CompositionIterator::base_type it,
+ TraversalState newState) {
+ bool result = false;
+
+ if (!isEnd(it)) {
+ this->base_reference() = it;
+ result = true;
+ m_state = newState;
+ }
+
+ return result;
+ }
+
+ void increment() {
+ switch (m_state) {
+ case Enter:
+ if (tryJumpToPos(childBegin(this->base()), Enter)) return;
+ if (tryJumpToPos(this->base(), Leave)) return;
+ break;
+ case Leave:
+ if (tryJumpToPos(std::next(this->base()), Enter)) return;
+ if (tryJumpToPos(parent(this->base()), Leave)) return;
+ break;
+ }
+
+ this->base_reference() = ChildIterator<T>(nullptr, nullptr);
+ }
+
+private:
+ traversal_state m_state = Enter;
+};
+
+template <typename Iterator>
+CompositionIterator<typename Iterator::value_type> compositionBegin(Iterator it)
+{
+ using CompositionIterator = CompositionIterator<typename Iterator::value_type>;
+ return CompositionIterator(it.node(), Enter);
+}
+
+template <typename Iterator>
+CompositionIterator<typename Iterator::value_type> compositionEnd(Iterator it)
+{
+ using CompositionIterator = CompositionIterator<typename Iterator::value_type>;
+ return it.node() ?
+ std::next(CompositionIterator(it.node(), Leave)) :
+ CompositionIterator(nullptr, Leave);
+}
+
+
+/*************************************************************************/
+/* DepthFirstIterator */
+/*************************************************************************/
+
+/**
+ * Depth-first iterator is used to traverse entire child-subtree of the node
+ * recursively in depth-first order. Every node is entered only once. It
+ * implements standard recursion iteration:
+ *
+ * * \c DepthFirstIterator<T, Enter> implements head-recursion, that is,
+ * the node is visited *before* its children
+ *
+ * * \c DepthFirstIterator<T, Leave> implements tail-recursion, that is,
+ * the node is visited *after* its children
+ *
+ * Use \c subtreeBegin() and \c subtreeEnd() for head-recursion and \c tailSubtreeBegin() and
+ * \c tailSubtreeEnd() for tail-recursion.
+ *
+ * Iterator models \c ForwardIterator concept.
+ *
+ * \code{.cpp}
+ *
+ * // Forest:
+ * //
+ * // 0 1
+ * // 2
+ * // 3 5 6
+ * // 7
+ * // 4
+ * // 8 9
+ * // 10
+ *
+ * KisForest<int>::iterator it3 = findValue(forest, 3);
+ *
+ * // iterate through all the children of '3' in head-recursive way
+ * for (auto it = subtreeBegin(it3); it != subtreeEnd(it3); ++it) {
+ * qDebug() << *it << it.state();
+ * }
+ * // prints: 3, 5, 6, 7
+ *
+ * // iterate through all the children of '3' in tail-recursive way
+ * for (auto it = tailSubtreeBegin(it3); it != tailSubtreeEnd(it3); ++it) {
+ * qDebug() << *it << it.state();
+ * }
+ * // prints: 6, 7, 5, 3
+ *
+ * \endcode
+ *
+ * WARNING: converting end() iterator to other iterator types currently leads
+ * to undefined behavior.
+ */
+
+template <typename T, TraversalState visit_on>
+class DepthFirstIterator :
+ public boost::iterator_adaptor<
+ DepthFirstIterator<T, visit_on>,
+ CompositionIterator<T>,
+ boost::use_default,
+ boost::forward_traversal_tag>
+{
+ using BaseClass = boost::iterator_adaptor<
+ DepthFirstIterator<T, visit_on>,
+ CompositionIterator<T>,
+ boost::use_default,
+ boost::forward_traversal_tag>;
+
+public:
+ using traversal_state = TraversalState;
+
+ DepthFirstIterator(Node<T> *node,
+ traversal_state state = traversal_state::Enter,
+ bool shouldSkipToBegin = false)
+ : BaseClass(CompositionIterator<T>(node, state))
+ {
+ if (shouldSkipToBegin) {
+ skipToState(visit_on);
+ }
+ }
+
+ Node<T>* node() const {
+ return this->base().node();
+ }
+
+private:
+ friend class boost::iterator_core_access;
+
+ void increment() {
+ this->base_reference()++;
+ skipToState(visit_on);
+ }
+
+ void skipToState(TraversalState state) {
+ while (this->base().node() && this->base().state() != state) {
+ this->base_reference()++;
+ }
+ }
+
+};
+
+template <typename Iterator,
+ typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Enter>>
+ResultIterator subtreeBegin(Iterator it)
+{
+ return ResultIterator(it.node(), Enter);
+}
+
+template <typename Iterator,
+ typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Enter>>
+ResultIterator subtreeEnd(Iterator it)
+{
+ return it.node() ?
+ std::next(ResultIterator(it.node(), Leave)) :
+ ResultIterator(nullptr, Leave);
+}
+
+template <typename Iterator,
+ typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Leave>>
+ResultIterator tailSubtreeBegin(Iterator it)
+{
+ return ResultIterator(it.node(), Enter, true);
+}
+
+template <typename Iterator,
+ typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Leave>>
+ResultIterator tailSubtreeEnd(Iterator it)
+{
+ return it.node() ?
+ std::next(ResultIterator(it.node(), Leave)) :
+ ResultIterator(nullptr, Leave);
+}
+
+
+/*************************************************************************/
+/* Forest */
+/*************************************************************************/
+
+/**
+ * Forest implements a container for composing tree-like structures from
+ * arbitrary objects.
+ *
+ * All add/remove operations are implemented via child_iterator. You can
+ * convert any iterator type into a child iterator via \c siblingCurrent()
+ * function.
+ *
+ * * \code{.cpp}
+ *
+ * // Forest:
+ * //
+ * // 0 1
+ * // 2
+ * // 3 5 6
+ * // 7
+ * // 4
+ * // 8 9
+ * // 10
+ *
+ * KisForest<int> forest;
+ *
+ * auto it0 = forest.insert(childBegin(forest), 0);
+ * auto it8 = forest.insert(childEnd(forest), 8);
+ *
+ * auto it1 = forest.insert(childEnd(it0), 1);
+ * auto it2 = forest.insert(childEnd(it0), 2);
+ * auto it3 = forest.insert(childEnd(it0), 3);
+ * auto it4 = forest.insert(childEnd(it0), 4);
+ *
+ * auto it5 = forest.insert(childEnd(it3), 5);
+ *
+ * auto it6 = forest.insert(childEnd(it5), 6);
+ * auto it7 = forest.insert(childEnd(it5), 7);
+ *
+ * auto it9 = forest.insert(childEnd(it8), 9);
+ * auto it10 = forest.insert(childEnd(it8), 10);
+ *
+ * // iterate through all elements of the forest
+ * for (auto it = subtreeBegin(forest); it != subtreeEnd(forest); ++it) {
+ * qDebug() << *it << it.state();
+ * }
+ * // prints: 0,1,2,3,5,6,7,4,8,9,10
+ *
+ * \endcode
+ *
+ *
+ */
+
+template <typename T>
+class Forest
+{
+public:
+ Forest()
+ {
+ }
+
+ using child_iterator = ChildIterator<T>;
+ using composition_iterator = CompositionIterator<T>;
+ using hierarchy_iterator = HierarchyIterator<T>;
+ using iterator = DepthFirstIterator<T, Enter>;
+ using depth_first_tail_iterator = DepthFirstIterator<T, Leave>;
+
+ iterator begin() {
+ return iterator(m_root.firstChild);
+ }
+
+ iterator end() {
+ return iterator(nullptr);
+ }
+
+ depth_first_tail_iterator depthFirstTailBegin() {
+ return tailSubtreeBegin(begin());
+ }
+
+ depth_first_tail_iterator depthFirstTailEnd() {
+ return tailSubtreeEnd(end());
+ }
+
+ child_iterator childBegin() {
+ return child_iterator(m_root.firstChild, &m_root);
+ }
+
+ child_iterator childEnd() {
+ return child_iterator(nullptr, &m_root);
+ }
+
+ composition_iterator compositionBegin() {
+ return composition_iterator(m_root.firstChild);
+ }
+
+ composition_iterator compositionEnd() {
+ return composition_iterator(nullptr);
+ }
+
+ /**
+ * @brief Inserts element \p value into position \p pos.
+ * \p value becomes the child of the same parent as \p pos
+ * and is placed right before \p pos.
+ * @return iterator pointing to the inserted element
+ */
+ child_iterator insert(child_iterator pos, T &&value) {
+ Node<T> *node = new Node<T>(std::forward<T>(value));
+
+ linkNode(pos, node);
+
+ return child_iterator(node, node->parent);
+ }
+
+ /**
+ * @brief Removes element at position \p pos.
+ * If \p pos is 'end', then result is undefined.
+ * @return the element following \p pos
+ */
+ child_iterator erase(child_iterator pos) {
+ child_iterator nextNode = std::next(pos);
+ Node<T> *node = pos.node();
+
+ Node<T> *lastNode = node;
+ for (auto it = tailSubtreeBegin(pos); it != tailSubtreeEnd(pos); ++it) {
+
+ if (lastNode != node) {
+ delete lastNode;
+ }
+ lastNode = it.node();
+ }
+
+ KIS_SAFE_ASSERT_RECOVER_RETURN_VALUE(lastNode == node, pos);
+
+ unlinkNode(node);
+ delete node;
+
+ return nextNode;
+ }
+
+ /**
+ * @brief erases all elements from \p pos to \p end (excluding \p end)
+ * @return \p end
+ */
+ child_iterator erase(child_iterator pos, child_iterator end) {
+ while (pos != end) {
+ pos = erase(pos);
+ }
+ return pos;
+ }
+
+ /**
+ * @brief move a subtree to new position
+ * Moves \p subtree into a new position pointer by \p newPos. \p newPos
+ * must not be inside the subtree, otherwise cycling links may appear.
+ * @return iterator to a new position of \p subtree
+ */
+ child_iterator move(child_iterator subtree, child_iterator newPos) {
+ // sanity check for cycling move
+ for (auto it = hierarchyBegin(newPos); it != hierarchyEnd(newPos); ++it) {
+ KIS_SAFE_ASSERT_RECOVER_RETURN_VALUE(it.node() != subtree.node(), subtree);
+ }
+
+ Node<T> *node = subtree.node();
+ unlinkNode(node);
+
+ node->prevSibling = nullptr;
+ node->nextSibling = nullptr;
+ node->parent = nullptr;
+
+ linkNode(newPos, node);
+ return child_iterator(node, node->parent);
+ }
+
+private:
+
+ inline void linkBefore(Node<T> *node, Node<T> *beforeMe) {
+ if (beforeMe) {
+ node->nextSibling = beforeMe;
+ beforeMe->prevSibling = node;
+ }
+ }
+
+ inline void linkAfter(Node<T> *node, Node<T> *afterMe) {
+ if (afterMe) {
+ node->prevSibling = afterMe;
+ afterMe->nextSibling = node;
+ }
+ }
+
+ inline void linkNode(child_iterator pos, Node<T> *node) {
+ Node<T> *nextNode = pos.node();
+ RootNode<T> *parentNode = pos.m_parent;
+
+ Node<T> *prevNode = nextNode ?
+ nextNode->prevSibling :
+ parentNode ? parentNode->lastChild : m_root.lastChild;
+
+ linkAfter(node, prevNode);
+ linkBefore(node, nextNode);
+
+ KIS_SAFE_ASSERT_RECOVER_RETURN(parentNode);
+ if (!nextNode) {
+ parentNode->lastChild = node;
+ }
+
+ if (nextNode == parentNode->firstChild) {
+ parentNode->firstChild = node;
+ }
+ node->parent = parentNode;
+ }
+
+ inline void unlinkNode(Node<T> *node) {
+ RootNode<T> *parentNode = node->parent;
+
+ if (node->nextSibling) {
+ node->nextSibling->prevSibling = node->prevSibling;
+ }
+
+ if (node->prevSibling) {
+ node->prevSibling->nextSibling = node->nextSibling;
+ }
+
+ KIS_SAFE_ASSERT_RECOVER_RETURN(parentNode);
+ if (parentNode->firstChild == node) {
+ parentNode->firstChild = node->nextSibling;
+ }
+
+ if (parentNode->lastChild == node) {
+ parentNode->lastChild = node->prevSibling;
+ }
+ }
+private:
+ RootNode<T> m_root;
+};
+
+template <typename T>
+typename Forest<T>::child_iterator childBegin(Forest<T> &forest)
+{
+ return forest.childBegin();
+}
+
+template <typename T>
+typename Forest<T>::child_iterator childEnd(Forest<T> &forest)
+{
+ return forest.childEnd();
+}
+
+template <typename T>
+typename Forest<T>::composition_iterator compositionBegin(Forest<T> &forest)
+{
+ return forest.compositionBegin();
+}
+
+template <typename T>
+typename Forest<T>::composition_iterator compositionEnd(Forest<T> &forest)
+{
+ return forest.compositionEnd();
+}
+
+template <typename T>
+typename Forest<T>::depth_first_tail_iterator tailSubtreeBegin(Forest<T> &forest)
+{
+ return forest.depthFirstTailBegin();
+}
+
+template <typename T>
+typename Forest<T>::depth_first_tail_iterator tailSubtreeEnd(Forest<T> &forest)
+{
+ return forest.depthFirstTailEnd();
+}
+
+
+using std::begin;
+using std::end;
+using std::make_reverse_iterator;
+}
+
+template<typename T>
+using KisForest = KisForestDetail::Forest<T>;
+
+
+#endif // KISFOREST_H
diff --git a/libs/global/tests/CMakeLists.txt b/libs/global/tests/CMakeLists.txt
index 48093cba83..f8c7126e44 100644
--- a/libs/global/tests/CMakeLists.txt
+++ b/libs/global/tests/CMakeLists.txt
@@ -6,5 +6,6 @@ macro_add_unittest_definitions()
ecm_add_tests(KisSharedThreadPoolAdapterTest.cpp
KisSignalAutoConnectionTest.cpp
KisSignalCompressorTest.cpp
+ KisForestTest.cpp
NAME_PREFIX libs-global-
LINK_LIBRARIES kritaglobal Qt5::Test)
diff --git a/libs/global/tests/KisForestTest.cpp b/libs/global/tests/KisForestTest.cpp
new file mode 100644
index 0000000000..330d82c370
--- /dev/null
+++ b/libs/global/tests/KisForestTest.cpp
@@ -0,0 +1,884 @@
+/*
+ * Copyright (c) 2019 Dmitry Kazakov <dimula73 at gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+#include "KisForestTest.h"
+
+#include "KisCppQuirks.h"
+#include "KisForest.h"
+#include <vector>
+
+struct IteratorToValue
+{
+ using value_type = int;
+
+ template <typename Iterator>
+ value_type operator() (Iterator it) const {
+ return *it;
+ }
+};
+
+template <typename Iterator, typename IteratorValuePolicy = IteratorToValue>
+bool testForestIteration(Iterator begin, Iterator end,
+ std::vector<typename IteratorValuePolicy::value_type> reference,
+ IteratorValuePolicy iteratorToValue = IteratorValuePolicy())
+{
+ using value_type = typename IteratorValuePolicy::value_type;
+
+ bool result = true;
+ std::vector<value_type> values;
+
+ std::size_t index = 0;
+ for (auto it = begin; it != end; ++it, ++index) {
+ value_type value = iteratorToValue(it);
+
+ if (index >= reference.size() || value != reference[index]) {
+ result = false;
+ }
+ values.push_back(value);
+
+ // emergency exit in case of infinite loop :)
+ // "40 forest items must be enough for everyone!" (c)
+ if (index > 40) {
+ result = false;
+ break;
+ }
+ }
+
+ result &= values.size() == reference.size();
+
+ if (!result) {
+ qDebug() << "Failed forest iteration:";
+ {
+ QDebug deb = qDebug();
+ deb << " result:";
+ Q_FOREACH(value_type value, values) {
+ deb << value;
+ }
+ }
+ {
+ QDebug deb = qDebug();
+ deb << " ref. :";
+ Q_FOREACH(value_type value, reference) {
+ deb << value;
+ }
+ }
+ }
+
+ return result;
+}
+
+void KisForestTest::testAddToRoot()
+{
+ KisForest<int> forest;
+
+ forest.insert(childBegin(forest), 2);
+ forest.insert(childBegin(forest), 1);
+ forest.insert(childBegin(forest), 0);
+ forest.insert(childEnd(forest), 3);
+
+ QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0,1,2,3}));
+
+}
+
+void KisForestTest::testAddToRootChained()
+{
+ KisForest<int> forest;
+
+ auto it = forest.insert(childBegin(forest), 3);
+ it = forest.insert(it, 2);
+ it = forest.insert(it, 1);
+ it = forest.insert(it, 0);
+
+ QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0,1,2,3}));
+}
+
+void KisForestTest::testAddToLeaf()
+{
+ KisForest<int> forest;
+
+ auto root = forest.insert(childBegin(forest), 0);
+ forest.insert(childBegin(root), 2);
+ forest.insert(childBegin(root), 1);
+ forest.insert(childEnd(root), 3);
+ forest.insert(childEnd(root), 4);
+
+ QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0}));
+ QVERIFY(testForestIteration(childBegin(root), childEnd(root), {1,2,3,4}));
+
+}
+
+void KisForestTest::testAddToLeafChained()
+{
+ KisForest<int> forest;
+
+ auto root = forest.insert(childBegin(forest), 0);
+ auto it = forest.insert(childBegin(root), 4);
+ it = forest.insert(it, 3);
+ it = forest.insert(it, 2);
+ it = forest.insert(it, 1);
+
+ QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0}));
+ QVERIFY(testForestIteration(childBegin(root), childEnd(root), {1,2,3,4}));
+
+}
+
+void KisForestTest::testDFSIteration()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ **/
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+ QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0, 8}));
+ QVERIFY(testForestIteration(childBegin(it0), childEnd(it0), {1,2,3,4}));
+ QVERIFY(testForestIteration(childBegin(it8), childEnd(it8), {9,10}));
+ QVERIFY(testForestIteration(childBegin(it3), childEnd(it3), {5}));
+ QVERIFY(testForestIteration(childBegin(it5), childEnd(it5), {6,7}));
+
+ QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,6,7,4,8,9,10}));
+}
+
+void KisForestTest::testHierarchyIteration()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ **/
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+ QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0, 8}));
+ QVERIFY(testForestIteration(childBegin(it0), childEnd(it0), {1,2,3,4}));
+ QVERIFY(testForestIteration(childBegin(it8), childEnd(it8), {9,10}));
+ QVERIFY(testForestIteration(childBegin(it3), childEnd(it3), {5}));
+ QVERIFY(testForestIteration(childBegin(it5), childEnd(it5), {6,7}));
+
+ QVERIFY(testForestIteration(hierarchyBegin(it0), hierarchyEnd(it0), {0}));
+ QVERIFY(testForestIteration(hierarchyBegin(forest.end()), hierarchyEnd(forest.end()), {}));
+
+ QVERIFY(testForestIteration(hierarchyBegin(it7), hierarchyEnd(it7), {7,5,3,0}));
+ QVERIFY(testForestIteration(hierarchyBegin(it5), hierarchyEnd(it5), {5,3,0}));
+ QVERIFY(testForestIteration(hierarchyBegin(it4), hierarchyEnd(it4), {4,0}));
+ QVERIFY(testForestIteration(hierarchyBegin(it10), hierarchyEnd(it10), {10,8}));
+}
+
+void KisForestTest::testSiblingIteration()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ **/
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+ /**
+ * Test if all types of iterators are convertible into a child iterator
+ */
+ QVERIFY(testForestIteration(siblingCurrent(it2), siblingEnd(it2), {2,3,4}));
+ QVERIFY(testForestIteration(siblingCurrent(hierarchyBegin(it2)), siblingEnd(hierarchyBegin(it2)), {2,3,4}));
+ QVERIFY(testForestIteration(siblingCurrent(subtreeBegin(it2)), siblingEnd(subtreeBegin(it2)), {2,3,4}));
+ QVERIFY(testForestIteration(siblingCurrent(tailSubtreeBegin(it2)), siblingEnd(tailSubtreeBegin(it2)), {2,3,4}));
+ QVERIFY(testForestIteration(siblingCurrent(compositionBegin(it2)), siblingEnd(compositionBegin(it2)), {2,3,4}));
+
+ QVERIFY(testForestIteration(siblingCurrent(compositionBegin(childEnd(it0))),
+ siblingEnd(compositionBegin(childEnd(it0))), {}));
+}
+
+void KisForestTest::testCompositionIteration()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ **/
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+ QVERIFY(testForestIteration(compositionBegin(forest), compositionEnd(forest), {0, 1, 1, 2, 2, 3, 5, 6, 6, 7, 7, 5, 3, 4, 4, 0, 8, 9, 9, 10, 10, 8}));
+
+}
+
+struct CompositonIteratorPairedValue
+{
+ using value_type = std::pair<int, KisForest<int>::composition_iterator::traversal_state>;
+
+ template <typename Iterator>
+ value_type operator() (Iterator it) const {
+ return std::make_pair(*it, it.state());
+ }
+};
+
+void KisForestTest::testCompositionIterationSubtree()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ **/
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+ QVERIFY(testForestIteration(compositionBegin(it3), compositionEnd(it3), {3, 5, 6, 6, 7, 7, 5, 3}));
+ QVERIFY(testForestIteration(compositionBegin(it5), compositionEnd(it5), {5, 6, 6, 7, 7, 5}));
+ QVERIFY(testForestIteration(compositionBegin(it8), compositionEnd(it8), {8, 9, 9, 10, 10, 8}));
+
+ using traversal_direction = KisForest<int>::composition_iterator::traversal_state;
+
+ std::vector<std::pair<int, traversal_direction>> references;
+
+ references = {{5, traversal_direction::Enter},
+ {6, traversal_direction::Enter},
+ {6, traversal_direction::Leave},
+ {7, traversal_direction::Enter},
+ {7, traversal_direction::Leave},
+ {5, traversal_direction::Leave}};
+
+ QVERIFY(testForestIteration(compositionBegin(it5), compositionEnd(it5),
+ references, CompositonIteratorPairedValue()));
+
+ references = {{3, traversal_direction::Enter},
+ {5, traversal_direction::Enter},
+ {6, traversal_direction::Enter},
+ {6, traversal_direction::Leave},
+ {7, traversal_direction::Enter},
+ {7, traversal_direction::Leave},
+ {5, traversal_direction::Leave},
+ {3, traversal_direction::Leave}};
+
+ QVERIFY(testForestIteration(compositionBegin(it3), compositionEnd(it3),
+ references, CompositonIteratorPairedValue()));
+
+}
+
+void KisForestTest::testSubtreeIteration()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ **/
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+
+ QVERIFY(testForestIteration(subtreeBegin(it3), subtreeEnd(it3), {3,5,6,7}));
+ QVERIFY(testForestIteration(subtreeBegin(it0), subtreeEnd(it0), {0,1,2,3,5,6,7,4}));
+ QVERIFY(testForestIteration(subtreeBegin(it8), subtreeEnd(it8), {8,9,10}));
+}
+
+void KisForestTest::testSubtreeTailIteration()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ **/
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+
+ QVERIFY(testForestIteration(tailSubtreeBegin(it3), tailSubtreeEnd(it3), {6,7,5,3}));
+ QVERIFY(testForestIteration(tailSubtreeBegin(it0), tailSubtreeEnd(it0), {1,2,6,7,5,3,4,0}));
+ QVERIFY(testForestIteration(tailSubtreeBegin(it8), tailSubtreeEnd(it8), {9,10,8}));
+
+ QVERIFY(testForestIteration(tailSubtreeBegin(forest), tailSubtreeEnd(forest), {1,2,6,7,5,3,4,0,9,10,8}));
+}
+
+void KisForestTest::testEraseNode()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ **/
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+
+ QCOMPARE(forest.erase(it6), it7);
+ QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,7,4,8,9,10}));
+
+ QCOMPARE(forest.erase(it7), childEnd(it5));
+ QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4,8,9,10}));
+
+ QCOMPARE(forest.erase(it10), childEnd(it8));
+ QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4,8,9}));
+
+ QCOMPARE(forest.erase(it9), childEnd(it8));
+ QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4,8}));
+
+ QCOMPARE(forest.erase(it8), childEnd(forest));
+ QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4}));
+}
+
+void KisForestTest::testEraseSubtree()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ **/
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+
+ QCOMPARE(forest.erase(it3), it4);
+ QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,4,8,9,10}));
+
+ QCOMPARE(forest.erase(it8), childEnd(forest));
+ QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,4}));
+
+ QCOMPARE(forest.erase(it0), childEnd(forest));
+ QVERIFY(testForestIteration(begin(forest), end(forest), {}));
+}
+
+void KisForestTest::testEraseRange()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ */
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+
+ QCOMPARE(forest.erase(it1, it4), it4);
+ QVERIFY(testForestIteration(begin(forest), end(forest), {0,4,8,9,10}));
+
+ QCOMPARE(forest.erase(it4, childEnd(it0)), childEnd(it0));
+ QVERIFY(testForestIteration(begin(forest), end(forest), {0,8,9,10}));
+}
+
+void KisForestTest::testMoveSubtree()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ */
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+
+ auto newPos = forest.move(it3, it9);
+ QCOMPARE(newPos, childBegin(it8));
+
+ QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,4,8,3,5,6,7,9,10}));
+
+ newPos = forest.move(it0, childEnd(it8));
+ QCOMPARE(newPos, std::prev(childEnd(it8)));
+
+ QVERIFY(testForestIteration(begin(forest), end(forest), {8,3,5,6,7,9,10,0,1,2,4}));
+}
+
+void KisForestTest::testReversedChildIteration()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ **/
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+ QVERIFY(testForestIteration(make_reverse_iterator(childEnd(forest)),
+ make_reverse_iterator(childBegin(forest)), {8, 0}));
+
+ QVERIFY(testForestIteration(make_reverse_iterator(childEnd(it0)),
+ make_reverse_iterator(childBegin(it0)), {4,3,2,1}));
+
+ QVERIFY(testForestIteration(make_reverse_iterator(childEnd(it3)),
+ make_reverse_iterator(childBegin(it3)), {5}));
+}
+
+void KisForestTest::testConversionsFromEnd()
+{
+ KisForest<int> forest;
+
+ /**
+ * 0 1
+ * 2
+ * 3 5 6
+ * 7
+ * 4
+ * 8 9
+ * 10
+ **/
+
+
+ auto it0 = forest.insert(childBegin(forest), 0);
+ auto it8 = forest.insert(childEnd(forest), 8);
+
+ auto it1 = forest.insert(childEnd(it0), 1);
+ auto it2 = forest.insert(childEnd(it0), 2);
+ auto it3 = forest.insert(childEnd(it0), 3);
+ auto it4 = forest.insert(childEnd(it0), 4);
+
+ auto it5 = forest.insert(childEnd(it3), 5);
+
+ auto it6 = forest.insert(childEnd(it5), 6);
+ auto it7 = forest.insert(childEnd(it5), 7);
+
+ auto it9 = forest.insert(childEnd(it8), 9);
+ auto it10 = forest.insert(childEnd(it8), 10);
+
+ Q_UNUSED(it1);
+ Q_UNUSED(it2);
+ Q_UNUSED(it6);
+ Q_UNUSED(it7);
+ Q_UNUSED(it4);
+ Q_UNUSED(it9);
+ Q_UNUSED(it10);
+
+ /**
+ * Currently, all operations on end-iterators are declared as "undefined behavior",
+ * but, ideally, we should care about them. Like, it should be possible to get children
+ * of the forest by calling childBegin/End(hierarchyEnd(it0)). I (DK) am not sure if
+ * it is possible to implement without overhead. So I just added this test to document
+ * "desired" behavior. But for now, noone should rely on this behavior, just consider
+ * all operations with end-iterators as UB.
+ */
+
+#define HIDE_UB_NOISE
+
+ QVERIFY(testForestIteration(childBegin(childEnd(it0)),
+ childEnd(childEnd(it0)), {}));
+
+#ifndef HIDE_UB_NOISE
+ QEXPECT_FAIL("", "Fetching children of root node should return roots of the forest?", Continue);
+ QVERIFY(testForestIteration(childBegin(hierarchyEnd(it0)),
+ childEnd(hierarchyEnd(it0)), {0, 8}));
+ QEXPECT_FAIL("", "End of composition should not (?) point to any existing node", Continue);
+ QVERIFY(testForestIteration(childBegin(compositionEnd(it0)),
+ childEnd(compositionEnd(it0)), {}));
+#endif
+
+ QVERIFY(testForestIteration(hierarchyBegin(childEnd(it0)),
+ hierarchyEnd(childEnd(it0)), {}));
+ QVERIFY(testForestIteration(hierarchyBegin(hierarchyEnd(it0)),
+ hierarchyEnd(hierarchyEnd(it0)), {}));
+#ifndef HIDE_UB_NOISE
+ QEXPECT_FAIL("", "End of composition should not (?) point to any existing node", Continue);
+ QVERIFY(testForestIteration(hierarchyBegin(compositionEnd(it0)),
+ hierarchyEnd(compositionEnd(it0)), {}));
+#endif
+
+ QVERIFY(testForestIteration(compositionBegin(childEnd(it0)),
+ compositionEnd(childEnd(it0)), {}));
+#ifndef HIDE_UB_NOISE
+ QEXPECT_FAIL("", "Starting composition on the root node should behave like we do it for the forest itself?", Continue);
+ QVERIFY(testForestIteration(compositionBegin(hierarchyEnd(it0)),
+ compositionEnd(hierarchyEnd(it0)), {0, 1, 1, 2, 2, 3, 5, 6, 6, 7, 7, 5, 3, 4, 4, 0, 8, 9, 9, 10, 10, 8}));
+ QEXPECT_FAIL("", "End of composition should not (?) point to any existing node", Continue);
+ QVERIFY(testForestIteration(compositionBegin(compositionEnd(it0)),
+ compositionEnd(compositionEnd(it0)), {}));
+#endif
+
+#ifndef HIDE_UB_NOISE
+ QEXPECT_FAIL("", "Fetching siblings from child-end should work?", Continue);
+ QVERIFY(testForestIteration(siblingBegin(childEnd(it0)),
+ siblingEnd(childEnd(it0)), {1,2,3,4}));
+#endif
+ QVERIFY(testForestIteration(siblingBegin(hierarchyEnd(it0)),
+ siblingEnd(hierarchyEnd(it0)), {}));
+ QVERIFY(testForestIteration(siblingBegin(compositionEnd(it0)),
+ siblingEnd(compositionEnd(it0)), {0,8}));
+
+
+
+ QVERIFY(testForestIteration(childBegin(childEnd(forest)),
+ childEnd(childEnd(forest)), {}));
+ QVERIFY(testForestIteration(childBegin(compositionEnd(forest)),
+ childEnd(compositionEnd(forest)), {}));
+
+ QVERIFY(testForestIteration(hierarchyBegin(childEnd(forest)),
+ hierarchyEnd(childEnd(forest)), {}));
+ QVERIFY(testForestIteration(hierarchyBegin(compositionEnd(forest)),
+ hierarchyEnd(compositionEnd(forest)), {}));
+
+ QVERIFY(testForestIteration(compositionBegin(childEnd(forest)),
+ compositionEnd(childEnd(forest)), {}));
+ QVERIFY(testForestIteration(compositionBegin(compositionEnd(forest)),
+ compositionEnd(compositionEnd(forest)), {}));
+
+#ifndef HIDE_UB_NOISE
+ QEXPECT_FAIL("", "Fetching siblings from forest's child-end should work?", Continue);
+ QVERIFY(testForestIteration(siblingBegin(childEnd(forest)),
+ siblingEnd(childEnd(forest)), {0,8}));
+ QEXPECT_FAIL("", "Fetching siblings from forest's composition-end should work?", Continue);
+ QVERIFY(testForestIteration(siblingBegin(compositionEnd(forest)),
+ siblingEnd(compositionEnd(forest)), {0,8}));
+#endif
+
+#undef HIDE_UB_NOISE
+}
+
+QTEST_MAIN(KisForestTest)
diff --git a/libs/global/tests/KisForestTest.h b/libs/global/tests/KisForestTest.h
new file mode 100644
index 0000000000..97a8765360
--- /dev/null
+++ b/libs/global/tests/KisForestTest.h
@@ -0,0 +1,55 @@
+/*
+ * Copyright (c) 2019 Dmitry Kazakov <dimula73 at gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+#ifndef KISFORESTTEST_H
+#define KISFORESTTEST_H
+
+
+#include <QtTest>
+#include <QObject>
+
+class KisForestTest : public QObject
+{
+ Q_OBJECT
+
+private Q_SLOTS:
+ void testAddToRoot();
+ void testAddToRootChained();
+ void testAddToLeaf();
+ void testAddToLeafChained();
+
+ void testDFSIteration();
+ void testHierarchyIteration();
+ void testSiblingIteration();
+ void testCompositionIteration();
+ void testCompositionIterationSubtree();
+
+ void testSubtreeIteration();
+ void testSubtreeTailIteration();
+
+ void testEraseNode();
+ void testEraseSubtree();
+ void testEraseRange();
+
+ void testMoveSubtree();
+
+ void testReversedChildIteration();
+
+ void testConversionsFromEnd();
+};
+
+#endif // KISFORESTTEST_H
More information about the kimageshop
mailing list