Base class for all iterators into Trees. More...

#include <geomc/Tree.h>

Classes
class	QueryIterator
	A forward iterator over this type of Subtree, which visits all the nodes which pass the supplied `TestFn`. More...

Public Types
typedef std::conditional< Const, ConstSubtree< NodeItem, LeafItem >, Subtree< NodeItem, LeafItem > >::type	self_t
	Self type. A ConstSubtree if this is a const iterator; a Subtree otherwise.

typedef ConstItemRef	const_item_iterator
	Const iterator to `LeafItem`s.

typedef std::conditional< Const, ConstItemRef, ItemRef >::type	item_iterator
	A (possibly const) iterator to `LeafItem`s.

typedef self_t	iterator
	A (possibly const) iterator over subtrees.

typedef ConstSubtree< NodeItem, LeafItem >	const_iterator
	Const iterator over subtrees.

typedef NodeItem	value_type
	The tree's `NodeItem` type.

typedef std::conditional< Const, constNodeItem &, NodeItem & >::type	reference
	A (possibly const) reference to the tree's `NodeItem` type.

typedef const NodeItem &	const_reference
	A const reference to the tree's `NodeItem` type.

typedef std::conditional< Const, constNodeItem , NodeItem >::type	pointer
	A (possibly const) pointer to the tree's `NodeItem` type.

typedef Tree< NodeItem, LeafItem >	tree_t
	Type of tree into which this iterator points.

typedef std::iterator_traits< NodeRef >::difference_type	difference_type
	Iterator difference type.

typedef std::iterator_traits< NodeRef >::iterator_category	iterator_category
	Iterator category.

Public Member Functions
std::conditional< Const, consttree_t &, tree_t & >::type	tree () const
	Obtain the tree into which this iterator points.

self_t	parent () const
	Get the parent node. More...

bool	is_root () const
	Return whether this node is the root of the entire tree.

self_t &	operator+ ()
	`+i`: Become first child

self_t &	operator- ()
	`-i`: Become parent

self_t &	operator++ ()
	`++i`: Become next sibling

self_t &	operator-- ()
	`--i`: Become previous sibling

self_t	operator++ (int)
	`i++`: Become next sibling

self_t	operator-- (int)
	`i--`: Become previous sibling

bool	operator== (const self_t &other) const
	Returns `true` iff `other` points to the same node of the same tree.

bool	operator!= (const self_t &other) const
	Returns `true` iff `other` does not point to the same node of the same tree.

reference	operator* () const
	`*i`: Get the value of the current node

pointer	operator-> () const
	`i->...`: Access member of current node

index_t	node_count () const
	Number of direct child nodes.

index_t	item_count () const
	Number of leaf items in this subtree.

self_t	begin () const
	Get first child.

self_t	end () const
	Get last (off-end) child.

item_iterator	items_begin () const
	Get first object inside this subtree.

item_iterator	items_end () const
	Get last (off-end) object in this subtree. It is invalid to increment or dereference this iterator.

self_t	subtree_begin () const
	Return the first subtree in a sequence covering all the nodes in this subtree, beginning with the first child of this node.

self_t	subtree_end () const
	Return the last (off-end) subtree in the sequence of all subtrees below this node.

self_t	global_begin () const
	Return an iterator to the first item in the entire tree (the global root). More...

self_t	global_end () const
	Return an iterator to the last item in the entire tree (the global off-end node). More...

self_t	find_parent (const const_item_iterator &i) const
	Exhaustively search for the direct parent node of item `i` in this subtree. More...

template<bool BoundingFn>
self_t	find_parent (const const_item_iterator &i) const
	Search for the direct parent node of item `i` in this subtree, using `BoundingFn` to exclude subtrees which cannot contain `i`. More...

template<typename Key , typename BoundingFn , typename TestFn >
QueryIterator< self_t, Key, BoundingFn, TestFn >	query (const Key &key, BoundingFn bound, TestFn test=visit_all_nodes< Key >) const
	Return an iterator over all the subtrees for which `test(*subtree, key)` returns true. The iterator dereferences to `self_t`. More...

Static Public Member Functions
template<typename Key >
static bool	visit_all_nodes (const self_t &s, const Key &k)
	Convenience test function for `query()` which returns `true` on all nodes.

template<typename Key >
static bool	visit_all_leaf_nodes (const self_t &s, const Key &k)
	Convenience test function for `query()` which returns `true` on all nodes with zero child nodes.

Protected Types
typedef Tree< NodeItem, LeafItem >	Storage

typedef Storage::NodeRef	NodeRef

typedef Storage::ItemRef	ItemRef

typedef Storage::ItemRef	ConstItemRef

typedef Storage::Node	Node

typedef std::conditional< Const, constStorage , Storage >::type	StorageRef

Protected Member Functions
	SubtreeBase (const NodeRef &root, StorageRef storage)

NodeRef	node_successor (const NodeRef &node) const

ItemRef	item_successor (NodeRef node) const

Protected Attributes
StorageRef	_storage

NodeRef	_root

Detailed Description

template<typename NodeItem, typename LeafItem, bool Const = true>
class geom::SubtreeBase< NodeItem, LeafItem, Const >

Base class for all iterators into Trees.

A Subtree's lifetime is valid no longer than the Tree from which it came. Think of a Subtree like an iterator– it is a window into the parent tree.

Mutations to the source Tree generally invalidate end() iterators.

It is invalid to dereference, mutate, or increment an end() iterator.

Member Function Documentation

◆ find_parent() [1/2]

self_t find_parent ( const const_item_iterator & i ) const

inline

Exhaustively search for the direct parent node of item i in this subtree.

If i is not in the subtree under this node, then return end().

◆ find_parent() [2/2]

self_t find_parent ( const const_item_iterator & i ) const

inline

Search for the direct parent node of item i in this subtree, using BoundingFn to exclude subtrees which cannot contain i.

If i is not in the subtree under this node, then return end().

Because BoundingFn is templated, it may be inlined for performance.

Parameters

i	The item to find the parent of.

Template Parameters

BoundingFn A function which returns true if node n might possibly contain item i.

◆ global_begin()

self_t global_begin ( ) const

inline

Return an iterator to the first item in the entire tree (the global root).

Alias for this->tree().begin().

◆ global_end()

self_t global_end ( ) const

inline

Return an iterator to the last item in the entire tree (the global off-end node).

Alias for this->tree().end().

◆ parent()

self_t parent ( ) const

inline

Get the parent node.

The parent of tree()->root() is tree()->end().

◆ query()

QueryIterator< self_t, Key, BoundingFn, TestFn > query	(	const Key &	key,
		BoundingFn	bound,
		TestFn	test = `visit_all_nodes<Key>`
	)		const

inline

Return an iterator over all the subtrees for which test(*subtree, key) returns true. The iterator dereferences to self_t.

The iterator's sequence finishes on this node's end() node. (QueryIterators and Subtree nodes can be compared directly).

visit_all_nodes() and visit_all_leaf_nodes() are convenience static member functions of this class which can be passed to test().

Parameters

bound	A callable object which accepts a Subtree as its first argument, and a `Key` as its second, and returns `true` if that Subtree might contain objects which pass `test()` for that key. Children of Subtrees which do not pass `bound()` will be skipped.
test	A callable object which accepts a Subtree as its first argument and a `Key` as its second, and returns `true` if that Subtree should be visited by the iterator. If omitted, all nodes which pass `bound()` will be visited.

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

geomc/Tree.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation

◆ find_parent() [1/2]

◆ find_parent() [2/2]

◆ global_begin()

◆ global_end()

◆ parent()

◆ query()