RStarTreeNode.hpp

Go to the documentation of this file.

// Class Name:  RStarTreeNode
// Description: Node of R*Tree.
// The algorithm was taken from the following paper:
//        Norbert Beckmann, H. Kriegel, R. Schnieder, and B. Seegar,
//              "The R*-tree: An Efficient and Robust Access Method
//              for Points and Rectangles", Proceedings of ACM SIGMOD
//              Int'l. Conf. on Management of Data, pp. 322-331, 1990.
// Creation Date: 7/21/02
// Owner:  David R. White
#ifndef RSTARTREENODE_HPP
#define RSTARTREENODE_HPP

#include "CubitDefines.h"
#include "GeometryDefines.h"
#include "CubitBox.hpp"

template <class X> class DLIList;
const int UNSET_RSTARNODE = -1;
const int DATA_RSTARNODE = 0;
const int LEAF_RSTARNODE = 1;

template <class Y> class RStarTreeNode 
{
private:
    //Data.
  IttyBit markedFlag : 1;
  IttyBit distIsBox : 1;
  int myId;
  
  RStarTreeNode<Y>** myChildrenNodes;
  int nextChildIndex;
  CubitBox *myBoundingBox;
  Y myData;
  int maxChildren, minChildren; //max/min number of children.
  RStarTreeNode<Y> *myParent;
  int myLevel;
  double myDist;
  
  

    //Functions.
  RStarTreeNode<Y>* choose_sub_tree( RStarTreeNode<Y> *n, RStarTreeNode<Y> *e );

  CubitStatus overflow_treatment( RStarTreeNode<Y>* l,
                                  RStarTreeNode<Y>* e,
                                  RStarTreeNode<Y> *&ll,
                                  RStarTreeNode<Y> *root,
                                  RStarTreeNode<Y> *&new_root,
                                  int *overflow_flags, int levels);

  CubitStatus reinsert(RStarTreeNode<Y>* l,
                       RStarTreeNode<Y>* e,
                       RStarTreeNode<Y> *root,
                       RStarTreeNode<Y> *&new_root,
                       int *overflow_flags, int levels);

  
  CubitStatus adjust_tree(RStarTreeNode<Y> *l, RStarTreeNode<Y> *ll,
                          RStarTreeNode<Y> *root_node,
                          RStarTreeNode<Y> *&new_root,
                          int *overflow_flags,
                          int levels);

  CubitStatus split_node( RStarTreeNode<Y> *l,
                          RStarTreeNode<Y> *e,
                          RStarTreeNode<Y> *&ll );
  double calc_overlap( RStarTreeNode<Y> *current,
                       RStarTreeNode<Y> *add_to);
  
  double calc_enlargement( RStarTreeNode<Y> *current, RStarTreeNode<Y> *add_to );
  double calc_enlargement( CubitBox &current,
                           CubitBox &add_to );

  CubitStatus find_leaf( Y e,
                         CubitBox &e_box,
                         RStarTreeNode<Y> *t,
                         RStarTreeNode<Y> *&l );

  CubitStatus condense_tree(RStarTreeNode<Y> *l,
                            RStarTreeNode<Y> *root,
                            RStarTreeNode<Y> *&new_root );
    
  
  double volume(CubitBox &box);
  double volume(RStarTreeNode<Y>* curr);

  static int sort_high_x(RStarTreeNode<Y> *&n_1,
                         RStarTreeNode<Y> *&n_2 );
  static int sort_high_y(RStarTreeNode<Y> *&n_1,
                         RStarTreeNode<Y> *&n_2 );
  static int sort_high_z(RStarTreeNode<Y> *&n_1,
                         RStarTreeNode<Y> *&n_2 );
  static int sort_low_x(RStarTreeNode<Y> *&n_1,
                        RStarTreeNode<Y> *&n_2);
  static int sort_low_y(RStarTreeNode<Y> *&n_1,
                        RStarTreeNode<Y> *&n_2);
  static int sort_low_z(RStarTreeNode<Y> *&n_1,
                        RStarTreeNode<Y> *&n_2);

  static int sort_center_distance( RStarTreeNode<Y> *&n_1,
                                   RStarTreeNode<Y> *&n_2 );

  

  double margin(CubitBox &bounding_box);

  CubitBox super_box(DLIList<RStarTreeNode<Y>*> &node_list);

public:
  RStarTreeNode(Y data, double tol, int max_children, int min_children );
  RStarTreeNode(CubitBox &bounding_box, int max_children, int min_children);
  
  ~RStarTreeNode();

  void validate_tree(int print);

  CubitStatus insert(RStarTreeNode<Y> *e, RStarTreeNode<Y> *&new_root,
                     int *overflow_flags, int levels);

  void set_leaf_level(int r_type)
  {myLevel = r_type;}
  int get_leaf_level()
    {return myLevel;}

  CubitBoolean is_leaf()
    {return (myLevel == LEAF_RSTARNODE)? CUBIT_TRUE : CUBIT_FALSE;}

  CubitBoolean is_data()
    {return (myLevel == DATA_RSTARNODE)? CUBIT_TRUE : CUBIT_FALSE;}

  Y get_data()
    {return myData;}
  
  void add_child(RStarTreeNode<Y>* child_node, CubitBoolean recalc_b_box);
  
  CubitBoolean can_add();

  int space_left();

  int num_children()
    {return nextChildIndex;}

  RStarTreeNode<Y>* get_child(int i)
    {return ((i < nextChildIndex) ? myChildrenNodes[i] : (RStarTreeNode<Y>*)NULL) ;}
  
    
  void flush(CubitBox &new_box);
  
  void recalc_b_box();
  
  RStarTreeNode<Y> *get_parent()
    {return myParent;}
  void set_parent(RStarTreeNode<Y> *parent)
    {myParent = parent;}

  CubitBoolean remove_child(RStarTreeNode<Y> *child);

  CubitBoolean remove(Y e, RStarTreeNode<Y> *&new_root, CubitBoolean &delete_root);

  CubitBox& bounding_box()
    {return *myBoundingBox;}

  double get_dist();
  void set_dist(double dis);

  int dist_is_box();
  void set_dist_is_box(int val);
  
      
};
template <class Y> inline int RStarTreeNode<Y>::dist_is_box()
{
  return distIsBox;
}
template <class Y> inline void RStarTreeNode<Y>::set_dist_is_box(int val)
{
  if ( val )
    distIsBox = 1;
  else
    distIsBox = 0;
}

template <class Y> inline double RStarTreeNode<Y>::get_dist()
{
  return myDist;
}
template <class Y> inline void RStarTreeNode<Y>::set_dist(double dist)
{
  myDist = dist;
}

//Calculate the volume of the box.
template <class Y> inline double RStarTreeNode<Y>::volume(CubitBox &box)
{
  return box.x_range()*box.y_range()*box.z_range();
}
//Calculate the volume of the RStarTreeNode.
template <class Y> inline double RStarTreeNode<Y>::volume(RStarTreeNode<Y>* curr)
{
  CubitBox box = curr->bounding_box();
  return box.x_range()*box.y_range()*box.z_range();
}

#include "RStarTreeNode.cpp"

#endif