Tree< stored_type, tree_type > Class Template Reference

#include <Tree.h>

Collaboration diagram for Tree< stored_type, tree_type >:

Collaboration graph
[legend]
List of all members.

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

Detailed Description

template<typename stored_type, typename tree_type>
class Tree< stored_type, tree_type >

Abstract representation of a tree. This is a tree in its most general form; each node can any number of children and can store any number of elements, regardless of being a leaf or not.

Definition at line 32 of file Tree.h.


Constructor & Destructor Documentation

template<typename stored_type, typename tree_type>
virtual Tree< stored_type, tree_type >::~Tree (  )  [inline, virtual]

Base tree deconstructor.

Definition at line 75 of file Tree.h.

template<typename stored_type, typename tree_type>
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.

template<typename stored_type, typename tree_type>
Tree< stored_type, tree_type >::Tree ( tree_type *  par  )  [inline]

Tree constructor used to create non-root nodes.

Parameters:
par The parent of the node under creation.

Definition at line 364 of file Tree.h.

References Tree< stored_type, tree_type >::parent.


Member Function Documentation

template<typename stored_type, typename tree_type>
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.

template<typename stored_type, typename tree_type>
int Tree< stored_type, tree_type >::getDepth (  )  const [inline]

Calculates and returns the depth of the current node.

Returns:
The depth of this 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().

template<typename stored_type, typename tree_type>
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.

See also:
getDepth()
Returns:
The height of the current subtree

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

template<typename stored_type, typename tree_type>
bool Tree< stored_type, tree_type >::isRoot (  )  const [inline]

Checks if the current node is the root of its tree.

Returns:
Whether or not the current node is the root.

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

template<typename stored_type, typename tree_type>
bool Tree< stored_type, tree_type >::isEmpty (  )  [inline]

Checks if the subtree (the tree with the current node as root), is empty (i.e., contains no elemenents and has no children).

Definition at line 132 of file Tree.h.

template<typename stored_type, typename tree_type>
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().

template<typename stored_type, typename tree_type>
tree_type Tree< stored_type, tree_type >::getChild ( int  index  )  [inline]

Returns a requested child node to the caller.

Parameters:
index The child number of the node the caller wants returned.
Returns:
The requested node.

Definition at line 415 of file Tree.h.

References Tree< stored_type, tree_type >::children.

template<typename stored_type, typename tree_type>
stored_type Tree< stored_type, tree_type >::getElement ( unsigned int  index  )  [inline]

Returns a requested element to the caller.

Parameters:
index The element number of the element the caller wants returned.
Returns:
The requested element.

Definition at line 425 of file Tree.h.

References Tree< stored_type, tree_type >::elements.

template<typename stored_type, typename tree_type>
virtual tree_type* Tree< stored_type, tree_type >::insert ( stored_type  newElement  )  [pure virtual]

Inserts elements in a Tree-type specific way. Virtual function.

Parameters:
newElement Pointer to the element the caller wants stored
Returns:
The root of the tree after the operation is done

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

template<typename stored_type, typename tree_type>
template<class InputIterator>
void Tree< stored_type, tree_type >::insertElements ( InputIterator  begin,
InputIterator  end 
) [inline]

Inserts a range of polytopes into the tree structure.

Parameters:
begin An iterator at the first polytope to be added.
end An iterator at one location past the last iterator to be added.

Definition at line 175 of file Tree.h.

template<typename stored_type, typename tree_type>
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.

Parameters:
element Pointer to the element to be removed
Returns:
The root of the tree after the operation is done

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

template<typename stored_type, typename tree_type>
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.

Parameters:
toSearch Pointer to the element we want to find in the tree
Returns:
Pointer to the node at which the to searched object was found

Implemented in Basic_R_tree, and Hilbert_R_tree.

template<typename stored_type, typename tree_type>
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.


Member Data Documentation

template<typename stored_type, typename tree_type>
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().

template<typename stored_type, typename tree_type>
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().

template<typename stored_type, typename tree_type>
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().


The documentation for this class was generated from the following file:
Generated on Sat Oct 13 17:34:43 2007 for R-Tree by  doxygen 1.5.2