A non-const iterator to a subtree. More...

#include <geomc/Tree.h>

Inheritance diagram for Subtree< NodeItem, LeafItem >:

Public Types
typedef ConstItemRef	const_item_iterator
	Const iterator to `LeafItem`s.

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 `LeafItem`s.

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 Subtree< NodeItem, LeafItem >	self_t

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
	Subtree (const Subtree< NodeItem, LeafItem > &other)=default
	Construct a duplicate iterator to the same node of the same tree.

self_t	begin () const
	Get first child.

self_t	begin () const
	Get first child.

self_t	end () const
	Get last (off-end) 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.

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

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	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_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).

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.

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.

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_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.

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.

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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.

self_t	parent () const
	Get the parent node.

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`.

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_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	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.

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

Mutation functions
template<typename ... Args>
self_t	insert_child_node (const self_t &insert_before, Args &&... args) const
	Insert a new tree node under this one, to the left of `insert_before`.

self_t	insert_child_node (const NodeItem &obj) const
	Convenience function to insert a new child node at the end of this node's children.

template<typename NodeItemIterator>
self_t	insert_child_nodes (const self_t &insert_before, NodeItemIterator i_begin, const NodeItemIterator &i_end) const
	Insert new tree nodes to the left of `insert_before`, under this node. Return the first newly created node.

template<typename NodeItemIterator>
self_t	insert_child_nodes (const NodeItemIterator &i_begin, const NodeItemIterator &i_end) const
	Convenience function to insert multiple new child nodes at the end of this node's children.

template<typename ... Args>
item_iterator	insert_item (const item_iterator &insert_before, Args &&... args) const
	Insert an item under this node.

item_iterator	insert_item (const LeafItem &item) const
	Convenience function to insert a new item at the end.

template<typename LeafItemIterator>
item_iterator	insert_items (const item_iterator &insert_before, const LeafItemIterator begin_item, const LeafItemIterator &end_item, index_t *new_item_count=nullptr) const
	Insert multiple leaf items into this node.

template<typename LeafItemIterator>
item_iterator	insert_items (const LeafItemIterator &begin_item, const LeafItemIterator &end_item) const
	Convenience function to insert multiple new items at the end of this node's item list.

self_t	adopt (const const_iterator &other_subtree, const self_t &insert_before) const
	Make a copy of `other_subtree` and insert it as a child of this node immediately before `insert_before`.

template<typename Func, typename P, typename ... Args>
self_t	split (Func compare, P pivot, Args &&... args) const
	Split this node into two sibling nodes.

item_iterator	erase (const item_iterator &item, bool *success=nullptr) const
	Remove an item from this subtree.

void	clear () const
	Empty this node of all child nodes and descendent items.

self_t	erase (const self_t &child, bool *success=nullptr) const
	Remove the subtree and its root at `child`, including all its leaf items.

void	flatten () const
	Recursively remove all the children of this node, and take ownership of all items beneath them.

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

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.

static bool	visit_all_nodes (const self_t &s, const Key &k)
	Convenience test function for `query()` which returns `true` on all nodes.

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 SubtreeBase< NodeItem, LeafItem, false >	base_t

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
	Subtree (const base_t &other)

	Subtree (const NodeRef &root, StorageRef storage)

ItemRef	item_successor (NodeRef node) const

ItemRef	item_successor (NodeRef node) const

NodeRef	node_successor (const NodeRef &node) const

NodeRef	node_successor (const NodeRef &node) const

void	recalculate_references () const

Protected Attributes
NodeRef	_root

NodeRef	_root

StorageRef	_storage

StorageRef	_storage

Friends
class	SubtreeBase< NodeItem, LeafItem, false >

class	Tree< NodeItem, LeafItem >

Detailed Description

template<typename NodeItem, typename LeafItem>
class geom::Subtree< NodeItem, LeafItem >

A non-const iterator to a subtree.

Member Function Documentation

◆ adopt()

template<typename NodeItem, typename LeafItem>

self_t adopt	(	const const_iterator &	other_subtree,
		const self_t &	insert_before ) const

inline

Make a copy of other_subtree and insert it as a child of this node immediately before insert_before.

If insert_before is not a child or end-child of this node, the tree is unchanged and end() is returned.

Invalidates all end() subtrees.

Parameters

other_subtree	The subtree to copy and adopt as a child.
insert_before	The child of this node before which to insert the new subtree.

Returns: An iterator pointing at the root of the new adopted subtree.

◆ erase() [1/2]

template<typename NodeItem, typename LeafItem>

item_iterator erase	(	const item_iterator &	item,
		bool *	success = nullptr ) const

inline

Remove an item from this subtree.

If item is not in the subtree, or if this subtree is not a leaf node, the tree will be unchanged.

Invalidates the iterator to this item, and potentially any end() item_iterators.

Parameters

item	The item to delete; a direct child of this node.
success	Optional return value pointer to be filled with `true` if the item was deleted; `false` if the tree is unchanged.

Returns: An iterator pointing to the position of the item just beyond the one that was deleted. This will be items_end() if the deleted item was the last one in its parent node.

◆ erase() [2/2]

template<typename NodeItem, typename LeafItem>

self_t erase	(	const self_t &	child,
		bool *	success = nullptr ) const

inline

Remove the subtree and its root at child, including all its leaf items.

If child is not a direct child of this node, the tree is unchanged.

Parameters

success An optional return value pointer; to be filled with true if the child was deleted; false if the tree is unchanged.

Returns: An iterator pointing to the position of the node following the deleted one (which may be end()).

◆ find_parent() [1/4]

self_t find_parent ( const const_item_iterator & i ) const

inlineinherited

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/4]

self_t find_parent ( const const_item_iterator & i ) const

inlineinherited

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() [3/4]

self_t find_parent ( const const_item_iterator & i ) const

inlineinherited

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.

◆ find_parent() [4/4]

self_t find_parent ( const const_item_iterator & i ) const

inlineinherited

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() [1/2]

self_t global_begin ( ) const

inlineinherited

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

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

◆ global_begin() [2/2]

self_t global_begin ( ) const

inlineinherited

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

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

◆ global_end() [1/2]

self_t global_end ( ) const

inlineinherited

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

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

◆ global_end() [2/2]

self_t global_end ( ) const

inlineinherited

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

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

◆ insert_child_node() [1/2]

template<typename NodeItem, typename LeafItem>

self_t insert_child_node ( const NodeItem & obj ) const

inline

Convenience function to insert a new child node at the end of this node's children.

Parameters

obj	NodeItem to insert into the new node.

◆ insert_child_node() [2/2]

template<typename NodeItem, typename LeafItem>

template<typename ... Args>

self_t insert_child_node	(	const self_t &	insert_before,
		Args &&...	args ) const

inline

Insert a new tree node under this one, to the left of insert_before.

If this node was previously empty, then its new first child will contain all of its LeafItems (this is to ensure those leaf items all have a parent which is a leaf node). Otherwise, the new node will be empty of any LeafItems.

If insert_before is the root node, or if insert_before is not a direct child (or end-child) of this node, then the tree is unaffected and end() is returned. Otherwise, the new node is returned.

Potentially invalidates the end() of other subtrees, or the begin() of this subtree if insert_before is begin().

Parameters

insert_before	A subtree pointing to a child or end-child of this node.
args	Construction arguments for the new `NodeItem`.

Returns: The newly created node, or end() if the node could not be created.

◆ insert_child_nodes()

template<typename NodeItem, typename LeafItem>

template<typename NodeItemIterator>

self_t insert_child_nodes	(	const self_t &	insert_before,
		NodeItemIterator	i_begin,
		const NodeItemIterator &	i_end ) const

inline

Insert new tree nodes to the left of insert_before, under this node. Return the first newly created node.

If this node was previously empty, then its new first child will contain all its LeafItems (this is to ensure those leaf items all have a parent which is a leaf node). All other new nodes will be empty of any LeafItems.

If insert_before is the root node, or if insert_before is not a child (or end-child) of this node, then the tree is unaffected and end() is returned. Likewise, if no new nodes were inserted, end() is returned. Otherwise, the first new node is returned.

Potentially invalidates the end() of other subtrees, or the begin() of this subtree if insert_before is begin().

Parameters

insert_before	A Subtree pointing to the sibling just after the last new node to be inserted.
i_begin	A forward iterator to the first NodeItem to be inserted.
i_end	A forward iterator just beyond the last NodeItem to be inserted.

Returns: The first newly created node, or end() if no new nodes were created.

◆ insert_item()

template<typename NodeItem, typename LeafItem>

template<typename ... Args>

item_iterator insert_item	(	const item_iterator &	insert_before,
		Args &&...	args ) const

inline

Insert an item under this node.

The new item will be inserted before the item at insert_before, which must belong to this node, otherwise the behavior is undefined. It is permissible for insert_before to be this node's items_begin() or items_end().

This must be a leaf node; i.e. one with no child nodes, so that placement of the new objects is not abiguous. If this is not a leaf node, the tree is unchanged.

Potentially invalidates the items_end() of other subtrees, or the items_begin() of this subtree if insert_before is items_begin().

Parameters

insert_before	Item belonging to `parent` which the new items are to be inserted before.
args	New `LeafItem` to be inserted, or constructor arguments for the new `LeafItem`.

Returns: An iterator to the first newly placed item if any were placed; items_end() otherwise.

◆ insert_items()

template<typename NodeItem, typename LeafItem>

template<typename LeafItemIterator>

item_iterator insert_items	(	const item_iterator &	insert_before,
		const LeafItemIterator	begin_item,
		const LeafItemIterator &	end_item,
		index_t *	new_item_count = nullptr ) const

inline

Insert multiple leaf items into this node.

The new items will be inserted before the item at insert_before, in the same order. insert_before must belong to the given node, otherwise the behavior is undefined. It is permissible for insert_before to be the node's items_begin() or items_end().

This must be a leaf node; i.e. one with no child nodes, so that placement of the new objects is not abiguous. If this is not a leaf node, the tree is unchanged.

Invalidates all end() item_iterators.

Parameters

parent	Leaf node under which the new items will be inserted.
insert_before	Item belonging to `parent` which the new items are to be inserted before.
first_item	Forward iterator to first `LeafItem` to be inserted.
off_end_item	Forward iterator just beyond the last `LeafItem` to be inserted.
new_item_count	Optional return pointer to receive the count of newly placed objects.

Returns: An iterator to the first newly placed item if any were placed; items_end() otherwise.

◆ parent() [1/2]

self_t parent ( ) const

inlineinherited

Get the parent node.

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

◆ parent() [2/2]

self_t parent ( ) const

inlineinherited

Get the parent node.

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

◆ query() [1/2]

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

inlineinherited

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.

◆ query() [2/2]

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

inlineinherited

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.

◆ split()

template<typename NodeItem, typename LeafItem>

template<typename Func, typename P, typename ... Args>

self_t split	(	Func	compare,
		P	pivot,
		Args &&...	args ) const

inline

Split this node into two sibling nodes.

A new node will be created just before this one, under the same parent, and this node's items will be split between them according to the result of compare(item, pivot): If the comparison is less than zero, the item will be moved to the left (new) node. Otherwise, it will remain in the right (existing) node.

The split node must not be the root, must have no children, and must contain at least two items. If any of these is the case, the tree will not be changed and the off-end node will be returned.

All iterators to the items under this node are invalidated by this operation, as well as potentially any end() item_iterators.

Parameters

compare	A callable object `compare(a,b)` which accepts a `LeafItem` as its left argument and a `P` as its right argument, and returns a signed number (negative for `a < b`, positive for `a > b`, zero for equality).
args	Constructor arguments for the `NodeItem` object to be assigned to the newly-created (low) node.

Returns: The newly created sibling, or the off-end node if this is the root node or has child nodes.

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

geomc/Tree.h

Public Types

Public Member Functions

Static Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Function Documentation

◆ adopt()

◆ erase() [1/2]

◆ erase() [2/2]

◆ find_parent() [1/4]

◆ find_parent() [2/4]

◆ find_parent() [3/4]

◆ find_parent() [4/4]

◆ global_begin() [1/2]

◆ global_begin() [2/2]

◆ global_end() [1/2]

◆ global_end() [2/2]

◆ insert_child_node() [1/2]

◆ insert_child_node() [2/2]

◆ insert_child_nodes()

◆ insert_item()

◆ insert_items()

◆ parent() [1/2]

◆ parent() [2/2]

◆ query() [1/2]

◆ query() [2/2]

◆ split()