ROSE  0.9.12.24
Classes | Enumerations | Functions
Sawyer::Tree Namespace Reference

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:

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" (define 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
 

Typedefs

using NodePtr = std::shared_ptr< Node >
 Short name for node pointers. More...
 
using ConstNodePtr = std::shared_ptr< const Node >
 Short name for node pointers. More...
 

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, nullptr_t) noexcept
 
template<class T >
bool operator!= (const ChildEdge< T > &lhs, nullptr_t) noexcept
 
template<class T >
bool operator< (const ChildEdge< T > &lhs, nullptr_t) noexcept
 
template<class T >
bool operator<= (const ChildEdge< T > &lhs, nullptr_t) noexcept
 
template<class T >
bool operator> (const ChildEdge< T > &lhs, nullptr_t) noexcept
 
template<class T >
bool operator>= (const ChildEdge< T > &lhs, nullptr_t) noexcept
 
template<class T >
bool operator== (nullptr_t, const ChildEdge< T > &rhs) noexcept
 
template<class T >
bool operator!= (nullptr_t, const ChildEdge< T > &rhs) noexcept
 
template<class T >
bool operator< (nullptr_t, const ChildEdge< T > &rhs) noexcept
 
template<class T >
bool operator<= (nullptr_t, const ChildEdge< T > &rhs) noexcept
 
template<class T >
bool operator> (nullptr_t, const ChildEdge< T > &rhs) noexcept
 
template<class T >
bool operator>= (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, nullptr_t) noexcept
 
bool operator!= (const ParentEdge &lhs, nullptr_t) noexcept
 
bool operator< (const ParentEdge &lhs, nullptr_t) noexcept
 
bool operator<= (const ParentEdge &lhs, nullptr_t) noexcept
 
bool operator> (const ParentEdge &lhs, nullptr_t) noexcept
 
bool operator>= (const ParentEdge &lhs, nullptr_t) noexcept
 
bool operator== (nullptr_t, const ParentEdge &rhs) noexcept
 
bool operator!= (nullptr_t, const ParentEdge &rhs) noexcept
 
bool operator< (nullptr_t, const ParentEdge &rhs) noexcept
 
bool operator<= (nullptr_t, const ParentEdge &rhs) noexcept
 
bool operator> (nullptr_t, const ParentEdge &rhs) noexcept
 
bool operator>= (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

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.

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

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.

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.