Basic_R_tree Class Reference

#include <basic-r-tree.h>

Inherits R_tree< Basic_R_tree >.

Inheritance diagram for Basic_R_tree:

Inheritance graph
[legend]
Collaboration diagram for Basic_R_tree:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 Basic_R_tree ()
 Basic_R_tree (R_tree_props *props)
virtual Basic_R_treeremove (BB_container *element)
virtual Basic_R_treegetRoot ()
virtual const Basic_R_treegetRoot () const
virtual Basic_R_treeinsert (BB_container *element)
virtual Basic_R_treesearch (BB_container *element)

Protected Types

typedef vector< Basic_R_tree
* >::const_iterator 
childIterator
typedef vector< BB_container
* >::const_iterator 
elemIterator

Protected Member Functions

Basic_R_treechooseLeaf (Basic_R_tree *v, const BB_type bb) const
Basic_R_treehandleOverflow (Basic_R_tree *node, BB_container *element)
void linearSplitElements (vector< BB_container * > oldItems, BB_container *newItem, vector< BB_container * > *set_one, vector< BB_container * > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension)
void linearSplitNodes (vector< Basic_R_tree * > oldItems, Basic_R_tree *newItem, vector< Basic_R_tree * > *set_one, vector< Basic_R_tree * > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension)
void quadraticSplitElements (vector< BB_container * > oldItems, BB_container *newItem, vector< BB_container * > *set_one, vector< BB_container * > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension)
void quadraticSplitNodes (vector< Basic_R_tree * > oldItems, Basic_R_tree *newItem, vector< Basic_R_tree * > *set_one, vector< Basic_R_tree * > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension)
Basic_R_treeinsert (Basic_R_tree *node)
Basic_R_treebuildNode (vector< BB_container * > input, BB_type *newMbr) const
Basic_R_treebuildNode (vector< Basic_R_tree * > input, BB_type *newMbr) const
void reinsert (vector< Basic_R_tree * > s)
void reinsert (Basic_R_tree *walk, Basic_R_tree *at)
Basic_R_treehandleOverflow (Basic_R_tree *node)
Basic_R_treemakeNewRoot (Basic_R_tree *child)
void setChildren (vector< Basic_R_tree * > newChildren, BB_type *newMbr)
void removeChild (Basic_R_tree *toRemove)
Basic_R_treeremove (Basic_R_tree *node, BB_container *element)

Detailed Description

Basic R-tree implementation as in [GUT84].

Definition at line 20 of file basic-r-tree.h.


Member Typedef Documentation

typedef vector< Basic_R_tree* >::const_iterator Basic_R_tree::childIterator [protected]

Defines the type of an iterator on the child nodes of this tree, const variation.

Reimplemented from R_tree< Basic_R_tree >.

Definition at line 25 of file basic-r-tree.h.

typedef vector< BB_container* >::const_iterator Basic_R_tree::elemIterator [protected]

Defines the type of an iterator on the elements stored at this node, const variation.

Definition at line 28 of file basic-r-tree.h.


Constructor & Destructor Documentation

Basic_R_tree::Basic_R_tree (  )  [inline]

Base constructor. Calls super constructor.

See also:
R_tree::R_tree()

Definition at line 229 of file basic-r-tree.h.

Referenced by buildNode(), and makeNewRoot().

Basic_R_tree::Basic_R_tree ( R_tree_props props  )  [inline]

Base constructor, does not create its own property class.

Parameters:
props The properties the current R-tree will use.

Definition at line 236 of file basic-r-tree.h.


Member Function Documentation

Basic_R_tree * Basic_R_tree::chooseLeaf ( Basic_R_tree v,
const BB_type  bb 
) const [protected]

This algorithm chooses a leaf to add an element with a given MBR to.

Parameters:
v The (sub)tree at which to add the element
bb The MBR of the element to be added
Returns:
A pointer to the node where the element should be added

Definition at line 1713 of file basic-r-tree.h.

References R_tree< Basic_R_tree >::areaEnlargement(), Tree< BB_container *, Basic_R_tree >::children, Tree< stored_type, tree_type >::isLeaf(), and Cart::Volume().

Referenced by insert().

Basic_R_tree * Basic_R_tree::handleOverflow ( Basic_R_tree node,
BB_container element 
) [protected]

This algorithm handles an overflow occuring at a given node at which a given container was to be added. This algorithm may employ different splitting strategies, as defined by the flag SPLIT_STRATEGY in r-tree.h. This algorithms results in the given node to be split in two. Both of these new nodes are added to the parent node. If this causes an overflow there as well, the handleOverflow algorithm is called recursively. If the given node does not have a parent (i.e., is root), a new root node is constructed with the two nodes resulting from the split as its children.

