ROSE
0.11.96.11
|
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:
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.
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 |
using Sawyer::Tree::NodePtr = typedef std::shared_ptr<Node> |
using Sawyer::Tree::ConstNodePtr = typedef std::shared_ptr<const Node> |