readability review for luken

ui/gfx/geometry/r_tree_base.cc

+// Copyright 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_base.h"
+
+#include <algorithm>
+
+#include "base/logging.h"
+
+// Helpers --------------------------------------------------------------------
+
+namespace {
+

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Either eliminate this blank line, or add one below the end-of-namespace
brace below.

[luken, 2014/05/21 20:19:36]

Done.

+// Returns a Vector2d to allow us to do arithmetic on the result such as
+// computing distances between centers.
+gfx::Vector2d CenterOfRect(const gfx::Rect& rect) {
+  return rect.OffsetFromOrigin() +
+         gfx::Vector2d(rect.width() / 2, rect.height() / 2);

[Peter Kasting, 2014/05/16 01:41:05]

Nit: The Google style guide is unclear here, but Chromium code typically indents
these lines by 4, instead of even with the end of the "return" above.  (Several
places)

[luken, 2014/05/21 20:19:36]

Done.

+}
+}
+
+namespace gfx {
+
+
+// RTreeBase::NodeBase --------------------------------------------------------
+
+RTreeBase::NodeBase::~NodeBase() {
+}
+
+void RTreeBase::NodeBase::RecomputeBoundsUpToRoot() {
+  RecomputeLocalBounds();
+  if (parent_)
+    parent_->RecomputeBoundsUpToRoot();
+}
+
+RTreeBase::NodeBase::NodeBase(const Rect& rect, NodeBase* parent)
+    : rect_(rect), parent_(parent) {

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Another unclear rule, but I read the style guide as suggesting that there
should be one initializer per line unless the whole constructor name, arg list,
and initializer list all fit on one line.

[luken, 2014/05/21 20:19:36]

Done.

+}
+
+
+// RTreeBase::RecordBase ------------------------------------------------------
+
+RTreeBase::RecordBase::RecordBase(const Rect& rect) : NodeBase(rect, NULL) {
+}
+
+RTreeBase::RecordBase::~RecordBase() {
+}
+
+void RTreeBase::RecordBase::SetRect(const Rect& rect) {
+  rect_ = rect;

[Peter Kasting, 2014/05/16 01:41:05]

This should probably be inlined into the header as "set_rect()".

[luken, 2014/05/21 20:19:36]

Done.

+}
+
+void RTreeBase::RecordBase::Query(const Rect& query_rect,
+                                  Records* matches_out) const {
+  if (!rect_.Intersects(query_rect))

[Peter Kasting, 2014/05/16 01:41:05]

Nit: It seems to read more clearly to me to reverse this and make the function
just:

  if (rect_.Intersects(query_rect))
    matches_out->push_back(this);

[luken, 2014/05/21 20:19:36]

Done.

+    return;
+
+  matches_out->push_back(this);
+}
+
+scoped_ptr<RTreeBase::NodeBase>
+RTreeBase::RecordBase::RemoveAndReturnLastChild() {
+  return scoped_ptr<NodeBase>();
+}
+
+const int RTreeBase::RecordBase::level() const {
+  return -1;
+}
+
+void RTreeBase::RecordBase::RecomputeLocalBounds() {
+}

[Peter Kasting, 2014/05/16 01:41:05]

Perhaps the base class should define this empty implementation, meaning
RecordBase doesn't need to?

[luken, 2014/05/21 20:19:36]

Done.

+
+void RTreeBase::RecordBase::GetAllValues(Records* matches_out) const {
+  matches_out->push_back(this);
+}
+
+
+// RTreeBase::Node ------------------------------------------------------------
+
+RTreeBase::Node::Node() : Node(0) {

[Peter Kasting, 2014/05/16 01:41:05]

Isn't calling one constructor from another C++11-only?  I don't believe Chromium
code can use C++11 yet.

[luken, 2014/05/21 20:19:36]

Done.

+}
+
+RTreeBase::Node::~Node() {
+}
+
+scoped_ptr<RTreeBase::Node> RTreeBase::Node::MakeParent() {
+  DCHECK(!parent_);
+  scoped_ptr<Node> new_parent(new Node(level_ + 1));
+  new_parent->AddChild(scoped_ptr<NodeBase>(this));
+  return new_parent.Pass();
+}
+
+scoped_ptr<RTreeBase::Node> RTreeBase::Node::MakeSibling() {
+  scoped_ptr<Node> new_sibling(new Node(level_));
+  return new_sibling.Pass();
+}
+
+void RTreeBase::Node::Query(const Rect& query_rect,
+                            Records* 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.
+  // We must query each of our children in turn.
+  for (Nodes::const_iterator i = children_.begin(); i != children_.end(); ++i) {

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Avoid braces since the loop header and body are both one line (unless you
want to put braces on all loops and conditionals) (several places)

[luken, 2014/05/21 20:19:36]

Done.

+    (*i)->Query(query_rect, matches_out);
+  }
+}
+
+void RTreeBase::Node::RemoveNodesForReinsert(size_t number_to_remove,
+                                             Nodes* nodes) {
+  DCHECK_LE(number_to_remove, children_.size());
+
+  std::sort(children_.begin(),

[Peter Kasting, 2014/05/16 01:41:05]

You can use partial_sort() instead of sort() here for a slight efficiency gain.

[luken, 2014/05/21 20:19:36]

Neat, didn't know about that. Done.

+            children_.end(),
+            &RTreeBase::Node::CompareCenterDistanceFromParent);
+
+  // Move the lowest-distance nodes to the returned vector.
+  nodes->insert(
+      nodes->end(), children_.begin(), children_.begin() + number_to_remove);
+  children_.weak_erase(children_.begin(), children_.begin() + number_to_remove);
+}
+
+size_t RTreeBase::Node::RemoveChild(NodeBase* child_node, Nodes* orphans) {
+  DCHECK_EQ(child_node->parent(), this);

[Peter Kasting, 2014/05/16 01:41:05]

Nit: (expected, actual)

[luken, 2014/05/21 20:19:36]

Done.

+
+  scoped_ptr<NodeBase> orphan = child_node->RemoveAndReturnLastChild();

[Peter Kasting, 2014/05/16 01:41:05]

Nit: See previous comment suggesting constructor-style init for non-BTs

[luken, 2014/05/21 20:19:36]

Done.

+  while (orphan) {
+    orphans->push_back(orphan.release());
+    orphan = child_node->RemoveAndReturnLastChild();

[Peter Kasting, 2014/05/16 01:41:05]

Curiosity: This will push the children onto the output vector in the reverse
order of how they were contained in |child_node|.  I wonder if this results in
us doing more sorting later -- to re-reverse this ordering -- versus if we
preserved the original order.  I suppose it depends on "how sorted" the child
nodes typically are?

[luken, 2014/05/21 20:19:36]

The nodes are sorted by 3 different criteria: lowest vertical coordinate, lowest
horizontal coordinate, and distance of center from distance of parent's center.
Given that each of these result in pretty different sorts, particularly the last
once since it's relative to the parent, I'm pretty confident the resorting cost
is cheap relative to the vector juggling required to either pop_front or
push_front to maintain child order.

[Peter Kasting, 2014/05/29 00:32:25]

This is an excellent argument, consider adding it as a comment here.

+  }
+
+  for (Nodes::iterator i = children_.begin(); i != children_.end(); ++i) {

[Peter Kasting, 2014/05/16 01:41:05]

How about using std::find?  It ought to make this slightly shorter and clearer.

[luken, 2014/05/21 20:19:36]

Done.

+    if (*i == child_node) {
+      children_.weak_erase(i);
+      break;
+    }
+  }
+
+  return children_.size();
+}
+
+scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::RemoveAndReturnLastChild() {
+  if (children_.empty())
+    return scoped_ptr<NodeBase>();
+
+  scoped_ptr<NodeBase> last_child(children_.back());
+  children_.weak_erase(children_.end() - 1);
+  last_child->SetParent(NULL);
+  return last_child.Pass();
+}
+
+RTreeBase::Node* RTreeBase::Node::ChooseSubtree(NodeBase* node) {
+  DCHECK(node);
+  // Should never be called on a node at equal or lower level in the tree than
+  // the node to insert.
+  DCHECK_GT(level_, node->level());
+
+  // If we are a parent of nodes on the provided node level, we are done.
+  if (level_ == node->level() + 1)
+    return this;
+
+  // Precompute a vector of expanded rects, used both by LeastOverlapIncrease

[Peter Kasting, 2014/05/16 01:41:05]

Nit: both by -> by both

[luken, 2014/05/21 20:19:36]

Done.

+  // and LeastAreaEnlargement.
+  std::vector<Rect> expanded_rects;

[Peter Kasting, 2014/05/16 01:41:05]

Use your Rects typedef (many places across the file)

[luken, 2014/05/21 20:19:36]

Done.

+  expanded_rects.reserve(children_.size());
+  for (Nodes::iterator i = children_.begin(); i != children_.end(); ++i) {
+    expanded_rects.push_back(UnionRects(node->rect(), (*i)->rect()));
+  }
+
+  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->rect(), expanded_rects);
+
+  // 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->rect(), expanded_rects);
+
+  DCHECK(best_candidate);
+  return best_candidate->ChooseSubtree(node);
+}
+
+size_t RTreeBase::Node::AddChild(scoped_ptr<NodeBase> node) {
+  DCHECK(node);
+  // Sanity-check that the level of the child being added is one less than ours.
+  DCHECK_EQ(level_ - 1, node->level());
+  node->SetParent(this);
+  rect_.Union(node->rect());
+  children_.push_back(node.release());
+  return children_.size();
+}
+
+RTreeBase::Node* RTreeBase::Node::Split(size_t min_children,
+                                        size_t max_children) {
+  // We should have too many children to begin with.
+  DCHECK_GT(children_.size(), max_children);
+
+  // Determine if we should split along the horizontal or vertical axis.
+  std::vector<NodeBase*> vertical_sort(children_.get());

[Peter Kasting, 2014/05/16 01:41:05]

Random thought: scoped_vector.h really ought to define a typedef for
std::vector<T*>... then we could do something here like "Nodes::RawVector"
instead of "std::vector<NodeBase*>", which would avoid encoding the same type
information ("container of NodeBases") at multiple distinct places.

Obviously, you need not do this in this change... but would you be interested in
doing it at all?

[luken, 2014/05/21 20:19:36]

It's a good idea. crbug.com/375480 filed. I'll take care of it after the review.

+  std::vector<NodeBase*> horizontal_sort(children_.get());
+  std::sort(vertical_sort.begin(),
+            vertical_sort.end(),
+            &RTreeBase::Node::CompareVertical);
+  std::sort(horizontal_sort.begin(),
+            horizontal_sort.end(),
+            &RTreeBase::Node::CompareHorizontal);
+
+  std::vector<Rect> low_vertical_bounds;
+  std::vector<Rect> low_horizontal_bounds;
+  BuildLowBounds(vertical_sort,
+                 horizontal_sort,
+                 &low_vertical_bounds,
+                 &low_horizontal_bounds);
+
+  std::vector<Rect> high_vertical_bounds;
+  std::vector<Rect> high_horizontal_bounds;
+  BuildHighBounds(vertical_sort,
+                  horizontal_sort,
+                  &high_vertical_bounds,
+                  &high_horizontal_bounds);
+
+  size_t end_index = max_children - min_children;

[Peter Kasting, 2014/05/16 01:41:05]

If we have more children than |max_children|, then shouldn't the end index
really be:

std::min(max_children, children_.size() - min_children)

?  Otherwise it seems like there's a range of indexes which would still leave at
least min_children in the second child which we could have used.

Also, if children_.size() is at least (max_children + min_children), then our
split could still leave the second child with more than max_children.  Is that a
problem?  Or are we expecting to be called as soon as we're a single child over?
 Maybe we should encode more of those assumptions as DCHECKs.

[luken, 2014/05/21 20:19:36]

That's a good point. This code only ever gets called when children_.size() ==
max_children + 1, so I tightened the DCHECK to that.

+  bool is_vertical_split =
+      SmallestMarginSum(min_children,
+                        end_index,
+                        low_horizontal_bounds,
+                        high_horizontal_bounds) <
+      SmallestMarginSum(
+          min_children, end_index, low_vertical_bounds, high_vertical_bounds);

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Wrap and indent both calls the same way.

[luken, 2014/05/21 20:19:36]

Done.

+
+  // Choose split index along chosen axis and perform the split.
+  const Rects& low_bounds(is_vertical_split ? low_vertical_bounds
+                                            : low_horizontal_bounds);

[Peter Kasting, 2014/05/16 01:41:05]

Nit: This is a clang-format bug; wrap like this instead:

  const Rects& low_bounds(
      is_vertical_split ? low_vertical_bounds : low_horizontal_bounds);

(3 places)

[luken, 2014/05/21 20:19:36]

Done.

+  const Rects& high_bounds(is_vertical_split ? high_vertical_bounds
+                                             : high_horizontal_bounds);
+  size_t split_index =
+      ChooseSplitIndex(min_children, max_children, low_bounds, high_bounds);
+
+  const std::vector<NodeBase*>& sort(is_vertical_split ? vertical_sort
+                                                       : horizontal_sort);
+  return DivideChildren(low_bounds, high_bounds, sort, split_index);
+}
+
+const int RTreeBase::Node::level() const {
+  return level_;
+}
+
+RTreeBase::Node::Node(int level) : NodeBase(Rect(), NULL), level_(level) {
+}
+
+// static
+bool RTreeBase::Node::CompareVertical(NodeBase* a, NodeBase* b) {
+  const Rect& a_rect = a->rect();
+  const Rect& b_rect = b->rect();
+  return (a_rect.y() < b_rect.y()) ||
+         ((a_rect.y() == b_rect.y()) && (a_rect.height() < b_rect.height()));
+}
+
+// static
+bool RTreeBase::Node::CompareHorizontal(NodeBase* a, NodeBase* b) {
+  const Rect& a_rect = a->rect();
+  const Rect& b_rect = b->rect();
+  return (a_rect.x() < b_rect.x()) ||
+         ((a_rect.x() == b_rect.x()) && (a_rect.width() < b_rect.width()));
+}
+
+// static
+bool RTreeBase::Node::CompareCenterDistanceFromParent(NodeBase* a,
+                                                      NodeBase* b) {
+  DCHECK(a->parent());
+  DCHECK_EQ(a->parent(), b->parent());
+
+  const NodeBase* p = a->parent();

[Peter Kasting, 2014/05/16 01:41:05]

Nit: You can put this above the DCHECKs and then use it in them.

[luken, 2014/05/21 20:19:36]

Done.

+
+  Vector2d p_center = CenterOfRect(p->rect());
+  Vector2d a_center = CenterOfRect(a->rect());
+  Vector2d b_center = CenterOfRect(b->rect());
+
+  // We don't bother with square roots because we are only comparing the two
+  // values for sorting purposes.
+  return (a_center - p_center).LengthSquared() <
+         (b_center - p_center).LengthSquared();
+}
+
+// static
+void RTreeBase::Node::BuildLowBounds(
+    const std::vector<NodeBase*>& vertical_sort,
+    const std::vector<NodeBase*>& horizontal_sort,
+    std::vector<Rect>* vertical_bounds,
+    std::vector<Rect>* horizontal_bounds) {
+  Rect vertical_bounds_rect;
+  vertical_bounds->reserve(vertical_sort.size());
+  for (std::vector<NodeBase*>::const_iterator i = vertical_sort.begin();
+       i != vertical_sort.end();
+       ++i) {
+    vertical_bounds_rect.Union((*i)->rect());
+    vertical_bounds->push_back(vertical_bounds_rect);
+  }
+
+  Rect horizontal_bounds_rect;
+  horizontal_bounds->reserve(horizontal_sort.size());
+  for (std::vector<NodeBase*>::const_iterator i = horizontal_sort.begin();
+       i != horizontal_sort.end();
+       ++i) {
+    horizontal_bounds_rect.Union((*i)->rect());
+    horizontal_bounds->push_back(horizontal_bounds_rect);
+  }
+}
+
+// static
+void RTreeBase::Node::BuildHighBounds(
+    const std::vector<NodeBase*>& vertical_sort,
+    const std::vector<NodeBase*>& horizontal_sort,
+    std::vector<Rect>* vertical_bounds,
+    std::vector<Rect>* horizontal_bounds) {
+  Rect vertical_bounds_rect;
+  vertical_bounds->reserve(vertical_sort.size());
+  for (std::vector<NodeBase*>::const_reverse_iterator i =
+           vertical_sort.rbegin();
+       i != vertical_sort.rend();
+       ++i) {
+    vertical_bounds_rect.Union((*i)->rect());
+    vertical_bounds->push_back(vertical_bounds_rect);
+  }
+  std::reverse(vertical_bounds->begin(), vertical_bounds->end());
+
+  Rect horizontal_bounds_rect;
+  horizontal_bounds->reserve(horizontal_sort.size());
+  for (std::vector<NodeBase*>::const_reverse_iterator i =
+           horizontal_sort.rbegin();
+       i != horizontal_sort.rend();
+       ++i) {
+    horizontal_bounds_rect.Union((*i)->rect());
+    horizontal_bounds->push_back(horizontal_bounds_rect);
+  }
+  std::reverse(horizontal_bounds->begin(), horizontal_bounds->end());
+}
+
+size_t RTreeBase::Node::ChooseSplitIndex(size_t min_children,
+                                         size_t max_children,

[Peter Kasting, 2014/05/16 01:41:05]

|max_children| is only used to compute the end index (max_children -
min_children).  The caller should pass in this end index directly; then this
function need not comment on why it's doing the subtraction, and any necessary
commenting can live solely in the caller.

[luken, 2014/05/21 20:19:36]

Done.

+                                         const std::vector<Rect>& low_bounds,
+                                         const std::vector<Rect>& high_bounds) {
+  DCHECK_EQ(low_bounds.size(), high_bounds.size());
+  DCHECK_LT(min_children, low_bounds.size());
+  DCHECK_LT(min_children, max_children - min_children);
+
+  int smallest_overlap_area =
+      UnionRects(low_bounds[min_children], high_bounds[min_children])
+          .size()
+          .GetArea();

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Personally, I'd wrap this as:

  int smallest_overlap_area =
      UnionRects(low_bounds[min_children],
                 high_bounds[min_children]).size().GetArea();

But up to you.

[luken, 2014/05/21 20:19:36]

Done.

+  int smallest_combined_area = low_bounds[min_children].size().GetArea() +
+                               high_bounds[min_children].size().GetArea();

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Again, I'd indent this 4, not even.

[luken, 2014/05/21 20:19:36]

Done.

+  size_t optimal_split_index = min_children;
+  // We stop looking for indicides at max_children - min_children to prevent
+  // choosing an index that will result in the second node having less than
+  // |min_children| after the split.
+  for (size_t p = min_children + 1; p < max_children - min_children; ++p) {
+    const int overlap_area =
+        UnionRects(low_bounds[p], high_bounds[p]).size().GetArea();
+    const int combined_area =
+        low_bounds[p].size().GetArea() + high_bounds[p].size().GetArea();
+    if ((overlap_area < smallest_overlap_area) ||
+        ((overlap_area == smallest_overlap_area) &&
+         (combined_area < smallest_combined_area))) {
+      smallest_overlap_area = overlap_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;
+}
+
+// static
+int RTreeBase::Node::SmallestMarginSum(size_t start_index,
+                                       size_t end_index,
+                                       const Rects& low_bounds,
+                                       const Rects& high_bounds) {
+  DCHECK_EQ(low_bounds.size(), high_bounds.size());
+  DCHECK_LT(start_index, low_bounds.size());
+  DCHECK_LE(start_index, end_index);
+  DCHECK_LE(end_index, low_bounds.size());
+  std::vector<Rect>::const_iterator i(low_bounds.begin() + start_index);
+  std::vector<Rect>::const_iterator j(high_bounds.begin() + start_index);
+  int smallest_sum = i->width() + i->height() + j->width() + j->height();
+  for (; i != (low_bounds.begin() + end_index); ++i, ++j) {
+    smallest_sum = std::min(
+        smallest_sum, i->width() + i->height() + j->width() + j->height());
+  }
+  return smallest_sum;
+}
+
+void RTreeBase::Node::RecomputeLocalBounds() {
+  rect_.SetRect(0, 0, 0, 0);
+  for (size_t i = 0; i < children_.size(); ++i) {
+    rect_.Union(children_[i]->rect());
+  }
+}
+
+void RTreeBase::Node::GetAllValues(Records* matches_out) const {
+  for (Nodes::const_iterator i = children_.begin(); i != children_.end(); ++i) {
+    (*i)->GetAllValues(matches_out);
+  }
+}
+
+int RTreeBase::Node::OverlapIncreaseToAdd(const Rect& rect,
+                                          size_t candidate,
+                                          const Rect& expanded_rect) const {
+  DCHECK_LT(candidate, children_.size());
+  NodeBase* candidate_node = children_[candidate];

[Peter Kasting, 2014/05/16 01:41:05]

Seems like instead of passing in |candidate|, the caller should pass in this
node directly.  This would also let us use an iterator instead of an index in
the loop below more easily.

[luken, 2014/05/21 20:19:36]

Done.

+
+  // Early-out option for when rect is contained completely within candidate.

[Peter Kasting, 2014/05/16 01:41:05]

Nit: rect -> |rect|, candidate -> the candidate

[luken, 2014/05/21 20:19:36]

Done.

+  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;
+    NodeBase* overlap_node = children_[i];
+    Rect overlap_rect = candidate_node->rect();

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Use IntersectRects() in this loop to simplify it:

  total_original_overlap += IntersectRects(
      candidate_node->rect(), overlap_node->rect()).size().GetArea();

(same for total_expanded_overlap)

[luken, 2014/05/21 20:19:36]

Done.

+    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();
+  }
+
+  return total_expanded_overlap - total_original_overlap;
+}
+
+RTreeBase::Node* RTreeBase::Node::DivideChildren(
+    const std::vector<Rect>& low_bounds,
+    const std::vector<Rect>& high_bounds,
+    const std::vector<NodeBase*>& sorted_children,
+    size_t split_index) {
+  DCHECK_EQ(low_bounds.size(), high_bounds.size());
+  DCHECK_EQ(low_bounds.size(), sorted_children.size());
+  DCHECK_LT(split_index, low_bounds.size());
+
+  Node* sibling = new Node(level_);
+  sibling->parent_ = parent_;
+  rect_ = low_bounds[split_index - 1];

[Peter Kasting, 2014/05/16 01:41:05]

Looks like this requires an assertion that split_index is greater than 0.

[luken, 2014/05/21 20:19:36]

Done.

+  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());
+
+  for (size_t i = 0; i < sibling->children_.size(); ++i) {
+    sibling->children_[i]->SetParent(sibling);
+  }
+
+  return sibling;
+}
+
+RTreeBase::Node* RTreeBase::Node::LeastOverlapIncrease(
+    const Rect& node_rect,
+    const std::vector<Rect>& expanded_rects) {
+  NodeBase* best_node = children_.front();
+  int least_overlap_increase =
+      OverlapIncreaseToAdd(node_rect, 0, expanded_rects[0]);
+  for (size_t i = 1; i < children_.size(); ++i) {
+    int overlap_increase =
+        OverlapIncreaseToAdd(node_rect, i, expanded_rects[i]);
+    if (overlap_increase < least_overlap_increase) {
+      least_overlap_increase = overlap_increase;
+      best_node = children_[i];
+    } else if (overlap_increase == least_overlap_increase) {
+      // 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;
+
+      best_node = NULL;
+    }
+  }
+
+  // Ensure that our children are always Nodes and not Records.
+  DCHECK_GE(level_, 1);
+  return static_cast<Node*>(best_node);
+}
+
+RTreeBase::Node* RTreeBase::Node::LeastAreaEnlargement(
+    const Rect& node_rect,
+    const std::vector<Rect>& expanded_rects) {
+  DCHECK(!children_.empty());
+  NodeBase* best_node = children_.front();
+  int least_area_enlargement =
+      expanded_rects[0].size().GetArea() - best_node->rect().size().GetArea();

[Peter Kasting, 2014/05/16 01:41:05]

Seems like we also should have an assertion that |expanded_rects| has the same
size as |children_|?

[luken, 2014/05/21 20:19:36]

Done.

+  for (size_t i = 1; i < children_.size(); ++i) {
+    NodeBase* candidate_node = children_[i];
+    int area_change = expanded_rects[i].size().GetArea() -
+                      candidate_node->rect().size().GetArea();
+    DCHECK_GE(area_change, 0);
+    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 the entry with the least area.
+      DCHECK(best_node);

[Peter Kasting, 2014/05/16 01:41:05]

This DCHECK seems unnecessary since |best_node| never takes on a NULL value.

Given that, you could combine the conditional below with the one above.

[luken, 2014/05/21 20:19:36]

Done.

+      if (candidate_node->rect().size().GetArea() <
+          best_node->rect().size().GetArea()) {
+        best_node = candidate_node;
+      }
+    }
+  }
+
+  // Ensure that our children are always Nodes and not Records.
+  DCHECK_GE(level_, 1);
+  return static_cast<Node*>(best_node);
+}
+

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Two blank lines here, if you're using two blank lines similarly elsewhere.

[luken, 2014/05/21 20:19:36]

Done.

+// RTree ----------------------------------------------------------------------

[Peter Kasting, 2014/05/16 01:41:05]

RTreeBase

[luken, 2014/05/21 20:19:36]

Done.

+
+RTreeBase::RTreeBase(size_t min_children, size_t max_children)
+    : root_(new Node()),
+      min_children_(min_children),
+      max_children_(max_children) {
+  // R-Trees require min_children >= 2

[Peter Kasting, 2014/05/16 01:41:05]

These two comments merely duplicate the code; remove them.

[luken, 2014/05/21 20:19:36]

Done.

+  DCHECK_GE(min_children_, 2U);
+  // R-Trees also require min_children <= max_children / 2
+  DCHECK_LE(min_children_, max_children_ / 2U);
+}
+
+RTreeBase::~RTreeBase() {
+}
+
+void RTreeBase::InsertNode(NodeBase* 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);
+  NodeBase* insert_node = node;
+  Node* insert_parent = static_cast<Node*>(parent);
+  NodeBase* needs_bounds_recomputed = insert_parent->parent();
+  ScopedVector<NodeBase> reinserts;

[Peter Kasting, 2014/05/16 01:41:05]

Use Node::Nodes as the type here to match the type used in the declaration of
the function you call below.