Parameters:
node The full node at which the given element should be added
element The to be added element
Returns:
The (new) tree root

Definition at line 1607 of file basic-r-tree.h.

References buildNode(), Tree< stored_type, tree_type >::elements, Tree< BB_container *, Basic_R_tree >::elements, EXPONENTIAL_SPLIT, Cubic_Bounding_Box::getDimension(), insert(), Tree< stored_type, tree_type >::isRoot(), LINEAR_SPLIT, linearSplitElements(), makeNewRoot(), Tree< stored_type, tree_type >::parent, QUADRATIC_SPLIT, quadraticSplitElements(), R_tree< r_tree_variation >::setElements(), and SPLIT_STRATEGY.

Referenced by insert().

void Basic_R_tree::linearSplitElements ( vector< BB_container * >  oldItems,
BB_container newItem,
vector< BB_container * > *  set_one,
vector< BB_container * > *  set_two,
BB_type mbr_one,
BB_type mbr_two,
int  dimension 
) [protected]

This algorithm does the actual splitting according to the linearSplit algorithm. It creates two sets which denote the resulting split. The algorithm as implemented as present, only considers the ordering based on maximum and minimum coordinates (and not, for example, center coordinates).

Parameters:
oldItems A set of items to which a new item is to be added.
newItem The new item to be added.
set_one The first split set.
set_two The second set split set.
mbr_one Pointer to where the first set MBR should be stored
mbr_two Pointer to where the second set MBR should be stored
dimension The item dimensions

Definition at line 1320 of file basic-r-tree.h.

References Cubic_Bounding_Box::_mins, R_tree< Basic_R_tree >::areaEnlargement(), Cubic_Bounding_Box::become(), R_tree_props::minimum, R_tree< Basic_R_tree >::properties, Cubic_Bounding_Box::toString(), and Cubic_Bounding_Box::unite().

Referenced by handleOverflow().

void Basic_R_tree::linearSplitNodes ( vector< Basic_R_tree * >  oldItems,
Basic_R_tree newItem,
vector< Basic_R_tree * > *  set_one,
vector< Basic_R_tree * > *  set_two,
BB_type mbr_one,
BB_type mbr_two,
int  dimension 
) [protected]

This algorithm does the actual splitting according to the linearSplit algorithm. It creates two sets which denote the resulting split. The algorithm as implemented as present, only considers the ordering based on maximum and minimum coordinates (and not, for example, center coordinates).

Parameters:
oldItems A set of items to which a new item is to be added.
newItem The new item to be added.
set_one The first split set.
set_two The second set split set.
mbr_one Pointer to where the first set MBR should be stored
mbr_two Pointer to where the second set MBR should be stored
dimension The item dimensions

Definition at line 1034 of file basic-r-tree.h.

References Cubic_Bounding_Box::_mins, R_tree< Basic_R_tree >::areaEnlargement(), Cubic_Bounding_Box::become(), R_tree< Basic_R_tree >::mbr, R_tree< r_tree_variation >::mbr, R_tree_props::minimum, R_tree< Basic_R_tree >::properties, and Cubic_Bounding_Box::toString().

Referenced by handleOverflow().

void Basic_R_tree::quadraticSplitElements ( vector< BB_container * >  oldItems,
BB_container newItem,
vector< BB_container * > *  set_one,
vector< BB_container * > *  set_two,
BB_type mbr_one,
BB_type mbr_two,
int  dimension 
) [protected]

This algorithm does the actual splitting according to the quadraticSplit algorithm. It creates two sets which denote the resulting split. The algorithm as implemented as present, only considers the ordering based on maximum and minimum coordinates (and not, for example, center coordinates).

Parameters:
oldItems A set of items to which a new item is to be added.
newItem The new item to be added.
set_one The first split set.
set_two The second set split set.
mbr_one Pointer to where the first set MBR should be stored
mbr_two Pointer to where the second set MBR should be stored
dimension Current dimensions of the BBs stored

Definition at line 763 of file basic-r-tree.h.

References Cubic_Bounding_Box::become(), R_tree< Basic_R_tree >::deadSpace(), R_tree_props::minimum, R_tree< Basic_R_tree >::properties, Cubic_Bounding_Box::unionWith(), and Cart::Volume().

Referenced by handleOverflow().

void Basic_R_tree::quadraticSplitNodes ( vector< Basic_R_tree * >  oldItems,
Basic_R_tree newItem,
vector< Basic_R_tree * > *  set_one,
vector< Basic_R_tree * > *  set_two,
BB_type mbr_one,
BB_type mbr_two,
int  dimension 
) [protected]

This algorithm does the actual splitting according to the quadraticSplit algorithm. It creates two sets which denote the resulting split. The algorithm as implemented as present, only considers the ordering based on maximum and minimum coordinates (and not, for example, center coordinates).

