Classes
class	BaseIterator

struct	BaseNode

class	ChildIterator

class	CompositionIterator

class	DepthFirstIterator

class	Forest

class	HierarchyIterator

struct	Node

struct	RootNodeImpl

Typedefs
template<typename T >
using	RootNode = RootNodeImpl<Node<T>>

Enumerations
enum	TraversalState { Enter , Leave }

Functions
template<typename value_type , bool is_const>
ChildIterator< value_type, is_const >	childBegin (const ChildIterator< value_type, is_const > &it)

template<typename T >
Forest< T >::const_child_iterator	childBegin (const Forest< T > &forest)

template<typename T >
Forest< T >::child_iterator	childBegin (Forest< T > &forest)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = ChildIterator<typename Iterator::value_type, is_const>>
ResultIterator	childBegin (Iterator it)

template<typename value_type , bool is_const>
ChildIterator< value_type, is_const >	childEnd (const ChildIterator< value_type, is_const > &it)

template<typename T >
Forest< T >::const_child_iterator	childEnd (const Forest< T > &forest)

template<typename T >
Forest< T >::child_iterator	childEnd (Forest< T > &forest)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = ChildIterator<typename Iterator::value_type, is_const>>
ResultIterator	childEnd (Iterator it)

template<typename T >
Forest< T >::const_composition_iterator	compositionBegin (const Forest< T > &forest)

template<typename T >
Forest< T >::composition_iterator	compositionBegin (Forest< T > &forest)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = CompositionIterator<typename Iterator::value_type, is_const>>
ResultIterator	compositionBegin (Iterator it)

template<typename T >
Forest< T >::const_composition_iterator	compositionEnd (const Forest< T > &forest)

template<typename T >
Forest< T >::composition_iterator	compositionEnd (Forest< T > &forest)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = CompositionIterator<typename Iterator::value_type, is_const>>
ResultIterator	compositionEnd (Iterator it)

template<typename T >
int	depth (const Forest< T > &forest)

template<typename T >
int	depth (typename Forest< T >::const_child_iterator beginIt, typename Forest< T >::const_child_iterator endIt)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = HierarchyIterator<typename Iterator::value_type, is_const>>
ResultIterator	hierarchyBegin (Iterator it)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = HierarchyIterator<typename Iterator::value_type, is_const>>
ResultIterator	hierarchyEnd (Iterator it)

template<typename T , bool is_const>
bool	isEnd (const ChildIterator< T, is_const > &it)

template<typename value_type , bool is_const>
QDebug	operator<< (QDebug dbg, const ChildIterator< value_type, is_const > &it)

template<typename value_type , bool is_const>
ChildIterator< value_type, is_const >	parent (const ChildIterator< value_type, is_const > &it)

template<typename value_type , bool is_const>
ChildIterator< value_type, is_const >	siblingBegin (const ChildIterator< value_type, is_const > &it)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = ChildIterator<typename Iterator::value_type, is_const>>
ResultIterator	siblingBegin (Iterator it)

template<typename value_type , bool is_const>
ChildIterator< value_type, is_const >	siblingCurrent (ChildIterator< value_type, is_const > it)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = ChildIterator<typename Iterator::value_type, is_const>>
ResultIterator	siblingCurrent (Iterator it)

template<typename value_type , bool is_const>
ChildIterator< value_type, is_const >	siblingEnd (const ChildIterator< value_type, is_const > &it)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = ChildIterator<typename Iterator::value_type, is_const>>
ResultIterator	siblingEnd (Iterator it)

template<typename T >
int	size (const Forest< T > &forest)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Enter, is_const>>
ResultIterator	subtreeBegin (Iterator it)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Enter, is_const>>
ResultIterator	subtreeEnd (Iterator it)

template<typename T >
Forest< T >::const_depth_first_tail_iterator	tailSubtreeBegin (const Forest< T > &forest)

template<typename T >
Forest< T >::depth_first_tail_iterator	tailSubtreeBegin (Forest< T > &forest)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Leave, is_const>>
ResultIterator	tailSubtreeBegin (Iterator it)

template<typename T >
Forest< T >::const_depth_first_tail_iterator	tailSubtreeEnd (const Forest< T > &forest)

template<typename T >
Forest< T >::depth_first_tail_iterator	tailSubtreeEnd (Forest< T > &forest)

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Leave, is_const>>
ResultIterator	tailSubtreeEnd (Iterator it)

Typedef Documentation

◆ RootNode

template<typename T >

using KisForestDetail::RootNode = RootNodeImpl<Node<T>>

Definition at line 54 of file KisForest.h.

Enumeration Type Documentation

◆ TraversalState

enum KisForestDetail::TraversalState

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 it.state() call.

Iterator models ForwardIterator concept.

// 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)

WARNING: converting end() iterator to other iterator types currently leads to undefined behavior.

Enumerator
Enter
Leave

Definition at line 479 of file KisForest.h.

                    {
    Enter,
    Leave
};

Function Documentation

◆ childBegin() [1/4]

template<typename value_type , bool is_const>

ChildIterator< value_type, is_const > KisForestDetail::childBegin ( const ChildIterator< value_type, is_const > & it )

Definition at line 290 of file KisForest.h.

{
    if (it.node()) {
        return ChildIterator<value_type, is_const>(it.node()->firstChild, it.node(), 0);
    } else {
        return ChildIterator<value_type, is_const>(nullptr, it.m_parent, it.m_offsetToParent + 1);
    }
}

References KisForestDetail::ChildIterator< T, is_const >::m_offsetToParent, KisForestDetail::ChildIterator< T, is_const >::m_parent, and KisForestDetail::BaseIterator< BaseClass, T, Tag, is_const >::node().

◆ childBegin() [2/4]

template<typename T >

Forest< T >::const_child_iterator KisForestDetail::childBegin ( const Forest< T > & forest )

Definition at line 1144 of file KisForest.h.

{
    return forest.childBegin();
}

References KisForestDetail::Forest< T >::childBegin().

◆ childBegin() [3/4]

template<typename T >

Forest< T >::child_iterator KisForestDetail::childBegin ( Forest< T > & forest )

Definition at line 1138 of file KisForest.h.

{
    return forest.childBegin();
}

References KisForestDetail::Forest< T >::childBegin().

◆ childBegin() [4/4]

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = ChildIterator<typename Iterator::value_type, is_const>>

ResultIterator KisForestDetail::childBegin ( Iterator it )

Definition at line 312 of file KisForest.h.

{
    return childBegin(siblingCurrent(it));
}

References childBegin(), and siblingCurrent().

◆ childEnd() [1/4]

template<typename value_type , bool is_const>

ChildIterator< value_type, is_const > KisForestDetail::childEnd ( const ChildIterator< value_type, is_const > & it )

Definition at line 300 of file KisForest.h.

{
    if (it.node()) {
        return ChildIterator<value_type, is_const>(nullptr, it.node(), 0);
    } else {
        return ChildIterator<value_type, is_const>(nullptr, it.m_parent, it.m_offsetToParent + 1);
    }
}

References KisForestDetail::ChildIterator< T, is_const >::m_offsetToParent, KisForestDetail::ChildIterator< T, is_const >::m_parent, and KisForestDetail::BaseIterator< BaseClass, T, Tag, is_const >::node().

◆ childEnd() [2/4]

template<typename T >

Forest< T >::const_child_iterator KisForestDetail::childEnd ( const Forest< T > & forest )

Definition at line 1157 of file KisForest.h.

{
    return forest.childEnd();
}

References KisForestDetail::Forest< T >::childEnd().

◆ childEnd() [3/4]

template<typename T >

Forest< T >::child_iterator KisForestDetail::childEnd ( Forest< T > & forest )

Definition at line 1151 of file KisForest.h.

{
    return forest.childEnd();
}

References KisForestDetail::Forest< T >::childEnd().

◆ childEnd() [4/4]

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = ChildIterator<typename Iterator::value_type, is_const>>

ResultIterator KisForestDetail::childEnd ( Iterator it )

Definition at line 320 of file KisForest.h.

{
    return childEnd(siblingCurrent(it));
}

References childEnd(), and siblingCurrent().

◆ compositionBegin() [1/3]

template<typename T >

Forest< T >::const_composition_iterator KisForestDetail::compositionBegin ( const Forest< T > & forest )

Definition at line 1169 of file KisForest.h.

{
    return forest.compositionBegin();
}

References KisForestDetail::Forest< T >::compositionBegin().

