Description

Tree data structure.

This name space contains the building blocks for relating heap-allocated objects (called nodes, base type Node) in a tree-like way. The children of a node are referenced either by name or iteratively. Each node of the tree has a single parent pointer which is adjusted automatically to ensure consistency. A node can also point to another node without creating a managed parent-child edge; such node pointers are not followed during traversals.

The primary purpose of these classes is to ensure consistency in the tree data structure:

Pointers from children to parents are maintained automatically.

Exceptions are thrown if the user attempts to link nodes together in a way that doesn't form a tree.

The infrastructure is exception safe.

Nodes are reference counted via std::shared_ptr.

Although this implementation is intended to be efficient in time and space, the primary goal is safety. When the two goals are in conflict, safety takes precedence.

The basic usage is that the user defines some node types that inherit from Tree::Node. If any of those types have parent-child tree edges (parent-to-child pointers that are followed during traversals), then those edges are declared as data members and initialized during construction:

class MyNode: public Tree::Node {
public:
    // Define a tree edge called "first" that points to a user-defined type
    // "First" (defined elsewhere) that derives from Tree::Node.
    Tree::ChildEdge<First> first;
 
    // Define a tree edge called "second" that points to another "MyNode" node.
    Tree::ChildEdge<MyNode> second;
 
    // Define a final edge called "third" that points to any kind of tree node.
    Tree::ChildEdge<Tree::Node> third;
 
    // Initialize the nodes during construction. The first will point to a
    // specified node, and the other two will be initialized to null.
    explicit MyNode(const std::shared_ptr<First> &first)
        : first(this, first), second(this), third(this) {}
}

The data members can be the left hand side of assignment operators, in which case the parent pointers of the affected nodes are updated automatically.

void test() {
    auto a = std::make_shared<First>();
    auto b = std::make_shared<First>();
 
    auto root = std::make_shared<MyNode>(a);
    assert(root->first == a);
    assert(a->parent == root);     // set automatically by c'tor defined above
 
    root->first = b;
    assert(root->first == b);
    assert(b->parent == root);     // set automatically
    assert(a->parent == nullptr);  // cleared automatically
}

See also, Graph, which can store non-class values such as 'int', is optimized for performance, and can easily handle cycles, self-edges, and parallel edges.

NOTICE: The Tree API is experimental and still under development. Currently, each child pointer occupies twice the space as a raw pointer. Dereferencing a child pointer takes constant time but includes one dynamic cast. Besides the child data member edges just described, each Node object also has a parent data member that occupies as much space as a raw pointer and can be dereferenced in constant time, and a children vector of pointers with one element per ChildEdge data member and one additional element.

Classes
class	ChildEdge
	An edge from a parent to a child. More...

class	Children
	Vector of parent-to-child pointers. More...

class	ConsistencyException
	Exception if tree consistency would be violated. More...

class	Exception
	Exceptions for tree-related operations. More...

class	ListNode
	A node containing only a list of children. More...

class	Node
	Base class for Tree nodes. More...

class	ParentEdge
	Edge pointing from child to parent. More...

struct	TraverseTypeHelper

Enumerations
enum	TraversalEvent { ENTER = 0x1, LEAVE = 0x2 }
	Traversal event bit flags. More...

enum	TraversalAction { CONTINUE, SKIP_CHILDREN, ABORT }
	Traversal actions. More...

Functions
template<class T , class U >
bool	operator== (const ChildEdge< T > &lhs, const ChildEdge< U > &rhs) noexcept

template<class T , class U >
bool	operator!= (const ChildEdge< T > &lhs, const ChildEdge< U > &rhs) noexcept

template<class T , class U >
bool	operator< (const ChildEdge< T > &lhs, const ChildEdge< U > &rhs) noexcept

template<class T , class U >
bool	operator<= (const ChildEdge< T > &lhs, const ChildEdge< U > &rhs) noexcept

template<class T , class U >
bool	operator> (const ChildEdge< T > &lhs, const ChildEdge< U > &rhs) noexcept