Parameters:
oldItems A set of items to which a new item is to be added.
newItem The new item to be added.
set_one The first split set.
set_two The second set split set.
mbr_one Pointer to where the first set MBR should be stored
mbr_two Pointer to where the second set MBR should be stored
dimension Current dimensions of the BBs stored

Definition at line 898 of file basic-r-tree.h.

References Cubic_Bounding_Box::become(), R_tree< Basic_R_tree >::deadSpace(), R_tree< Basic_R_tree >::mbr, R_tree_props::minimum, R_tree< Basic_R_tree >::properties, Cubic_Bounding_Box::unionWith(), and Cart::Volume().

Referenced by handleOverflow().

Basic_R_tree * Basic_R_tree::insert ( Basic_R_tree node  )  [protected]

This procedure is called when a given node should be added to the *current* *internal* node. Calls the overflow handling algorithm if so required.

Parameters:
node The to be added node child
Returns:
The (new) tree root

Definition at line 702 of file basic-r-tree.h.

References Tree< BB_container *, Basic_R_tree >::children, R_tree< Basic_R_tree >::full(), getRoot(), handleOverflow(), Tree< BB_container *, Basic_R_tree >::parent, Tree< stored_type, tree_type >::parent, and R_tree< Basic_R_tree >::updateMBR().

Referenced by handleOverflow(), and reinsert().

Basic_R_tree * Basic_R_tree::buildNode ( vector< BB_container * >  input,
BB_type newMbr 
) const [protected]

Builds a leaf node from a collection of container data elements.

Parameters:
input The data elements to be stored at the new leaf node
newMbr The minimum bounding rectangle containing all input elements
Returns:
The requested leaf node

Definition at line 573 of file basic-r-tree.h.

References Basic_R_tree(), Tree< stored_type, tree_type >::elements, R_tree< r_tree_variation >::mbr, and R_tree< Basic_R_tree >::properties.

Referenced by handleOverflow().

Basic_R_tree * Basic_R_tree::buildNode ( vector< Basic_R_tree * >  input,
BB_type newMbr 
) const [protected]

Builds an internal node from a collection of other R-tree nodes.

Parameters:
input The subtrees to be stored at the new internal node
newMbr The minimum bounding rectangle containing all input subtrees MBRs
Returns:
The requested internal node.

Definition at line 595 of file basic-r-tree.h.

References Basic_R_tree(), Tree< stored_type, tree_type >::children, R_tree< r_tree_variation >::mbr, and R_tree< Basic_R_tree >::properties.

void Basic_R_tree::reinsert ( vector< Basic_R_tree * >  s  )  [protected]

Re-inserts all elements stored in the subtrees with roots given in a supplied vector.

Parameters:
s A collection of subtrees

Definition at line 526 of file basic-r-tree.h.

References insert().

Referenced by reinsert(), and remove().

void Basic_R_tree::reinsert ( Basic_R_tree walk,
Basic_R_tree at 
) [protected]

Re-inserts all elements stored in a given subtree at a given node

Parameters:
walk The subtree which elements are to be re-inserted
at The tree at which the elements are to be re-inserted

Definition at line 561 of file basic-r-tree.h.

References Tree< BB_container *, Basic_R_tree >::children, Tree< BB_container *, Basic_R_tree >::elements, insert(), Tree< stored_type, tree_type >::isLeaf(), and reinsert().

Basic_R_tree * Basic_R_tree::handleOverflow ( Basic_R_tree node  )  [protected]

This algorithm handles an overflow occuring at the *current* *internal* node, at which a given node has to be added. The algorithm is completely the same as for the leaf nodes, with the only difference being that it operates on internal nodes, instead of elements, obviously.

Parameters:
node The to be added node
Returns:
The (new) root of the tree

Definition at line 619 of file basic-r-tree.h.

References buildNode(), Tree< BB_container *, Basic_R_tree >::children, EXPONENTIAL_SPLIT, Cubic_Bounding_Box::getDimension(), insert(), LINEAR_SPLIT, linearSplitNodes(), makeNewRoot(), R_tree< r_tree_variation >::mbr, Tree< BB_container *, Basic_R_tree >::parent, QUADRATIC_SPLIT, quadraticSplitNodes(), setChildren(), and SPLIT_STRATEGY.

Basic_R_tree * Basic_R_tree::makeNewRoot ( Basic_R_tree child  )  [protected]

Creates a new root and makes the current and the given node children of this new root.

Parameters:
child The second child of the new root
Returns:
A root node with the current node and the given node as children

Definition at line 476 of file basic-r-tree.h.

References Basic_R_tree(), Tree< stored_type, tree_type >::children, Tree< stored_type, tree_type >::parent, Tree< BB_container *, Basic_R_tree >::parent, R_tree< Basic_R_tree >::properties, and R_tree< r_tree_variation >::updateMBRLocal().

Referenced by handleOverflow().

void Basic_R_tree::setChildren ( vector< Basic_R_tree * >  newChildren,
BB_type newMbr 
) [protected]

Sets a collection of nodes to be the children of this node.

Parameters:
newChildren The collection of new children
newMbr The minimum bounding rectangle of newChildren

Definition at line 370 of file basic-r-tree.h.

References Tree< BB_container *, Basic_R_tree >::children, Tree< BB_container *, Basic_R_tree >::elements, Tree< BB_container *, Basic_R_tree >::isLeaf(), R_tree< Basic_R_tree >::mbr, and R_tree< Basic_R_tree >::setElements().

Referenced by handleOverflow().

void Basic_R_tree::removeChild ( Basic_R_tree toRemove  )  [protected]

Removes a given child node from the current node.

Parameters:
toRemove The child node to be removed.

Definition at line 352 of file basic-r-tree.h.

References Tree< BB_container *, Basic_R_tree >::children.

Referenced by remove().

Basic_R_tree * Basic_R_tree::remove ( Basic_R_tree node,
BB_container element 
) [protected]

Removes a given element from a given node. Only call this method directly if the node at which the to-be removed element was known beforehand. Otherwise, simply call remove( BB_container *container).

Parameters:
node The node the supplied element is stored at
element The pointer to the container to-be deleted
Returns:
The (new) root node of the tree

Definition at line 283 of file basic-r-tree.h.

References Tree< stored_type, tree_type >::children, Tree< stored_type, tree_type >::elements, Cubic_Bounding_Box_Container::getID(), Tree< stored_type, tree_type >::isLeaf(), Tree< stored_type, tree_type >::isRoot(), R_tree< r_tree_variation >::mbr, R_tree_props::minimum, Tree< stored_type, tree_type >::parent, R_tree< r_tree_variation >::properties, R_tree< Basic_R_tree >::properties, reinsert(), removeChild(), and R_tree< r_tree_variation >::updateMBRNode().

Basic_R_tree * Basic_R_tree::remove ( BB_container element  )  [virtual]

Removes a stored polytope from the R-tree structure. A pointer to the polytope must be explicitly given. If the polytope cannot be found within the R-tree, a warning is printed to stderr but no further action is taken.

Parameters:
element The element to be removed from the R-tree.
Returns:
The (new) root of the R-tree.

Implements Spatial_Tree< Basic_R_tree, BB_type, BB_container >.

Definition at line 1873 of file basic-r-tree.h.

References getRoot(), search(), and R_tree< r_tree_variation >::updateMBR().

Basic_R_tree * Basic_R_tree::getRoot (  )  [virtual]

Searches and returns the root of the R-tree the current node is in.

Returns:
The requested root node.

Reimplemented from R_tree< Basic_R_tree >.

Definition at line 1861 of file basic-r-tree.h.

References Tree< BB_container *, Basic_R_tree >::children, and Tree< BB_container *, Basic_R_tree >::elements.

Referenced by insert(), and remove().

const Basic_R_tree * Basic_R_tree::getRoot (  )  const [virtual]

Searches and returns the root of the R-tree the current node is in. Const version.

Returns:
The requested root node (const).

Definition at line 1849 of file basic-r-tree.h.

References Tree< BB_container *, Basic_R_tree >::children, and Tree< BB_container *, Basic_R_tree >::elements.

Basic_R_tree * Basic_R_tree::insert ( BB_container element  )  [virtual]

Insert a given container element into the R-trree structure.

Parameters:
element The to be added element
Returns:
The (new) root of the current tree

Implements Spatial_Tree< Basic_R_tree, BB_type, BB_container >.

Definition at line 1786 of file basic-r-tree.h.

References chooseLeaf(), Tree< stored_type, tree_type >::elements, R_tree< r_tree_variation >::full(), getRoot(), handleOverflow(), Tree< stored_type, tree_type >::isLeaf(), R_tree< r_tree_variation >::updateMBR(), and R_tree< r_tree_variation >::writeTreeToFile().

Basic_R_tree * Basic_R_tree::search ( BB_container element  )  [virtual]

Searches the R-tree for a given polytope, and returns the leaf node at which it is stored.

Parameters:
element The element to be found
Returns:
The leaf node at which the given polytope is found

Implements Tree< BB_container *, Basic_R_tree >.

Definition at line 1752 of file basic-r-tree.h.

References Tree< BB_container *, Basic_R_tree >::children, Tree< BB_container *, Basic_R_tree >::elements, Cubic_Bounding_Box_Container::getID(), and Cubic_Bounding_Box::intersects().

Referenced by remove().


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