cgma
RTreeNode.cpp
Go to the documentation of this file.
00001 //---------------------------------------------------------------------------
00002 // Class Name:  RTreeNode
00003 // Description: Node of Rectangle tree.  Contians many of the
00004 //              required functions for building the tree and traversing it.
00005 // The algorithm was taken from the following paper:
00006 //        Guttman, A., "R-Trees: A Dynamic Index Structure for
00007 //              Spatial Searching", Proceedings of the SIGMOD
00008 //              Conference, Boston, June 1984, p. 47-57.
00009 // Creation Date: 3/13/02
00010 // Owner:  David R. White
00011 //---------------------------------------------------------------------------
00012 
00013 //---------------------------------
00014 //Include Files
00015 //---------------------------------
00016 #include "RTreeNode.hpp"
00017 #include "DLIList.hpp"
00018 #include "CubitMessage.hpp"
00019 
00020 //---------------------------
00021 //Initialize Static Members
00022 //---------------------------
00023 
00024 #ifdef INLINE_TEMPLATES
00025 #define MY_INLINE inline
00026 #else
00027 #define MY_INLINE
00028 #endif
00029 
00030 
00031 template <class Y> MY_INLINE RTreeNode<Y>::RTreeNode (Y data, double tol,
00032                                                       int max_children,
00033                                                       int min_children)
00034 {
00035   maxChildren = max_children;
00036   minChildren = min_children;
00037   myChildrenNodes = new RTreeNode<Y>* [maxChildren];
00038   int ii;
00039   for ( ii = 0; ii < maxChildren; ii++ )
00040     myChildrenNodes[ii] = (RTreeNode<Y>*) NULL;
00041   if ( data == NULL )
00042   {
00043     PRINT_ERROR("Building RTree with null data is not allowed!\n");
00044     assert(data != NULL);
00045   }
00046   myData = data;
00047   myLevel = DATA_RNODE;
00048   CubitBox temp_box = data->bounding_box();
00049     //Check to see if any of the min/max pairs are less than the tolerance.
00050     //make them bigger if they are...
00051   CubitVector min = temp_box.minimum();
00052   CubitVector max = temp_box.maximum();
00053   if ( max.x() - min.x() < tol )
00054   {
00055     min.x(min.x()-.6*tol);
00056     max.x(max.x()+.6*tol);
00057   }
00058   if ( max.y() - min.y() < tol )
00059   {
00060     min.y(min.y()-.6*tol);
00061     max.y(max.y()+.6*tol);
00062   }
00063   if ( max.z() - min.z() < tol )
00064   {
00065     min.z(min.z()-.6*tol);
00066     max.z(max.z()+.6*tol);
00067   }
00068   myBoundingBox = new CubitBox(min, max);
00069   myParent = NULL;
00070   nextChildIndex = 0;
00071   markedFlag = 0;
00072   distIsBox = 1;
00073   myDist = CUBIT_DBL_MAX;
00074 }
00075 template <class Y> MY_INLINE RTreeNode<Y>::RTreeNode (CubitBox &bounding_box,
00076                                                       int max_children,
00077                                                       int min_children)
00078 {  
00079   maxChildren = max_children;
00080   minChildren = min_children;
00081   myBoundingBox = new CubitBox(bounding_box);
00082   myChildrenNodes = new RTreeNode<Y>* [maxChildren];
00083   int ii;
00084   for ( ii = 0; ii < maxChildren; ii++ )
00085     myChildrenNodes[ii] = (RTreeNode<Y>*) NULL;
00086   myData = NULL;
00087   myLevel = UNSET_RNODE;
00088   myParent = NULL;
00089   nextChildIndex = 0;
00090   markedFlag = 0;
00091   distIsBox = 1;
00092   myDist = CUBIT_DBL_MAX;
00093 }
00094 //-----------------------------------------------------------
00095 // Destructor
00096 //-----------------------------------------------------------
00097 template <class Y> MY_INLINE RTreeNode<Y>::~RTreeNode()
00098 {
00099   if ( myChildrenNodes )
00100     delete [] myChildrenNodes;
00101   if ( myBoundingBox )
00102     delete myBoundingBox;
00103 }
00104 
00105 //-----------------------------------------------------------
00106 // Algorithm: insert
00107 //  Insert a new index entry e into an R-Tree.
00108 //     I1. [Find postiion for new record] Invoke choose_leaf to select
00109 //        a leaf node in l, in which to place e.
00110 //     I2. [Add record to leaf node].a) If l has room for
00111 //        another entry, install E. b) Otherwise invoke split_node to
00112 //        obtain l and ll containing e and all the old entries of l.
00113 //     I3. [Propogate changes upward] Invoke adjust_tree on l, also passing ll
00114 //        if a split was performed.
00115 //     I4. [Grow Tree Taller] If node split propogation caused the root
00116 //         to split create a new root whose children are the two resulting
00117 //         nodes.
00118 //-----------------------------------------------------------
00119 template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::insert(RTreeNode<Y> *e, RTreeNode<Y> *&new_root)
00120 {
00121   CubitStatus stat;
00122   new_root = NULL;//only set this if the root node changes.  Assume
00123     //that this RTreeNode object is the root...
00124 
00125   
00126     // I1. Invoke choose_leaf to select a leaf node l in which to place
00127     //e
00128   RTreeNode<Y> *l = choose_leaf(this, e);
00129     //just test.
00130     // make sure l is not null.
00131     // make sure l is one level above e.
00132   if ( l ==  NULL || l->get_leaf_level() != (e->get_leaf_level() + 1) )
00133   {
00134     PRINT_ERROR("Choosing leaf for inseartion into rtree failed.\n");
00135     return CUBIT_FAILURE;
00136   }
00137   RTreeNode<Y> *ll = NULL;
00138     //I2 a) If l has room for another entry install e.
00139   if ( l->can_add() )
00140   {
00141     l->add_child(e, CUBIT_TRUE);
00142   }
00143   else
00144   {
00145       //I2 b)
00146       //Otherwise invoke split_node to obtain l and ll containing e and
00147       //all the old entries of l.
00148     stat = quadratic_split_node(l,e,ll);
00149     if ( stat != CUBIT_SUCCESS || ll == NULL )
00150     {
00151       PRINT_ERROR("Problems splitting node during insertion to RTree.\n");
00152       return CUBIT_FAILURE;
00153     }
00154   }
00155     //I3.  Propagate changes upward.
00156     //I4, grow tree taller (do both inside adjust_tree...)
00157   stat = adjust_tree(l, ll, this, new_root);
00158   if ( stat!= CUBIT_SUCCESS )
00159     return stat;
00160   return CUBIT_SUCCESS;
00161 }
00162 
00163 //--------------------------------------------
00164 // Algorithm: ChooseLeaf: Select a leaf node in which to place
00165 // a new index entry e.  Recursive search the subtrees of n
00166 // until n is a leaf node.
00167 //----------------------------------------------
00168 template <class Y> MY_INLINE RTreeNode<Y>* RTreeNode<Y>::choose_leaf( RTreeNode<Y>* n,
00169                                                             RTreeNode<Y>* e )
00170 {   
00171     //If n is a leaf node, or one level greater than e,
00172     //we are done.
00173   if ( n->get_leaf_level() == (e->get_leaf_level() + 1) )
00174     return n;
00175     //Now choose the entry f in n (children of n that is)
00176     //whose bounding box f_box needs
00177     //least enlargement to include e_box. Resolve ties by
00178     //choosing the entry with the bounding box of smallest volume.
00179   double min_enlargement = CUBIT_DBL_MAX, curr_enlargement;
00180   RTreeNode<Y> *curr_node;
00181   int child_index = -1;
00182   int ii;
00183   for(ii = 0; (ii < maxChildren) && (n->myChildrenNodes[ii] != NULL); ii++  )
00184   {
00185 
00186     curr_node = n->myChildrenNodes[ii];
00187     curr_enlargement = calc_enlargement(curr_node, e);
00188     if ( curr_enlargement <= min_enlargement )
00189     {
00190       if ( curr_enlargement == min_enlargement && child_index >= 0 )
00191       {
00192           //only reset if the curr_node has a smaller volume.
00193         double curr_vol = volume(curr_node);
00194         double old_vol = volume(n->myChildrenNodes[child_index]);
00195         if ( old_vol < curr_vol )
00196           continue;
00197       }
00198       child_index = ii;
00199       min_enlargement = curr_enlargement;
00200     }  
00201   }
00202     //do error checking...
00203   if ( child_index == -1 || child_index >= maxChildren )
00204     return (RTreeNode<Y>*)NULL;
00205   RTreeNode<Y> *f = n->myChildrenNodes[child_index];
00206     //Now continue on...
00207   curr_node = choose_leaf(f,e);
00208   return curr_node;
00209 }
00210 //----------------------------------------------------------------------
00211 // calc_enlargement:  Calculate the enlargement required for increasing
00212 // the bounding box of current so that it would encapsulate the bounding
00213 // box of add_to.  So to do that, create the union of the two bounding
00214 // boxes, then of that supper box subtrace the volume of the current.
00215 // The result should be the volumetric difference between how much
00216 // current has and how much it would need be or the enlargement.
00217 //----------------------------------------------------------------------
00218 template <class Y> MY_INLINE double RTreeNode<Y>::calc_enlargement(RTreeNode<Y> *current, RTreeNode<Y> *add_to )
00219 {
00220     //The enlargement area is the volume of the box that would
00221     //be the union of current and add_to minus the volume of the current.
00222   CubitBox curr_box = current->bounding_box();
00223   CubitBox add_to_box = add_to->bounding_box();
00224   CubitBox supper = curr_box;
00225     //Unite add_to_box to the curr_box.
00226   supper|= add_to_box;
00227   double area_big = volume(supper);
00228   return area_big - volume(current);
00229 }
00230 template <class Y> MY_INLINE double RTreeNode<Y>::calc_enlargement(CubitBox &current, CubitBox &add_to )
00231 {
00232     //The enlargement area is the volume of the box that would
00233     //be the union of current and add_to minus the volume of the current.
00234   CubitBox supper = current;
00235     // unite the add_to box.
00236   supper |= add_to;
00237   double area_big = volume(supper);
00238   return area_big - volume(current);
00239 }
00240 //------------------------------------------------------------------
00241 // Algorithm: adjust_tree
00242 // Description:  Ascend from a leaf node L to the root, adjusting covering
00243 // bounding boxes and propagating nodes splits as necesary.
00244 //------------------------------------------------------------------
00245 template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::adjust_tree(RTreeNode<Y> *l, RTreeNode<Y> *ll,
00246                                    RTreeNode<Y> *root_node,
00247                                    RTreeNode<Y> *&new_root)
00248 {
00249   CubitStatus stat;
00250   //we need to move up the tree and correct things that have changed.
00251   if ( l == root_node )
00252   {
00253     if ( ll == NULL )
00254       return CUBIT_SUCCESS;
00255     else
00256     {
00257         //Create a new root node and store l and ll there
00258       CubitBox root_box = l->bounding_box();
00259       root_box |= ll->bounding_box();
00260       new_root = new RTreeNode<Y>(root_box, maxChildren, minChildren);
00261       int new_level = l->get_leaf_level() + 1;
00262       new_root->set_leaf_level(new_level);
00263       new_root->add_child(l, CUBIT_TRUE);
00264       new_root->add_child(ll, CUBIT_TRUE);
00265       return CUBIT_SUCCESS;
00266     }
00267   }
00268   RTreeNode<Y> *parent_node = l->get_parent();
00269   RTreeNode<Y> *new_group = NULL;
00270   if ( ll != NULL )
00271   {
00272       //We need to add ll to the parent if we can,
00273       //and then we need to update the parent's bounding box...
00274     if ( parent_node->can_add() )
00275     {
00276       parent_node->add_child(ll, CUBIT_FALSE);
00277         //we need to recalculate the bounding box for the
00278         //entire set since both l and ll were modified...
00279       parent_node->recalc_b_box();
00280     }
00281     else
00282     {
00283         //Now we must split the children of the parent. l should
00284         //already be in the chilren list of the paretn.  So send
00285         //to split node the parent_node and ll.
00286         //parent node during this process will have its b_box recalced.
00287       stat = quadratic_split_node(parent_node, ll, new_group);
00288       if ( stat != CUBIT_SUCCESS || new_group == NULL )
00289       {
00290         PRINT_ERROR("Problems splitting node during insertion to RTree.\n");
00291         return CUBIT_FAILURE;
00292       }
00293     }
00294   }
00295   else
00296   {
00297       //just recalulate the b_box for the parent_node.
00298     parent_node->recalc_b_box();
00299   }
00300   stat = adjust_tree(parent_node, new_group, root_node, new_root);
00301   if ( stat != CUBIT_SUCCESS )
00302     return CUBIT_FAILURE;
00303   return CUBIT_SUCCESS;
00304 }
00305 //------------------------------------------------------------------
00306 // Algorithm: quadratic_split_node
00307 //  Description:  For the RTree, this is where most of the variations
00308 //  on implementations have occured.  The best method proposed by Guttman
00309 //  was a quadratic split, which I'll implement here.  The Rstar tree
00310 //  did some slightly more complicated things which I might try later.
00311 // Description of function:
00312 //  e is the node to which we want to add l, but l's children's list
00313 //  is full.  Split the children of l and e up into two groups.  The
00314 //  groups are stored in l and ll.
00315 // Assume:  assume that l's myChildrenNodes are maxChildren in size.
00316 //
00317 //  Divide a set of maxChildren + 1 index entries into two groups.
00318 //  QS1  [Pick first entry for each group]  Apply algorithm pick_seeds,
00319 //       to choose two entries to be the first elements of the groups.
00320 //       Assign each to a group.
00321 //  QS2  [Check if done]  If all entries have been assigned, stop.
00322 //       If one group has so few entries that all the rest must
00323 //       be assigned to it in order for it to have the minimum number m,
00324 //       assign them and stop.
00325 //  QS3  [Select entry to assign]  Invoke Algorithm pick_next to choose
00326 //       the next entry to assign.  Add it to the group whose covering
00327 //       rectangle will have to be enlarged least to accommodate it.
00328 //       Resolve ties by adding the entry to the group with the smaller
00329 //       volume, then to the one with fewer entries, then to either. Repeat
00330 //       QS2.
00331 //
00332 //------------------------------------------------------------------
00333 template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::quadratic_split_node( RTreeNode<Y> *l,
00334                                              RTreeNode<Y> *e,
00335                                              RTreeNode<Y> *&ll )
00336 {
00337   int ii;
00338     //create a new list containing all the nodes we want to split.
00339   RTreeNode<Y> **input_list = new RTreeNode<Y>* [maxChildren + 1];
00340   DLIList <RTreeNode<Y>*> nodes_remaining;
00341   for ( ii = 0; ii < maxChildren; ii++ )
00342   {
00343     input_list[ii] = l->myChildrenNodes[ii];
00344   }
00345   input_list[maxChildren] = e;
00346   
00347     //QS1, pick first entry for each group.
00348   RTreeNode<Y> *seed_1, *seed_2;
00349   CubitStatus stat = pick_seeds(input_list, maxChildren+1,seed_1,
00350                                 seed_2);
00351   if ( stat != CUBIT_SUCCESS )
00352   {
00353     delete [] input_list;
00354     return stat;
00355   }
00356     //now flush out l. This cleans out the bounding box and
00357     //chindrenNodes and resets the bounding box.  Also
00358     //create ll, make l and ll non-leaf nodes and add
00359     //seed_1 and seed_2 to l and ll. (doesn't matter which...)
00360   l->flush(seed_1->bounding_box());
00361   l->add_child(seed_1, CUBIT_FALSE);
00362     //this is still a leaf node.
00363     //this will change if necessary the parent...
00364   l->set_leaf_level(e->get_leaf_level() + 1);
00365   ll = new RTreeNode<Y>(seed_2->bounding_box(), maxChildren, minChildren );
00366   ll->add_child(seed_2, CUBIT_FALSE);
00367   ll->set_leaf_level(l->get_leaf_level());
00368     //build the nodes remaining list...
00369   for ( ii = 0; ii < maxChildren+1; ii++ )
00370   {
00371     if ( input_list[ii] != seed_1 &&
00372          input_list[ii] != seed_2 )
00373       nodes_remaining.append(input_list[ii]);
00374   }
00375   delete [] input_list;
00376   RTreeNode<Y> *next_node;
00377   CubitBoolean add_to_group_1;
00378     //Q2
00379   while (nodes_remaining.size() > 0 )
00380   {
00381       //Q2 continued.
00382     if ( l->space_left() < minChildren &&
00383          minChildren - l->space_left() >= nodes_remaining.size() )
00384     {
00385         //just add the rest of the nodes to l.
00386       for ( ii = nodes_remaining.size(); ii > 0; ii-- )
00387         l->add_child(nodes_remaining.get_and_step(), CUBIT_TRUE);
00388       nodes_remaining.clean_out();
00389       break;
00390     }
00391     else if ( ll->space_left() < minChildren &&
00392          minChildren - ll->space_left() >= nodes_remaining.size() )
00393     {
00394         //just add the rest of the nodes to l.
00395       for ( ii = nodes_remaining.size(); ii > 0; ii-- )
00396         ll->add_child(nodes_remaining.get_and_step(), CUBIT_TRUE);
00397       nodes_remaining.clean_out();
00398       break;
00399     }
00400       //Q3
00401       //pick next selects the next node and the group to
00402       //put it in.  It also removes the node from nodes remaining.
00403       //Some of these steps were added to pick next for efficiency...
00404     stat = pick_next(nodes_remaining, l, ll, next_node,
00405                      add_to_group_1 );
00406     if ( stat != CUBIT_SUCCESS )
00407       return stat;
00408     if ( add_to_group_1 )
00409       l->add_child(next_node, CUBIT_TRUE);
00410     else
00411       ll->add_child(next_node, CUBIT_TRUE);
00412   }
00413   return CUBIT_SUCCESS;
00414 }
00415 template <class Y> MY_INLINE void RTreeNode<Y>::flush( CubitBox &new_box )
00416 {
00417   int ii;
00418   nextChildIndex = 0;
00419   for ( ii = 0; ii < maxChildren; ii++ )
00420     myChildrenNodes[ii] = NULL;
00421   delete myBoundingBox;
00422   myBoundingBox = new CubitBox(new_box);
00423 }
00424 template <class Y> MY_INLINE void RTreeNode<Y>::add_child(RTreeNode<Y> *child_node,
00425                                                 CubitBoolean recalc_b_box)
00426 {
00427   assert(nextChildIndex < maxChildren && child_node != NULL );
00428   myChildrenNodes[nextChildIndex] = child_node;
00429     //update the bounding box. by uniting with child node...
00430   if ( recalc_b_box )
00431   {
00432     CubitBox *old_box = myBoundingBox;
00433     myBoundingBox = new CubitBox( *old_box |= child_node->bounding_box());
00434     delete old_box;
00435   }
00436   nextChildIndex++;
00437   child_node->set_parent(this);
00438 }
00439 template <class Y> MY_INLINE CubitBoolean RTreeNode<Y>::can_add()
00440 {
00441   if (nextChildIndex >= maxChildren )
00442     return CUBIT_FALSE;
00443   else
00444     return CUBIT_TRUE;
00445 }
00446 template <class Y> MY_INLINE int RTreeNode<Y>::space_left()
00447 {
00448   return maxChildren - nextChildIndex;
00449 }
00450 //------------------------------------------------------------------
00451 // Algorithm pick_seeds: 
00452 //  Select two entries to be the first elements of the groups.
00453 //  PS1 [Calculate inefficiency of grouping entries together] For
00454 //      each pair of entries, e1 and e2, compose a rectangle (bounding_box)
00455 //      j, including e1 and e2, calculate:
00456 //      d = volume(j) - volume(e1) - volume(e2)
00457 //  PS2 [Choose the most wasteful pair] Choose the pair with the largest
00458 //      d.
00459 //------------------------------------------------------------------
00460 template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::pick_seeds(RTreeNode<Y> **input_list,
00461                                                         const int input_list_size,
00462                                                         RTreeNode<Y> *&seed_1,
00463                                                         RTreeNode<Y> *&seed_2)
00464 {
00465   int ii, jj;
00466   RTreeNode<Y> *e_1, *e_2;
00467   CubitBox e_box_1, e_box_2, j;
00468   double d, max_d = -CUBIT_DBL_MAX;
00469   seed_1 = (RTreeNode<Y>*)NULL;
00470   seed_2 = (RTreeNode<Y>*)NULL;
00471   
00472   for(ii = 0; ii < input_list_size; ii++ )
00473   {
00474     e_1 = input_list[ii];
00475     e_box_1 = e_1->bounding_box();
00476     for ( jj = ii+1; jj < input_list_size; jj++ )
00477     {
00478       e_2 = input_list[jj];
00479       e_box_2 = e_2->bounding_box();
00480         //unite the boxes.
00481       j = e_box_1;
00482       j |= e_box_2;
00483         //find the most wastefull boxes to separate the groups.
00484       d = volume(j) - volume(e_box_1) - volume(e_box_2);
00485       if ( d > max_d )
00486       {
00487         seed_1 = e_1;
00488         seed_2 = e_2;
00489         max_d = d;
00490       }
00491     }
00492   }
00493   return CUBIT_SUCCESS;
00494 }
00495 //------------------------------------------------------------------
00496 // Algorithm pick_next: 
00497 //  Select one remaining entry for classification in a group.
00498 //  PN1 [Determine cost of putting each entry in group] For each entry
00499 //      e not yet in a group, calculate d1 = area increase required in the
00500 //      covering rectangle of group_1 to include E.  Calculate d2 similarly
00501 //      for group_2
00502 //  PN2 [Find entry with greatest preference for one group]  Choose
00503 //      any entry with the maximum difference between d1 and d2.
00504 //------------------------------------------------------------------
00505 template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::pick_next(DLIList <RTreeNode<Y>*> &remaining_nodes,
00506                                                        RTreeNode<Y>* group_1,
00507                                                        RTreeNode<Y>* group_2,
00508                                                        RTreeNode<Y>*& next,
00509                                                        CubitBoolean &add_to_group_1)
00510 {
00511   int ii, next_index = 0;
00512   double d1, d2, max_diff = -CUBIT_DBL_MAX;
00513   add_to_group_1 = CUBIT_TRUE;
00514   RTreeNode<Y> *max_diff_node = (RTreeNode<Y>*)NULL;
00515   RTreeNode<Y> *curr_node;
00516   CubitBox group_1_box = group_1->bounding_box();
00517   CubitBox group_2_box = group_2->bounding_box();
00518   CubitBox curr_box;
00519   double v1 = volume(group_1_box);
00520   double v2 = volume(group_2_box);
00521   remaining_nodes.reset();
00522   for ( ii = 0; ii < remaining_nodes.size(); ii++ )
00523   {
00524     curr_node = remaining_nodes.get_and_step();
00525     curr_box = curr_node->bounding_box();
00526     d1 = calc_enlargement(group_1_box, curr_box);
00527     d2 = calc_enlargement(group_2_box, curr_box);
00528     if ( d1 > d2 )
00529     {
00530       if ( max_diff < d1 - d2 )
00531       {
00532         //add to group whose covering area would have
00533         //to be enlarged least.
00534         add_to_group_1 = CUBIT_FALSE;
00535         max_diff = d1 - d2;
00536         max_diff_node = curr_node;
00537         next_index = ii;
00538       }
00539     }
00540     else if ( d2 > d1 )
00541     {
00542       if ( max_diff < d2 - d1 )
00543       {
00544         //add to group whose covering area would have
00545         //to be enlarged least.
00546         add_to_group_1 = CUBIT_TRUE;
00547         max_diff = d2 - d1;
00548         max_diff_node = curr_node;
00549         next_index = ii;
00550       }
00551     }
00552     else {
00553       if ( max_diff < 0.0 )
00554       {
00555           //Add to group with smaller area.
00556         if ( v1 < v2 )
00557           add_to_group_1 = CUBIT_TRUE;
00558         else if ( v2 < v1 )
00559           add_to_group_1 = CUBIT_FALSE;
00560         else
00561         {
00562             //add to group with fewest entries.
00563           int num_left_1 = group_1->space_left();
00564           int num_left_2 = group_2->space_left();
00565           if ( num_left_1 > num_left_2 )
00566             add_to_group_1 = CUBIT_TRUE;
00567           else
00568             add_to_group_1 = CUBIT_FALSE;
00569         }
00570         max_diff = 0.0;
00571         max_diff_node = curr_node;
00572         next_index = ii;
00573       }
00574     }
00575   }
00576   next = NULL;
00577   if ( max_diff_node == NULL )
00578     return CUBIT_FAILURE;
00579   else
00580     next = max_diff_node;
00581     //remove next from the remaining_nodes list.
00582   remaining_nodes.reset();
00583   remaining_nodes.step(next_index);
00584   RTreeNode<Y> *check_node = remaining_nodes.remove();
00585   if ( check_node != max_diff_node )
00586   {
00587     PRINT_ERROR("Error in pick next algorithm logic of rtree...");
00588     return CUBIT_FAILURE;
00589   }
00590   return CUBIT_SUCCESS;
00591 }
00592 template <class Y> MY_INLINE void RTreeNode<Y>::recalc_b_box()
00593 {
00594   if(myLevel == DATA_RNODE )
00595     return;
00596   int ii;
00597   CubitBox temp_box;
00598   CubitBoolean first_box = CUBIT_TRUE;
00599   for ( ii = 0; ii < nextChildIndex; ii++ )
00600   {
00601     if ( first_box )
00602     {
00603       temp_box = myChildrenNodes[ii]->bounding_box();
00604       first_box = CUBIT_FALSE;
00605     }
00606     else
00607       temp_box |= myChildrenNodes[ii]->bounding_box();
00608   }
00609   delete myBoundingBox;
00610   myBoundingBox = new CubitBox(temp_box);
00611   return;
00612 }
00613 //-------------------------------------------------------------
00614 // Algorithm: remove.  Remove index record e from an R-tree.
00615 //   D1)  [Find node containing record].  Invoke find_leaf to locate
00616 //        the leaf node l containing e.  Stop if the record was not
00617 //        found.
00618 //   D2)  [Delete record.]  Remove e from l.
00619 //   D3)  [Propagate changes.]  Invoke CondenseTree, passing L.
00620 //   D4)  [Shorten tree.]  If the root node has only one child
00621 //        after the tree has been adjusted, make the child the new
00622 //        root.
00623 //-------------------------------------------------------------
00624 template <class Y> MY_INLINE CubitBoolean RTreeNode<Y>::remove( Y e,
00625                                                       RTreeNode<Y> *&new_root,
00626                                                       CubitBoolean &delete_root)
00627 {
00628     //D1) Find node containting record.
00629   if(this->is_data()){
00630     if(this->get_data() == e){
00631       myData = NULL;
00632       myLevel = UNSET_RNODE;
00633       return CUBIT_TRUE;
00634     }
00635     else if(this->num_children() == 0){
00636       return CUBIT_FALSE;
00637     }
00638   }
00639   RTreeNode<Y> *l = NULL;
00640   CubitBox my_box = e->bounding_box();
00641   CubitStatus stat = find_leaf(e, my_box, this, l);
00642   if ( l == NULL || stat != CUBIT_SUCCESS )
00643     return CUBIT_FALSE;
00644     //Now l is the RTreeNode that holds the actual data (a DATA_RNODE)
00645     //not a leaf.  This was done for efficiency.
00646   RTreeNode<Y> *data_node = l;
00647   l = data_node->get_parent();
00648     //D2) [Delete record]  Remove e from l.
00649   
00650     //remove the data node from the children and delete
00651     //the node.
00652   l->remove_child(data_node);
00653   delete data_node;
00654 
00655     //D3) [Propogate Changes].
00656   stat = condense_tree(l, this, new_root);
00657     //D4) [Shorten the tree].
00658   RTreeNode<Y> *root = this;
00659   if ( new_root != NULL )
00660     root = new_root;
00661   if ( root->num_children() == 1 )
00662   {
00663     new_root = root->get_child(0);
00664     new_root->set_parent((RTreeNode<Y>*)NULL);
00665     delete_root = CUBIT_TRUE;
00666   }
00667   return CUBIT_TRUE;
00668 }
00669 template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::find_leaf( Y e,
00670                                                         CubitBox &e_box,
00671                                                         RTreeNode<Y> *t,
00672                                                         RTreeNode<Y> *&l )
00673 {
00674   int ii;
00675   l = NULL;
00676   int loop_size = t->num_children();
00677   RTreeNode<Y> *curr_node;
00678   if ( t->get_leaf_level() > LEAF_RNODE )
00679   {
00680     for ( ii = 0; ii < loop_size; ii++ )
00681     {
00682       curr_node = t->get_child(ii);
00683       if ( curr_node == NULL )
00684       {
00685         PRINT_ERROR("Problems finding boxes in range.\n");
00686         assert(curr_node != NULL);
00687         return CUBIT_FAILURE;
00688       }
00689       if ( e_box.overlap(GEOMETRY_RESABS, curr_node->bounding_box()) )
00690       {
00691           //okay now search through this now.
00692         find_leaf(e, e_box,curr_node,l);
00693         if ( l != NULL )
00694           return CUBIT_SUCCESS;
00695       }
00696     }
00697   }
00698   else if ( t->is_leaf() )
00699   {
00700       //search through the children for e.
00701     for ( ii = 0; ii < loop_size; ii++ )
00702     {
00703       curr_node = t->get_child(ii);
00704       if ( curr_node == NULL )
00705       {
00706         PRINT_ERROR("Problems finding boxes in range.\n");
00707         assert(curr_node != NULL);
00708         return CUBIT_FAILURE;
00709       }
00710       if ( curr_node->get_data() == e )
00711       {
00712         l = curr_node;
00713         return CUBIT_SUCCESS;
00714       }
00715     }
00716   }
00717   return CUBIT_SUCCESS;
00718 }
00719 template <class Y> MY_INLINE CubitBoolean RTreeNode<Y>::remove_child( RTreeNode<Y> *child )
00720 {
00721     //first find which item this child is at.
00722   int ii;
00723   int index_child = -1;
00724   int loop_size = this->num_children();
00725   for ( ii = 0; ii < loop_size; ii++ )
00726   {
00727     if ( myChildrenNodes[ii] == child )
00728       index_child = ii;
00729   }
00730   if ( index_child == -1 )
00731     return CUBIT_FALSE;
00732     //Now we need to bubble the array from this point
00733     //upward.
00734   for ( ii = index_child; ii < loop_size-1; ii++ )
00735   {
00736     myChildrenNodes[ii] = myChildrenNodes[ii+1];
00737   }
00738     //decrement the position of the next available child.
00739   nextChildIndex--;
00740     //now go from nextChildIndex to the end and make sure it is
00741     //null.
00742   for (ii = nextChildIndex; ii < maxChildren; ii++ )
00743     myChildrenNodes[ii] = NULL;
00744   
00745   return CUBIT_TRUE;
00746 }
00747 //--------------------------------------------------------------------------
00748 // Algorithm: condense_tree
00749 //  Given a leaf node l from which an entry has been deleted, eliminate
00750 //  the node if it has too few entries and relocate its entries.  Propagate
00751 //  node elimination upaward as necessary.  Adjust all covering rectangles
00752 //  on the path to the root, making them smaller if possible.
00753 //  CT1) [Initialize]  Set n=l, Set q, the set of eliminated nodes, to be
00754 //       empty.
00755 //  CT2) [Find parent entry]  If n is the root, go to CT6.  Otherwise
00756 //       let p be the parent of n, and let en be n's entry in p.
00757 //  CT3) [Eliminate under-full node.] If n has fewer than minChildren,
00758 //       delete en from p and add n to set q.
00759 //  CT4) [Adjust covering rectangle]  If n has not been eliminated, adjust
00760 //       en's bounding box to tightly contain all entries in n.
00761 //  CT5) [Move up one level in tree] Set n=p, and repeat from CT2.
00762 //  CT6) [Reinsert orphaned entries].  Reinsert all entries of nodes in set q.
00763 //       entries from eliminated leaf nodes are re-inserted in tree leaves
00764 //       as described in algorithm insert, but entries from higher-level
00765 //       nodes must be placed higher in the tree so that leaves of their
00766 //       dependent subtrees will be on the same level as leaves of the
00767 //       main tree.
00768 //--------------------------------------------------------------------------
00769 template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::condense_tree(RTreeNode<Y> *l,
00770                                                            RTreeNode<Y> *root,
00771                                                            RTreeNode<Y> *&new_root )
00772 {
00773   int ii;
00774   new_root = NULL;
00775     //CT1)
00776   RTreeNode<Y> *n = l, *p;
00777   DLIList <RTreeNode<Y>*> set_q;
00778     //CT2)
00779   while ( n != root )
00780   {
00781     p = n->get_parent();
00782     if ( n->num_children() < minChildren )
00783     {
00784         //CT3
00785         //take these children and add them to set_q.
00786       for ( ii = 0;ii < n->num_children(); ii++ )
00787         set_q.append(n->get_child(ii));
00788         //remove n from p.
00789       p->remove_child(n);
00790         //delete n.
00791       delete n;
00792         //now continue on.
00793     }
00794     else
00795     {
00796         //CT4
00797       n->recalc_b_box();
00798     }
00799       //CT5
00800     n = p;
00801   }
00802     //now reinsert all nodes in set_q.
00803   RTreeNode<Y> *curr_node, *temp_root;
00804   temp_root = root;
00805   for (ii = set_q.size(); ii > 0; ii-- )
00806   {
00807     curr_node = set_q.get_and_step();
00808     temp_root->insert(curr_node, new_root);
00809     if ( new_root != NULL )
00810       temp_root = new_root;
00811   }
00812   if ( temp_root != root )
00813     new_root = temp_root;
00814   return CUBIT_SUCCESS;
00815 }
00816 
00817 
00818 
00819   
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines