VGServer::RTree::Tree::Node

VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData > Class Template Reference

node page augmented by a data type: either the childMBR + childPageId for InnerNodes or the childData for LeafNodes. More...

#include <RTree.h>

Inheritance diagram for VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >:

VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead VGServer::RTree::Tree< _DataType, _DataTypeCallback >::InnerNode VGServer::RTree::Tree< _DataType, _DataTypeCallback >::LeafNode List of all members.

Public Types

typedef _NodeData NodeData
 public typedef of the NodeData
typedef Node< NodeData > NodeType
 typedef of our own type

Public Member Functions

void adjustTree (Tree &tree, pageid_t mypageid, const NodeHead &adj, pageid_t adjpage, std::stack< pageid_t > &path)
 adjust the rectangles in the path upward
void adjustTreeReinsert (Tree &tree, pageid_t mypageid, const NodeHead &adj, pageid_t adjpage, std::stack< pageid_t > &path)
 adjust the parent nodeMBR after a reinsert was performed on the child (but before the actual reinsertion calls)
void adjustTreeSplit (Tree &tree, pageid_t mypageid, const NodeHead &adjN, pageid_t adjNpage, const NodeHead &adjNN, pageid_t adjNNpage, std::stack< pageid_t > &path, char *overflowedLevel)
 after a split, insert the new node NN into this page and adjust the MBRs upward.
AreaType calcOverlap (const Tree &tree) const
 calculate the sum of all overlaps of this node and all children
void calcStats (const Tree &tree, Stats &s) const
 calculate the sum of all overlaps of this node and all children
AreaType calcWasteArea (const Tree &tree) const
 calculate the sum of the "wasted" space of this node and all children
bool checkNode (const Tree &tree, unsigned int thislevel, unsigned int *numentries) const
 test various invariants of this node and it's children
NodeHead * chooseSubtree (Tree &tree, const Rect &newrect, unsigned int maxlevel, std::stack< pageid_t > &path)
 select the leaf in which to insert a new rectangle, and save it's path down the tree.
void condenseTree (Tree &tree, pageid_t mypageid, std::stack< pageid_t > &toReinsert, std::queue< pageid_t > &path)
 condense a node if has too few entries
void deleteChild (const Tree &tree, unsigned int ci)
 delete the child rectangle at position ci, used by condenseTree
LeafNode * findLeaf (Tree &tree, const class LeafNodeData &rmdata, std::queue< pageid_t > &path)
 algorithm findLeaf used in deleteRect
unsigned int findLeastEnlargement (const Tree &tree, const Rect &newrect) const
 find the child which's MBR needs least enlargement to include newrect.
unsigned int findLeastOverlap (const Tree &tree, const Rect &newrect) const
 find the child which's MBR need least overlap enlargement when the new rect is added.
bool insertChild (Tree &tree, pageid_t mypageid, const NodeData &newdata, std::stack< pageid_t > &path, char *overflowedLevel)
 insert a new child rectangle in this inner node.
void pickSeedsLinear (const Tree &tree, const Rect &newrect, unsigned int &seed1, unsigned int &seed2) const
 pick the two group seeds using the linear algorithm
void pickSeedsQuadratic (const Tree &tree, const Rect &newrect, unsigned int &seed1, unsigned int &seed2) const
 pick the two group seeds using the quadratic algorithm
void recalcChildrenMBR (const Tree &tree, class Rect &dest) const
 recalculate the MBR of all children. used at various places
void reinsertData (Tree &tree, pageid_t mypageid, const NodeData &newdata, std::stack< pageid_t > &path, char *overflowedLevel)
 R*-Tree forced reinsert of a number of rectangles from this node's elements.
void splitNode (Tree &tree, const NodeData &newdata, NodeType **nndest, pageid_t &nn_page)
 split this node into two nodes of the same type, thus creating a new one which is placed into nndest.
void splitNodeMakeGroups (const Tree &tree, const Rect &newrect, std::vector< unsigned int > &group1, std::vector< unsigned int > &group2) const
 separate the rectangles of this node into two groups using the quadratic algorithm
void splitNodeMakeGroupsRStar (const Tree &tree, const Rect &newrect, std::vector< unsigned int > &group1, std::vector< unsigned int > &group2) const
 separate the rectangles of this node into two groups using the algorithm described in the R*-Tree paper.
void writeFig (const Tree &tree, std::ostream &o, int maxlevel) const
 write the rectangles out in the fig format. stop at a given level (0 are the leaves)

Public Attributes

NodeData children [pagesize]
 array of data elements within this node

Classes

struct  SplitDist
 data struct to order computed distributions More...

Detailed Description

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
class VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >

node page augmented by a data type: either the childMBR + childPageId for InnerNodes or the childData for LeafNodes.

It contains generic functions used to insert, split nodes containing _NodeData elements.

Definition at line 390 of file RTree.h.

Member Typedef Documentation

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
typedef _NodeData VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::NodeData

public typedef of the NodeData

Definition at line 394 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
typedef Node<NodeData> VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::NodeType

typedef of our own type

Definition at line 397 of file RTree.h.

Member Function Documentation

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::adjustTree ( Tree &  tree,
pageid_t  mypageid,
const NodeHead &  adj,
pageid_t  adjpage,
std::stack< pageid_t > &  path 
) [inline]

adjust the rectangles in the path upward

Definition at line 916 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::adjustTreeReinsert ( Tree &  tree,
pageid_t  mypageid,
const NodeHead &  adj,
pageid_t  adjpage,
std::stack< pageid_t > &  path 
) [inline]

adjust the parent nodeMBR after a reinsert was performed on the child (but before the actual reinsertion calls)

Definition at line 990 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::adjustTreeSplit ( Tree &  tree,
pageid_t  mypageid,
const NodeHead &  adjN,
pageid_t  adjNpage,
const NodeHead &  adjNN,
pageid_t  adjNNpage,
std::stack< pageid_t > &  path,
char *  overflowedLevel 
) [inline]

after a split, insert the new node NN into this page and adjust the MBRs upward.

Definition at line 951 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
AreaType VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::calcOverlap ( const Tree &  tree  )  const [inline]

calculate the sum of all overlaps of this node and all children

Definition at line 740 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::calcStats ( const Tree &  tree,
Stats &  s 
) const [inline]

calculate the sum of all overlaps of this node and all children

Definition at line 674 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
AreaType VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::calcWasteArea ( const Tree &  tree  )  const [inline]

calculate the sum of the "wasted" space of this node and all children

Definition at line 773 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
bool VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::checkNode ( const Tree &  tree,
unsigned int  thislevel,
unsigned int *  numentries 
) const [inline]

test various invariants of this node and it's children

Definition at line 636 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
class NodeHead* VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::chooseSubtree ( Tree &  tree,
const Rect &  newrect,
unsigned int  maxlevel,
std::stack< pageid_t > &  path 
) [inline]

select the leaf in which to insert a new rectangle, and save it's path down the tree.

Definition at line 518 of file RTree.h.

Referenced by VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::chooseSubtree().

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::condenseTree ( Tree &  tree,
pageid_t  mypageid,
std::stack< pageid_t > &  toReinsert,
std::queue< pageid_t > &  path 
) [inline]

condense a node if has too few entries

Definition at line 1821 of file RTree.h.

Referenced by VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::condenseTree().

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::deleteChild ( const Tree &  tree,
unsigned int  ci 
) [inline]

delete the child rectangle at position ci, used by condenseTree

Definition at line 1109 of file RTree.h.

Referenced by VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::condenseTree().

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
class LeafNode* VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::findLeaf ( Tree &  tree,
const class LeafNodeData &  rmdata,
std::queue< pageid_t > &  path 
) [inline]

