|
geomc 1.0
A c++ linear algebra template library
|
A dynamic tree of arbitrary arity. More...
#include <geomc/Tree.h>
Public Member Functions | |
| Tree () | |
| Construct an empty Tree. | |
| Tree (Tree< NodeItem, LeafItem > &&other)=default | |
| Default move constructor. | |
| template<typename LeafItemIterator > | |
| Tree (LeafItemIterator begin, LeafItemIterator end) | |
Construct a tree having a single root node, and copy the items in [begin, end) to it. | |
| Tree (const Tree< NodeItem, LeafItem > &other) | |
| Make a copy of the given tree. | |
| Tree (const ConstSubtree< NodeItem, LeafItem > &other) | |
| Construct a new tree from the given subtree. | |
| Subtree< NodeItem, LeafItem > | root () |
| Get a subtree iterator to the root of this tree. | |
| ConstSubtree< NodeItem, LeafItem > | root () const |
| Get a const subtree iterator to the root of this tree. | |
| Subtree< NodeItem, LeafItem > | begin () |
| Return an iterator to the first item in the tree (root), in sibling-contiguous order. | |
| Subtree< NodeItem, LeafItem > | end () |
| Return an iterator to the last (off-end) item in the tree, in sibling-contiguous order. | |
| ConstSubtree< NodeItem, LeafItem > | begin () const |
| Return a const iterator to the first item in the tree (root), in sibling-contiguous order. | |
| ConstSubtree< NodeItem, LeafItem > | end () const |
| Return a const iterator to the last (off-end) item in the tree, in sibling-contiguous order. | |
| Subtree< NodeItem, LeafItem > | subtree (ConstSubtree< NodeItem, LeafItem > &i) |
| Convert a ConstSubtree into a Subtree by removing its constness. More... | |
| size_t | size () const |
| Total number of nodes in this Tree. | |
| size_t | item_count () const |
| Total number of items in this Tree. | |
| bool | operator== (const Tree< NodeItem, LeafItem > &other) const |
| Tree equality. | |
| bool | operator!= (const Tree< NodeItem, LeafItem > &other) const |
| Tree inequality. | |
Protected Member Functions | |
| void | recalculate_tree () |
| void | update_boundary_items (NodeRef leaf, ItemRef new_first, ItemRef new_last, index_t delta_items) |
Friends | |
| class | SubtreeBase< NodeItem, LeafItem, true > |
| class | SubtreeBase< NodeItem, LeafItem, false > |
| class | ConstSubtree< NodeItem, LeafItem > |
| class | Subtree< NodeItem, LeafItem > |
A dynamic tree of arbitrary arity.
Each node in the tree may store an associated NodeItem object. A node may have any number of child nodes.
Leaf nodes may own a list of LeafItem objects. LeafItems are kept in (contiguous) depth-first order, and internal nodes may therefore provide iterators to the first and last LeafItems in their respective subtrees.
All mutation and access to a tree is provided through the Subtree and ConstSubtree classes; both thin iterators pointing into the Tree data structure.
Trees are kept in "sibling-contiguous" order, as replicated by this pseudocode:
traverse(node):
for each child c of node:
visit(c)
for each child c of node:
traverse(c)
which produces nodes in this order:
[node] ... [c1 c2 c3 c4 ...]
[children of c1]
[descendents of c1...]
[children of c2]
[descendents of c2...]
...
In this manner, a subtree may be distant from its root, but that entire subtree is contiguous. This also preserves the contiguousness of siblings.
| NodeItem | Type of data to be kept with internal tree nodes. |
| LeafItem | Type of data to be kept by leaf nodes. |
|
inline |
Convert a ConstSubtree into a Subtree by removing its constness.
Allows code with mutable access to the source tree to use ConstSubtree handles for any mutation with constant overhead.
If the supplied ConstSubtree does not belong to this Tree, then end() is returned.
1.9.2