1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
///--------------------------------------------------------------------------
// 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 <--- 'class RStarTreeNode' does not have a copy constructor which is recommended since the class contains a pointer to allocated memory.<--- 'class RStarTreeNode' does not have a copy constructor which is recommended since the class contains a pointer to allocated memory.
{
private:
    //Data.
  IttyBit markedFlag : 1;
    ///
    ///Generic mark flag.
    ///
  IttyBit distIsBox : 1;
  int myId;
  
    ///
    ///Mark if the distance measured is to the
    ///bounding box or the real data.  This is
    ///for the nearest neighbor search.
    ///
  RStarTreeNode<Y>** myChildrenNodes;
  int nextChildIndex;
  CubitBox *myBoundingBox;
  Y myData;
  int maxChildren, minChildren; //max/min number of children.
  RStarTreeNode<Y> *myParent;
  int myLevel;
    ///
    ///Level of node
    ///Level 0 equals data level.
    ///Level 1 equals leaf node level.
    ///Higher levels are non-leaf node levels.
    ///
  double myDist;
    ///
    ///used for nearest neigbhor searches...
    ///
  
  

    //Functions.
  RStarTreeNode<Y>* choose_sub_tree( RStarTreeNode<Y> *n, RStarTreeNode<Y> *e );
    ///
    /// Select a leaf node in which to place
    /// a new index entry e.  Recursive search the subtrees of n
    /// until n is a leaf node.
    ///

  CubitStatus overflow_treatment( RStarTreeNode<Y>* l,
                                  RStarTreeNode<Y>* e,
                                  RStarTreeNode<Y> *&ll,
                                  RStarTreeNode<Y> *root,
                                  RStarTreeNode<Y> *&new_root,
                                  int *overflow_flags, int levels);
    ///
    /// Determines if the node should be split or if nodes should be reinserted.
    /// If this is not the first time that the nodes have been overflown on this
    /// level (as determed by the overflow flags), then remove p items and reinsert
    /// them hoping to get a better box distribution.  Otherwise, split the node.
    /// We spend more time reinserting and less time splitting on average
    /// so the result is a better tree at basically the same cost.
    ///

  CubitStatus reinsert(RStarTreeNode<Y>* l,
                       RStarTreeNode<Y>* e,
                       RStarTreeNode<Y> *root,
                       RStarTreeNode<Y> *&new_root,
                       int *overflow_flags, int levels);
    ///
    /// Sorts the elements based on their distance to the centroid of the bounding rectangle.
    /// reinserts the top p nodes back into the tree (after removing them first of course.)
    ///

  
  CubitStatus adjust_tree(RStarTreeNode<Y> *l, RStarTreeNode<Y> *ll,
                          RStarTreeNode<Y> *root_node,
                          RStarTreeNode<Y> *&new_root,
                          int *overflow_flags,
                          int levels);
    ///
    /// Ascend from a leaf node L to the root, adjusting covering
    /// bounding boxes and propagating nodes splits as necesary.
    ///

  CubitStatus split_node( RStarTreeNode<Y> *l,
                          RStarTreeNode<Y> *e,
                          RStarTreeNode<Y> *&ll );
    ///
    /// Since element e won't fit into l, split l into two groups, l and ll.
    /// For the RTree, this is where most of the variations
    /// on implementations have occured.  Hopefully this is the best
    /// method for splitting.  Though I have seen some optimizations or variations
    /// on this that have claimed slightly better performance for given algorithms.
    ///
  double calc_overlap( RStarTreeNode<Y> *current,
                       RStarTreeNode<Y> *add_to);
    ///
    /// Calculates the current overlap between current's children nodes
    /// and add's to it the overlap that would occur from adding add_to to
    /// that list.
    ///
  
  double calc_enlargement( RStarTreeNode<Y> *current, RStarTreeNode<Y> *add_to );
  double calc_enlargement( CubitBox &current,
                           CubitBox &add_to );
    ///
    /// Calculate the enlargement required for increasing
    /// the bounding box of current so that it would encapsulate
    /// the bounding box of add_to.
    ///

  CubitStatus find_leaf( Y e,
                         CubitBox &e_box,
                         RStarTreeNode<Y> *t,
                         RStarTreeNode<Y> *&l );
    ///
    /// find the entry e in the tree t.  l
    /// is the entry that contains e. (e is a data member of l).
    /// The parent of l, is the leaf node containing it.
    ///

  CubitStatus condense_tree(RStarTreeNode<Y> *l,
                            RStarTreeNode<Y> *root,
                            RStarTreeNode<Y> *&new_root );
    ///
    ///  Given a leaf node l from which an entry has been deleted, eliminate
    ///  the node if it has too few entries and relocate its entries.  Propagate
    ///  node elimination upaward as necessary.  Adjust all covering rectangles
    ///  on the path to the root, making them smaller if possible.
    ///
    
  
  double volume(CubitBox &box);
    ///
    /// Calculate the volume of the box.
    ///
  double volume(RStarTreeNode<Y>* curr);
    ///
    /// Calculate the volume of the RStarTreeNode.
    ///

  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);
    ///
    /// Functions to help sort the DLIList (thats why they are static).
    /// Returns -1 if n_1 is < than n_2 in that dimension, 0 if they
    /// are equivalent or 1.
    ///

  static int sort_center_distance( RStarTreeNode<Y> *&n_1,
                                   RStarTreeNode<Y> *&n_2 );
    ///
    /// Function for sorting during the reinsert function.
    /// Returns -1 if n_1->get_dist() is > than n_2, 0 if equal,
    /// else 1.
    ///

  

  double margin(CubitBox &bounding_box);
    ///
    /// Calculates the margin of the mounding box
    /// margin = ([xmax-xmin]+[ymax-ymin]+[zmax-zmin])*2^(d-1))
    ///

  CubitBox super_box(DLIList<RStarTreeNode<Y>*> &node_list);
    ///
    /// Finds the bounding box of all the nodes in the list.
    ///