template<class T , class U >
bool	operator>= (const ChildEdge< T > &lhs, const ChildEdge< U > &rhs) noexcept

template<class T >
bool	operator== (const ChildEdge< T > &lhs, std::nullptr_t) noexcept

template<class T >
bool	operator!= (const ChildEdge< T > &lhs, std::nullptr_t) noexcept

template<class T >
bool	operator< (const ChildEdge< T > &lhs, std::nullptr_t) noexcept

template<class T >
bool	operator<= (const ChildEdge< T > &lhs, std::nullptr_t) noexcept

template<class T >
bool	operator> (const ChildEdge< T > &lhs, std::nullptr_t) noexcept

template<class T >
bool	operator>= (const ChildEdge< T > &lhs, std::nullptr_t) noexcept

template<class T >
bool	operator== (std::nullptr_t, const ChildEdge< T > &rhs) noexcept

template<class T >
bool	operator!= (std::nullptr_t, const ChildEdge< T > &rhs) noexcept

template<class T >
bool	operator< (std::nullptr_t, const ChildEdge< T > &rhs) noexcept

template<class T >
bool	operator<= (std::nullptr_t, const ChildEdge< T > &rhs) noexcept

template<class T >
bool	operator> (std::nullptr_t, const ChildEdge< T > &rhs) noexcept

template<class T >
bool	operator>= (std::nullptr_t, const ChildEdge< T > &rhs) noexcept

template<class T , class U >
bool	operator== (const ChildEdge< T > &lhs, const std::shared_ptr< U > &rhs) noexcept

template<class T , class U >
bool	operator!= (const ChildEdge< T > &lhs, const std::shared_ptr< U > &rhs) noexcept

template<class T , class U >
bool	operator< (const ChildEdge< T > &lhs, const std::shared_ptr< U > &rhs) noexcept

template<class T , class U >
bool	operator<= (const ChildEdge< T > &lhs, const std::shared_ptr< U > &rhs) noexcept

template<class T , class U >
bool	operator> (const ChildEdge< T > &lhs, const std::shared_ptr< U > &rhs) noexcept

template<class T , class U >
bool	operator>= (const ChildEdge< T > &lhs, const std::shared_ptr< U > &rhs) noexcept

template<class T , class U >
bool	operator== (const std::shared_ptr< T > &lhs, const ChildEdge< U > &rhs) noexcept

template<class T , class U >
bool	operator!= (const std::shared_ptr< T > &lhs, const ChildEdge< U > &rhs) noexcept

template<class T , class U >
bool	operator< (const std::shared_ptr< T > &lhs, const ChildEdge< U > &rhs) noexcept

template<class T , class U >
bool	operator<= (const std::shared_ptr< T > &lhs, const ChildEdge< U > &rhs) noexcept

template<class T , class U >
bool	operator> (const std::shared_ptr< T > &lhs, const ChildEdge< U > &rhs) noexcept

template<class T , class U >
bool	operator>= (const std::shared_ptr< T > &lhs, const ChildEdge< U > &rhs) noexcept

bool	operator== (const ParentEdge &lhs, std::nullptr_t) noexcept

bool	operator!= (const ParentEdge &lhs, std::nullptr_t) noexcept

bool	operator< (const ParentEdge &lhs, std::nullptr_t) noexcept

bool	operator<= (const ParentEdge &lhs, std::nullptr_t) noexcept

bool	operator> (const ParentEdge &lhs, std::nullptr_t) noexcept

bool	operator>= (const ParentEdge &lhs, std::nullptr_t) noexcept

bool	operator== (std::nullptr_t, const ParentEdge &rhs) noexcept

bool	operator!= (std::nullptr_t, const ParentEdge &rhs) noexcept

bool	operator< (std::nullptr_t, const ParentEdge &rhs) noexcept

bool	operator<= (std::nullptr_t, const ParentEdge &rhs) noexcept

bool	operator> (std::nullptr_t, const ParentEdge &rhs) noexcept

