Description
Base class for Tree nodes.
All nodes of a tree inherit from this type. The main features that this class provides are:
- When declaring a tree node, the parent-child edges are declared using the ChildEdge type as described in that type's documentation.
- Every node has a
childrendata member that enumerates the nodes pointed to by the ChildEdge data members. This list of all children is updated automatically as assignments are made to the ChildEdge data members.
- Every node has a
parentdata member that points to the parent node in the tree, or null if this node is the root of a tree. The parent pointers are updated automatically as nodes are inserted into and removed from the tree.
- Node memory is managed using
std::shared_ptr, and node memory is reclaimed automatically when there are no more references to the node, either as parent-child edges or other shared pointers outside the tree's control. The pointers from child to parent within the tree data structure itself are weak and do not count as references to the parent node.
- a number of traversals are defined, the two most general being traverse and traverseParents. The other traversals are more specialized and are built upon the first two.
Definition at line 479 of file util/Sawyer/Tree.h.
#include <util/Sawyer/Tree.h>
Public Member Functions | |
| Node () | |
| Construct an empty node. More... | |
| virtual | ~Node () |
| Nodes are polymorphic. More... | |
| Node (const Node &)=delete | |
| Node & | operator= (const Node &)=delete |
| template<class Functor > | |
| TraversalAction | traverse (Functor functor) |
| Traverse the tree starting at this node and following child pointers. More... | |
| template<class Functor > | |
| TraversalAction | traverse (Functor functor) const |
| Traverse the tree starting at this node and following child pointers. More... | |
| template<class T , class Functor > | |
| TraversalAction | traverseType (Functor functor) |
| Traverse the tree restricted by type. More... | |
| template<class T , class Functor > | |
| TraversalAction | traverseType (Functor functor) const |
| Traverse the tree restricted by type. More... | |
| template<class Functor > | |
| TraversalAction | traverseParents (Functor functor) |
| Traverse the tree by following parent pointers. More... | |
| template<class Functor > | |
| TraversalAction | traverseParents (Functor functor) const |
| Traverse the tree by following parent pointers. More... | |
| template<class Predicate > | |
| NodePtr | find (Predicate predicate) |
| Traverse an tree to find the first node satisfying the predicate. | |
| template<class Predicate > | |
| NodePtr | find (Predicate predicate) const |
| Traverse an tree to find the first node satisfying the predicate. | |
| template<class T > | |
| std::shared_ptr< T > | findType () |
| Find first child that's the specified type. | |
| template<class T > | |
| std::shared_ptr< T > | findType () const |
| Find first child that's the specified type. | |
| template<class T , class Predicate > | |
| std::shared_ptr< T > | findType (Predicate predicate) |
| Find first child of specified type satisfying the predicate. | |
| template<class T , class Predicate > | |
| std::shared_ptr< T > | findType (Predicate predicate) const |
| Find first child of specified type satisfying the predicate. | |
| template<class Predicate > | |
| NodePtr | findParent (Predicate predicate) |
| Find closest ancestor that satifies the predicate. | |
| template<class Predicate > | |
| NodePtr | findParent (Predicate predicate) const |
| Find closest ancestor that satifies the predicate. | |
| template<class T > | |
| std::shared_ptr< T > | findParentType () |
| Find closest ancestor of specified type. | |
| template<class T > | |
| std::shared_ptr< T > | findParentType () const |
| Find closest ancestor of specified type. | |
| template<class T , class Predicate > | |
| std::shared_ptr< T > | findParentType (Predicate predicate) |
| Find closest ancestor of specified type that satisfies the predicate. | |
| template<class T , class Predicate > | |
| std::shared_ptr< T > | findParentType (Predicate predicate) const |
| Find closest ancestor of specified type that satisfies the predicate. | |
Public Attributes | |
| ParentEdge | parent |
| Pointer to the parent node, if any. More... | |
| Children | children |
| Vector of pointers to children. More... | |
Constructor & Destructor Documentation
|
inline |
Construct an empty node.
Definition at line 489 of file util/Sawyer/Tree.h.
|
inlinevirtual |
Nodes are polymorphic.
Definition at line 492 of file util/Sawyer/Tree.h.
Member Function Documentation
|
inline |
Traverse the tree starting at this node and following child pointers.
The functor takes two arguments: the tree node under consideration, and a TraversalEvent that indicates whether the traversal is entering or leaving the node. The functor must return a TraversalAction to describe what should happen next.
If the functor called by the node enter event returns SKIP_CHILDREN, then none of the children are traversed and the next call to the functor is for leaving that same node.
If any call to the functor returns ABORT, then the traversal is immediately aborted.
If any functor returns ABORT, then the traverse function also returns ABORT. Otherwise the traverse function returns CONTINUE.
Definition at line 516 of file util/Sawyer/Tree.h.
|
inline |
Traverse the tree starting at this node and following child pointers.
The functor takes two arguments: the tree node under consideration, and a TraversalEvent that indicates whether the traversal is entering or leaving the node. The functor must return a TraversalAction to describe what should happen next.
If the functor called by the node enter event returns SKIP_CHILDREN, then none of the children are traversed and the next call to the functor is for leaving that same node.
If any call to the functor returns ABORT, then the traversal is immediately aborted.
If any functor returns ABORT, then the traverse function also returns ABORT. Otherwise the traverse function returns CONTINUE.
Definition at line 520 of file util/Sawyer/Tree.h.
| TraversalAction Sawyer::Tree::Node::traverseType | ( | Functor | functor | ) |
Traverse the tree restricted by type.
Traverses the entire tree, but calls the functor only for nodes of the specified type (or subtype).
Definition at line 1107 of file util/Sawyer/Tree.h.
| TraversalAction Sawyer::Tree::Node::traverseType | ( | Functor | functor | ) | const |
Traverse the tree restricted by type.
Traverses the entire tree, but calls the functor only for nodes of the specified type (or subtype).
Definition at line 1113 of file util/Sawyer/Tree.h.
|
inline |
Traverse the tree by following parent pointers.
Other than following pointers from children to parents, this traversal is identical to the downward traverse method.
Definition at line 543 of file util/Sawyer/Tree.h.
|
inline |
Traverse the tree by following parent pointers.
Other than following pointers from children to parents, this traversal is identical to the downward traverse method.
Definition at line 547 of file util/Sawyer/Tree.h.
Member Data Documentation
| ParentEdge Sawyer::Tree::Node::parent |
Pointer to the parent node, if any.
Definition at line 484 of file util/Sawyer/Tree.h.
| Children Sawyer::Tree::Node::children |
Vector of pointers to children.
Definition at line 485 of file util/Sawyer/Tree.h.
Referenced by Sawyer::Tree::ListNode< T >::at(), Sawyer::Tree::ListNode< T >::back(), Sawyer::Tree::ListNode< T >::capacity(), Sawyer::Tree::ListNode< T >::clear(), Sawyer::Tree::ListNode< T >::empty(), Sawyer::Tree::ListNode< T >::eraseAt(), Sawyer::Tree::ListNode< T >::front(), Sawyer::Tree::ListNode< T >::insertAt(), Sawyer::Tree::ListNode< T >::max_size(), Sawyer::Tree::ListNode< T >::operator[](), Sawyer::Tree::ListNode< T >::push_back(), Sawyer::Tree::ListNode< T >::reserve(), Sawyer::Tree::ListNode< T >::setAt(), Sawyer::Tree::ChildEdge< T >::shared(), Sawyer::Tree::ListNode< T >::shrink_to_fit(), and Sawyer::Tree::ListNode< T >::size().
The documentation for this class was generated from the following file:
