geomc 1.0
A c++ linear algebra template library
|
A non-const iterator to a subtree. More...
#include <geomc/Tree.h>
Public Types | |
typedef Subtree< NodeItem, LeafItem > | self_t |
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 | |
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_t & | operator+ () |
+i : Become first child | |
self_t & | operator- () |
-i : Become parent | |
self_t & | operator++ () |
++i : Become next sibling | |
self_t | operator++ (int) |
i++ : Become next sibling | |
self_t & | operator-- () |
--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 > |
A non-const iterator to a subtree.
|
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.
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. |
|
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_iterator
s.
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. |
items_end()
if the deleted item was the last one in its parent node. 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.
success | An optional return value pointer; to be filled with true if the child was deleted; false if the tree is unchanged. |
end()
).
|
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()
.
|
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.
i | The item to find the parent of. |
BoundingFn | A function which returns true if node n might possibly contain item i . |
|
inlineinherited |
|
inlineinherited |
|
inline |
Convenience function to insert a new child node at the end of this node's children.
obj | NodeItem to insert into the new node. |
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 LeafItem
s (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 LeafItem
s.
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()
.
insert_before | A subtree pointing to a child or end-child of this node. |
args | Construction arguments for the new NodeItem . |
end()
if the node could not be created.
|
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 LeafItem
s (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 LeafItem
s.
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()
.
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. |
end()
if no new nodes were created.
|
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()
.
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 . |
items_end()
otherwise.
|
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_iterator
s.
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. |
items_end()
otherwise.
|
inlineinherited |
|
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. (QueryIterator
s 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()
.
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. |
|
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_iterator
s.
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. |