Description
template<class B>
class Sawyer::Tree::Vertex< B >
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:
- In a separate header file intended to be lightweight, often named "BasicTypes.h", create a forward declaration for the class.
- Declare the C++ constructors with protected access and replace them with public, static member functions named
instancethat 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.
- Create a nested type named
Ptrinside the class. This should be an alias for thestd::shared_ptrtype. 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 post-order depth-first traversals, and they can return user-defined types, and they can short-circuit 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 cross-tree 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 parent-to-child 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) |
| Pre-order forward traversal. More... | |
| template<class T , class Visitor > | |
| auto | traversePost (const Visitor &visitor) |
| Post-order 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 () |
Member Typedef Documentation
| 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 |
Member Function Documentation
| 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 depth-first 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 depth-first 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 default-constructed value.
|
inline |
Pre-order forward traversal.
Perform a depth-first pre-order 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 default-constructed value.
|
inline |
Post-order forward traversal.
Perform a depth-first post-order 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 default-constructed 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 |
Member Data Documentation
| 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().
The documentation for this class was generated from the following file:
