ROSE
0.11.145.0

Base class for tree vertices.
A tree vertex is a type with zero or more edges that point to child vertices. The set of all vertices recursively reachable from any particular vertex along these edges forms a tree data structure.
The user might want to have multiple independent tree types whose vertices aren't derived from any common base class. This is accomplished by the user's base class inheriting from this class template, whose argument is the user's base class.
All vertex instantiations are reference counted and ponted to by std::shared_ptr
. Some good practices are:
instance
that allocate a new object in the heap and return a pointer to it. This prevents users from accidentally instantiating objects on the stack or in the data segment.Ptr
inside the class. This should be an alias for the std::shared_ptr
type. If you do this consistently, then you can always use "Ptr" instead of the much longer "std::shared_ptr<MyClassName>". Since one often needs this type outside this header file, adding an alias to the aforementioned "BasicTypes.h" is prudent, in which case the one in BasicTypes.h should be like "MyClassNamePtr" (i.e., ending with "Ptr") and the alias inside the class would be "using Ptr =
MyClassNamePtr".As mentioned, a vertex may have zero or more edges that point to children of the same tree. These are data members whose type is Edge<T>
or EdgeList<T>
(or anything else that inherits from EdgeBase
). These types do not have default constructors, so the constructor in the containing class is expected to construct them by passing *this
as the first argument to their constructors.
In addition to edges that are part of the tree, it is permissible for a vertex to point directly to other vertices inside or outside the tree from which they're pointed. These are called "cross tree" pointers and do not use the EdgeBase
types. By the way, the difference between an "edge" and a "pointer" in this context is that an edge is bidirectional.
Every vertex also has a parent
public data member that points to the parent vertex in the tree. The parent
data member is updated automatically whenever a child is attached to or detached from a parent vertex. A vertex may have exactly zero or one parent. If vertex v has no parent, then there does not exist any vertex that has an edge pointing to v. Vice versa, if there exists a vertex pointing to v then v>parent points to that vertex.
Two types of traversals are defined: forward and reverse. The traversals visit only vertices of the specified type (or derivatives thereof), they support both pre and postorder depthfirst traversals, and they can return userdefined types, and they can shortcircuit by returning a certain class of values. For more information, see traverse and traverseReverse. All other traversals can be defined in terms of these two.
Example of a class that has two scalar children one of which is always allocated, one vector child, and one crosstree pointer.
#include <util/Sawyer/Tree.h>
Classes  
class  CycleError 
Error when attaching a vertex to a tree would cause a cycle. More...  
class  Edge 
A parenttochild edge in a tree. More...  
class  EdgeVector 
A 1:N tree edge from parent to children. More...  
class  Exception 
Base class for errors and exceptions for this vertex type. More...  
class  InsertionError 
Error when attaching a vertex to a tree and the vertex is already attached somewhere else. More...  
class  ReverseEdge 
Points from a child to a parent in the tree. More...  
Public Types  
using  UserBase = B 
User's base class. More...  
using  UserBasePtr = std::shared_ptr< UserBase > 
Pointer to user's base class. More...  
using  TraversalEvent = Sawyer::Tree::TraversalEvent 
Alias for traversal events. More...  
Public Member Functions  
UserBasePtr  pointer () 
Returns a shared pointer to this vertex. More...  
template<class T >  
std::shared_ptr< T >  isa () 
Tests whether this object is a certain type. More...  
template<class T , class Visitor >  
auto  traverseReverse (const Visitor &visitor) 
Traverse in reverse direction from children to parents. More...  
template<class T , class Visitor >  
auto  traverse (const Visitor &visitor) 
Traverse in forward direction from parents to children. More...  
template<class T , class Visitor >  
auto  traversePre (const Visitor &visitor) 
Preorder forward traversal. More...  
template<class T , class Visitor >  
auto  traversePost (const Visitor &visitor) 
Postorder forward traversal. More...  
template<class T >  
std::shared_ptr< T >  findFirstAncestor () 
Traversal that finds the closest ancestor of type T or derived from T. More...  
template<class T >  
std::shared_ptr< T >  findLastAncestor () 
Traversal that finds the farthest ancestor of type T or derived from T. More...  
template<class T >  
std::vector< std::shared_ptr< T > >  findDescendants () 
Traversal that finds all the descendants of a particular type. More...  
UserBasePtr  child (size_t i) const 
Returns the pointer for a child. More...  
size_t  nChildren () const 
Returns the number of children. More...  
Public Attributes  
ReverseEdge  parent 
Pointer to the parent in the tree. More...  
EdgeBase *  treeEdges_ = nullptr 
Protected Member Functions  
virtual void  destructorHelper () 
using Sawyer::Tree::Vertex< B >::UserBase = B 
using Sawyer::Tree::Vertex< B >::UserBasePtr = std::shared_ptr<UserBase> 
using Sawyer::Tree::Vertex< B >::TraversalEvent = Sawyer::Tree::TraversalEvent 
Vertex< B >::UserBasePtr Vertex::pointer  (  ) 
Returns a shared pointer to this vertex.
Definition at line 1081 of file Tree.h.
Referenced by Sawyer::Tree::Vertex< B >::ReverseEdge::operator()(), Sawyer::Tree::Vertex< Node >::traverse(), and Sawyer::Tree::Vertex< Node >::traverseReverse().
std::shared_ptr< T > Vertex::isa  (  ) 