◆ compositionBegin() [2/3]

template<typename T >

Forest< T >::composition_iterator KisForestDetail::compositionBegin ( Forest< T > & forest )

Definition at line 1163 of file KisForest.h.

{
    return forest.compositionBegin();
}

References KisForestDetail::Forest< T >::compositionBegin().

◆ compositionBegin() [3/3]

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = CompositionIterator<typename Iterator::value_type, is_const>>

ResultIterator KisForestDetail::compositionBegin ( Iterator it )

Definition at line 562 of file KisForest.h.

{
    return ResultIterator(it.node(), Enter);
}

References Enter.

◆ compositionEnd() [1/3]

template<typename T >

Forest< T >::const_composition_iterator KisForestDetail::compositionEnd ( const Forest< T > & forest )

Definition at line 1182 of file KisForest.h.

{
    return forest.compositionEnd();
}

References KisForestDetail::Forest< T >::compositionEnd().

◆ compositionEnd() [2/3]

template<typename T >

Forest< T >::composition_iterator KisForestDetail::compositionEnd ( Forest< T > & forest )

Definition at line 1176 of file KisForest.h.

{
    return forest.compositionEnd();
}

References KisForestDetail::Forest< T >::compositionEnd().

◆ compositionEnd() [3/3]

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = CompositionIterator<typename Iterator::value_type, is_const>>

ResultIterator KisForestDetail::compositionEnd ( Iterator it )

Definition at line 570 of file KisForest.h.

{
    return it.node() ?
        std::next(ResultIterator(it.node(), Leave)) :
        ResultIterator(nullptr, Leave);
}

References Leave.

◆ depth() [1/2]

template<typename T >

int KisForestDetail::depth ( const Forest< T > & forest )

Definition at line 1227 of file KisForest.h.

                                   {
    return depth<T>(childBegin(forest), childEnd(forest));
}

References childBegin(), and childEnd().

◆ depth() [2/2]

template<typename T >

int KisForestDetail::depth	(	typename Forest< T >::const_child_iterator	beginIt,
		typename Forest< T >::const_child_iterator	endIt )

Definition at line 1213 of file KisForest.h.

{
 
    int currentDepth = 0;
 
    for (auto it = beginIt; it != endIt; ++it) {
        currentDepth = std::max(currentDepth, 1 + depth<T>(childBegin(it), childEnd(it)));
    }
 
    return currentDepth;
}

References childBegin(), and childEnd().

◆ hierarchyBegin()

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = HierarchyIterator<typename Iterator::value_type, is_const>>

ResultIterator KisForestDetail::hierarchyBegin ( Iterator it )

Definition at line 419 of file KisForest.h.

{
    return ResultIterator(it.node());
}

◆ hierarchyEnd()

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = HierarchyIterator<typename Iterator::value_type, is_const>>

ResultIterator KisForestDetail::hierarchyEnd ( Iterator it )

Definition at line 427 of file KisForest.h.

{
    Q_UNUSED(it);
    return ResultIterator(nullptr);
}

◆ isEnd()

template<typename T , bool is_const>

bool KisForestDetail::isEnd ( const ChildIterator< T, is_const > & it )

inline

Definition at line 341 of file KisForest.h.

                                                        {
    return !it.node();
}

References KisForestDetail::BaseIterator< BaseClass, T, Tag, is_const >::node().

◆ operator<<()

template<typename value_type , bool is_const>

QDebug KisForestDetail::operator<<	(	QDebug	dbg,
		const ChildIterator< value_type, is_const > &	it )

Definition at line 228 of file KisForest.h.

{
    if (it.node()) {
        dbg.nospace() << "ChildIterator(" << it.node() << "(" <<  it.node()->value << ")" << ", parent:" << it.m_parent << ")";
    } else {
        dbg.nospace() << "ChildIterator(" << "nullptr" << ", parent:" << it.m_parent << ", offset:" << it.m_offsetToParent << ")";
    }
    return dbg;
}

References KisForestDetail::ChildIterator< T, is_const >::m_offsetToParent, KisForestDetail::ChildIterator< T, is_const >::m_parent, and KisForestDetail::BaseIterator< BaseClass, T, Tag, is_const >::node().

◆ parent()

template<typename value_type , bool is_const>

