#include <Tree.h>
Collaboration diagram for Tree< stored_type, tree_type >:
Public Member Functions | |
virtual | ~Tree () |
Tree () | |
Tree (tree_type *par) | |
tree_type * | getRoot () |
int | getDepth () const |
int | getHeight () const |
bool | isRoot () const |
bool | isEmpty () |
bool | isLeaf () const |
tree_type | getChild (int index) |
stored_type | getElement (unsigned int index) |
virtual tree_type * | insert (stored_type newElement)=0 |
template<class InputIterator> | |
void | insertElements (InputIterator begin, InputIterator end) |
virtual tree_type * | remove (stored_type element)=0 |
virtual tree_type * | search (stored_type toSearch)=0 |
void | printTreeToStdOut (const int x, const void *par) const |
Protected Attributes | |
vector< stored_type > | elements |
vector< tree_type * > | children |
tree_type * | parent |
Definition at line 32 of file Tree.h.
Tree< stored_type, tree_type >::Tree | ( | ) | [inline] |
Base Tree constructor.
Definition at line 352 of file Tree.h.
References Tree< stored_type, tree_type >::parent.
Tree< stored_type, tree_type >::Tree | ( | tree_type * | par | ) | [inline] |
Tree constructor used to create non-root nodes.
par | The parent of the node under creation. |
Definition at line 364 of file Tree.h.
References Tree< stored_type, tree_type >::parent.
tree_type * Tree< stored_type, tree_type >::getRoot | ( | ) | [inline] |
Gets the root of the tree where this node belongs to.
Reimplemented in Basic_R_tree, Hilbert_R_tree, R_tree< r_tree_variation >, R_tree< Basic_R_tree >, and R_tree< Hilbert_R_tree >.
Definition at line 384 of file Tree.h.
References Tree< stored_type, tree_type >::isRoot(), and Tree< stored_type, tree_type >::parent.
int Tree< stored_type, tree_type >::getDepth | ( | ) | const [inline] |
Calculates and returns the depth of the current node.
Definition at line 392 of file Tree.h.
References Tree< stored_type, tree_type >::isRoot(), and Tree< stored_type, tree_type >::parent.
Referenced by Tree< stored_type, tree_type >::getHeight().
int Tree< stored_type, tree_type >::getHeight | ( | ) | const [inline] |
Calculates and returns the height of the current subtree. Take note that this function should only be called from the root node.
Definition at line 400 of file Tree.h.
References Tree< stored_type, tree_type >::children, Tree< stored_type, tree_type >::getDepth(), and Tree< stored_type, tree_type >::isLeaf().
bool Tree< stored_type, tree_type >::isRoot | ( | ) | const [inline] |
Checks if the current node is the root of its tree.
Definition at line 126 of file Tree.h.
Referenced by Tree< stored_type, tree_type >::getDepth(), Tree< stored_type, tree_type >::getRoot(), Basic_R_tree::handleOverflow(), and Basic_R_tree::remove().
bool Tree< stored_type, tree_type >::isEmpty | ( | ) | [inline] |
bool Tree< stored_type, tree_type >::isLeaf | ( | ) | const [inline] |
Checks if the current node is a leaf element (i.e., if the current node has no children).
Definition at line 138 of file Tree.h.
Referenced by Basic_R_tree::chooseLeaf(), Tree< stored_type, tree_type >::getHeight(), Basic_R_tree::insert(), Tree< stored_type, tree_type >::printTreeToStdOut(), Basic_R_tree::reinsert(), and Basic_R_tree::remove().
tree_type Tree< stored_type, tree_type >::getChild | ( | int | index | ) | [inline] |
Returns a requested child node to the caller.
index | The child number of the node the caller wants returned. |
Definition at line 415 of file Tree.h.
References Tree< stored_type, tree_type >::children.
stored_type Tree< stored_type, tree_type >::getElement | ( | unsigned int | index | ) | [inline] |
Returns a requested element to the caller.
index | The element number of the element the caller wants returned. |
Definition at line 425 of file Tree.h.
References Tree< stored_type, tree_type >::elements.
virtual tree_type* Tree< stored_type, tree_type >::insert | ( | stored_type | newElement | ) | [pure virtual] |
Inserts elements in a Tree-type specific way. Virtual function.
newElement | Pointer to the element the caller wants stored |
Implemented in Basic_R_tree, Hilbert_R_tree, Spatial_Tree< tree_type, bb_type, container_type >, Spatial_Tree< r_tree_variation, BB_type, BB_container >, Spatial_Tree< Hilbert_R_tree, BB_type, BB_container >, and Spatial_Tree< Basic_R_tree, BB_type, BB_container >.
Referenced by Tree< BB_container *, r_tree_variation >::insertElements().
void Tree< stored_type, tree_type >::insertElements | ( | InputIterator | begin, | |
InputIterator | end | |||
) | [inline] |
virtual tree_type* Tree< stored_type, tree_type >::remove | ( | stored_type | element | ) | [pure virtual] |
Removes elements from the tree. This is also a tree-type specific operation and thus is virtual here. Typically requires use of the search() function, which is also virtual.
element | Pointer to the element to be removed |
Implemented in Basic_R_tree, Hilbert_R_tree, Spatial_Tree< tree_type, bb_type, container_type >, Spatial_Tree< r_tree_variation, BB_type, BB_container >, Spatial_Tree< Hilbert_R_tree, BB_type, BB_container >, and Spatial_Tree< Basic_R_tree, BB_type, BB_container >.
virtual tree_type* Tree< stored_type, tree_type >::search | ( | stored_type | toSearch | ) | [pure virtual] |
Searches a specific element in the tree. Search is a tree-specific operation and thus is virtual here.
toSearch | Pointer to the element we want to find in the tree |
Implemented in Basic_R_tree, and Hilbert_R_tree.
void Tree< stored_type, tree_type >::printTreeToStdOut | ( | const int | x, | |
const void * | par | |||
) | const [inline] |
Reimplemented in R_tree< r_tree_variation >, R_tree< Basic_R_tree >, and R_tree< Hilbert_R_tree >.
Definition at line 313 of file Tree.h.
References Tree< stored_type, tree_type >::children, Tree< stored_type, tree_type >::isLeaf(), and Tree< stored_type, tree_type >::parent.
vector< stored_type > Tree< stored_type, tree_type >::elements [protected] |
Elements stored at this node.
Definition at line 36 of file Tree.h.
Referenced by Hilbert_R_tree::buildNode(), Basic_R_tree::buildNode(), Tree< stored_type, tree_type >::getElement(), Hilbert_R_tree::handleOverflow(), Basic_R_tree::handleOverflow(), Basic_R_tree::insert(), Tree< BB_container *, r_tree_variation >::isEmpty(), and Basic_R_tree::remove().
vector< tree_type* > Tree< stored_type, tree_type >::children [protected] |
Children of this node.
Definition at line 39 of file Tree.h.
Referenced by Hilbert_R_tree::buildNode(), Basic_R_tree::buildNode(), Tree< stored_type, tree_type >::getChild(), Tree< stored_type, tree_type >::getHeight(), Hilbert_R_tree::handleOverflow(), Tree< BB_container *, r_tree_variation >::isEmpty(), Tree< BB_container *, r_tree_variation >::isLeaf(), Basic_R_tree::makeNewRoot(), Tree< stored_type, tree_type >::printTreeToStdOut(), and Basic_R_tree::remove().
tree_type* Tree< stored_type, tree_type >::parent [protected] |
Pointer to parent node.
Definition at line 47 of file Tree.h.
Referenced by Tree< stored_type, tree_type >::getDepth(), Tree< stored_type, tree_type >::getRoot(), Hilbert_R_tree::handleOverflow(), Basic_R_tree::handleOverflow(), Basic_R_tree::insert(), Tree< BB_container *, r_tree_variation >::isRoot(), Basic_R_tree::makeNewRoot(), Tree< stored_type, tree_type >::printTreeToStdOut(), Basic_R_tree::remove(), and Tree< stored_type, tree_type >::Tree().