Description

template<class B>
class Sawyer::Tree::Vertex

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 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.

Create a nested type named 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 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.

class Test: public Base {  // Base ultimately inherits from Tree::Vertex<T>
public:
    using Ptr = TestPtr;   // defined in BasicTypes.h as "using TestPtr = std::shared_ptr<Test>"
 
public:
    Edge<Test> left;       // tree edge to the "left" child
    Edge<Other> right;     // tree edge to the "right" child, always allocated. Other must also inherit from Base.
    EdgeList<Test> list;   // tree edges to a bunch of children
    TestPtr cross;         // non-tree pointer to some other vertex
 
protected:
    Test()                 // C++ constructor hidden from casual users
        : left(*this),
          right(*this, Other::instance()),
          list(*this) {}
 
public:
    static Ptr instance(const Ptr &a, const Ptr &b) {
        auto self = Ptr(new Test);
        self->left = a;
        self->list.push_back(b);
 
        // Adjustments the parents happens automatically
        assert(self->left == a && a->parent == self);
        assert(self->list.front() == b && b->parent == self);
 
        return self;
    }
};

Definition at line 125 of file Tree.h.

#include <Sawyer/Tree.h>

Inheritance diagram for Sawyer::Tree::Vertex:

[legend]

Collaboration diagram for Sawyer::Tree::Vertex:

[legend]

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.

using	UserBasePtr = std::shared_ptr< UserBase >
	Pointer to user's base class.

using	TraversalEvent = Sawyer::Tree::TraversalEvent
	Alias for traversal events.

Public Member Functions
UserBasePtr	pointer ()
	Returns a shared pointer to this vertex.

template<class T >
std::shared_ptr< T >	isa ()
	Tests whether this object is a certain type.

template<class T , class Visitor >
auto	traverseReverse (const Visitor &visitor)
	Traverse in reverse direction from children to parents.

template<class T , class Visitor >
auto	traverse (const Visitor &visitor)
	Traverse in forward direction from parents to children.

template<class T , class Visitor >
auto	traversePre (const Visitor &visitor)
	Pre-order forward traversal.

template<class T , class Visitor >
auto	traversePost (const Visitor &visitor)
	Post-order forward traversal.

template<class T >
std::shared_ptr< T >	findFirstAncestor ()
	Traversal that finds the closest ancestor of type T or derived from T.

template<class T >
std::shared_ptr< T >	findLastAncestor ()
	Traversal that finds the farthest ancestor of type T or derived from T.

template<class T >
std::vector< std::shared_ptr< T > >	findDescendants ()
	Traversal that finds all the descendants of a particular type.

UserBasePtr	child (size_t i) const
	Returns the pointer for a child.

size_t	nChildren () const
	Returns the number of children.

Public Attributes
ReverseEdge	parent
	Pointer to the parent in the tree.

Protected Member Functions
virtual void	destructorHelper ()

Member Typedef Documentation

◆ UserBase

template<class B >

using Sawyer::Tree::Vertex::UserBase = B

User's base class.

Definition at line 129 of file Tree.h.

◆ UserBasePtr

template<class B >

using Sawyer::Tree::Vertex::UserBasePtr = std::shared_ptr<UserBase>

Pointer to user's base class.

Definition at line 132 of file Tree.h.

◆ TraversalEvent

template<class B >

using Sawyer::Tree::Vertex::TraversalEvent = Sawyer::Tree::TraversalEvent

Alias for traversal events.

Definition at line 135 of file Tree.h.

Constructor & Destructor Documentation

◆ Vertex()

template<class B >

Vertex::Vertex ( )

protected

Definition at line 1326 of file Tree.h.

Member Function Documentation

◆ destructorHelper()

template<class B >

virtual void Sawyer::Tree::Vertex::destructorHelper ( )

inlineprotectedvirtual

Definition at line 944 of file Tree.h.

◆ pointer()

template<class B >

Vertex::UserBasePtr Vertex::pointer ( )

Returns a shared pointer to this vertex.

Definition at line 1331 of file Tree.h.

Referenced by Sawyer::Tree::Vertex::ReverseEdge::operator()(), Sawyer::Tree::Vertex::traverse(), and Sawyer::Tree::Vertex::traverseReverse().

