A dynamic tree of arbitrary arity. More...

#include <geomc/Tree.h>

Public Member Functions
	Tree ()
	Construct an empty Tree.

	Tree (const ConstSubtree< NodeItem, LeafItem > &other)
	Construct a new tree from the given subtree.

	Tree (const Tree< NodeItem, LeafItem > &other)
	Make a copy of the given tree.

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 (Tree< NodeItem, LeafItem > &&other)=default
	Default move constructor.

Subtree< NodeItem, LeafItem >	begin ()
	Return an iterator to the first item in the tree (root), 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.

Subtree< NodeItem, LeafItem >	end ()
	Return an iterator to the last (off-end) item in the tree, 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.

size_t	item_count () const
	Total number of items in this Tree.

bool	operator!= (const Tree< NodeItem, LeafItem > &other) const
	Tree inequality.

bool	operator== (const Tree< NodeItem, LeafItem > &other) const
	Tree equality.

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.

size_t	size () const
	Total number of nodes in this Tree.

Subtree< NodeItem, LeafItem >	subtree (ConstSubtree< NodeItem, LeafItem > &i)
	Convert a ConstSubtree into a Subtree by removing its constness.

Protected Member Functions
void	recalculate_tree ()

void	update_boundary_items (NodeRef leaf, ItemRef new_first, ItemRef new_last, index_t delta_items)

Friends
class	ConstSubtree< NodeItem, LeafItem >

class	Subtree< NodeItem, LeafItem >

class	SubtreeBase< NodeItem, LeafItem, false >

class	SubtreeBase< NodeItem, LeafItem, true >

Detailed Description

template<typename NodeItem, typename LeafItem>
class geom::Tree< 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.

Template Parameters

NodeItem	Type of data to be kept with internal tree nodes.
LeafItem	Type of data to be kept by leaf nodes.

Member Function Documentation

◆ subtree()

template<typename NodeItem, typename LeafItem>

Subtree< NodeItem, LeafItem > subtree ( ConstSubtree< NodeItem, LeafItem > & i )

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.

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

geomc/Tree.h

Public Member Functions

Protected Member Functions

Friends

Detailed Description

Member Function Documentation

◆ subtree()