ChildIterator< value_type, is_const > KisForestDetail::parent ( const ChildIterator< value_type, is_const > & it )

Definition at line 327 of file KisForest.h.

{
    if (it.m_parent->isRoot()) {
        return ChildIterator<value_type, is_const>(nullptr, it.m_parent, qMax(-1, it.m_offsetToParent - 1));
    } else if (it.m_offsetToParent == 0) {
        using NodeType = typename ChildIterator<value_type, is_const>::NodeType;
        NodeType *parentNode = static_cast<NodeType*>(it.m_parent);
        return ChildIterator<value_type, is_const>(parentNode, parentNode->parent, 0);
    } else {
        return ChildIterator<value_type, is_const>(nullptr, it.m_parent, it.m_offsetToParent - 1);
    }
}

References KisForestDetail::ChildIterator< T, is_const >::m_offsetToParent, and KisForestDetail::ChildIterator< T, is_const >::m_parent.

◆ siblingBegin() [1/2]

template<typename value_type , bool is_const>

ChildIterator< value_type, is_const > KisForestDetail::siblingBegin ( const ChildIterator< value_type, is_const > & it )

Definition at line 246 of file KisForest.h.

{
    using RootNodeType = typename ChildIterator<value_type, is_const>::RootNodeType;
    if (!it.node() && it.m_offsetToParent != 0) return it;
    RootNodeType *parent = it.m_parent;
    return ChildIterator<value_type, is_const>(parent ? parent->firstChild : nullptr, parent, 0);
}

References KisForestDetail::ChildIterator< T, is_const >::m_offsetToParent, KisForestDetail::ChildIterator< T, is_const >::m_parent, KisForestDetail::BaseIterator< BaseClass, T, Tag, is_const >::node(), and parent().

◆ siblingBegin() [2/2]

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = ChildIterator<typename Iterator::value_type, is_const>>

ResultIterator KisForestDetail::siblingBegin ( Iterator it )

Definition at line 276 of file KisForest.h.

{
    return siblingBegin(siblingCurrent(it));
}

References siblingBegin(), and siblingCurrent().

◆ siblingCurrent() [1/2]

template<typename value_type , bool is_const>

ChildIterator< value_type, is_const > KisForestDetail::siblingCurrent ( ChildIterator< value_type, is_const > it )

Definition at line 240 of file KisForest.h.

{
    return it;
}

◆ siblingCurrent() [2/2]

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = ChildIterator<typename Iterator::value_type, is_const>>

ResultIterator KisForestDetail::siblingCurrent ( Iterator it )

Definition at line 264 of file KisForest.h.

{
    // TODO: conversion of an end-iterator into a child iterator is still not implemented
    //       and considered as UB. We need to implement all special-cases for that.
    KIS_SAFE_ASSERT_RECOVER_NOOP(it.node());
 
    return ResultIterator(it.node(), it.node() ? it.node()->parent : nullptr, 0);
}

References KIS_SAFE_ASSERT_RECOVER_NOOP.

◆ siblingEnd() [1/2]

template<typename value_type , bool is_const>

ChildIterator< value_type, is_const > KisForestDetail::siblingEnd ( const ChildIterator< value_type, is_const > & it )

Definition at line 255 of file KisForest.h.

{
    if (!it.node() && it.m_offsetToParent != 0) return it;
    return ChildIterator<value_type, is_const>(nullptr, it.m_parent, 0);
}

References KisForestDetail::ChildIterator< T, is_const >::m_offsetToParent, KisForestDetail::ChildIterator< T, is_const >::m_parent, and KisForestDetail::BaseIterator< BaseClass, T, Tag, is_const >::node().

◆ siblingEnd() [2/2]

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = ChildIterator<typename Iterator::value_type, is_const>>

ResultIterator KisForestDetail::siblingEnd ( Iterator it )

Definition at line 284 of file KisForest.h.

{
    return siblingEnd(siblingCurrent(it));
}

References siblingCurrent(), and siblingEnd().

◆ size()

template<typename T >

int KisForestDetail::size ( const Forest< T > & forest )

Definition at line 1232 of file KisForest.h.

                                  {
    return std::distance(begin(forest), end(forest));
}

◆ subtreeBegin()

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Enter, is_const>>