algorithm findLeaf used in deleteRect

Definition at line 554 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
unsigned int VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::findLeastEnlargement ( const Tree &  tree,
const Rect &  newrect 
) const [inline]

find the child which's MBR needs least enlargement to include newrect.

Definition at line 415 of file RTree.h.

Referenced by VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::chooseSubtree().

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
unsigned int VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::findLeastOverlap ( const Tree &  tree,
const Rect &  newrect 
) const [inline]

find the child which's MBR need least overlap enlargement when the new rect is added.

Definition at line 451 of file RTree.h.

Referenced by VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::chooseSubtree().

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
bool VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::insertChild ( Tree &  tree,
pageid_t  mypageid,
const NodeData &  newdata,
std::stack< pageid_t > &  path,
char *  overflowedLevel 
) [inline]

insert a new child rectangle in this inner node.

if there is no more room, invoke splitNode. returns true if the tree was adjusted.

Definition at line 819 of file RTree.h.

Referenced by VGServer::RTree::Tree< _DataType, _DataTypeCallback >::insertRect().

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::pickSeedsLinear ( const Tree &  tree,
const Rect &  newrect,
unsigned int &  seed1,
unsigned int &  seed2 
) const [inline]

pick the two group seeds using the linear algorithm

Definition at line 1468 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::pickSeedsQuadratic ( const Tree &  tree,
const Rect &  newrect,
unsigned int &  seed1,
unsigned int &  seed2 
) const [inline]

pick the two group seeds using the quadratic algorithm

Definition at line 1427 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::recalcChildrenMBR ( const Tree &  tree,
class Rect &  dest 
) const [inline]

recalculate the MBR of all children. used at various places

Definition at line 405 of file RTree.h.

Referenced by VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::condenseTree().

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::reinsertData ( Tree &  tree,
pageid_t  mypageid,
const NodeData &  newdata,
std::stack< pageid_t > &  path,
char *  overflowedLevel 
) [inline]

R*-Tree forced reinsert of a number of rectangles from this node's elements.

Definition at line 1023 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::splitNode ( Tree &  tree,
const NodeData &  newdata,
NodeType **  nndest,
pageid_t &  nn_page 
) [inline]

split this node into two nodes of the same type, thus creating a new one which is placed into nndest.

Definition at line 1129 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::splitNodeMakeGroups ( const Tree &  tree,
const Rect &  newrect,
std::vector< unsigned int > &  group1,
std::vector< unsigned int > &  group2 
) const [inline]

separate the rectangles of this node into two groups using the quadratic algorithm

Definition at line 1197 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::splitNodeMakeGroupsRStar ( const Tree &  tree,
const Rect &  newrect,
std::vector< unsigned int > &  group1,
std::vector< unsigned int > &  group2 
) const [inline]

separate the rectangles of this node into two groups using the algorithm described in the R*-Tree paper.

Definition at line 1617 of file RTree.h.

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::writeFig ( const Tree &  tree,
std::ostream &  o,
int  maxlevel 
) const [inline]

write the rectangles out in the fig format. stop at a given level (0 are the leaves)

Definition at line 601 of file RTree.h.

Member Data Documentation

template<typename _DataType, typename _DataTypeCallback>
template<typename _NodeData>
NodeData VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::children[pagesize]

array of data elements within this node

Definition at line 400 of file RTree.h.

Referenced by VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::calcOverlap(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::calcStats(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::calcWasteArea(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::checkNode(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::chooseSubtree(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::condenseTree(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::LeafNode::deleteDataLeaf(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::findLeaf(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::findLeastEnlargement(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::findLeastOverlap(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::insertChild(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::queryNearestNeighbor(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::queryRange(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::recalcChildrenMBR(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::splitNode(), and VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::writeFig().

The documentation for this class was generated from the following file:
Generated on Wed Sep 27 14:34:01 2006 for VGServer by  doxygen 1.4.7