Hilbert_R_tree Class Reference

#include <Hilbert_R-Tree.h>

Inherits R_tree< Hilbert_R_tree >.

Inheritance diagram for Hilbert_R_tree:

Inheritance graph
[legend]
Collaboration diagram for Hilbert_R_tree:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 Hilbert_R_tree ()
 Hilbert_R_tree (R_tree_props *props)
virtual ~Hilbert_R_tree ()
virtual void postBulkLoad ()
int compareLHV (const Hilbert_R_tree *b) const
void visualiseTree (const int level, Hilbert_R_tree *ref)
Hilbert_R_tree * getRoot ()
virtual Hilbert_R_tree * insert (BB_container *element)
virtual Hilbert_R_tree * remove (BB_container *element)
virtual Hilbert_R_tree * search (BB_container *element)

Protected Member Functions

Hilbert_R_tree * buildNode (vector< Hilbert_R_tree * > &input, BB_type *newMbr) const
Hilbert_R_tree * buildNode (vector< BB_container * > &input, BB_type *newMbr) const
Hilbert_R_tree * chooseLeaf (const double h)
void handleOverflow ()
void handleRootOverflow ()
void handleUnderflow ()
void insert (BB_container *element, double h)
void removeElement (BB_container *element)
void updateLHVLocal ()
void updateLHV ()
void setChildren (vector< Hilbert_R_tree * > newChildren, BB_type *newMbr)

Private Attributes

double LHV

Classes

class  HilbertTreeOrdering

Detailed Description

An Hilbert-R_tree. Similar to a B-tree by using the Hilbert coordinate transform. Employs s-to-s+1 splitting. s is defined at source level, default at 2.

Definition at line 26 of file Hilbert_R-Tree.h.

Constructor & Destructor Documentation

Hilbert_R_tree::Hilbert_R_tree (  )  [inline]

Inhereted constructor. Also sets LHV to zero.

Definition at line 138 of file Hilbert_R-Tree.h.

References LHV.

Referenced by buildNode(), and handleOverflow().

Hilbert_R_tree::Hilbert_R_tree ( R_tree_props *  props  )  [inline]

Inhereted constructor. Also sets LHV to zero.

Definition at line 141 of file Hilbert_R-Tree.h.

References LHV.

virtual Hilbert_R_tree::~Hilbert_R_tree (  )  [inline, virtual]

Base deconstructor.

Definition at line 146 of file Hilbert_R-Tree.h.

Member Function Documentation

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

Function creating an internal node with as children a set of other internal nodes.

Parameters:
input The other set of internal nodes.
newMbr The MBR of the resulting internal tree node.
Returns:
The resulting internal tree node.

Definition at line 253 of file Hilbert_R-Tree.h.

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

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

Function creating an internal node containing a given set of elements to store.

Parameters:
input The given set of elements to store.
newMbr The MBR of the resulting internal tree node.
Returns:
The resulting internal tree node.

Definition at line 276 of file Hilbert_R-Tree.h.

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

Hilbert_R_tree * Hilbert_R_tree::chooseLeaf ( const double  h  )  [protected]

Hilbert-variant of chooseLeaf. As described in [FK94], returns the node with min LHV larger than the supplied h. If there is no LHV larger than h, the node with max LHV is selected instead.

Parameters:
h The supplied Hilbert coordinate
Returns:
The selected node

Definition at line 348 of file Hilbert_R-Tree.h.

References Tree< BB_container *, Hilbert_R_tree >::children, chooseLeaf(), Tree< BB_container *, Hilbert_R_tree >::isLeaf(), and LHV.

Referenced by chooseLeaf(), and insert().

void Hilbert_R_tree::handleOverflow (  )  [protected]

Hilbert-variant of overflow handling. Should be called on a node which currently contains more elements than allowed.

Definition at line 379 of file Hilbert_R-Tree.h.

References Tree< BB_container *, Hilbert_R_tree >::children, Tree< stored_type, tree_type >::children, Tree< BB_container *, Hilbert_R_tree >::elements, Tree< stored_type, tree_type >::elements, getRoot(), handleOverflow(), Hilbert_R_tree(), Tree< BB_container *, Hilbert_R_tree >::isLeaf(), Tree< BB_container *, Hilbert_R_tree >::isRoot(), LHV, R_tree_props::maximum, Tree< BB_container *, Hilbert_R_tree >::parent, Tree< stored_type, tree_type >::parent, R_tree< Hilbert_R_tree >::properties, Sfrom, Ordering< bb_type >::sort(), HilbertOrdering3D< cur_type >::sort(), updateLHV(), R_tree< r_tree_variation >::updateMBR(), R_tree< r_tree_variation >::updateMBRLocal(), and visualiseTree().

Referenced by handleOverflow(), and insert().

void Hilbert_R_tree::handleRootOverflow (  )  [protected]

Hilbert-variant of overflow handling. Should be called on the root when it contains more elements than allowed.

void Hilbert_R_tree::handleUnderflow (  )  [protected]

Hilbert-variant of underrflow handling. Should be called on a node with currently contains less elements than allowed.

Definition at line 648 of file Hilbert_R-Tree.h.

void Hilbert_R_tree::insert ( BB_container *  element,
double  h 
) [protected]

Inserts an element with a given hilbert value at the current node.