ResultIterator KisForestDetail::subtreeBegin ( Iterator it )

Definition at line 688 of file KisForest.h.

{
    return ResultIterator(it.node(), Enter);
}

References Enter.

◆ subtreeEnd()

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Enter, is_const>>

ResultIterator KisForestDetail::subtreeEnd ( Iterator it )

Definition at line 696 of file KisForest.h.

{
    return it.node() ?
        std::next(ResultIterator(it.node(), Leave)) :
        ResultIterator(nullptr, Leave);
}

References Leave.

◆ tailSubtreeBegin() [1/3]

template<typename T >

Forest< T >::const_depth_first_tail_iterator KisForestDetail::tailSubtreeBegin ( const Forest< T > & forest )

Definition at line 1195 of file KisForest.h.

{
    return forest.depthFirstTailBegin();
}

References KisForestDetail::Forest< T >::depthFirstTailBegin().

◆ tailSubtreeBegin() [2/3]

template<typename T >

Forest< T >::depth_first_tail_iterator KisForestDetail::tailSubtreeBegin ( Forest< T > & forest )

Definition at line 1189 of file KisForest.h.

{
    return forest.depthFirstTailBegin();
}

References KisForestDetail::Forest< T >::depthFirstTailBegin().

◆ tailSubtreeBegin() [3/3]

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Leave, is_const>>

ResultIterator KisForestDetail::tailSubtreeBegin ( Iterator it )

Definition at line 706 of file KisForest.h.

{
    return ResultIterator(it.node(), Enter, true);
}

References Enter.

◆ tailSubtreeEnd() [1/3]

template<typename T >

Forest< T >::const_depth_first_tail_iterator KisForestDetail::tailSubtreeEnd ( const Forest< T > & forest )

Definition at line 1207 of file KisForest.h.

{
    return forest.depthFirstTailEnd();
}

References KisForestDetail::Forest< T >::depthFirstTailEnd().

◆ tailSubtreeEnd() [2/3]

template<typename T >

Forest< T >::depth_first_tail_iterator KisForestDetail::tailSubtreeEnd ( Forest< T > & forest )

Definition at line 1201 of file KisForest.h.

{
    return forest.depthFirstTailEnd();
}

References KisForestDetail::Forest< T >::depthFirstTailEnd().

◆ tailSubtreeEnd() [3/3]

template<typename Iterator , bool is_const = std::is_const_v<typename Iterator::NodeType>, typename ResultIterator = DepthFirstIterator<typename Iterator::value_type, Leave, is_const>>

ResultIterator KisForestDetail::tailSubtreeEnd ( Iterator it )

Definition at line 714 of file KisForest.h.

{
    return it.node() ?
        std::next(ResultIterator(it.node(), Leave)) :
        ResultIterator(nullptr, Leave);
}

References Leave.

Classes

Typedefs

Enumerations

Functions

Typedef Documentation

◆ RootNode

Enumeration Type Documentation

◆ TraversalState

Function Documentation

◆ childBegin() [1/4]

◆ childBegin() [2/4]

◆ childBegin() [3/4]

◆ childBegin() [4/4]

◆ childEnd() [1/4]

◆ childEnd() [2/4]

◆ childEnd() [3/4]

◆ childEnd() [4/4]

◆ compositionBegin() [1/3]

◆ compositionBegin() [2/3]

◆ compositionBegin() [3/3]

◆ compositionEnd() [1/3]

◆ compositionEnd() [2/3]

◆ compositionEnd() [3/3]

◆ depth() [1/2]

◆ depth() [2/2]

◆ hierarchyBegin()

◆ hierarchyEnd()

◆ isEnd()

◆ operator<<()

◆ parent()

◆ siblingBegin() [1/2]

◆ siblingBegin() [2/2]

◆ siblingCurrent() [1/2]

◆ siblingCurrent() [2/2]

◆ siblingEnd() [1/2]

◆ siblingEnd() [2/2]

◆ size()

◆ subtreeBegin()

◆ subtreeEnd()

◆ tailSubtreeBegin() [1/3]

◆ tailSubtreeBegin() [2/3]

◆ tailSubtreeBegin() [3/3]

◆ tailSubtreeEnd() [1/3]

◆ tailSubtreeEnd() [2/3]

◆ tailSubtreeEnd() [3/3]