public:
  RStarTreeNode(Y data, double tol, int max_children, int min_children );
    ///
    /// Constructor for data.
    ///
  RStarTreeNode(CubitBox &bounding_box, int max_children, int min_children);
    ///
    /// Constructor for typical parent node.
    ///
  
  ~RStarTreeNode();
    /// Constructor/Destructor

  void validate_tree(int print);
    /// Makes sure the children point to parents...

  CubitStatus insert(RStarTreeNode<Y> *e, RStarTreeNode<Y> *&new_root,
                     int *overflow_flags, int levels);
    ///
    /// Inserts the node e into the proper position of this.  Assumeing
    /// this is the root.  Sometimes the root will need to be split,
    /// so a new root may be returned.  If the new_root is not null,
    /// then the new_root must take the place of this...
    /// The overflow_flow flags variable needs to be initialized to
    /// be an aray of size equal to the number of levels + 1, and initialized
    /// to have values of zero.  The internal code uses this as to flag
    /// the levels as they get treated for overflow.
    ///

  void set_leaf_level(int r_type)
  {myLevel = r_type;}
    ///
    /// Set the type of level of the node.
    ///
  int get_leaf_level()
    {return myLevel;}
    ///
    /// get the level of the node.
    ///

  CubitBoolean is_leaf()
    {return (myLevel == LEAF_RSTARNODE)? CUBIT_TRUE : CUBIT_FALSE;}
    ///
    /// Determine if the RStarTreeNode is a leaf node.
    ///

  CubitBoolean is_data()
    {return (myLevel == DATA_RSTARNODE)? CUBIT_TRUE : CUBIT_FALSE;}
    ///
    /// Determine if the RStarTreeNode is a leaf node.
    ///

  Y get_data()
    {return myData;}
    ///
    /// Determine if the RStarTreeNode is a leaf node.
    ///
  
  void add_child(RStarTreeNode<Y>* child_node, CubitBoolean recalc_b_box);
    ///
    /// Add the child to the myChildrenNodes' list. Adds
    /// it to the next availabel spot.  Won't add if overflow will
    /// occur.
    ///
  
  CubitBoolean can_add();
    ///
    /// Tests if there is any space in the myChildrenNodes' list.
    ///

  int space_left();
    ///
    /// Returns the number of positions left in the myChildrenNode's list.
    ///

  int num_children()
    {return nextChildIndex;}
    ///
    /// Returns the number of children in the myChildrenNode's array.
    ///

  RStarTreeNode<Y>* get_child(int i)
    {return ((i < nextChildIndex) ? myChildrenNodes[i] : (RStarTreeNode<Y>*)NULL) ;}
  
    
  void flush(CubitBox &new_box);
    ///
    /// Clears out the myChildrenNodes by setting the array values
    /// to null.  Resets the counters and sets the range as the new_box.
    ///
  
  void recalc_b_box();
    ///
    /// recalculates the bounding box for the node. (won't do it if
    /// this is a data node...
    ///
  
  RStarTreeNode<Y> *get_parent()
    {return myParent;}
  void set_parent(RStarTreeNode<Y> *parent)
    {myParent = parent;}

  CubitBoolean remove_child(RStarTreeNode<Y> *child);
    ///
    /// Removes the child from the myChildrenNodes array and condenses
    /// the array.  decrements the number of children or increments the
    /// num positions available.
    ///

  CubitBoolean remove(Y e, RStarTreeNode<Y> *&new_root, CubitBoolean &delete_root);
    ///
    /// Removes the data e from the tree and cleans up the tree.  A new
    /// root node could be found from this.  Assume the root node is
    /// calling this function...
    ///

  CubitBox& bounding_box()
    {return *myBoundingBox;}
    ///
    /// Returns the bounding box of this node.
    ///

  double get_dist();
  void set_dist(double dis);
    ///
    /// This is used in several places to store some distance
    /// on the node.  It is used in sorting and overflow treatment.
    /// Basically at times the nodes need to be sorted according to
    /// some distance measurement.
    ///

  int dist_is_box();
  void set_dist_is_box(int val);
    ///
    /// Returns/sets the distIsBox flag used to determine if the
    /// stored distance is the distance between some object and this's
    /// bounding box or between some object and this's actual data.
    ///
  
      
};
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