Index.h
Go to the documentation of this file.
1 /* Copyright (C) 2008 National Institute For Space Research (INPE) - Brazil.
2 
3  This file is part of the TerraLib - a Framework for building GIS enabled applications.
4 
5  TerraLib is free software: you can redistribute it and/or modify
6  it under the terms of the GNU Lesser General Public License as published by
7  the Free Software Foundation, either version 3 of the License,
8  or (at your option) any later version.
9 
10  TerraLib is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU Lesser General Public License for more details.
14 
15  You should have received a copy of the GNU Lesser General Public License
16  along with TerraLib. See COPYING. If not, write to
17  TerraLib Team at <terralib-team@terralib.org>.
18  */
19 
20 /*!
21  \file Index.h
22 
23  \brief An implementation of R-tree data structure for main memory.
24 */
25 
26 #ifndef __TERRALIB_SAM_RTREE_INTERNAL_INDEX_H
27 #define __TERRALIB_SAM_RTREE_INTERNAL_INDEX_H
28 
29 // TerraLib
30 #include "Node.h"
31 #include "PartitionVars.h"
32 
33 // STL
34 #include <cassert>
35 #include <vector>
36 
37 namespace te
38 {
39  namespace sam
40  {
41  namespace rtree
42  {
43  /*!
44  \class Index
45 
46  \brief A class that represents an R-tree.
47 
48  This implementation is based on:
49 
50  <i>Antonin Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. ACM SIGMOD: International Conference on Management of Data, 1984, pp. 47-57</i>.
51 
52  and in his original source code.
53 
54  \todo Implement nearest neighbour query.
55  */
56  template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2> class Index
57  {
58  public:
59 
61  typedef typename NodeType::BranchType BranchType;
63 
64  /*! \brief Constructor. */
65  Index();
66 
67  /*!
68  \brief Constructor.
69 
70  \param mbr The MBR of all elements in the R-tree.
71 
72  \pre The given MBR must be valid.
73  */
74  Index(const te::gm::Envelope& mbr);
75 
76  /*! \brief Destructor. */
77  ~Index();
78 
79  /*!
80  \brief It returns the number of elements in the tree.
81 
82  \return The number of indexed elements.
83  */
84  std::size_t size(void) const;
85 
86  /*!
87  \brief It returns true if the tree is empty.
88 
89  \return True if the tree is empty.
90  */
91  bool isEmpty(void) const;
92 
93  /*! It clears all tree nodes and make it ready for new insertions. */
94  void clear(void);
95 
96  /*!
97  \brief It inserts an item into the tree.
98 
99  \param mbr The object MBR.
100  \param data The object to be indexed.
101  */
102  void insert(const te::gm::Envelope& mbr, const DATATYPE& data);
103 
104  /*!
105  \brief It removes an item from the tree.
106 
107  \param mbr The object MBR.
108  \param data The object to be removed from the tree.
109 
110  \return True if the object is found and removed, false otherwise.
111  */
112  bool remove(const te::gm::Envelope& mbr, const DATATYPE& data);
113 
114  /*!
115  \brief Range search query.
116 
117  \param mbr The search rectangle.
118  \param report A vector to output the founded objects.
119 
120  \return the number of found objects.
121  */
122  int search(const te::gm::Envelope& mbr, std::vector<DATATYPE>& report) const;
123 
124  /*!
125  \brief It sets the bounding box of all elements in the tree.
126 
127  \param mbr The bounding box of all elements in the tree.
128  */
129  void setMBR(const te::gm::Envelope& mbr);
130 
131  /*!
132  \brief It returns the bounding box of all elements in the tree.
133 
134  \return The bounding box of all elements in the tree.
135  */
136  const te::gm::Envelope& getMBR(void) const;
137 
138  protected:
139 
140  /*!
141  \brief It inserts a data rectangle into an index structure.
142 
143  \return It returns true if root was split, false if it was not.
144  */
145  bool insert(const te::gm::Envelope& mbr, const DATATYPE& data, NodeType** root, int level);
146 
147  /*!
148  \brief It deletes a data rectangle from an index structure.
149 
150  \return It returns 1 if record not found, 0 if success.
151  */
152  bool remove(const te::gm::Envelope& mbr, const DATATYPE& data, NodeType** root);
153 
154  /*!
155  \brief It deletes a rectangle from non-root part of an index structure.
156 
157  \return
158  */
159  bool remove2(const te::gm::Envelope& mbr, const DATATYPE& data, NodeType* n, std::vector<NodeType*>& ee);
160 
161  /*!
162  \brief It disconnects a dependent node.
163  */
164  void disconBranch(NodeType* n, int i);
165 
166  /*!
167  \brief It inserts a new data rectangle into the index structure.
168  */
169  bool chooseLeaf(const te::gm::Envelope& mbr,
170  const DATATYPE& data,
171  NodeType* node,
172  NodeType** newNode,
173  int level);
174 
175  /*!
176  \brief Recursive range query.
177  */
178  void search(const te::gm::Envelope& mbr,
179  NodeType* node,
180  std::vector<DATATYPE>& report,
181  int& foundObjs) const;
182 
183  /*!
184  \brief Find the smallest rectangle that includes all rectangles in branches of a node.
185  */
186  te::gm::Envelope nodeCover(NodeType* n) const;
187 
188  /*!
189  \brief Combine two rectangles into larger one containing both.
190  */
192  const te::gm::Envelope& mbrB) const;
193 
194  /*!
195  \brief Add a branch to a node.
196  */
197  bool addBranch(BranchType* branch,
198  NodeType* node,
199  NodeType** newNode) const;
200 
201  /*!
202  \brief Pick a branch.
203  */
204  int pickBranch(const te::gm::Envelope& mbr, NodeType* node) const;
205 
206  /*!
207  \brief Split a node.
208  */
209  void splitNode(NodeType* node, BranchType* branch, NodeType** newNode) const;
210 
211  void getBranches(NodeType* n, BranchType* b, PartitionVarsType& p) const;
212 
213  void methodZero(PartitionVarsType& p) const;
214 
215  void pickSeeds(PartitionVarsType& p) const;
216 
217  void classify(int i, int group, PartitionVarsType& p) const;
218 
219  void pigeonhole(PartitionVarsType& p) const;
220 
221  void loadNodes(NodeType* n, NodeType* q, PartitionVarsType& p) const;
222 
223  /*!
224  \brief Erases a node from the tree and all nodes below it.
225 
226  \param node The node to be removed.
227 
228  \pos The node pointer will be invalidated.
229  */
230  void erase(NodeType* node);
231 
232 
233  private:
234 
235 
236  /*!
237  \brief No copy constructor allowed.
238 
239  \param rhs The other rtree.
240  */
241  Index(const Index& rhs);
242 
243  /*!
244  \brief No assignment operator allowed.
245 
246  \param rhs The other rtree.
247 
248  \return A reference for this instance.
249  */
250  Index& operator=(const Index& rhs);
251 
252 
253  private:
254 
255  NodeType* m_root; //!< Pointer to the root node.
256  te::gm::Envelope m_mbr; //!< Bounding box of the tree.
257  mutable std::size_t m_size; //!< The size of R-Tree (number of nodes).
258  };
259 
260  template<class DATATYPE, int MAXNODES, int MINNODES> inline
262  : m_root(0), m_size(0)
263  {
264  ++m_size;
265  m_root = new NodeType();
266  m_root->m_level = 0;
267  }
268 
269  template<class DATATYPE, int MAXNODES, int MINNODES> inline
271  : m_root(0), m_mbr(mbr), m_size(0)
272  {
273  assert(m_mbr.isValid());
274  ++m_size;
275  m_root = new NodeType();
276  m_root->m_level = 0;
277  }
278 
279  template<class DATATYPE, int MAXNODES, int MINNODES> inline
281  {
282  clear();
283  delete m_root;
284  }
285 
286  template<class DATATYPE, int MAXNODES, int MINNODES> inline
288  {
289  return m_size;
290  }
291 
292  template<class DATATYPE, int MAXNODES, int MINNODES> inline
294  {
295  return (m_root->m_count == 0);
296  }
297 
298  template<class DATATYPE, int MAXNODES, int MINNODES> inline
300  {
301  if(m_root)
302  {
303  erase(m_root);
304  m_root = 0;
305 
306  m_size = 1;
307  m_root = new NodeType();
308  m_root->m_level = 0;
309  }
310  }
311 
312  template<class DATATYPE, int MAXNODES, int MINNODES> inline
313  void Index<DATATYPE, MAXNODES, MINNODES>::insert(const te::gm::Envelope& mbr, const DATATYPE& data)
314  {
315  insert(mbr, data, &m_root, 0);
316  m_mbr.Union(mbr);
317  }
318 
319  template<class DATATYPE, int MAXNODES, int MINNODES> inline
320  bool Index<DATATYPE, MAXNODES, MINNODES>::remove(const te::gm::Envelope& mbr, const DATATYPE& data)
321  {
322  return remove(mbr, data, &m_root);
323  }
324 
325  template<class DATATYPE, int MAXNODES, int MINNODES> inline
326  int Index<DATATYPE, MAXNODES, MINNODES>::search(const te::gm::Envelope& mbr, std::vector<DATATYPE>& report) const
327  {
328  int foundObjs = 0;
329 
330  if(m_root)
331  search(mbr, m_root, report, foundObjs);
332 
333  return foundObjs;
334  }
335 
336  template<class DATATYPE, int MAXNODES, int MINNODES> inline
338  {
339  m_mbr = mbr;
340  }
341 
342  template<class DATATYPE, int MAXNODES, int MINNODES> inline
344  {
345  return m_mbr;
346  }
347 
348  template<class DATATYPE, int MAXNODES, int MINNODES> inline
349  bool Index<DATATYPE, MAXNODES, MINNODES>::insert(const te::gm::Envelope& mbr, const DATATYPE& data, NodeType** root, int level)
350  {
351 // this is the algorithm insert
352  NodeType* newRoot;
353  NodeType* newNode;
354  BranchType branch;
355 
356  if(chooseLeaf(mbr, data, *root, &newNode, level)) // I1
357  {
358 // I4
359 // if root was split
360 // grow a new root, make tree taller
361  ++m_size;
362  newRoot = new NodeType();
363 
364  newRoot->m_level = (*root)->m_level + 1;
365 
366 // first half node
367  branch.m_mbr = nodeCover(*root);
368  branch.m_child = *root;
369  addBranch(&branch, newRoot, 0);
370 
371 // second half node
372  branch.m_mbr = nodeCover(newNode);
373  branch.m_child = newNode;
374  addBranch(&branch, newRoot, 0);
375 
376  *root = newRoot;
377 
378  return true;
379  }
380 
381  return false;
382  }
383 
384  template<class DATATYPE, int MAXNODES, int MINNODES> inline
385  bool Index<DATATYPE, MAXNODES, MINNODES>::remove(const te::gm::Envelope& mbr, const DATATYPE& data, NodeType** root)
386  {
387  int i;
388  NodeType *t;
389  std::vector<NodeType*> reInsertList;
390 
391  if(remove2(mbr, data, *root, reInsertList))
392  {
393 // if we are here, so we have found and deleted a data item
394 
395 // reinsert any branches from eliminated nodes
396  while(!reInsertList.empty())
397  {
398  t = reInsertList[0];
399 
400  for(i = 0; i < t->m_count; ++i)
401  insert(t->m_branch[i].m_mbr, t->m_branch[i].m_data, root, t->m_level);
402 
403 // erase node from list
404  reInsertList.erase(reInsertList.begin());
405 
406 // remove node card from memory
407  delete t;
408  --m_size;
409  }
410 
411 // check for redundant root (not leaf, 1 child) and eliminate
412  if(((*root)->m_count == 1) && ((*root)->isInternalNode()))
413  {
414  t = (*root)->m_branch[0].m_child;
415 
416  delete (*root);
417  --m_size;
418 
419  *root = t;
420  }
421 
422  return true;
423  }
424 
425  return false;
426  }
427 
428  template<class DATATYPE, int MAXNODES, int MINNODES> inline
429  bool Index<DATATYPE, MAXNODES, MINNODES>::remove2(const te::gm::Envelope& mbr, const DATATYPE& data, NodeType* n, std::vector<NodeType*>& ee)
430  {
431  int i;
432 
433  if(n->isInternalNode()) /* not a leaf node */
434  {
435  for(i = 0; i < n->m_count; ++i)
436  {
437  if(mbr.intersects(n->m_branch[i].m_mbr))
438  {
439  if(remove2(mbr, data, n->m_branch[i].m_child, ee))
440  {
441  if(n->m_branch[i].m_child->m_count >= MINNODES)
442  n->m_branch[i].m_mbr = nodeCover(n->m_branch[i].m_child);
443  else
444  {
445  /* not enough entries in child, eliminate child node */
446  ee.push_back(n->m_branch[i].m_child); //reInsert(n->m_branch[i].m_child, ee);
447  disconBranch(n, i);
448  }
449 
450  return true; // found item
451  }
452  }
453  }
454 
455  return false; // din't find item
456  }
457  else /* a leaf node */
458  {
459  for(i = 0; i < n->m_count; ++i)
460  {
461  if(n->m_branch[i].m_data == data)
462  {
463  disconBranch(n, i);
464  return true; // found item
465  }
466  }
467 
468  return false; // didn't find item
469  }
470  }
471 
472  template<class DATATYPE, int MAXNODES, int MINNODES>
474  {
475 // remove element copying the last element in array
476  n->m_branch[i] = n->m_branch[n->m_count - 1];
477 
478  --(n->m_count);
479  }
480 
481  template<class DATATYPE, int MAXNODES, int MINNODES>
482  bool Index<DATATYPE, MAXNODES, MINNODES>::chooseLeaf(const te::gm::Envelope& mbr, const DATATYPE& data, NodeType* node, NodeType** newNode, int level)
483  {
484  BranchType b;
485  NodeType* n2;
486 
487  if(node->m_level > level)
488  {
489 // Still above level for insertion, go down tree recursively
490  int i = pickBranch(mbr, node); // CL3
491 
492  if(!chooseLeaf(mbr, data, node->m_branch[i].m_child, &n2, level))
493  {
494 // child was not split
495  node->m_branch[i].m_mbr = combineRect(mbr, node->m_branch[i].m_mbr);
496 
497  return false;
498  }
499  else
500  {
501 // child was split
502  node->m_branch[i].m_mbr = nodeCover(node->m_branch[i].m_child);
503 
504  b.m_child = n2;
505  b.m_mbr = nodeCover(n2);
506 
507  return addBranch(&b, node, newNode);
508  }
509  }
510  else if (node->m_level == level)
511  {
512 // have reached level for insertion. Add mbr, split if necessary
513 
514  b.m_mbr = mbr;
515  //b.m_child = (NodeType*) data;
516  b.m_data = data;
517 
518 // child field of leaves contains tid of data record
519  return addBranch(&b, node, newNode);
520  }
521  else
522  {
523 // Not supposed to happen
524  //throw;
525  return false;
526  }
527  }
528 
529  template<class DATATYPE, int MAXNODES, int MINNODES>
530  void Index<DATATYPE, MAXNODES, MINNODES>::search(const te::gm::Envelope& mbr, NodeType* node, std::vector<DATATYPE>& report, int& foundObjs) const
531  {
532  int i;
533 // S1
534  if(node->isInternalNode()) // This is an internal node in the tree
535  {
536  for(i = 0; i < node->m_count; ++i)
537  {
538  if(mbr.intersects(node->m_branch[i].m_mbr))
539  search(mbr, node->m_branch[i].m_child, report, foundObjs);
540  }
541  }
542 // S2
543  else // This is a leaf node
544  {
545  for(i = 0; i < node->m_count; ++i)
546  {
547  if(mbr.intersects(node->m_branch[i].m_mbr))
548  {
549  DATATYPE& id = node->m_branch[i].m_data;
550 
551  report.push_back(id);
552 
553  ++foundObjs;
554  }
555  }
556  }
557 
558  return;
559  }
560 
561  template<class DATATYPE, int MAXNODES, int MINNODES>
563  {
564  bool flag = true;
565 
567 
568  for(int i = 0; i < n->m_count; ++i)
569  {
570  if(flag)
571  {
572  r = n->m_branch[i].m_mbr;
573  flag = false;
574  }
575  else
576  r = combineRect(r, n->m_branch[i].m_mbr);
577  }
578 
579  return r;
580  }
581 
582  template<class DATATYPE, int MAXNODES, int MINNODES> inline
584  {
585  te::gm::Envelope newRect(mbrA);
586  newRect.Union(mbrB);
587  return newRect;
588  }
589 
590  template<class DATATYPE, int MAXNODES, int MINNODES> inline
592  {
593  if(node->m_count < MAXNODES) /* split won't be necessary */
594  {
595  node->m_branch[node->m_count] = *branch;
596  ++(node->m_count);
597  return false;
598  }
599  else
600  {
601  splitNode(node, branch, newNode);
602  return true;
603  }
604  }
605 
606  template<class DATATYPE, int MAXNODES, int MINNODES> inline
608  {
609 // CL3
610  bool flag = true;
611  double bestIncr = -1.0;
612  double bestArea = 0.;
613  int best = 0;
614 
615  for(int i = 0; i < node->m_count; ++i)
616  {
617  te::gm::Envelope rr = node->m_branch[i].m_mbr;
618  double area = rr.getArea();
619 
620  rr = combineRect(mbr, rr);
621 
622  double increase = rr.getArea() - area;
623 
624  if((increase < bestIncr) || flag)
625  {
626  best = i;
627  bestArea = area;
628  bestIncr = increase;
629  flag = false;
630  }
631  else if((increase == bestIncr) && (area < bestArea))
632  {
633  best = i;
634  bestArea = area;
635  bestIncr = increase;
636  }
637  }
638 
639  return best;
640  }
641 
642  template<class DATATYPE, int MAXNODES, int MINNODES> inline
644  {
645  PartitionVarsType partitions;
646 
647 // load all the branches into a buffer, initialize old node
648  int level = node->m_level;
649 
650  getBranches(node, branch, partitions);
651 
652 // find partition
653  methodZero(partitions);
654 
655 // put branches from buffer into 2 nodes according to chosen partition
656  ++m_size;
657 
658  *newNode = new NodeType();
659  (*newNode)->m_level = node->m_level = level;
660 
661  loadNodes(node, *newNode, partitions);
662  }
663 
664  template<class DATATYPE, int MAXNODES, int MINNODES> inline
666  {
667 // load the branch buffer
668  for(int i = 0; i < MAXNODES; ++i)
669  {
670  p.m_branchBuf[i] = n->m_branch[i];
671  }
672 
673  p.m_branchBuf[MAXNODES] = *b;
674 
675 // calculate mbr containing all in the set
676  p.m_coverSplit = p.m_branchBuf[0].m_mbr;
677 
678  for(int i = 1; i <= MAXNODES; ++i)
679  p.m_coverSplit = combineRect(p.m_coverSplit, p.m_branchBuf[i].m_mbr);
680 
681  n->init();
682  }
683 
684  template<class DATATYPE, int MAXNODES, int MINNODES> inline
686  {
687  p.init();
688  pickSeeds(p);
689  pigeonhole(p);
690  }
691 
692  template<class DATATYPE, int MAXNODES, int MINNODES> inline
694  {
695  double w;
696  double separation;
697  double bestSep;
698  double width[2];
699  int leastUpper[2];
700  int greatestLower[2];
701  int seed0;
702  int seed1;
703  int i;
704 // LPS1
705 // find the rectangles farthest out in each dimbrion along dimens "x"
706  greatestLower[0] = leastUpper[0] = 0;
707 
708  for(i = 1; i <= MAXNODES; ++i)
709  {
710  te::gm::Envelope& r = p.m_branchBuf[i].m_mbr;
711 
712  if(r.m_llx > p.m_branchBuf[greatestLower[0]].m_mbr.m_llx)
713  greatestLower[0] = i;
714 
715  if(r.m_urx < p.m_branchBuf[leastUpper[0]].m_mbr.m_urx)
716  leastUpper[0] = i;
717  }
718 
719 // LPS2
720 // LPS3
721 // find the width of the whole collection along this dimension
722  width[0] = p.m_coverSplit.m_urx - p.m_coverSplit.m_llx;
723 
724 // find the rectangles farthest out in each dimbrion along dimens "y"
725  greatestLower[1] = leastUpper[1] = 0;
726 
727  for(i = 1; i <= MAXNODES; ++i)
728  {
729  te::gm::Envelope& r = p.m_branchBuf[i].m_mbr;
730 
731  if(r.m_lly > p.m_branchBuf[greatestLower[1]].m_mbr.m_lly)
732  greatestLower[1] = i;
733 
734  if(r.m_ury < p.m_branchBuf[leastUpper[1]].m_mbr.m_ury)
735  leastUpper[1] = i;
736  }
737 
738 // LPS2
739 // LPS3
740 // find the width of the whole collection along this dimension
741  width[1] = p.m_coverSplit.m_ury - p.m_coverSplit.m_lly;
742 
743 
744 // pick the best separation dimension and the two seed mbrs
745 
746 // divisor for normalizing by width
747 
748 // x
749  if(width[0] == 0.0)
750  w = 1.0;
751  else
752  w = width[0];
753 
754  te::gm::Envelope rlow = p.m_branchBuf[leastUpper[0]].m_mbr;
755  te::gm::Envelope rhigh = p.m_branchBuf[greatestLower[0]].m_mbr;
756 
757  seed0 = leastUpper[0];
758  seed1 = greatestLower[0];
759 
760  bestSep = (rhigh.m_llx - rlow.m_urx) / w;
761 
762 // y
763  if(width[1] == 0.0)
764  w = 1.0;
765  else
766  w = width[1];
767 
768  rlow = p.m_branchBuf[leastUpper[1]].m_mbr;
769  rhigh = p.m_branchBuf[greatestLower[1]].m_mbr;
770 
771  separation = (rhigh.m_lly - rlow.m_ury) / w;
772 
773 // LPS3
774  if(separation > bestSep)
775  {
776  seed0 = leastUpper[1];
777  seed1 = greatestLower[1];
778 
779  bestSep = separation;
780  }
781 
782  if(seed0 != seed1)
783  {
784  classify(seed0, 0, p);
785  classify(seed1, 1, p);
786  }
787  }
788 
789  template<class DATATYPE, int MAXNODES, int MINNODES> inline
791  {
792  p.m_partition[i] = group;
793  p.m_taken[i] = 1;
794 
795  if(p.m_count[group] == 0)
796  p.m_cover[group] = p.m_branchBuf[i].m_mbr;
797  else
798  p.m_cover[group] = combineRect(p.m_branchBuf[i].m_mbr, p.m_cover[group]);
799 
800  p.m_area[group] = p.m_cover[group].getArea();
801 
802  ++(p.m_count[group]);
803  }
804 
805  template<class DATATYPE, int MAXNODES, int MINNODES> inline
807  {
808  te::gm::Envelope newCover[2];
809 
810  double newArea[2];
811  double increase[2];
812 
813  for(int i = 0; i <= MAXNODES; ++i)
814  {
815  if(p.m_taken[i] == 0)
816  {
817 // if one group too full, put mbr in the other regardless
818  if(p.m_count[0] >= (MAXNODES + 1 - MINNODES))
819  {
820  classify(i, 1, p);
821  continue;
822  }
823  else if(p.m_count[1] >= (MAXNODES + 1 - MINNODES))
824  {
825  classify(i, 0, p);
826  continue;
827  }
828 
829 // find the areas of the two groups' old and new covers
830  for(int group = 0; group < 2; ++group)
831  {
832  if(p.m_count[group] > 0)
833  {
834  newCover[group] = combineRect(p.m_branchBuf[i].m_mbr, p.m_cover[group]);
835  }
836  else
837  {
838  newCover[group] = p.m_branchBuf[i].m_mbr;
839  }
840 
841  newArea[group] = newCover[group].getArea();
842  increase[group] = newArea[group] - p.m_area[group];
843  }
844 
845 // put mbr in group whose cover will need to expand less
846  if(increase[0] < increase[1])
847  classify(i, 0, p);
848  else if(increase[1] < increase[0])
849  classify(i, 1, p);
850 // put mbr in group that will have a smaller area cover
851  else if(p.m_area[0] < p.m_area[1])
852  classify(i, 0, p);
853  else if(p.m_area[1] < p.m_area[0])
854  classify(i, 1, p);
855 // put mbr in group with fewer elements
856  else if(p.m_count[0] < p.m_count[1])
857  classify(i, 0, p);
858  else
859  classify(i, 1, p);
860  }
861  }
862  }
863 
864  template<class DATATYPE, int MAXNODES, int MINNODES> inline
866  {
867  for(int i = 0; i <= MAXNODES; ++i)
868  {
869  if(p.m_partition[i] == 0)
870  addBranch(&(p.m_branchBuf[i]), n, 0);
871  else if(p.m_partition[i] == 1)
872  addBranch(&(p.m_branchBuf[i]), q, 0);
873  //else
874  // throw; // ERROR
875  }
876  }
877 
878  template<class DATATYPE, int MAXNODES, int MINNODES> inline
880  {
881  if(node->isLeaf())
882  {
883  delete node;
884  return;
885  }
886 
887  for(int i = 0u; i < node->m_count; ++i)
888  erase(node->m_branch[i].m_child);
889 
890  delete node;
891  return;
892  }
893 
894  } // end namespace rtree
895  } // end namespace sam
896 } // end namespace te
897 
898 
899 #endif // __TERRALIB_SAM_RTREE_INTERNAL_INDEX_H
900 
bool remove(const te::gm::Envelope &mbr, const DATATYPE &data)
It removes an item from the tree.
Definition: Index.h:320
int m_partition[MAXNODES+1]
Auxiliary partition vector.
Definition: PartitionVars.h:45
void pickSeeds(PartitionVarsType &p) const
Definition: Index.h:693
NodeType * m_root
Pointer to the root node.
Definition: Index.h:255
bool intersects(const Envelope &rhs) const
It returns true if the envelopes "spatially intersects".
Definition: Envelope.h:493
void splitNode(NodeType *node, BranchType *branch, NodeType **newNode) const
Split a node.
Definition: Index.h:643
bool chooseLeaf(const te::gm::Envelope &mbr, const DATATYPE &data, NodeType *node, NodeType **newNode, int level)
It inserts a new data rectangle into the index structure.
Definition: Index.h:482
void classify(int i, int group, PartitionVarsType &p) const
Definition: Index.h:790
void disconBranch(NodeType *n, int i)
It disconnects a dependent node.
Definition: Index.h:473
A class that represents an R-tree.
Definition: Index.h:56
NodeType::BranchType BranchType
Definition: Index.h:61
void loadNodes(NodeType *n, NodeType *q, PartitionVarsType &p) const
Definition: Index.h:865
A class that represents an R-tree node.
Definition: Node.h:45
te::gm::Envelope nodeCover(NodeType *n) const
Find the smallest rectangle that includes all rectangles in branches of a node.
Definition: Index.h:562
te::gm::Envelope m_coverSplit
Auxiliary box covering branchBuf.
Definition: PartitionVars.h:51
te::gm::Envelope m_mbr
Bounding box of the tree.
Definition: Index.h:256
double m_urx
Upper right corner x-coordinate.
Definition: Envelope.h:346
void init()
Initializes partition vars.
Definition: PartitionVars.h:54
DATATYPE m_data
An object-identifier (oid).
Definition: Branch.h:52
void init()
This method is used during split when a node retained and used again (beeing re-filled).
Definition: Node.h:78
te::gm::Envelope combineRect(const te::gm::Envelope &mbrA, const te::gm::Envelope &mbrB) const
Combine two rectangles into larger one containing both.
Definition: Index.h:583
bool isInternalNode() const
It returns true if this is a internal node.
Definition: Node.h:62
int m_level
Leaf is zero, others positive.
Definition: Node.h:111
void Union(const Envelope &rhs)
It updates the envelop with coordinates of another envelope.
Definition: Envelope.h:555
double m_area[2]
Auxiliary area of each new page.
Definition: PartitionVars.h:49
void pigeonhole(PartitionVarsType &p) const
Definition: Index.h:806
int m_count
The number of elements in the node (count).
Definition: Node.h:110
bool isEmpty(void) const
It returns true if the tree is empty.
Definition: Index.h:293
NodeType
The type of node read by XML reader.
Definition: Enums.h:40
double m_llx
Lower left corner x-coordinate.
Definition: Envelope.h:344
Index()
Constructor.
Definition: Index.h:261
An Envelope defines a 2D rectangular region.
Definition: Envelope.h:51
void setMBR(const te::gm::Envelope &mbr)
It sets the bounding box of all elements in the tree.
Definition: Index.h:337
mydialect insert("+", new te::da::BinaryOpEncoder("+"))
URI C++ Library.
double getArea() const
It returns the area of this envelope as measured in the spatial reference system of it...
Definition: Envelope.h:453
void methodZero(PartitionVarsType &p) const
Definition: Index.h:685
BRANCH m_branchBuf[MAXNODES+1]
Auxiliary branch buffer.
Definition: PartitionVars.h:50
te::sam::rtree::PartitionVars< BranchType, MAXNODES > PartitionVarsType
Definition: Index.h:62
BranchType m_branch[MAXNODES]
Branches.
Definition: Node.h:112
int search(const te::gm::Envelope &mbr, std::vector< DATATYPE > &report) const
Range search query.
Definition: Index.h:326
std::size_t m_size
The size of R-Tree (number of nodes).
Definition: Index.h:257
bool isLeaf() const
It returns true if this is a leaf node.
Definition: Node.h:72
te::gm::Envelope m_mbr
Bounding box containing all the objects under the branch or an object bounding box.
Definition: Branch.h:47
Index & operator=(const Index &rhs)
No assignment operator allowed.
bool addBranch(BranchType *branch, NodeType *node, NodeType **newNode) const
Add a branch to a node.
Definition: Index.h:591
double m_lly
Lower left corner y-coordinate.
Definition: Envelope.h:345
void erase(NodeType *node)
Erases a node from the tree and all nodes below it.
Definition: Index.h:879
~Index()
Destructor.
Definition: Index.h:280
const te::gm::Envelope & getMBR(void) const
It returns the bounding box of all elements in the tree.
Definition: Index.h:343
void insert(const te::gm::Envelope &mbr, const DATATYPE &data)
It inserts an item into the tree.
Definition: Index.h:313
double m_ury
Upper right corner y-coordinate.
Definition: Envelope.h:347
std::size_t size(void) const
It returns the number of elements in the tree.
Definition: Index.h:287
int m_count[2]
Number of entries in each new page.
Definition: PartitionVars.h:47
int pickBranch(const te::gm::Envelope &mbr, NodeType *node) const
Pick a branch.
Definition: Index.h:607
void getBranches(NodeType *n, BranchType *b, PartitionVarsType &p) const
Definition: Index.h:665
te::gm::Envelope m_cover[2]
Auxiliary box of each new page.
Definition: PartitionVars.h:48
int m_taken[MAXNODES+1]
Flag to indicate that entry is ok.
Definition: PartitionVars.h:46
NODE * m_child
A pointer to the child node.
Definition: Branch.h:51
Auxiliary structure when searching for a split partition.
Definition: PartitionVars.h:43
Node< DATATYPE, MAXNODES, MINNODES > NodeType
Definition: Index.h:60
bool isValid() const
It tells if the rectangle is valid or not.
Definition: Envelope.h:438
bool remove2(const te::gm::Envelope &mbr, const DATATYPE &data, NodeType *n, std::vector< NodeType * > &ee)
It deletes a rectangle from non-root part of an index structure.
Definition: Index.h:429
void clear(void)
Definition: Index.h:299