bool	operator>= (std::nullptr_t, const ParentEdge &rhs) noexcept

template<class T >
bool	operator== (const ParentEdge &lhs, const std::shared_ptr< T > &rhs) noexcept

template<class T >
bool	operator!= (const ParentEdge &lhs, const std::shared_ptr< T > &rhs) noexcept

template<class T >
bool	operator< (const ParentEdge &lhs, const std::shared_ptr< T > &rhs) noexcept

template<class T >
bool	operator<= (const ParentEdge &lhs, const std::shared_ptr< T > &rhs) noexcept

template<class T >
bool	operator> (const ParentEdge &lhs, const std::shared_ptr< T > &rhs) noexcept

template<class T >
bool	operator>= (const ParentEdge &lhs, const std::shared_ptr< T > &rhs) noexcept

template<class T >
bool	operator== (const std::shared_ptr< T > &lhs, const ParentEdge &rhs) noexcept

template<class T >
bool	operator!= (const std::shared_ptr< T > &lhs, const ParentEdge &rhs) noexcept

template<class T >
bool	operator< (const std::shared_ptr< T > &lhs, const ParentEdge &rhs) noexcept

template<class T >
bool	operator<= (const std::shared_ptr< T > &lhs, const ParentEdge &rhs) noexcept

template<class T >
bool	operator> (const std::shared_ptr< T > &lhs, const ParentEdge &rhs) noexcept

template<class T >
bool	operator>= (const std::shared_ptr< T > &lhs, const ParentEdge &rhs) noexcept

template<class T >
bool	operator== (const ParentEdge &lhs, const ChildEdge< T > &rhs) noexcept

template<class T >
bool	operator!= (const ParentEdge &lhs, const ChildEdge< T > &rhs) noexcept

template<class T >
bool	operator< (const ParentEdge &lhs, const ChildEdge< T > &rhs) noexcept

template<class T >
bool	operator<= (const ParentEdge &lhs, const ChildEdge< T > &rhs) noexcept

template<class T >
bool	operator> (const ParentEdge &lhs, const ChildEdge< T > &rhs) noexcept

template<class T >
bool	operator>= (const ParentEdge &lhs, const ChildEdge< T > &rhs) noexcept

template<class T >
bool	operator== (const ChildEdge< T > &lhs, const ParentEdge &rhs) noexcept

template<class T >
bool	operator!= (const ChildEdge< T > &lhs, const ParentEdge &rhs) noexcept

template<class T >
bool	operator< (const ChildEdge< T > &lhs, const ParentEdge &rhs) noexcept

template<class T >
bool	operator<= (const ChildEdge< T > &lhs, const ParentEdge &rhs) noexcept

template<class T >
bool	operator> (const ChildEdge< T > &lhs, const ParentEdge &rhs) noexcept

template<class T >
bool	operator>= (const ChildEdge< T > &lhs, const ParentEdge &rhs) noexcept

Typedef Documentation

◆ NodePtr

using Sawyer::Tree::NodePtr = typedef std::shared_ptr<Node>

Short name for node pointers.

A shared-ownership pointer for nodes.

Definition at line 105 of file Tree.h.

◆ ConstNodePtr

using Sawyer::Tree::ConstNodePtr = typedef std::shared_ptr<const Node>

Short name for node pointers.

A shared-ownership pointer for nodes.

Definition at line 106 of file Tree.h.

Enumeration Type Documentation

◆ TraversalEvent

enum Sawyer::Tree::TraversalEvent

Traversal event bit flags.

Enumerator
ENTER	Traversal has just entered the node under consideration.
LEAVE	Traversal has just left the node under consideration.

Definition at line 119 of file Tree.h.

◆ TraversalAction

enum Sawyer::Tree::TraversalAction

Traversal actions.

Enumerator
CONTINUE	Continue with the traversal.
SKIP_CHILDREN	For enter events, do not traverse into the node's children.
ABORT	Abort the traversal immediately.

Definition at line 125 of file Tree.h.