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 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 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	end () const
	Get last (off-end) child.
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
	Exhaustively search for the direct parent node of item i in this subtree.
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.
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.
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_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
NodeRef	node_successor (const NodeRef &node) const
void	recalculate_references () const

Protected Attributes
NodeRef	_root
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/2]

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

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

◆ global_begin()

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

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

self_t parent ( ) const

inlineinherited

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

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

◆ find_parent() [2/2]

◆ global_begin()

◆ global_end()

◆ insert_child_node() [1/2]

◆ insert_child_node() [2/2]

◆ insert_child_nodes()

◆ insert_item()

◆ insert_items()

◆ parent()

◆ query()

◆ split()