inline 
Traverse in reverse direction from children to parents.
The visitor is called for each vertex from the current vertex whose type is T
until the root of the tree is reached unless the visitor indicates that the traversal should end. It does so by returning a value that is true in a Boolean context, and this value becomes the return value for the entire traversal.
Example: Find the closest ancestor whose type is Foo or is derived from Foo.
Example: Find the most distant ancestor whose type is Foo or is derived from Foo. The only change from the previous example is that we test as we leave the vertices. I.e., as the depthfirst traversal is returning.
If you want to exclude the current vertex from the traversal, start searching at the parent instead, but be careful that the parent is not null or else its arrow operator will fail.

inline 
Traverse in forward direction from parents to children.
Perform a depthfirst traversal of the tree starting with this vertex. The visitor functor is called twice for each vertex, first in the forward direction from the parent, then in the reverse direction from the children. The functor takes two arguments: the vertex being visited and an enum indicating whether the visit is the first (Traverse::ENTER) or the second (Traverse::LEAVE) visitation. The traversal has the same return type as the functor. If the functor returns a value which evaluates to true in Boolean context, then the traversal immediately returns that value, otherwise it continues until the entire subtree is visited and returns a defaultconstructed value.

inline 
Preorder forward traversal.
Perform a depthfirst preorder traversal. The functor is called once for each vertex before any of its children are traversed. This is equivalent to the traverse traversal where the functor checks that the event is an ENTER
event before doing anything. If the functor returns a value which evaluates to true in Boolean context, then the traversal immediately returns that value, otherwise it continues until the entire subtree is visited and returns a defaultconstructed value.

inline 
Postorder forward traversal.
Perform a depthfirst postorder traversal. The functor is called once for each vertex all of its children are traversed. This is equivalent to the traverse traversal where the functor checks that the event is an LEAVE
event before doing anything. If the functor returns a value which evaluates to true in Boolean context, then the traversal immediately returns that value, otherwise it continues until the entire subtree is visited and returns a defaultconstructed value.

inline 

inline 

inline 
Traversal that finds all the descendants of a particular type.
Note that this is probably not the way you want to do this because it's expensive to create the list of all matching pointers. Instead, you probably want to call traverse and handle each matching vertex inside the functor.
Vertex< B >::UserBasePtr Vertex::child  (  size_t  i  )  const 
Returns the pointer for a child.
Returns the pointer for the child at index i
. If i
is out of range, then a null pointer is returned, which is indistinguishable from the case when a valid index is specified but that child is a null pointer.
Definition at line 1096 of file Tree.h.
Referenced by Sawyer::Tree::Vertex< B >::Edge< T >::operator=().
size_t Vertex::nChildren  (  )  const 
ReverseEdge Sawyer::Tree::Vertex< B >::parent 
Pointer to the parent in the tree.
A vertex's parent pointer is adjusted automatically when the vertex is inserted or removed as a child of another vertex. An invariant of this design is that whenever vertex A is a child of vertex B, then vertex B is a parent of vertex A.
Definition at line 694 of file Tree.h.
Referenced by Sawyer::Tree::Vertex< B >::Edge< T >::operator=(), Sawyer::Tree::Vertex< Node >::traverseReverse(), and Sawyer::Tree::Vertex< B >::Edge< T >::~Edge().