Parameters:
element The element to-be stored
h The hilbert value of that data element

Definition at line 627 of file Hilbert_R-Tree.h.

References Tree< BB_container *, Hilbert_R_tree >::elements, handleOverflow(), R_tree_props::maximum, R_tree< Hilbert_R_tree >::properties, updateLHV(), and R_tree< Hilbert_R_tree >::updateMBR().

Referenced by insert().

void Hilbert_R_tree::removeElement ( BB_container *  element  )  [protected]

Removes a given element from the current node.

Parameters:
The to-be removed element
Warning: when checking for equality of stored elements with the supplied element, only IDs are compared. Note: While only IDs are compared here, the BB information *is* required to find the current node at which the element is stored. I.e., upon removal, the BB should still overlap with the BB presently stored in the tree.

Definition at line 650 of file Hilbert_R-Tree.h.

void Hilbert_R_tree::updateLHVLocal (  )  [protected]

Updates the LHV values, of the current node. May recurse down the tree, if LHV values were not initialised there.

Definition at line 298 of file Hilbert_R-Tree.h.

References Tree< BB_container *, Hilbert_R_tree >::children, Tree< BB_container *, Hilbert_R_tree >::elements, Tree< BB_container *, Hilbert_R_tree >::isLeaf(), LHV, and HilbertCoordinateMapper::toHilbert3D().

Referenced by updateLHV().

void Hilbert_R_tree::updateLHV (  )  [protected]

Updates the LHV values, beginning at the current node and propagating upwards.

See also:
updateLHVLocal()

Definition at line 340 of file Hilbert_R-Tree.h.

References Tree< BB_container *, Hilbert_R_tree >::isRoot(), Tree< BB_container *, Hilbert_R_tree >::parent, updateLHV(), and updateLHVLocal().

Referenced by handleOverflow(), insert(), postBulkLoad(), and updateLHV().

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

Sets the children of this node to be a given set of internal nodes.

Parameters:
newChildren The given set of internal nodes.
newMbr The MBR this node should store.

Definition at line 222 of file Hilbert_R-Tree.h.

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

virtual void Hilbert_R_tree::postBulkLoad (  )  [inline, virtual]

For this tree variant, the LHVs must be set after bulkloading

Reimplemented from R_tree< Hilbert_R_tree >.

Definition at line 149 of file Hilbert_R-Tree.h.

References getRoot(), and updateLHV().

int Hilbert_R_tree::compareLHV ( const Hilbert_R_tree *  b  )  const

Function which compares LHV values with another Hilbert R-tree node.

Parameters:
b The other Hilbert R-tree node.
Returns:
-1 if the current node has a smaller LHV value than the other node, 0 if equal, 1 if larger.

Definition at line 621 of file Hilbert_R-Tree.h.

References LHV.

void Hilbert_R_tree::visualiseTree ( const int  level,
Hilbert_R_tree *  ref 
)

Method to print the general tree structure to stdout.

Parameters:
level Current tree level.
ref Pointer to the caller node.

Definition at line 652 of file Hilbert_R-Tree.h.

References Tree< BB_container *, Hilbert_R_tree >::children, Tree< BB_container *, Hilbert_R_tree >::elements, Tree< BB_container *, Hilbert_R_tree >::isLeaf(), R_tree_props::maximum, Tree< BB_container *, Hilbert_R_tree >::parent, and R_tree< Hilbert_R_tree >::properties.

Referenced by handleOverflow().

Hilbert_R_tree * Hilbert_R_tree::getRoot (  ) 

Gets the root of the current Hilbert R-tree.

Returns:
The root of the Hilbert R-tree.

Reimplemented from R_tree< Hilbert_R_tree >.

Definition at line 697 of file Hilbert_R-Tree.h.

References getRoot(), Tree< BB_container *, Hilbert_R_tree >::isRoot(), and Tree< BB_container *, Hilbert_R_tree >::parent.

Referenced by getRoot(), handleOverflow(), and postBulkLoad().

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

Basic insertion algorithm for the Hilbert R-tree. Warning: ONLY WORKS FOR 3D CONTAINERS!

Parameters:
element The 3-D element to be added in the current tree

Implements Spatial_Tree< Hilbert_R_tree, BB_type, BB_container >.

Definition at line 673 of file Hilbert_R-Tree.h.

References chooseLeaf(), Cubic_Bounding_Box::getCenterCoordinate(), insert(), and HilbertCoordinateMapper::toHilbert3D().

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

Removes an element from the R-tree.

Parameters:
element Pointer to the element to be removed.

Implements Spatial_Tree< Hilbert_R_tree, BB_type, BB_container >.

Definition at line 689 of file Hilbert_R-Tree.h.

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

Searches for a given element in the R-tree.

Parameters:
element Pointer to the element to be searched.

Implements Tree< BB_container *, Hilbert_R_tree >.

Definition at line 693 of file Hilbert_R-Tree.h.

Member Data Documentation

double Hilbert_R_tree::LHV [private]

The maximum Hilbert value of the _data_ elements contained in this subtree

Definition at line 31 of file Hilbert_R-Tree.h.

Referenced by chooseLeaf(), compareLHV(), Hilbert_R_tree::HilbertTreeOrdering::getVal(), handleOverflow(), Hilbert_R_tree(), setChildren(), and updateLHVLocal().

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