geomc 1.0
A c++ linear algebra template library
Public Types | Public Member Functions | Static Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | Friends | List of all members
Subtree< NodeItem, LeafItem > Class Template Reference

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

#include <geomc/Tree.h>

Inheritance diagram for Subtree< NodeItem, LeafItem >:
SubtreeBase< NodeItem, LeafItem, false >

Public Types

typedef Subtree< NodeItem, LeafItem > self_t
 
typedef ConstItemRef const_item_iterator
 Const iterator to LeafItems.
 
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 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

 Subtree (const Subtree< NodeItem, LeafItem > &other)=default
 Construct a duplicate iterator to the same node of the same tree.
 
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_toperator+ ()
 +i: Become first child
 
self_toperator- ()
 -i: Become parent
 
self_toperator++ ()
 ++i: Become next sibling
 
self_t operator++ (int)
 i++: Become next sibling
 
self_toperator-- ()
 --i: Become previous 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...
 
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...
 
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...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
template<typename Func , typename P , typename ... Args>
self_t split (Func compare, P pivot, Args &&... args) const
 Split this node into two sibling nodes. More...
 
item_iterator erase (const item_iterator &item, bool *success=nullptr) const
 Remove an item from this subtree. More...
 
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. More...
 
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_nodes (const self_t &s, const Key &k)
 Convenience test function for query() which returns true on all 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.
 

Protected Types

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

 Subtree (const base_t &other)
 
 Subtree (const NodeRef &root, StorageRef storage)
 
void recalculate_references () const
 
NodeRef node_successor (const NodeRef &node) const
 
ItemRef item_successor (NodeRef node) const
 

Protected Attributes

StorageRef _storage
 
NodeRef _root
 

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

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_subtreeThe subtree to copy and adopt as a child.
insert_beforeThe 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]

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
itemThe item to delete; a direct child of this node.
successOptional 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]

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
successAn 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

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
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
iThe item to find the parent of.
Template Parameters
BoundingFnA function which returns true if node n might possibly contain item i.

◆ 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]

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
objNodeItem to insert into the new node.

◆ insert_child_node() [2/2]

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_beforeA subtree pointing to a child or end-child of this node.
argsConstruction arguments for the new NodeItem.
Returns
The newly created node, or end() if the node could not be created.

◆ insert_child_nodes()

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_beforeA Subtree pointing to the sibling just after the last new node to be inserted.
i_beginA forward iterator to the first NodeItem to be inserted.
i_endA 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()

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_beforeItem belonging to parent which the new items are to be inserted before.
argsNew 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()

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
parentLeaf node under which the new items will be inserted.
insert_beforeItem belonging to parent which the new items are to be inserted before.
first_itemForward iterator to first LeafItem to be inserted.
off_end_itemForward iterator just beyond the last LeafItem to be inserted.
new_item_countOptional 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
boundA 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.
testA 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()

self_t split ( Func  compare,
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
compareA 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).
argsConstructor 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: