Adds an RTree data structure to gfx/geometry

ui/gfx/geometry/r_tree.cc

+// Copyright (c) 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "ui/gfx/geometry/r_tree.h"
+
+#include <algorithm>
+#include <limits>
+
+#include "base/logging.h"
+
+namespace {
+
+// Returns the center coordinates of the given rectangle.
+gfx::Vector2d CenterOfRect(const gfx::Rect& rect) {
+  return rect.OffsetFromOrigin() +
+         gfx::Vector2d(rect.width() / 2, rect.height() / 2);
+}
+
+}
+
+namespace gfx {
+
+RTree::Node::Node(int level) : level_(level), parent_(NULL), key_(NULL) {
+}
+
+RTree::Node::Node(const Rect& rect, const void* key)
+    : rect_(rect), level_(-1), parent_(NULL), key_(key) {
+}
+
+RTree::Node::~Node() {
+  Clear();
+}
+
+void RTree::Node::Clear() {
+  // Iterate through children and delete them all.
+  children_.clear();
+  key_ = NULL;
+}
+
+void RTree::Node::Query(const Rect& query_rect,
+                        std::set<const void*>* matches_out) const {
+  // Check own bounding box for intersection, can cull all children if no
+  // intersection.
+  if (!rect_.Intersects(query_rect)) {
+    return;
+  }
+
+  // Conversely if we are completely contained within the query rect we can
+  // confidently skip all bounds checks for ourselves and all our children.
+  if (query_rect.Contains(rect_)) {
+    GetAllValues(matches_out);
+    return;
+  }
+
+  // We intersect the query rect but we are not are not contained within it.
+  // If we are a record node, then add our record value. Otherwise we must
+  // query each of our children in turn.
+  if (key_) {
+    DCHECK_EQ(level_, -1);
+    matches_out->insert(key_);
+  } else {
+    for (size_t i = 0; i < children_.size(); ++i) {
+      // Sanity-check our children.
+      Node* node = children_[i];
+      DCHECK_EQ(node->parent_, this);
+      DCHECK_EQ(level_ - 1, node->level_);
+      DCHECK(rect_.Contains(node->rect_));
+      node->Query(query_rect, matches_out);
+    }
+  }
+}
+
+void RTree::Node::RecomputeBounds() {
+  RecomputeBoundsNoParents();
+  // Recompute our parent's bounds recursively up to the root.
+  if (parent_) {
+    parent_->RecomputeBounds();
+  }
+}
+
+void RTree::Node::RemoveNodesForReinsert(size_t number_to_remove,
+                                         std::vector<Node*>* nodes) {

[piman, 2014/04/28 18:24:28]

nit: it'd be good to return nodes in a ScopedVector as well, to indicate that
ownership is transferred.

[luken, 2014/04/29 21:01:04]

Done.

+  DCHECK_GE(children_.size(), number_to_remove);
+
+  // Sort our children by their distance from the center of their rectangles to
+  // the center of our bounding rectangle.
+  std::sort(children_.begin(),
+            children_.end(),
+            &RTree::Node::CompareCenterDistanceFromParent);
+
+  // Add lowest distance nodes from our children list to the returned vector.
+  nodes->insert(
+      nodes->end(), children_.begin(), children_.begin() + number_to_remove);
+  // Remove those same nodes from our list, without deleting them.
+  children_.weak_erase(children_.begin(), children_.begin() + number_to_remove);
+}
+
+size_t RTree::Node::RemoveChild(Node* child_node, std::vector<Node*>* orphans) {

[piman, 2014/04/28 18:24:28]

Same here wrt ScopedVector

[luken, 2014/04/29 21:01:04]

Done.

+  // Should actually be one of our children.
+  DCHECK_EQ(child_node->parent_, this);
+
+  // Add children of child_node to the orphans vector.
+  orphans->insert(orphans->end(),
+                  child_node->children_.begin(),
+                  child_node->children_.end());
+  // Remove without deletion those children from the child_node vector.
+  child_node->children_.weak_clear();
+
+  // Find an iterator to this Node in our own children_ vector.
+  ScopedVector<Node>::iterator child_it = children_.end();
+  for (size_t i = 0; i < children_.size(); ++i) {
+    if (children_[i] == child_node) {
+      child_it = children_.begin() + i;
+      break;
+    }
+  }
+  // Should have found the pointer in our children_ vector.
+  DCHECK(child_it != children_.end());
+  // Remove without deleting the child node from our children_ vector.
+  children_.weak_erase(child_it);
+
+  return children_.size();
+}
+
+RTree::Node* RTree::Node::RemoveAndReturnLastChild() {

[piman, 2014/04/28 18:24:28]

return scoped_ptr

[luken, 2014/04/29 21:01:04]

Done.

+  if (!children_.size())
+    return NULL;
+
+  Node* last_child = children_[children_.size() - 1];
+  DCHECK_EQ(last_child->parent_, this);
+  children_.weak_erase(children_.begin() + children_.size() - 1);
+  // Invalidate parent, as this child may even become the new root.
+  last_child->parent_ = NULL;
+  return last_child;
+}
+
+// Uses the R*-Tree algorithm CHOOSELEAF proposed by Beckmann et al.
+RTree::Node* RTree::Node::ChooseSubtree(Node* node) {
+  // Should never be called on a record node.
+  DCHECK(!key_);
+  DCHECK(level_ >= 0);
+  DCHECK(node);
+
+  // If we are a parent of nodes on the provided node level, we are done.
+  if (level_ == node->level_ + 1)
+    return this;
+
+  // We are an internal node, and thus guaranteed to have children.
+  DCHECK_GT(children_.size(), 0U);
+
+  // Iterate over all children to find best candidate for insertion.
+  Node* best_candidate = NULL;
+
+  // For parents of leaf nodes, we pick the node that will cause the least
+  // increase in overlap by the addition of this new node. This may detect a
+  // tie, in which case it will return NULL.
+  if (level_ == 1)
+    best_candidate = LeastOverlapIncrease(node);
+
+  // For non-parents of leaf nodes, or for parents of leaf nodes with ties in
+  // overlap increase, we choose the subtree with least area enlargement caused
+  // by the addition of the new node.
+  if (!best_candidate)
+    best_candidate = LeastAreaEnlargement(node);
+
+  DCHECK(best_candidate);
+  return best_candidate->ChooseSubtree(node);
+}
+
+RTree::Node* RTree::Node::LeastAreaEnlargement(Node* node) {
+  Node* best_node = NULL;
+  int least_area_enlargement = std::numeric_limits<int>::max();
+  for (size_t i = 0; i < children_.size(); ++i) {
+    Node* candidate_node = children_[i];
+    Rect expanded_rect = candidate_node->rect_;
+    expanded_rect.Union(node->rect_);
+    int area_change =
+        expanded_rect.size().GetArea() - candidate_node->rect_.size().GetArea();
+    if (area_change < least_area_enlargement) {
+      best_node = candidate_node;
+      least_area_enlargement = area_change;
+    } else if (area_change == least_area_enlargement) {
+      // Ties are broken by choosing entry with least area.
+      DCHECK(best_node);
+      if (candidate_node->rect_.size().GetArea() <
+          best_node->rect_.size().GetArea()) {
+        best_node = candidate_node;
+      }
+    }
+  }
+
+  DCHECK(best_node);
+  return best_node;
+}
+
+RTree::Node* RTree::Node::LeastOverlapIncrease(RTree::Node* node) {
+  Node* best_node = NULL;
+  Node* tied_node = NULL;

[piman, 2014/04/28 18:24:28]

nit: this could just be a bool.

[luken, 2014/04/29 21:01:04]

Done.

+  int least_overlap_increase = std::numeric_limits<int>::max();
+  for (size_t i = 0; i < children_.size(); ++i) {
+    Node* candidate_node = children_[i];
+    Rect expanded_rect = candidate_node->rect_;
+    expanded_rect.Union(node->rect_);

[piman, 2014/04/28 18:24:28]

I would really like if we didn't do redundant computations... that was sort of
my feedback on the previous PS.

In this case, we computed all these expanded rects for all the children in
LeastAreaEnlargement. We threw it out at the end of the function, and recompute
it here. I guess that's the side effect of breaking the loop into 2 functions.

Can we save that computation so that we can reuse it?

[luken, 2014/04/29 21:01:04]

Done.

+    int overlap_increase = OverlapIncreaseToAdd(node->rect_, i, expanded_rect);
+    if (overlap_increase < least_overlap_increase) {
+      least_overlap_increase = overlap_increase;
+      best_node = candidate_node;
+      tied_node = NULL;
+    } else if (overlap_increase == least_overlap_increase) {
+      tied_node = candidate_node;
+      // If we are tied at zero there is no possible better overlap increase,
+      // so we can report a tie early.
+      if (overlap_increase == 0) {
+        return NULL;
+      }
+    }
+  }
+
+  // If we ended up with a tie return NULL to report it.
+  if (tied_node)
+    return NULL;
+
+  return best_node;
+}
+
+int RTree::Node::OverlapIncreaseToAdd(const Rect& rect,
+                                      size_t candidate,
+                                      const Rect& expanded_rect) {
+  Node* candidate_node = children_[candidate];
+
+  // Early-out option for when rect is contained completely within candidate.
+  if (candidate_node->rect_.Contains(rect)) {
+    return 0;
+  }
+
+  int total_original_overlap = 0;
+  int total_expanded_overlap = 0;
+
+  // Now calculate overlap with all other rects in this node.
+  for (size_t i = 0; i < children_.size(); ++i) {
+    // Skip calculating overlap with the candidate rect.
+    if (i == candidate)
+      continue;
+    Node* overlap_node = children_[i];
+    Rect overlap_rect = candidate_node->rect_;
+    overlap_rect.Intersect(overlap_node->rect_);
+    total_original_overlap += overlap_rect.size().GetArea();
+    Rect expanded_overlap_rect = expanded_rect;
+    expanded_overlap_rect.Intersect(overlap_node->rect_);
+    total_expanded_overlap += expanded_overlap_rect.size().GetArea();
+  }
+
+  // Compare this overlap increase with best one to date, update best.
+  int overlap_increase = total_expanded_overlap - total_original_overlap;
+  return overlap_increase;
+}
+
+size_t RTree::Node::AddChild(Node* node) {
+  DCHECK(node);
+  // Sanity-check that the level of the child being added is one more than ours.
+  DCHECK_EQ(level_ - 1, node->level_);
+  node->parent_ = this;
+  children_.push_back(node);
+  rect_.Union(node->rect_);
+  return children_.size();
+}
+
+RTree::Node* RTree::Node::Split(size_t min_children, size_t max_children) {
+  // Please don't attempt to split a record Node.
+  DCHECK(!key_);
+  // We should have too many children to begin with.
+  DCHECK_GT(children_.size(), max_children);
+  // First determine if splitting along the horizontal or vertical axis. We
+  // sort the rectangles of our children by lower then upper values along both
+  // horizontal and vertical axes.
+  std::vector<Node*> vertical_sort(children_.get());
+  std::vector<Node*> horizontal_sort(children_.get());
+  std::sort(vertical_sort.begin(),
+            vertical_sort.end(),
+            &RTree::Node::CompareVertical);
+  std::sort(horizontal_sort.begin(),
+            horizontal_sort.end(),
+            &RTree::Node::CompareHorizontal);
+
+  // We will be examining the bounding boxes of different splits of our children
+  // sorted along each axis. Here we precompute the bounding boxes of these
+  // distributions. For the low bounds the ith element can be considered the
+  // union of all rects [0,i] in the relevant sorted axis array.
+  std::vector<Rect> low_vertical_bounds;
+  std::vector<Rect> low_horizontal_bounds;
+  BuildLowBounds(vertical_sort,
+                 horizontal_sort,
+                 &low_vertical_bounds,
+                 &low_horizontal_bounds);
+
+  // For the high bounds the ith element can be considered the union of all
+  // rects [i, children_.size()) in the relevant sorted axis array.
+  std::vector<Rect> high_vertical_bounds;
+  std::vector<Rect> high_horizontal_bounds;
+  BuildHighBounds(vertical_sort,
+                  horizontal_sort,
+                  &high_vertical_bounds,
+                  &high_horizontal_bounds);
+
+  bool is_vertical_split = ChooseSplitAxis(low_vertical_bounds,
+                                           high_vertical_bounds,
+                                           low_horizontal_bounds,
+                                           high_horizontal_bounds,
+                                           min_children,
+                                           max_children);
+
+  // Lastly we determine optimal index and do the split.
+  Node* sibling = NULL;
+  if (is_vertical_split) {
+    size_t split_index = ChooseSplitIndex(
+        min_children, max_children, low_vertical_bounds, high_vertical_bounds);
+    sibling = DivideChildren(
+        low_vertical_bounds, high_vertical_bounds, vertical_sort, split_index);
+  } else {
+    size_t split_index = ChooseSplitIndex(min_children,
+                                          max_children,
+                                          low_horizontal_bounds,
+                                          high_horizontal_bounds);
+    sibling = DivideChildren(low_horizontal_bounds,
+                             high_horizontal_bounds,
+                             horizontal_sort,
+                             split_index);
+  }
+
+  return sibling;
+}
+
+// static
+void RTree::Node::BuildLowBounds(const std::vector<Node*>& vertical_sort,
+                                 const std::vector<Node*>& horizontal_sort,
+                                 std::vector<Rect>* vertical_bounds,
+                                 std::vector<Rect>* horizontal_bounds) {
+  DCHECK_EQ(vertical_sort.size(), horizontal_sort.size());
+  Rect vertical_bounds_rect;
+  Rect horizontal_bounds_rect;
+  vertical_bounds->reserve(vertical_sort.size());
+  horizontal_bounds->reserve(horizontal_sort.size());
+  for (size_t i = 0; i < vertical_sort.size(); ++i) {
+    vertical_bounds_rect.Union(vertical_sort[i]->rect_);
+    horizontal_bounds_rect.Union(horizontal_sort[i]->rect_);
+    vertical_bounds->push_back(vertical_bounds_rect);
+    horizontal_bounds->push_back(horizontal_bounds_rect);
+  }
+}
+
+// static
+void RTree::Node::BuildHighBounds(const std::vector<Node*>& vertical_sort,
+                                  const std::vector<Node*>& horizontal_sort,
+                                  std::vector<Rect>* vertical_bounds,
+                                  std::vector<Rect>* horizontal_bounds) {
+  DCHECK_EQ(vertical_sort.size(), horizontal_sort.size());
+  Rect vertical_bounds_rect;
+  Rect horizontal_bounds_rect;
+  vertical_bounds->resize(vertical_sort.size());
+  horizontal_bounds->resize(horizontal_sort.size());
+  for (int i = static_cast<int>(vertical_sort.size()) - 1; i >= 0; --i) {
+    vertical_bounds_rect.Union(vertical_sort[i]->rect_);
+    horizontal_bounds_rect.Union(horizontal_sort[i]->rect_);
+    vertical_bounds->at(i) = vertical_bounds_rect;
+    horizontal_bounds->at(i) = horizontal_bounds_rect;
+  }
+}
+
+// static
+bool RTree::Node::ChooseSplitAxis(
+    const std::vector<Rect>& low_vertical_bounds,
+    const std::vector<Rect>& high_vertical_bounds,
+    const std::vector<Rect>& low_horizontal_bounds,
+    const std::vector<Rect>& high_horizontal_bounds,
+    size_t min_children,
+    size_t max_children) {
+  // Examine the possible distributions of each sorted list by iterating through
+  // valid split points p, min_children <= p <= max_children - min_children, and
+  // computing the sums of the margins of the bounding boxes in each group.
+  // Smallest margin sum will determine split axis.
+  int smallest_horizontal_margin_sum = std::numeric_limits<int>::max();
+  int smallest_vertical_margin_sum = std::numeric_limits<int>::max();
+  for (size_t p = min_children; p < max_children - min_children; ++p) {
+    int horizontal_margin_sum =
+        low_horizontal_bounds[p].width() + low_horizontal_bounds[p].height() +
+        high_horizontal_bounds[p].width() + high_horizontal_bounds[p].height();
+    int vertical_margin_sum =
+        low_vertical_bounds[p].width() + low_vertical_bounds[p].height() +
+        high_vertical_bounds[p].width() + high_vertical_bounds[p].height();
+    // Update margin minima if necessary.
+    smallest_horizontal_margin_sum =
+        std::min(horizontal_margin_sum, smallest_horizontal_margin_sum);
+    smallest_vertical_margin_sum =
+        std::min(vertical_margin_sum, smallest_vertical_margin_sum);
+  }
+
+  // Split along the axis perpendicular to the axis with the overall smallest
+  // margin sum. Meaning the axis sort resulting in two boxes with the smallest
+  // combined margin will become the axis along which the sorted rectangles are
+  // distributed to the two Nodes.
+  bool is_vertical_split =
+      smallest_vertical_margin_sum < smallest_horizontal_margin_sum;
+  return is_vertical_split;
+}
+
+RTree::Node* RTree::Node::DivideChildren(
+    const std::vector<Rect>& low_bounds,
+    const std::vector<Rect>& high_bounds,
+    const std::vector<Node*>& sorted_children,
+    size_t split_index) {
+  Node* sibling = new Node(level_);
+  sibling->parent_ = parent_;
+  rect_ = low_bounds[split_index - 1];
+  sibling->rect_ = high_bounds[split_index];
+  // Our own children_ vector is unsorted, so we wipe it out and divide the
+  // sorted bounds rects between ourselves and our sibling.
+  children_.weak_clear();
+  children_.insert(children_.end(),
+                   sorted_children.begin(),
+                   sorted_children.begin() + split_index);
+  sibling->children_.insert(sibling->children_.end(),
+                            sorted_children.begin() + split_index,
+                            sorted_children.end());
+
+  // Fix up sibling parentage or it's gonna be an awkward Thanksgiving.
+  for (size_t i = 0; i < sibling->children_.size(); ++i) {
+    sibling->children_[i]->parent_ = sibling;
+  }
+
+  return sibling;
+}
+
+void RTree::Node::SetRect(const Rect& rect) {
+  // Record nodes only, please.
+  DCHECK(key_);
+  rect_ = rect;
+}
+
+// Returns all contained record_node values for this node and all children.
+void RTree::Node::GetAllValues(std::set<const void*>* matches_out) const {
+  if (key_) {
+    DCHECK_EQ(level_, -1);
+    matches_out->insert(key_);
+  } else {
+    for (size_t i = 0; i < children_.size(); ++i) {
+      Node* node = children_[i];
+      // Sanity-check our children.
+      DCHECK_EQ(node->parent_, this);
+      DCHECK_EQ(level_ - 1, node->level_);
+      DCHECK(rect_.Contains(node->rect_));
+      node->GetAllValues(matches_out);
+    }
+  }
+}
+
+// static
+bool RTree::Node::CompareVertical(Node* a, Node* b) {
+  // Sort nodes by top coordinate first.
+  if (a->rect_.y() < b->rect_.y()) {
+    return true;
+  } else if (a->rect_.y() == b->rect_.y()) {
+    // If top coordinate is equal, sort by lowest bottom coordinate.
+    return a->rect_.height() < b->rect_.height();
+  }
+  return false;
+}
+
+// static
+bool RTree::Node::CompareHorizontal(Node* a, Node* b) {
+  // Sort nodes by left coordinate first.
+  if (a->rect_.x() < b->rect_.x()) {
+    return true;
+  } else if (a->rect_.x() == b->rect_.x()) {
+    // If left coordinate is equal, sort by lowest right coordinate.
+    return a->rect_.width() < b->rect_.width();
+  }
+  return false;
+}
+
+// Sort these two nodes by the distance of the center of their rects from the
+// center of their parent's rect. We don't bother with square roots because we
+// are only comparing the two values for sorting purposes.
+// static
+bool RTree::Node::CompareCenterDistanceFromParent(Node* a, Node* b) {
+  // This comparison assumes the nodes have the same parent.
+  DCHECK(a->parent_ == b->parent_);
+  // This comparison requires that each node have a parent.
+  DCHECK(a->parent_);
+  // Sanity-check level_ of these nodes is equal.
+  DCHECK_EQ(a->level_, b->level_);
+  // Also the parent of the nodes should have level one higher.
+  DCHECK_EQ(a->level_, a->parent_->level_ - 1);
+
+  // Find the parent.
+  Node* p = a->parent();
+
+  Vector2d p_center = CenterOfRect(p->rect_);
+  Vector2d a_center = CenterOfRect(a->rect_);
+  Vector2d b_center = CenterOfRect(b->rect_);
+
+  return (a_center - p_center).LengthSquared() <
+         (b_center - p_center).LengthSquared();
+}
+
+size_t RTree::Node::ChooseSplitIndex(size_t min_children,
+                                     size_t max_children,
+                                     const std::vector<Rect>& low_bounds,
+                                     const std::vector<Rect>& high_bounds) {
+  int smallest_overlap_area = std::numeric_limits<int>::max();
+  int smallest_combined_area = std::numeric_limits<int>::max();
+  size_t optimal_split_index = 0;
+  for (size_t p = min_children; p < max_children - min_children; ++p) {
+    Rect overlap_bounds = low_bounds[p];
+    overlap_bounds.Union(high_bounds[p]);
+    int overlap_area = overlap_bounds.size().GetArea();
+    if (overlap_area < smallest_overlap_area) {
+      smallest_overlap_area = overlap_area;
+      smallest_combined_area =
+          low_bounds[p].size().GetArea() + high_bounds[p].size().GetArea();
+      optimal_split_index = p;
+    } else if (overlap_area == smallest_overlap_area) {
+      // Break ties with smallest combined area of the two bounding boxes.
+      int combined_area =
+          low_bounds[p].size().GetArea() + high_bounds[p].size().GetArea();
+      if (combined_area < smallest_combined_area) {
+        smallest_combined_area = combined_area;
+        optimal_split_index = p;
+      }
+    }
+  }
+
+  // optimal_split_index currently points at the last element in the first set,
+  // so advance it by 1 to point at the first element in the second set.
+  return optimal_split_index + 1;
+}
+
+void RTree::Node::RecomputeBoundsNoParents() {
+  // Clear our rectangle, then reset it to union of our children.
+  rect_.SetRect(0, 0, 0, 0);
+  for (size_t i = 0; i < children_.size(); ++i) {
+    rect_.Union(children_[i]->rect_);
+  }
+}
+
+RTree::RTree(size_t min_children, size_t max_children)
+    : root_(new Node(0)),
+      min_children_(min_children),
+      max_children_(max_children) {
+  // R-Trees require min_children >= 2
+  DCHECK_GE(min_children_, 2U);
+  // R-Trees also require min_children <= max_children / 2
+  DCHECK_LE(min_children_, max_children_ / 2U);
+  root_.reset(new Node(0));
+}
+
+RTree::~RTree() {
+  Clear();
+}
+
+void RTree::Insert(const Rect& rect, const void* key) {
+  // Non-NULL keys, please.
+  DCHECK(key);
+
+  Node* record_node = NULL;
+  // Check if this key is already present in the tree.
+  std::map<const void*, Node*>::iterator it = record_map_.find(key);
+  if (it != record_map_.end()) {
+    // We will re-use this node structure, regardless of re-insert or return.
+    record_node = it->second;
+    // If the new rect and the current rect are identical we can skip rest of
+    // Insert() as nothing has changed.
+    if (record_node->rect() == rect)
+      return;
+
+    // Remove the node from the tree in its current position.
+    RemoveNode(record_node);
+
+    // If we are replacing this key with an empty rectangle we just remove the
+    // old node from the list and return, thus preventing insertion of empty
+    // rectangles into our spatial database.
+    if (rect.IsEmpty()) {
+      record_map_.erase(it);
+      delete record_node;
+      return;
+    }
+
+    // Reset the rectangle to the new value.
+    record_node->SetRect(rect);
+  } else {
+    if (rect.IsEmpty())
+      return;
+    // Build a new record Node for insertion in to tree.
+    record_node = new Node(rect, key);
+    // Add this new node to our map, for easy retrieval later.
+    record_map_.insert(std::make_pair(key, record_node));
+  }
+
+  // Call internal Insert with this new node and allowing all re-inserts.
+  int starting_level = -1;
+  InsertNode(record_node, &starting_level);
+}
+
+void RTree::Remove(const void* key) {
+  // Search the map for the leaf parent that has the provided record.
+  std::map<const void*, Node*>::iterator it = record_map_.find(key);
+  // If not in the map it's not in the tree, we're done.
+  if (it == record_map_.end())
+    return;
+
+  Node* node = it->second;
+  // Remove this node from the map.
+  record_map_.erase(it);
+  // Now remove it from the RTree.
+  RemoveNode(node);
+  delete node;
+
+  // Lastly check the root. If it has only one non-leaf child, delete it and
+  // replace it with its child.
+  if (root_->count() == 1 && root_->level() > 0)
+    root_.reset(root_->RemoveAndReturnLastChild());
+}
+
+void RTree::Query(const Rect& query_rect,
+                  std::set<const void*>* matches_out) const {
+  root_->Query(query_rect, matches_out);
+}
+
+void RTree::Clear() {
+  record_map_.clear();
+  root_.reset(new Node(0));
+}
+
+void RTree::InsertNode(Node* node, int* highest_reinsert_level) {
+  // Find the most appropriate parent to insert node into.
+  Node* parent = root_->ChooseSubtree(node);
+  DCHECK(parent);
+  // Verify ChooseSubtree returned a Node at the correct level.
+  DCHECK_EQ(parent->level(), node->level() + 1);
+  Node* insert_node = node;
+  Node* insert_parent = parent;
+  Node* needs_bounds_recomputed = insert_parent->parent();
+  std::vector<Node*> reinserts;
+  // Attempt to insert the Node, if this overflows the Node we must handle it.
+  while (insert_parent &&
+         insert_parent->AddChild(insert_node) > max_children_) {
+    // If we have yet to re-insert nodes at this level during this data insert,
+    // and we're not at the root, R*-Tree calls for re-insertion of some of the
+    // nodes, resulting in a better balance on the tree.
+    if (insert_parent->parent() &&
+        insert_parent->level() > *highest_reinsert_level) {
+      insert_parent->RemoveNodesForReinsert(max_children_ / 3, &reinserts);
+      // Adjust highest_reinsert_level to this level.
+      *highest_reinsert_level = insert_parent->level();
+      // We didn't create any new nodes so we have nothing new to insert.
+      insert_node = NULL;
+      // RemoveNodesForReinsert() does not recompute bounds, so mark it.
+      needs_bounds_recomputed = insert_parent;
+      break;
+    }
+
+    // Split() will create a sibling to insert_parent both of which will have
+    // valid bounds, but this invalidates their parent's bounds.
+    insert_node = insert_parent->Split(min_children_, max_children_);
+    insert_parent = insert_parent->parent();
+    needs_bounds_recomputed = insert_parent;
+  }
+
+  // If we have a Node to insert, and we hit the root of the current tree,
+  // we create a new root which is the parent of the current root and the
+  // insert_node
+  if (!insert_parent && insert_node) {
+    Node* old_root = root_.release();
+    root_.reset(new Node(old_root->level() + 1));
+    root_->AddChild(old_root);
+    root_->AddChild(insert_node);
+  }
+
+  // Recompute bounds along insertion path.
+  if (needs_bounds_recomputed) {
+    needs_bounds_recomputed->RecomputeBounds();
+  }
+
+  // Complete re-inserts, if any.
+  for (size_t i = 0; i < reinserts.size(); ++i) {
+    InsertNode(reinserts[i], highest_reinsert_level);
+  }
+}
+
+void RTree::RemoveNode(Node* node) {
+  // We need to remove this node from its parent.
+  Node* parent = node->parent();
+  // Record nodes are never allowed as the root, so we should always have a
+  // parent.
+  DCHECK(parent);
+  // Should always be a leaf that had the record.
+  DCHECK_EQ(parent->level(), 0);
+  std::vector<Node*> orphans;
+  Node* child = node;
+
+  // Traverse up the tree, removing the child from each parent and deleting
+  // parent nodes, until we either encounter the root of the tree or a parent
+  // that still has sufficient children.
+  while (parent && parent->RemoveChild(child, &orphans) < min_children_) {
+    if (child != node) {
+      delete child;
+    }
+    child = parent;
+    parent = parent->parent();
+  }
+
+  // If we stopped deleting nodes up the tree before encountering the root,
+  // we'll need to fix up the bounds from the first parent we didn't delete
+  // up to the root.
+  if (parent) {
+    parent->RecomputeBounds();
+  }
+
+  // Now re-insert each of the orphaned nodes back into the tree.
+  for (size_t i = 0; i < orphans.size(); ++i) {
+    int starting_level = -1;
+    InsertNode(orphans[i], &starting_level);
+  }
+}
+
+}  // namespace gfx