ui/gfx/geometry/r_tree_base.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "ui/gfx/geometry/r_tree_base.h"
   6
   7 #include <algorithm>
   8
   9 #include "base/logging.h"
  10
  11
  12 // Helpers --------------------------------------------------------------------
  13
  14 namespace {
  15
  16 // Returns a Vector2d to allow us to do arithmetic on the result such as
  17 // computing distances between centers.
  18 gfx::Vector2d CenterOfRect(const gfx::Rect& rect) {
  19   return rect.OffsetFromOrigin() +
  20       gfx::Vector2d(rect.width() / 2, rect.height() / 2);
  21 }
  22
  23 }
  24
  25 namespace gfx {
  26
  27
  28 // RTreeBase::NodeBase --------------------------------------------------------
  29
  30 RTreeBase::NodeBase::~NodeBase() {
  31 }
  32
  33 void RTreeBase::NodeBase::RecomputeBoundsUpToRoot() {
  34   RecomputeLocalBounds();
  35   if (parent_)
  36     parent_->RecomputeBoundsUpToRoot();
  37 }
  38
  39 RTreeBase::NodeBase::NodeBase(const Rect& rect, NodeBase* parent)
  40     : rect_(rect),
  41       parent_(parent) {
  42 }
  43
  44 void RTreeBase::NodeBase::RecomputeLocalBounds() {
  45 }
  46
  47 // RTreeBase::RecordBase ------------------------------------------------------
  48
  49 RTreeBase::RecordBase::RecordBase(const Rect& rect) : NodeBase(rect, NULL) {
  50 }
  51
  52 RTreeBase::RecordBase::~RecordBase() {
  53 }
  54
  55 void RTreeBase::RecordBase::AppendIntersectingRecords(
  56     const Rect& query_rect, Records* matches_out) const {
  57   if (rect().Intersects(query_rect))
  58     matches_out->push_back(this);
  59 }
  60
  61 void RTreeBase::RecordBase::AppendAllRecords(Records* matches_out) const {
  62   matches_out->push_back(this);
  63 }
  64
  65 scoped_ptr<RTreeBase::NodeBase>
  66 RTreeBase::RecordBase::RemoveAndReturnLastChild() {
  67   return nullptr;
  68 }
  69
  70 int RTreeBase::RecordBase::Level() const {
  71   return -1;
  72 }
  73
  74
  75 // RTreeBase::Node ------------------------------------------------------------
  76
  77 RTreeBase::Node::Node() : NodeBase(Rect(), NULL), level_(0) {
  78 }
  79
  80 RTreeBase::Node::~Node() {
  81 }
  82
  83 scoped_ptr<RTreeBase::Node> RTreeBase::Node::ConstructParent() {
  84   DCHECK(!parent());
  85   scoped_ptr<Node> new_parent(new Node(level_ + 1));
  86   new_parent->AddChild(scoped_ptr<NodeBase>(this));
  87   return new_parent.Pass();
  88 }
  89
  90 void RTreeBase::Node::AppendIntersectingRecords(
  91     const Rect& query_rect, Records* matches_out) const {
  92   // Check own bounding box for intersection, can cull all children if no
  93   // intersection.
  94   if (!rect().Intersects(query_rect))
  95     return;
  96
  97   // Conversely if we are completely contained within the query rect we can
  98   // confidently skip all bounds checks for ourselves and all our children.
  99   if (query_rect.Contains(rect())) {
 100     AppendAllRecords(matches_out);
 101     return;
 102   }
 103
 104   // We intersect the query rect but we are not are not contained within it.
 105   // We must query each of our children in turn.
 106   for (Nodes::const_iterator i = children_.begin(); i != children_.end(); ++i)
 107     (*i)->AppendIntersectingRecords(query_rect, matches_out);
 108 }
 109
 110 void RTreeBase::Node::AppendAllRecords(Records* matches_out) const {
 111   for (Nodes::const_iterator i = children_.begin(); i != children_.end(); ++i)
 112     (*i)->AppendAllRecords(matches_out);
 113 }
 114
 115 void RTreeBase::Node::RemoveNodesForReinsert(size_t number_to_remove,
 116                                              Nodes* nodes) {
 117   DCHECK_LE(number_to_remove, children_.size());
 118
 119   std::partial_sort(children_.begin(),
 120                     children_.begin() + number_to_remove,
 121                     children_.end(),
 122                     &RTreeBase::Node::CompareCenterDistanceFromParent);
 123
 124   // Move the lowest-distance nodes to the returned vector.
 125   nodes->insert(
 126       nodes->end(), children_.begin(), children_.begin() + number_to_remove);
 127   children_.weak_erase(children_.begin(), children_.begin() + number_to_remove);
 128 }
 129
 130 scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::RemoveChild(
 131     NodeBase* child_node, Nodes* orphans) {
 132   DCHECK_EQ(this, child_node->parent());
 133
 134   scoped_ptr<NodeBase> orphan(child_node->RemoveAndReturnLastChild());
 135   while (orphan) {
 136     orphans->push_back(orphan.release());
 137     orphan = child_node->RemoveAndReturnLastChild();
 138   }
 139
 140   Nodes::iterator i = std::find(children_.begin(), children_.end(), child_node);
 141   DCHECK(i != children_.end());
 142   children_.weak_erase(i);
 143
 144   return scoped_ptr<NodeBase>(child_node);
 145 }
 146
 147 scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::RemoveAndReturnLastChild() {
 148   if (children_.empty())
 149     return nullptr;
 150
 151   scoped_ptr<NodeBase> last_child(children_.back());
 152   children_.weak_erase(children_.end() - 1);
 153   last_child->set_parent(NULL);
 154   return last_child.Pass();
 155 }
 156
 157 RTreeBase::Node* RTreeBase::Node::ChooseSubtree(NodeBase* node) {
 158   DCHECK(node);
 159   // Should never be called on a node at equal or lower level in the tree than
 160   // the node to insert.
 161   DCHECK_GT(level_, node->Level());
 162
 163   // If we are a parent of nodes on the provided node level, we are done.
 164   if (level_ == node->Level() + 1)
 165     return this;
 166
 167   // Precompute a vector of expanded rects, used by both LeastOverlapIncrease
 168   // and LeastAreaEnlargement.
 169   Rects expanded_rects;
 170   expanded_rects.reserve(children_.size());
 171   for (Nodes::iterator i = children_.begin(); i != children_.end(); ++i)
 172     expanded_rects.push_back(UnionRects(node->rect(), (*i)->rect()));
 173
 174   Node* best_candidate = NULL;
 175   // For parents of leaf nodes, we pick the node that will cause the least
 176   // increase in overlap by the addition of this new node. This may detect a
 177   // tie, in which case it will return NULL.
 178   if (level_ == 1)
 179     best_candidate = LeastOverlapIncrease(node->rect(), expanded_rects);
 180
 181   // For non-parents of leaf nodes, or for parents of leaf nodes with ties in
 182   // overlap increase, we choose the subtree with least area enlargement caused
 183   // by the addition of the new node.
 184   if (!best_candidate)
 185     best_candidate = LeastAreaEnlargement(node->rect(), expanded_rects);
 186
 187   DCHECK(best_candidate);
 188   return best_candidate->ChooseSubtree(node);
 189 }
 190
 191 size_t RTreeBase::Node::AddChild(scoped_ptr<NodeBase> node) {
 192   DCHECK(node);
 193   // Sanity-check that the level of the child being added is one less than ours.
 194   DCHECK_EQ(level_ - 1, node->Level());
 195   node->set_parent(this);
 196   set_rect(UnionRects(rect(), node->rect()));
 197   children_.push_back(node.release());
 198   return children_.size();
 199 }
 200
 201 scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::Split(size_t min_children,
 202                                                        size_t max_children) {
 203   // We should have too many children to begin with.
 204   DCHECK_EQ(max_children + 1, children_.size());
 205
 206   // Determine if we should split along the horizontal or vertical axis.
 207   std::vector<NodeBase*> vertical_sort(children_.get());
 208   std::vector<NodeBase*> horizontal_sort(children_.get());
 209   std::sort(vertical_sort.begin(),
 210             vertical_sort.end(),
 211             &RTreeBase::Node::CompareVertical);
 212   std::sort(horizontal_sort.begin(),
 213             horizontal_sort.end(),
 214             &RTreeBase::Node::CompareHorizontal);
 215
 216   Rects low_vertical_bounds;
 217   Rects low_horizontal_bounds;
 218   BuildLowBounds(vertical_sort,
 219                  horizontal_sort,
 220                  &low_vertical_bounds,
 221                  &low_horizontal_bounds);
 222
 223   Rects high_vertical_bounds;
 224   Rects high_horizontal_bounds;
 225   BuildHighBounds(vertical_sort,
 226                   horizontal_sort,
 227                   &high_vertical_bounds,
 228                   &high_horizontal_bounds);
 229
 230   // Choose |end_index| such that both Nodes after the split will have
 231   // min_children <= children_.size() <= max_children.
 232   size_t end_index = std::min(max_children, children_.size() - min_children);
 233   bool is_vertical_split =
 234       SmallestMarginSum(min_children,
 235                         end_index,
 236                         low_horizontal_bounds,
 237                         high_horizontal_bounds) <
 238       SmallestMarginSum(min_children,
 239                         end_index,
 240                         low_vertical_bounds,
 241                         high_vertical_bounds);
 242
 243   // Choose split index along chosen axis and perform the split.
 244   const Rects& low_bounds(
 245       is_vertical_split ? low_vertical_bounds : low_horizontal_bounds);
 246   const Rects& high_bounds(
 247       is_vertical_split ? high_vertical_bounds : high_horizontal_bounds);
 248   size_t split_index =
 249       ChooseSplitIndex(min_children, end_index, low_bounds, high_bounds);
 250
 251   const std::vector<NodeBase*>& sort(
 252       is_vertical_split ? vertical_sort : horizontal_sort);
 253   return DivideChildren(low_bounds, high_bounds, sort, split_index);
 254 }
 255
 256 int RTreeBase::Node::Level() const {
 257   return level_;
 258 }
 259
 260 RTreeBase::Node::Node(int level) : NodeBase(Rect(), NULL), level_(level) {
 261 }
 262
 263 // static
 264 bool RTreeBase::Node::CompareVertical(const NodeBase* a, const NodeBase* b) {
 265   const Rect& a_rect = a->rect();
 266   const Rect& b_rect = b->rect();
 267   return (a_rect.y() < b_rect.y()) ||
 268          ((a_rect.y() == b_rect.y()) && (a_rect.height() < b_rect.height()));
 269 }
 270
 271 // static
 272 bool RTreeBase::Node::CompareHorizontal(const NodeBase* a, const NodeBase* b) {
 273   const Rect& a_rect = a->rect();
 274   const Rect& b_rect = b->rect();
 275   return (a_rect.x() < b_rect.x()) ||
 276          ((a_rect.x() == b_rect.x()) && (a_rect.width() < b_rect.width()));
 277 }
 278
 279 // static
 280 bool RTreeBase::Node::CompareCenterDistanceFromParent(const NodeBase* a,
 281                                                       const NodeBase* b) {
 282   const NodeBase* p = a->parent();
 283
 284   DCHECK(p);
 285   DCHECK_EQ(p, b->parent());
 286
 287   Vector2d p_center = CenterOfRect(p->rect());
 288   Vector2d a_center = CenterOfRect(a->rect());
 289   Vector2d b_center = CenterOfRect(b->rect());
 290
 291   // We don't bother with square roots because we are only comparing the two
 292   // values for sorting purposes.
 293   return (a_center - p_center).LengthSquared() <
 294          (b_center - p_center).LengthSquared();
 295 }
 296
 297 // static
 298 void RTreeBase::Node::BuildLowBounds(
 299     const std::vector<NodeBase*>& vertical_sort,
 300     const std::vector<NodeBase*>& horizontal_sort,
 301     Rects* vertical_bounds,
 302     Rects* horizontal_bounds) {
 303   Rect vertical_bounds_rect;
 304   vertical_bounds->reserve(vertical_sort.size());
 305   for (std::vector<NodeBase*>::const_iterator i = vertical_sort.begin();
 306        i != vertical_sort.end();
 307        ++i) {
 308     vertical_bounds_rect.Union((*i)->rect());
 309     vertical_bounds->push_back(vertical_bounds_rect);
 310   }
 311
 312   Rect horizontal_bounds_rect;
 313   horizontal_bounds->reserve(horizontal_sort.size());
 314   for (std::vector<NodeBase*>::const_iterator i = horizontal_sort.begin();
 315        i != horizontal_sort.end();
 316        ++i) {
 317     horizontal_bounds_rect.Union((*i)->rect());
 318     horizontal_bounds->push_back(horizontal_bounds_rect);
 319   }
 320 }
 321
 322 // static
 323 void RTreeBase::Node::BuildHighBounds(
 324     const std::vector<NodeBase*>& vertical_sort,
 325     const std::vector<NodeBase*>& horizontal_sort,
 326     Rects* vertical_bounds,
 327     Rects* horizontal_bounds) {
 328   Rect vertical_bounds_rect;
 329   vertical_bounds->reserve(vertical_sort.size());
 330   for (std::vector<NodeBase*>::const_reverse_iterator i =
 331            vertical_sort.rbegin();
 332        i != vertical_sort.rend();
 333        ++i) {
 334     vertical_bounds_rect.Union((*i)->rect());
 335     vertical_bounds->push_back(vertical_bounds_rect);
 336   }
 337   std::reverse(vertical_bounds->begin(), vertical_bounds->end());
 338
 339   Rect horizontal_bounds_rect;
 340   horizontal_bounds->reserve(horizontal_sort.size());
 341   for (std::vector<NodeBase*>::const_reverse_iterator i =
 342            horizontal_sort.rbegin();
 343        i != horizontal_sort.rend();
 344        ++i) {
 345     horizontal_bounds_rect.Union((*i)->rect());
 346     horizontal_bounds->push_back(horizontal_bounds_rect);
 347   }
 348   std::reverse(horizontal_bounds->begin(), horizontal_bounds->end());
 349 }
 350
 351 size_t RTreeBase::Node::ChooseSplitIndex(size_t start_index,
 352                                          size_t end_index,
 353                                          const Rects& low_bounds,
 354                                          const Rects& high_bounds) {
 355   DCHECK_EQ(low_bounds.size(), high_bounds.size());
 356
 357   int smallest_overlap_area = UnionRects(
 358       low_bounds[start_index], high_bounds[start_index]).size().GetArea();
 359   int smallest_combined_area = low_bounds[start_index].size().GetArea() +
 360       high_bounds[start_index].size().GetArea();
 361   size_t optimal_split_index = start_index;
 362   for (size_t p = start_index + 1; p < end_index; ++p) {
 363     const int overlap_area =
 364         UnionRects(low_bounds[p], high_bounds[p]).size().GetArea();
 365     const int combined_area =
 366         low_bounds[p].size().GetArea() + high_bounds[p].size().GetArea();
 367     if ((overlap_area < smallest_overlap_area) ||
 368         ((overlap_area == smallest_overlap_area) &&
 369          (combined_area < smallest_combined_area))) {
 370       smallest_overlap_area = overlap_area;
 371       smallest_combined_area = combined_area;
 372       optimal_split_index = p;
 373     }
 374   }
 375
 376   // optimal_split_index currently points at the last element in the first set,
 377   // so advance it by 1 to point at the first element in the second set.
 378   return optimal_split_index + 1;
 379 }
 380
 381 // static
 382 int RTreeBase::Node::SmallestMarginSum(size_t start_index,
 383                                        size_t end_index,
 384                                        const Rects& low_bounds,
 385                                        const Rects& high_bounds) {
 386   DCHECK_EQ(low_bounds.size(), high_bounds.size());
 387   DCHECK_LT(start_index, low_bounds.size());
 388   DCHECK_LE(start_index, end_index);
 389   DCHECK_LE(end_index, low_bounds.size());
 390   Rects::const_iterator i(low_bounds.begin() + start_index);
 391   Rects::const_iterator j(high_bounds.begin() + start_index);
 392   int smallest_sum = i->width() + i->height() + j->width() + j->height();
 393   for (; i != (low_bounds.begin() + end_index); ++i, ++j) {
 394     smallest_sum = std::min(
 395         smallest_sum, i->width() + i->height() + j->width() + j->height());
 396   }
 397
 398   return smallest_sum;
 399 }
 400
 401 void RTreeBase::Node::RecomputeLocalBounds() {
 402   Rect bounds;
 403   for (size_t i = 0; i < children_.size(); ++i)
 404     bounds.Union(children_[i]->rect());
 405
 406   set_rect(bounds);
 407 }
 408
 409 int RTreeBase::Node::OverlapIncreaseToAdd(const Rect& rect,
 410                                           const NodeBase* candidate_node,
 411                                           const Rect& expanded_rect) const {
 412   DCHECK(candidate_node);
 413
 414   // Early-out when |rect| is contained completely within |candidate|.
 415   if (candidate_node->rect().Contains(rect))
 416     return 0;
 417
 418   int total_original_overlap = 0;
 419   int total_expanded_overlap = 0;
 420
 421   // Now calculate overlap with all other rects in this node.
 422   for (Nodes::const_iterator it = children_.begin();
 423        it != children_.end(); ++it) {
 424     // Skip calculating overlap with the candidate rect.
 425     if ((*it) == candidate_node)
 426       continue;
 427     NodeBase* overlap_node = (*it);
 428     total_original_overlap += IntersectRects(
 429         candidate_node->rect(), overlap_node->rect()).size().GetArea();
 430     Rect expanded_overlap_rect = expanded_rect;
 431     expanded_overlap_rect.Intersect(overlap_node->rect());
 432     total_expanded_overlap += expanded_overlap_rect.size().GetArea();
 433   }
 434
 435   return total_expanded_overlap - total_original_overlap;
 436 }
 437
 438 scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::DivideChildren(
 439     const Rects& low_bounds,
 440     const Rects& high_bounds,
 441     const std::vector<NodeBase*>& sorted_children,
 442     size_t split_index) {
 443   DCHECK_EQ(low_bounds.size(), high_bounds.size());
 444   DCHECK_EQ(low_bounds.size(), sorted_children.size());
 445   DCHECK_LT(split_index, low_bounds.size());
 446   DCHECK_GT(split_index, 0U);
 447
 448   scoped_ptr<Node> sibling(new Node(level_));
 449   sibling->set_parent(parent());
 450   set_rect(low_bounds[split_index - 1]);
 451   sibling->set_rect(high_bounds[split_index]);
 452
 453   // Our own children_ vector is unsorted, so we wipe it out and divide the
 454   // sorted bounds rects between ourselves and our sibling.
 455   children_.weak_clear();
 456   children_.insert(children_.end(),
 457                    sorted_children.begin(),
 458                    sorted_children.begin() + split_index);
 459   sibling->children_.insert(sibling->children_.end(),
 460                             sorted_children.begin() + split_index,
 461                             sorted_children.end());
 462
 463   for (size_t i = 0; i < sibling->children_.size(); ++i)
 464     sibling->children_[i]->set_parent(sibling.get());
 465
 466   return sibling.Pass();
 467 }
 468
 469 RTreeBase::Node* RTreeBase::Node::LeastOverlapIncrease(
 470     const Rect& node_rect,
 471     const Rects& expanded_rects) {
 472   NodeBase* best_node = children_.front();
 473   int least_overlap_increase =
 474       OverlapIncreaseToAdd(node_rect, children_[0], expanded_rects[0]);
 475   for (size_t i = 1; i < children_.size(); ++i) {
 476     int overlap_increase =
 477         OverlapIncreaseToAdd(node_rect, children_[i], expanded_rects[i]);
 478     if (overlap_increase < least_overlap_increase) {
 479       least_overlap_increase = overlap_increase;
 480       best_node = children_[i];
 481     } else if (overlap_increase == least_overlap_increase) {
 482       // If we are tied at zero there is no possible better overlap increase,
 483       // so we can report a tie early.
 484       if (overlap_increase == 0)
 485         return NULL;
 486
 487       best_node = NULL;
 488     }
 489   }
 490
 491   // Ensure that our children are always Nodes and not Records.
 492   DCHECK_GE(level_, 1);
 493   return static_cast<Node*>(best_node);
 494 }
 495
 496 RTreeBase::Node* RTreeBase::Node::LeastAreaEnlargement(
 497     const Rect& node_rect,
 498     const Rects& expanded_rects) {
 499   DCHECK(!children_.empty());
 500   DCHECK_EQ(children_.size(), expanded_rects.size());
 501
 502   NodeBase* best_node = children_.front();
 503   int least_area_enlargement =
 504       expanded_rects[0].size().GetArea() - best_node->rect().size().GetArea();
 505   for (size_t i = 1; i < children_.size(); ++i) {
 506     NodeBase* candidate_node = children_[i];
 507     int area_change = expanded_rects[i].size().GetArea() -
 508                       candidate_node->rect().size().GetArea();
 509     DCHECK_GE(area_change, 0);
 510     if (area_change < least_area_enlargement) {
 511       best_node = candidate_node;
 512       least_area_enlargement = area_change;
 513     } else if (area_change == least_area_enlargement &&
 514         candidate_node->rect().size().GetArea() <
 515             best_node->rect().size().GetArea()) {
 516       // Ties are broken by choosing the entry with the least area.
 517       best_node = candidate_node;
 518     }
 519   }
 520
 521   // Ensure that our children are always Nodes and not Records.
 522   DCHECK_GE(level_, 1);
 523   return static_cast<Node*>(best_node);
 524 }
 525
 526
 527 // RTreeBase ------------------------------------------------------------------
 528
 529 RTreeBase::RTreeBase(size_t min_children, size_t max_children)
 530     : root_(new Node()),
 531       min_children_(min_children),
 532       max_children_(max_children) {
 533   DCHECK_GE(min_children_, 2U);
 534   DCHECK_LE(min_children_, max_children_ / 2U);
 535 }
 536
 537 RTreeBase::~RTreeBase() {
 538 }
 539
 540 void RTreeBase::InsertNode(
 541     scoped_ptr<NodeBase> node, int* highest_reinsert_level) {
 542   // Find the most appropriate parent to insert node into.
 543   Node* parent = root_->ChooseSubtree(node.get());
 544   DCHECK(parent);
 545   // Verify ChooseSubtree returned a Node at the correct level.
 546   DCHECK_EQ(parent->Level(), node->Level() + 1);
 547   Node* insert_parent = static_cast<Node*>(parent);
 548   NodeBase* needs_bounds_recomputed = insert_parent->parent();
 549   Nodes reinserts;
 550   // Attempt to insert the Node, if this overflows the Node we must handle it.
 551   while (insert_parent &&
 552          insert_parent->AddChild(node.Pass()) > max_children_) {
 553     // If we have yet to re-insert nodes at this level during this data insert,
 554     // and we're not at the root, R*-Tree calls for re-insertion of some of the
 555     // nodes, resulting in a better balance on the tree.
 556     if (insert_parent->parent() &&
 557         insert_parent->Level() > *highest_reinsert_level) {
 558       insert_parent->RemoveNodesForReinsert(max_children_ / 3, &reinserts);
 559       // Adjust highest_reinsert_level to this level.
 560       *highest_reinsert_level = insert_parent->Level();
 561       // RemoveNodesForReinsert() does not recompute bounds, so mark it.
 562       needs_bounds_recomputed = insert_parent;
 563       break;
 564     }
 565
 566     // Split() will create a sibling to insert_parent both of which will have
 567     // valid bounds, but this invalidates their parent's bounds.
 568     node = insert_parent->Split(min_children_, max_children_);
 569     insert_parent = static_cast<Node*>(insert_parent->parent());
 570     needs_bounds_recomputed = insert_parent;
 571   }
 572
 573   // If we have a Node to insert, and we hit the root of the current tree,
 574   // we create a new root which is the parent of the current root and the
 575   // insert_node. Note that we must release() the |root_| since
 576   // ConstructParent() will take ownership of it.
 577   if (!insert_parent && node) {
 578     root_ = root_.release()->ConstructParent();
 579     root_->AddChild(node.Pass());
 580   }
 581
 582   // Recompute bounds along insertion path.
 583   if (needs_bounds_recomputed)
 584     needs_bounds_recomputed->RecomputeBoundsUpToRoot();
 585
 586   // Complete re-inserts, if any. The algorithm only allows for one invocation
 587   // of RemoveNodesForReinsert() per level of the tree in an overall call to
 588   // Insert().
 589   while (!reinserts.empty()) {
 590     Nodes::iterator last_element = reinserts.end() - 1;
 591     NodeBase* temp_ptr(*last_element);
 592     reinserts.weak_erase(last_element);
 593     InsertNode(make_scoped_ptr(temp_ptr), highest_reinsert_level);
 594   }
 595 }
 596
 597 scoped_ptr<RTreeBase::NodeBase> RTreeBase::RemoveNode(NodeBase* node) {
 598   // We need to remove this node from its parent.
 599   Node* parent = static_cast<Node*>(node->parent());
 600   // Record nodes are never allowed as the root, so we should always have a
 601   // parent.
 602   DCHECK(parent);
 603   // Should always be a leaf that had the record.
 604   DCHECK_EQ(0, parent->Level());
 605
 606   Nodes orphans;
 607   scoped_ptr<NodeBase> removed_node(parent->RemoveChild(node, &orphans));
 608
 609   // It's possible that by removing |node| from |parent| we have made |parent|
 610   // have less than the minimum number of children, in which case we will need
 611   // to remove and delete |parent| while reinserting any other children that it
 612   // had. We traverse up the tree doing this until we remove a child from a
 613   // parent that still has greater than or equal to the minimum number of Nodes.
 614   while (parent->count() < min_children_) {
 615     NodeBase* child = parent;
 616     parent = static_cast<Node*>(parent->parent());
 617
 618     // If we've hit the root, stop.
 619     if (!parent)
 620       break;
 621
 622     parent->RemoveChild(child, &orphans);
 623   }
 624
 625   // If we stopped deleting nodes up the tree before encountering the root,
 626   // we'll need to fix up the bounds from the first parent we didn't delete
 627   // up to the root.
 628   if (parent)
 629     parent->RecomputeBoundsUpToRoot();
 630   else
 631     root_->RecomputeBoundsUpToRoot();
 632
 633   while (!orphans.empty()) {
 634     Nodes::iterator last_element = orphans.end() - 1;
 635     NodeBase* temp_ptr(*last_element);
 636     orphans.weak_erase(last_element);
 637     int starting_level = -1;
 638     InsertNode(make_scoped_ptr(temp_ptr), &starting_level);
 639   }
 640
 641   return removed_node.Pass();
 642 }
 643
 644 void RTreeBase::PruneRootIfNecessary() {
 645   if (root()->count() == 1 && root()->Level() > 0) {
 646     // Awkward reset(cast(release)) pattern here because there's no better way
 647     // to downcast the scoped_ptr from RemoveAndReturnLastChild() from NodeBase
 648     // to Node.
 649     root_.reset(
 650         static_cast<Node*>(root_->RemoveAndReturnLastChild().release()));
 651   }
 652 }
 653
 654 void RTreeBase::ResetRoot() {
 655   root_.reset(new Node());
 656 }
 657
 658 }  // namespace gfx