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
14namespace {
15
16// Returns a Vector2d to allow us to do arithmetic on the result such as
17// computing distances between centers.
18gfx::Vector2d CenterOfRect(const gfx::Rect& rect) {
19  return rect.OffsetFromOrigin() +
20      gfx::Vector2d(rect.width() / 2, rect.height() / 2);
21}
22
23}
24
25namespace gfx {
26
27
28// RTreeBase::NodeBase --------------------------------------------------------
29
30RTreeBase::NodeBase::~NodeBase() {
31}
32
33void RTreeBase::NodeBase::RecomputeBoundsUpToRoot() {
34  RecomputeLocalBounds();
35  if (parent_)
36    parent_->RecomputeBoundsUpToRoot();
37}
38
39RTreeBase::NodeBase::NodeBase(const Rect& rect, NodeBase* parent)
40    : rect_(rect),
41      parent_(parent) {
42}
43
44void RTreeBase::NodeBase::RecomputeLocalBounds() {
45}
46
47// RTreeBase::RecordBase ------------------------------------------------------
48
49RTreeBase::RecordBase::RecordBase(const Rect& rect) : NodeBase(rect, NULL) {
50}
51
52RTreeBase::RecordBase::~RecordBase() {
53}
54
55void 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
61void RTreeBase::RecordBase::AppendAllRecords(Records* matches_out) const {
62  matches_out->push_back(this);
63}
64
65scoped_ptr<RTreeBase::NodeBase>
66RTreeBase::RecordBase::RemoveAndReturnLastChild() {
67  return scoped_ptr<NodeBase>();
68}
69
70int RTreeBase::RecordBase::Level() const {
71  return -1;
72}
73
74
75// RTreeBase::Node ------------------------------------------------------------
76
77RTreeBase::Node::Node() : NodeBase(Rect(), NULL), level_(0) {
78}
79
80RTreeBase::Node::~Node() {
81}
82
83scoped_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
90void 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
110void 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
115void 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
130scoped_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
147scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::RemoveAndReturnLastChild() {
148  if (children_.empty())
149    return scoped_ptr<NodeBase>();
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
157RTreeBase::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
191size_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
201scoped_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
256int RTreeBase::Node::Level() const {
257  return level_;
258}
259
260RTreeBase::Node::Node(int level) : NodeBase(Rect(), NULL), level_(level) {
261}
262
263// static
264bool 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
272bool 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
280bool 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
298void 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
323void 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
351size_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
382int 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
401void 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
409int 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
438scoped_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.PassAs<NodeBase>();
467}
468
469RTreeBase::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
496RTreeBase::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
529RTreeBase::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
537RTreeBase::~RTreeBase() {
538}
539
540void 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
597scoped_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
644void 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
654void RTreeBase::ResetRoot() {
655  root_.reset(new Node());
656}
657
658}  // namespace gfx
659