SubtreeBase< NodeItem, LeafItem, Const > Class Template Reference

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 ConstItemRef	const_item_iterator
	Const iterator to LeafItems.
typedef ConstSubtree< NodeItem, LeafItem >	const_iterator
	Const iterator over subtrees.
typedef const NodeItem &	const_reference
	A const reference to the tree's NodeItem type.
typedef std::iterator_traits< NodeRef >::difference_type	difference_type
	Iterator difference type.
typedef std::conditional< Const, ConstItemRef, ItemRef >::type	item_iterator
	A (possibly const) iterator to LeafItems.
typedef self_t	iterator
	A (possibly const) iterator over subtrees.
typedef std::iterator_traits< NodeRef >::iterator_category	iterator_category
	Iterator category.
typedef std::conditional< Const, constNodeItem *, NodeItem * >::type	pointer
	A (possibly const) pointer to the tree's NodeItem type.
typedef std::conditional< Const, constNodeItem &, NodeItem & >::type	reference
	A (possibly const) reference to the tree's NodeItem type.
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 Tree< NodeItem, LeafItem >	tree_t
	Type of tree into which this iterator points.
typedef NodeItem	value_type
	The tree's NodeItem type.

Public Member Functions
self_t	begin () const
	Get first child.
self_t	end () const
	Get last (off-end) child.
self_t	find_parent (const const_item_iterator &i) const
	Exhaustively search for the direct parent node of item i in this subtree.
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.
self_t	global_begin () const
	Return an iterator to the first item in the entire tree (the global root).
self_t	global_end () const
	Return an iterator to the last item in the entire tree (the global off-end node).
bool	is_root () const
	Return whether this node is the root of the entire tree.
index_t	item_count () const
	Number of leaf items in this subtree.
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.
index_t	node_count () const
	Number of direct child nodes.
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
self_t &	operator+ ()
	+i: Become first child
self_t &	operator++ ()
	++i: Become next sibling
self_t	operator++ (int)
	i++: Become next sibling
self_t &	operator- ()
	-i: Become parent
self_t &	operator-- ()
	--i: Become previous sibling
self_t	operator-- (int)
	i--: Become previous sibling
pointer	operator-> () const
	i->...: Access member of current node
bool	operator== (const self_t &other) const
	Returns true iff other points to the same node of the same tree.
self_t	parent () const
	Get the parent node.
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.
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.
std::conditional< Const, consttree_t &, tree_t & >::type	tree () const
	Obtain the tree into which this iterator points.

Static Public Member Functions
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.
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.

Protected Types
typedef Storage::ItemRef	ConstItemRef
typedef Storage::ItemRef	ItemRef
typedef Storage::Node	Node
typedef Storage::NodeRef	NodeRef
typedef Tree< NodeItem, LeafItem >	Storage
typedef std::conditional< Const, constStorage *, Storage * >::type	StorageRef

Protected Member Functions
	SubtreeBase (const NodeRef &root, StorageRef storage)
ItemRef	item_successor (NodeRef node) const
NodeRef	node_successor (const NodeRef &node) const

Protected Attributes
NodeRef	_root
StorageRef	_storage

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]

template<typename NodeItem, typename LeafItem, bool Const = true>

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]

template<typename NodeItem, typename LeafItem, bool Const = true>

template<bool BoundingFn>

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()

template<typename NodeItem, typename LeafItem, bool Const = true>

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()

template<typename NodeItem, typename LeafItem, bool Const = true>

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()

template<typename NodeItem, typename LeafItem, bool Const = true>

self_t parent ( ) const

inline

Get the parent node.

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

query()

template<typename NodeItem, typename LeafItem, bool Const = true>

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

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