◆ isa()

template<class B >

template<class T >

std::shared_ptr< T > Vertex::isa ( )

Tests whether this object is a certain type.

Returns a shared pointer to the object if the object is of dynamic type T, otherwise returns a null pointer.

Definition at line 1340 of file Tree.h.

◆ traverseReverse()

template<class B >

template<class T , class Visitor >

auto Sawyer::Tree::Vertex::traverseReverse ( const Visitor & visitor )

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.

auto foundFirst = tree->traverseReverse<Foo>([](const Foo::Ptr &foo, TraversalEvent event) {
    return TraversalEvent::ENTER == event ? foo : nullptr;
});

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.

auto foundLast = tree->traverseReverse<Foo>([](const Foo::Ptr &foo, TraversalEvent event) {
    return TraversalEvent::LEAVE == event ? foo : nullptr;
});

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.

auto foundFirstNotMe = tree->parent->traverseReverse<Foo>([](const Foo::Ptr &foo, TraversalEvent event) {
    return TraversalEvent::ENTER == event ? foo : nullptr;
});

Definition at line 989 of file Tree.h.

References Sawyer::Tree::ENTER, Sawyer::Tree::LEAVE, Sawyer::Tree::Vertex::parent, and Sawyer::Tree::Vertex::pointer().

◆ traverse()

template<class B >

template<class T , class Visitor >

auto Sawyer::Tree::Vertex::traverse ( const Visitor & visitor )

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.

Definition at line 1017 of file Tree.h.

References Sawyer::Tree::ENTER, Sawyer::Tree::LEAVE, and Sawyer::Tree::Vertex::pointer().

◆ traversePre()

template<class B >

template<class T , class Visitor >

auto Sawyer::Tree::Vertex::traversePre ( const Visitor & visitor )

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.

Definition at line 1042 of file Tree.h.

References Sawyer::Tree::ENTER.

◆ traversePost()

template<class B >

template<class T , class Visitor >

auto Sawyer::Tree::Vertex::traversePost ( const Visitor & visitor )

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.

Definition at line 1060 of file Tree.h.

References Sawyer::Tree::LEAVE.

◆ findFirstAncestor()

template<class B >

template<class T >

std::shared_ptr< T > Sawyer::Tree::Vertex::findFirstAncestor ( )

inline

Traversal that finds the closest ancestor of type T or derived from T.

Definition at line 1072 of file Tree.h.

References Sawyer::Tree::ENTER.

◆ findLastAncestor()

template<class B >

template<class T >

std::shared_ptr< T > Sawyer::Tree::Vertex::findLastAncestor ( )

inline

Traversal that finds the farthest ancestor of type T or derived from T.

Definition at line 1080 of file Tree.h.

References Sawyer::Tree::LEAVE.

◆ findDescendants()

template<class B >

template<class T >

std::vector< std::shared_ptr< T > > Sawyer::Tree::Vertex::findDescendants ( )

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.

Definition at line 1091 of file Tree.h.

References Sawyer::Tree::ENTER.

◆ child()

template<class B >

Vertex::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 1346 of file Tree.h.

◆ nChildren()

template<class B >

size_t Vertex::nChildren ( ) const

Returns the number of children.

This is the number of children for this class and the base class, recursively. Some children may be null pointers.

Definition at line 1362 of file Tree.h.

Member Data Documentation

◆ parent

template<class B >

ReverseEdge Sawyer::Tree::Vertex::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 856 of file Tree.h.

Referenced by Sawyer::Tree::Vertex::Edge< T >::~Edge(), Sawyer::Tree::Vertex::Edge< T >::operator=(), and Sawyer::Tree::Vertex::traverseReverse().

The documentation for this class was generated from the following file:

Tree.h

Description

Classes

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Member Typedef Documentation

◆ UserBase

◆ UserBasePtr

◆ TraversalEvent

Constructor & Destructor Documentation

◆ Vertex()

Member Function Documentation

◆ destructorHelper()

◆ pointer()

◆ isa()

◆ traverseReverse()

◆ traverse()

◆ traversePre()

◆ traversePost()

◆ findFirstAncestor()

◆ findLastAncestor()

◆ findDescendants()

◆ child()

◆ nChildren()

Member Data Documentation

◆ parent