[luken, 2014/05/21 20:19:36]

Done.

+  // Attempt to insert the Node, if this overflows the Node we must handle it.
+  while (insert_parent &&
+         insert_parent->AddChild(scoped_ptr<NodeBase>(insert_node)) >

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Consider using make_scoped_ptr(insert_node) to avoid listing the type
explicitly (2 places)

[luken, 2014/05/21 20:19:36]

Done.

+             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 = static_cast<Node*>(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

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Trailing period.

[luken, 2014/05/21 20:19:36]

Done.

+  if (!insert_parent && insert_node) {
+    Node* old_root = root_.release();
+    root_ = old_root->MakeParent();

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Could just be

    root_ = root_.release()->MakeParent();

[luken, 2014/05/21 20:19:36]

Done.

+    root_->AddChild(scoped_ptr<NodeBase>(insert_node));
+  }
+
+  // Recompute bounds along insertion path.
+  if (needs_bounds_recomputed) {
+    needs_bounds_recomputed->RecomputeBoundsUpToRoot();
+  }
+
+  // Complete re-inserts, if any.
+  for (size_t i = 0; i < reinserts.size(); ++i) {

[Peter Kasting, 2014/05/16 01:41:05]

Nit: Prefer iterators to indexes where possible.

[luken, 2014/05/21 20:19:36]

Done.

+    InsertNode(reinserts[i], highest_reinsert_level);
+  }
+
+  // Clear out reinserts without deleting any of the children, as they have been
+  // re-inserted into the tree.
+  reinserts.weak_clear();
+}
+
+void RTreeBase::RemoveNode(NodeBase* node) {
+  // We need to remove this node from its parent.
+  Node* parent = static_cast<Node*>(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);

[Peter Kasting, 2014/05/16 01:41:05]

Nit: (expected, actual)

[luken, 2014/05/21 20:19:36]

Done.

+  ScopedVector<NodeBase> orphans;
+  NodeBase* 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) {
+    size_t children_remaining = parent->RemoveChild(child, &orphans);
+    if (child != node)
+      delete child;
+
+    if (children_remaining >= min_children_)
+      break;
+
+    child = parent;
+    parent = static_cast<Node*>(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->RecomputeBoundsUpToRoot();
+  }
+
+  // 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);
+  }
+
+  // Clear out the orphans list without deleting any of the children, as they
+  // have been re-inserted into the tree.
+  orphans.weak_clear();
+}
+
+}  // namespace gfx