readability review for luken

ui/gfx/geometry/r_tree.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.h"
 
 #include <algorithm>
 #include <limits>
 
 #include "base/logging.h"
 
 namespace {

[Peter Kasting, 2014/05/02 18:04:57]

Nit: Totally optional, but in files that include definitions of multiple classes
and/or helpers, I like to divide the file akin to:

... blah ...


// Classname ---------------------- (out to 79 columns)

Classname::blah...

Generally, with two blank lines above the divider and one below, and using a
divider called "Helpers" for helper functions and file-scoped data.  See e.g.
http://src.chromium.org/viewvc/chrome/trunk/src/chrome/browser/google/google_...
.

IMO, this makes it a bit easier to scroll through the file to the section you
wanted.

[luken, 2014/05/08 00:00:08]

Done.

 
 // Returns the center coordinates of the given rectangle.

[Peter Kasting, 2014/05/02 18:04:57]

Nit: Comment not necessary (we can tell this from the function name)

[luken, 2014/05/08 00:00:08]

Done.

 gfx::Vector2d CenterOfRect(const gfx::Rect& rect) {

[Peter Kasting, 2014/05/02 18:04:57]

It seems odd that this returns a vector instead of a point.  I might expect
callers to make that conversion if they desired it.  At least this deserves a
comment.

[luken, 2014/05/08 00:00:08]

Done.

   return rect.OffsetFromOrigin() +
          gfx::Vector2d(rect.width() / 2, rect.height() / 2);
 }
+
 }
 
 namespace gfx {
 
 RTree::Node::Node(int level) : level_(level), parent_(NULL), key_(0) {
 }
 
 RTree::Node::Node(const Rect& rect, intptr_t key)
     : rect_(rect), level_(-1), parent_(NULL), key_(key) {

[Peter Kasting, 2014/05/02 18:04:57]

From
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Constr...
:

"Constructor initializer lists can be all on one line or with subsequent lines
indented four spaces."

Given the examples at that link, my reading is that if your initializer list
doesn't fit on the same line as the function name, you should have one
initializer per line.

[luken, 2014/05/08 00:00:08]

clang format wants to move them all back to one line. I will break them up back
to individual lines.

 }
 
 RTree::Node::~Node() {
   Clear();
 }
 
 void RTree::Node::Clear() {
   // Iterate through children and delete them all.

[Peter Kasting, 2014/05/02 18:04:57]

Documenting what ScopedVector::clear() does doesn't seem necessary.

[luken, 2014/05/08 00:00:08]

Done.

   children_.clear();
   key_ = 0;
 }
 
 void RTree::Node::Query(const Rect& query_rect,
                         base::hash_set<intptr_t>* matches_out) const {

[Peter Kasting, 2014/05/02 18:04:57]

You should probably add to the comment in the header a note about how this
appends to |matches_out| instead of overwriting it, so it can be called
recursively; otherwise, a reader would normally expect the outparam to be reset
on exit.

[luken, 2014/05/08 00:00:08]

Done.

   // Check own bounding box for intersection, can cull all children if no
   // intersection.
   if (!rect_.Intersects(query_rect)) {

[Peter Kasting, 2014/05/02 18:04:57]

This style is legal, but in Chrome code we normally omit braces when the style
guide allows it (i.e. when the body of a loop or conditional is one physical
line).

Ignore this if there is a consistent standard in ui/gfx/geometry (or ui/gfx or
whatever) to always use braces -- more important to be consistent with your
module than with Chrome as a whole (though ideally the two wouldn't diverge).

[luken, 2014/05/08 00:00:08]

Done.

     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);

[Peter Kasting, 2014/05/02 18:04:57]

Nit: (expected, actual) for DCHECK_EQ and DCHECK_NE (this also applies to CHECK,
EXPECT, and ASSERT; notably, it does not apply to inequalities such as
xxx_GT().)  Multiple places in this file.

However, this is a bit of an odd place for this DCHECK.  I would expect to see
it in code that set or at least depended on the level, but here it seems
incidental -- nothing cares what |level_| is.

[luken, 2014/05/08 00:00:08]

I will remove needless DCHECKs and fix ordering on the ones that remain.

     matches_out->insert(key_);
   } else {
     for (size_t i = 0; i < children_.size(); ++i) {

[Peter Kasting, 2014/05/02 18:04:57]

Prefer using iterators over indexes (primarily in loops) where it's feasible to
do so.

[luken, 2014/05/08 00:00:08]

Done.

       // Sanity-check our children.
       Node* node = children_[i];

[Peter Kasting, 2014/05/02 18:04:57]

This really should be a const Node* (or, if using iterators, we should use
const_iterator).

[luken, 2014/05/08 00:00:08]

Done.

       DCHECK_EQ(node->parent_, this);
       DCHECK_EQ(level_ - 1, node->level_);

[Peter Kasting, 2014/05/02 18:04:57]

Again, these first two checks don't seem to have anything to do with the
functionality or return value of this function, and probably shouldn't be here.

[luken, 2014/05/08 00:00:08]

Done.

       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,
                                          ScopedVector<Node>* nodes) {
   DCHECK_GE(children_.size(), number_to_remove);

[Peter Kasting, 2014/05/02 18:04:57]

For DCHECK_GE() and similar, write in "natural" order; you're trying to check if
(number_to_remove <= children_.size()), so write DCHECK_LE(number_to_remove,
children_.size()).  This makes the expression easier to read (it's easy to get
mentally turned around trying to read a flipped expression).

[luken, 2014/05/08 00:00:08]

Done.

 
   // Sort our children by their distance from the center of their rectangles to
   // the center of our bounding rectangle.

[Peter Kasting, 2014/05/02 18:04:57]

Nit: This comment (and others below, see subsequent comment) simply restates the
code and should thus be avoided.  Write comments about the overall function of
larger blocks of code, or pointing out critical details or rationale.  If none
are necessary, omit the comment.

[luken, 2014/05/08 00:00:08]

Done.

   std::sort(children_.begin(),
             children_.end(),
             &RTree::Node::CompareCenterDistanceFromParent);
 
   // Add lowest distance nodes from our children list to the returned vector.

[Peter Kasting, 2014/05/02 18:04:57]

Nit: If you say "Move the lowest-distance children to the returned vector.", you
can omit the comment below.

This would be preferred anyway, because it describes the function of the code
here at a higher level, instead of having a pair of comments that restate the
code.

Even better might be something like:

  // Move the children closest to the center of our bounding rectangle onto
  // |nodes|.
  std::sort(...);
  nodes->insert(...);
  children_.weak_erase(...);

This is still a short enough block of code that considering it as one idea for
the purpose of commenting is reasonable.

[luken, 2014/05/08 00:00:08]

Done.

   nodes->insert(
       nodes->end(), children_.begin(), children_.begin() + number_to_remove);

[Peter Kasting, 2014/05/02 18:04:57]

Nit: This is clang-format's preferred formatting here, but personally, I prefer

  nodes->insert(nodes->end(), children_.begin(),
                children_.begin() + number_to_remove);

So do some other reviewers; see http://crbug.com/350851 for more discussion on
this issue.

Either style is legal.

[luken, 2014/05/08 00:00:08]

Done.

   // 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, ScopedVector<Node>* orphans) {
   // Should actually be one of our children.
   DCHECK_EQ(child_node->parent_, this);
 
   // Add children of child_node to the orphans vector.

[Peter Kasting, 2014/05/02 18:04:57]

Nit: Same comments as above... I won't make notes on further instances of this
sort of thing.

[luken, 2014/05/08 00:00:08]

Done.

   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;

[Peter Kasting, 2014/05/02 18:04:57]

Nit: Again, using an iterator for the loop above would be preferred, and would
also save you the need to construct one here (you'd already have it directly).

[luken, 2014/05/08 00:00:08]

Done.

       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();
 }
 
 scoped_ptr<RTree::Node> RTree::Node::RemoveAndReturnLastChild() {
   if (!children_.size())

[Peter Kasting, 2014/05/02 18:04:57]

Use empty() instead of !size().

[luken, 2014/05/08 00:00:08]

Done.

     return scoped_ptr<Node>();
 
   scoped_ptr<Node> last_child(children_[children_.size() - 1]);

[Peter Kasting, 2014/05/02 18:04:57]

Use .back() instead of [children_.size() - 1].

[luken, 2014/05/08 00:00:08]

Done.

   DCHECK_EQ(last_child->parent_, this);

[Peter Kasting, 2014/05/02 18:04:57]

This DCHECK is arguable -- at least it's not totally unrelated to what the
function is doing, but we don't actually look at or care about the parent value,
so I'd still omit it.

[luken, 2014/05/08 00:00:08]

Done.

   children_.weak_erase(children_.begin() + children_.size() - 1);

[Peter Kasting, 2014/05/02 18:04:57]

Use children_.end() - 1 instead of children_.begin() + children_.size() - 1.

[luken, 2014/05/08 00:00:08]

Done.

   // Invalidate parent, as this child may even become the new root.

[Peter Kasting, 2014/05/02 18:04:57]

I'd have expected the |parent_| field to get cleared anyway, so this comment
actually confused me, since it implied that, if the child wouldn't become the
root, clearing the field wouldn't be necessary.  (Technically it probably
wouldn't, but I had to think about why.)  It seems like it'd be better to keep
nodes in a consistent state by default, and only comment when we're doing
something other than that.

[luken, 2014/05/08 00:00:08]

Done.

   last_child->parent_ = NULL;
   return last_child.Pass();
 }
 
 // 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_);

[Peter Kasting, 2014/05/02 18:04:57]

The second DCHECK seems sufficient.  This method doesn't care about keys, so it
shouldn't check whether the exist.

[luken, 2014/05/08 00:00:08]

Done.

   DCHECK(level_ >= 0);

[Peter Kasting, 2014/05/02 18:04:57]

DCHECK_GE

[luken, 2014/05/08 00:00:08]

Done.

   DCHECK(node);

[Peter Kasting, 2014/05/02 18:04:57]

Nit: Consider putting this DCHECK above the comment above, both to make it clear
it isn't related to that comment, and because I'd sort of expect to validate the
function arguments before validating local state (but maybe that latter is just
me).

[luken, 2014/05/08 00:00:08]

Done.

 
   // If we are a parent of nodes on the provided node level, we are done.

[Peter Kasting, 2014/05/02 18:04:57]

What if we're _at_ the node's level, or below it?  I don't think I fully
understand the algorithm here, but wouldn't that break things?  It seems like
this function maybe expects to be called higher in the tree than |node|.

[luken, 2014/05/08 00:00:08]

It does, I corrected the DCHECK above to account, and fixed the comment.

   if (level_ == node->level_ + 1)
     return this;
 
   // We are an internal node, and thus guaranteed to have children.
   DCHECK_GT(children_.size(), 0U);

[Peter Kasting, 2014/05/02 18:04:57]

Use !empty().  But really, I don't see how this function would break if this
DCHECK failed, so once again, I'd remove it.

[luken, 2014/05/08 00:00:08]

Done.

 
   // Iterate over all children to find best candidate for insertion.

[Peter Kasting, 2014/05/02 18:04:57]

This method doesn't iterate, so this comment doesn't belong.

[luken, 2014/05/08 00:00:08]

Done.

   Node* best_candidate = NULL;

[Peter Kasting, 2014/05/02 18:04:57]

From
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Local_...
:

"...declare [variables]... as close to the first use as possible."

[luken, 2014/05/08 00:00:08]

Done.

 
   // Precompute a vector of expanded rects, used both by LeastOverlapIncrease
   // and LeastAreaEnlargement.
   std::vector<Rect> expanded_rects;
   expanded_rects.reserve(children_.size());
   for (size_t i = 0; i < children_.size(); ++i) {
     Rect expanded_rect(node->rect_);
     expanded_rect.Union(children_[i]->rect_);
     expanded_rects.push_back(expanded_rect);

[Peter Kasting, 2014/05/02 18:04:57]

This can be simplified using the helpers in ui/gfx/geometry/rect.h:

  expanded_rects.push_back(UnionRects(node->rect_, children_[i]->rect_));

There are many other places in this file where UnionRects() or IntersectRects()
can save you a temp and a few lines of code.

[luken, 2014/05/08 00:00:08]

Done.

   }
 
   // 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);
 }
 
 RTree::Node* RTree::Node::LeastAreaEnlargement(

[Peter Kasting, 2014/05/02 18:04:57]

Keep .cc function definition order the same as the .h declaration order.

     const Rect& node_rect,
     const std::vector<Rect>& expanded_rects) {
   Node* best_node = NULL;
   int least_area_enlargement = std::numeric_limits<int>::max();

[Peter Kasting, 2014/05/02 18:04:57]

Nit: I suggest this:

  Node* best_node = children_.front();
  int least_area_enlargement = expanded_rects[i].size().GetArea() -
      candidate_node->rect_.size().GetArea();
  for (Children::const_iterator i(children_.begin() + 1); i != children_.end();
       ++i) {
    ...

This makes it clearer you always want a candidate node.  It also avoids
comparing anything to INT_MAX, which should work, but always makes me
uncomfortable ("what if the value of the subtraction was actually INT_MAX?").

Similar considerations are in play many other places in this file where I give
similar refactoring suggestions.

(Random annoyance: How come we have to call Rect::size().GetArea() instead of
just Rect::GetArea()?  I think of area as a property of Rects directly as well
as sizes... grr.)

[luken, 2014/05/08 00:00:08]

I got rid of the INT_MAX. I'd prefer to keep with an index because I am
iterating both through |children_| and |expanded_rects| at the same time, unless
you think it's better to maintain two iterators? I agree with you that the
size().GetArea() pattern is counter-intuitive.

[Peter Kasting, 2014/05/08 18:08:21]

Ah, sorry, I think I missed that.  Using an index is OK.

[luken, 2014/05/14 00:12:04]

Done.

   for (size_t i = 0; i < children_.size(); ++i) {
     Node* candidate_node = children_[i];
     int area_change = expanded_rects[i].size().GetArea() -

[Peter Kasting, 2014/05/02 18:04:57]

Can area change be negative?  (I assume not.)  Maybe this should be DCHECKed?

[luken, 2014/05/08 00:00:08]

You are correct, by definition of Union area change cannot be negative, as it is
impossible for Union to decrease the area of a rectangle. I added a DCHECK.

                       candidate_node->rect_.size().GetArea();

[Peter Kasting, 2014/05/02 18:04:57]

Nit: I believe this should be indented 4 rather than even, though the style
guide is unclear.

[luken, 2014/05/08 00:00:08]

Done.

     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.

[Peter Kasting, 2014/05/02 18:04:57]

Nit Add articles ("the" two places)

[luken, 2014/05/08 00:00:08]

Done.

       DCHECK(best_node);
       if (candidate_node->rect_.size().GetArea() <
           best_node->rect_.size().GetArea()) {
         best_node = candidate_node;
       }
     }
   }
 
   DCHECK(best_node);

[Peter Kasting, 2014/05/02 18:04:57]

If |children_| is empty, we'll fail this.  It seems worth putting a DCHECK about
this atop the function to make it clearer that's a precondition.

[luken, 2014/05/08 00:00:08]

Done.

   return best_node;
 }
 
 RTree::Node* RTree::Node::LeastOverlapIncrease(
     const Rect& node_rect,
     const std::vector<Rect>& expanded_rects) {
   Node* best_node = NULL;
   bool has_tied_node = false;

[Peter Kasting, 2014/05/02 18:04:57]

You don't actually need this if you follow the same pattern I suggested in the
previous function, and initialize |best_node| and |least_overlap_increase|.  At
that point, you can indicate a tie directly by just setting |best_node| to NULL.
 This also removes the need for the conditional at the end of the function.

[luken, 2014/05/08 00:00:08]

Done.

   int least_overlap_increase = std::numeric_limits<int>::max();
   for (size_t i = 0; 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];
       has_tied_node = false;
     } else if (overlap_increase == least_overlap_increase) {
       has_tied_node = true;

[Peter Kasting, 2014/05/02 18:04:57]

Nit: This can go below the conditional (more efficient, not that it actually
matters)

[luken, 2014/05/08 00:00:08]

Done.

       // 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 (has_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];

[Peter Kasting, 2014/05/02 18:04:57]

This definitely deserves a DCHECK that |candidate| is within children_.size().

[luken, 2014/05/08 00:00:08]

Done.

 
   // 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.

[Peter Kasting, 2014/05/02 18:04:57]

This comment doesn't seem to be describing the code.  The lines below neither
compare nor update anything.

[luken, 2014/05/08 00:00:08]

Done.

   int overlap_increase = total_expanded_overlap - total_original_overlap;

[Peter Kasting, 2014/05/02 18:04:57]

Nit: Just return this directly, don't create a temp to return on the next line.

[luken, 2014/05/14 00:12:04]

Done.

   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.

[Peter Kasting, 2014/05/02 18:04:57]

It's actually one less.

[luken, 2014/05/08 00:00:08]

Done.

   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.

[Peter Kasting, 2014/05/02 18:04:57]

Since record nodes have no children, this DCHECK is unnecessary; the subsequent
one will catch it.

[luken, 2014/05/08 00:00:08]

Done.

   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

[Peter Kasting, 2014/05/02 18:04:57]

Nit: splitting -> we should split

[luken, 2014/05/08 00:00:08]

Done.

   // 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.

[Peter Kasting, 2014/05/02 18:04:57]

Nit: Try to avoid duplicating commentary here and on function declarations -- if
BuildLowBounds() already describes what it does in the header, don't repeat the
same information here.

[luken, 2014/05/08 00:00:08]

Done.

   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;
@@ skipping 19 matching lines @@
         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);
   }

[Peter Kasting, 2014/05/02 18:04:57]

I suggest the alternate formulation below.

Not only is this shorter, it makes it more obvious to the reader that what
you've written as two codepaths do exactly the same thing, just with different
variables.  (This also prevents us from e.g. writing a change to one arm in the
future and then accidentally omitting it on the other arm.)

  const std::vector<Rect>& low_bounds(
      is_vertical_split ? low_vertical_bounds : low_horizontal_bounds);
  const std::vector<Rect>& high_bounds(
      is_vertical_split ? high_vertical_bounds : high_horizontal_bounds);
  size_t split_index =
      ChooseSplitIndex(min_children, max_children, low_bounds, high_bounds);
  return DivideChildren(low_bounds, high_bounds,
                        is_vertical_split ? vertical_sort : horizontal_sort,
                        split_index);

[luken, 2014/05/08 00:00:08]

Done.

 
   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) {

[Peter Kasting, 2014/05/02 18:04:57]

Nit: I would split this into two loops (horizontal and vertical).  This would:
* Allow you to use iterators
* Make clear that the two sets of calculations are independent
* Eliminate the need for the DCHECK at top

[luken, 2014/05/08 00:00:08]

Done.

     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) {

[Peter Kasting, 2014/05/02 18:04:57]

Nit: I would again use two loops.  For maximum safety and clarity, I might also
use a reverse_iterator to traverse the input, along with "push back, then
reverse at end" on the output vector (changing the resize() call to a
reserve()).  This shouldn't really be any less efficient than what you're doing,
I don't believe (since the resize() call constructs all the entries, and then
you copy over them in the loop).  It's also possible to use the reverse iterator
method and calculate an index from it to write into the output vector, but it
looks a bit ugly ("i.base() - 1 - xxx_sort.begin()").

[luken, 2014/05/08 00:00:08]

Done.

     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) {

[Peter Kasting, 2014/05/02 18:04:57]

If you wrote a helper function,

int SmallestMarginSum(const std::vector<Rect>& low_bounds,
                      const std::vector<Rect>& high_bounds,
                      size_t start_index,
                      size_t end_index) {
  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;
}

Then this entire function could be eliminated, and the lone caller in Split()
changed to:

  size_t end_index = max_children - min_children;
  bool is_vertical_split =
      SmallestMarginSum(low_horizontal_bounds, high_horizontal_bounds,
                        min_children, end_index) <
      SmallestMarginSum(low_vertical_bounds, high_vertical_bounds,
                        min_children, end_index);

[luken, 2014/05/08 00:00:08]

Done.

   // Examine the possible distributions of each sorted list by iterating through
   // valid split points p, min_children <= p <= max_children - min_children, and

[Peter Kasting, 2014/05/02 18:04:57]

This looks weird to me.  I would think "max_children - min_children" would
represent the number of children to examine, not the max child index, so we
would loop from min_children <= p < max_children.  (Also, note that the comment
you wrote says "<=" where the loop below does "<".  I assume "<" is correct.) 
Am I wrong?

[luken, 2014/05/08 00:00:08]

This code is now deprecated, but we really do need to stop looking at
max_children - min_children, because no node can have fewer than min_children
nodes.

[Peter Kasting, 2014/05/08 18:08:21]

OK, so the node we're splitting is assumed to have exactly |max_children| nodes
right now?  Maybe this value should have been named |current_children| or
something, and then some comment like the one you give above added, to make this
clearer.

Though if this is deprecated, it's obviously not important...

[luken, 2014/05/14 00:12:04]

It's assumed to have max_children + 1 nodes, but yes this code is deprecated per
your suggestion to refactor it to SmallestMarginSum.

   // 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() +
@@ skipping 11 matching lines @@
   // 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) {

[Peter Kasting, 2014/05/02 18:04:57]

I suspect you want the following DCHECKs here:

  DCHECK_EQ(low_bounds.size(), high_bounds.size());
  DCHECK_EQ(low_bounds.size(), sorted_children.size());
  DCHECK_LT(split_index, low_bounds.size());

Note that these are actually more strenuous than the function requires, but I
think they match how your callers use this function, and the precise DCHECKs the
code below actually requires are slightly more verbose and confusing than the
ones listed above.

[luken, 2014/05/08 00:00:08]

Done.

   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

[Peter Kasting, 2014/05/02 18:04:57]

Nit: In general, if you're writing a comment about a following block of code, I
suggest a blank line above said comment.

[luken, 2014/05/08 00:00:08]

Done.

   // 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.

[Peter Kasting, 2014/05/02 18:04:57]

Remove this comment; the code is clear enough.

[luken, 2014/05/08 00:00:08]

Done.

   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.

[Peter Kasting, 2014/05/02 18:04:57]

Remove this comment, you say something similar in the .h.

As earlier, this deserves an added comment about how it appends to the outparam
instead of overwriting.

[luken, 2014/05/08 00:00:08]

Done.

 void RTree::Node::GetAllValues(base::hash_set<intptr_t>* matches_out) const {
   if (key_) {
     DCHECK_EQ(level_, -1);

[Peter Kasting, 2014/05/02 18:04:57]

Again, this is not necessary.

[luken, 2014/05/08 00:00:08]

Done.

     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_));

[Peter Kasting, 2014/05/02 18:04:57]

None of these three DCHECKs seems to have anything to do with this function, so
they should probably not be here.

[luken, 2014/05/08 00:00:08]

Done.

       node->GetAllValues(matches_out);
     }
   }
 }
 
 // static
 bool RTree::Node::CompareVertical(Node* a, Node* b) {
   // Sort nodes by top coordinate first.

[Peter Kasting, 2014/05/02 18:04:57]

These comments pretty much duplicate the code.  It would probably be better to
say something like:

  // Sort nodes primarily by increasing y coordinates, and secondarily by
  // increasing height.

This obviates the need for the comment below.

Because this comment describes the whole function, it probably belongs in the
.h.

[luken, 2014/05/08 00:00:08]

Done.

   if (a->rect_.y() < b->rect_.y()) {
     return true;
   } else if (a->rect_.y() == b->rect_.y()) {

[Peter Kasting, 2014/05/02 18:04:57]

From http://dev.chromium.org/developers/coding-style :

"Don't use else after return"

[luken, 2014/05/08 00:00:08]

Done.

     // If top coordinate is equal, sort by lowest bottom coordinate.
     return a->rect_.height() < b->rect_.height();
   }
   return false;

[Peter Kasting, 2014/05/02 18:04:57]

Nit: The second half of this function could just be:

  return (a->rect_.y() == b->rect_.y()) &&
      (a->rect_.height() < b->rect_.height());

In fact the whole function could just be:

  return (a->rect_.y() < b->rect_.y()) ||
      ((a->rect_.y() == b->rect_.y()) &&
       (a->rect_.height() < b->rect_.height()));

Which, combined with the modified comment proposed above, is still clear, and
shorter.

[luken, 2014/05/08 00:00:08]

Done.

 }
 
 // static
 bool RTree::Node::CompareHorizontal(Node* a, Node* b) {

[Peter Kasting, 2014/05/02 18:04:57]

Similar comments apply to this function.

[luken, 2014/05/08 00:00:08]

Done.

   // 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.

[Peter Kasting, 2014/05/02 18:04:57]

This second sentence belongs in the code, directly above where you actually call
LengthSquared().

The first sentence, then, is another case of describing the whole function, and
thus belonging in the header.

[luken, 2014/05/08 00:00:08]

Done.

 // static
 bool RTree::Node::CompareCenterDistanceFromParent(Node* a, Node* b) {
   // This comparison assumes the nodes have the same parent.

[Peter Kasting, 2014/05/02 18:04:57]

All four of the comments here simply duplicate the code, and should be removed.

[luken, 2014/05/08 00:00:08]

Done.

   DCHECK(a->parent_ == b->parent_);

[Peter Kasting, 2014/05/02 18:04:57]

Nit: DCHECK_EQ

[luken, 2014/05/08 00:00:08]

Done.

   // This comparison requires that each node have a parent.
   DCHECK(a->parent_);

[Peter Kasting, 2014/05/02 18:04:57]

Tiny nit: I suggest putting this DCHECK first (so they read like "|a| has a
parent, and |b| has the same parent")

[luken, 2014/05/08 00:00:08]

Done.

   // Sanity-check level_ of these nodes is equal.
   DCHECK_EQ(a->level_, b->level_);

[Peter Kasting, 2014/05/02 18:04:57]

This function doesn't require either of these next two DCHECKs, so they should
probably be removed.

[luken, 2014/05/08 00:00:08]

Done.

   // Also the parent of the nodes should have level one higher.
   DCHECK_EQ(a->level_, a->parent_->level_ - 1);
 
   // Find the parent.

[Peter Kasting, 2014/05/02 18:04:57]

Comment duplicates the code, remove it.

[luken, 2014/05/08 00:00:08]

Done.

   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) {

[Peter Kasting, 2014/05/02 18:04:57]

Again, this function probably deserves DCHECKs like:

  DCHECK_EQ(low_bounds.size(), high_bounds.size());
  DCHECK_LT(min_children, low_bounds.size());
  DCHECK_LT(min_children, max_children - min_children);

And again, the choice of "max_children - min_children" as an end index instead
of an element count looks suspicious.

Nit: It seems a little weird to me that ChooseSplitIndex() and ChooseSplitAxis()
differ on whether the vectors or the child indexes come first.

[luken, 2014/05/08 00:00:08]

DCHECKs added.

Index is correct. I'll add a comment here because I'm sure you're not the only
one thinking those indices are a bug.

Arguments nit solved by deprecation of the latter function :).

   int smallest_overlap_area = std::numeric_limits<int>::max();

[Peter Kasting, 2014/05/02 18:04:57]

This whole block can be simplified:

  int smallest_overlap_area = UnionRects(
      low_bounds[min_children], high_bounds[min_children]).size().GetArea();
  int smallest_combined_area = low_bounds[min_children].size().GetArea() +
      high_bounds[min_children].size().GetArea();
  size_t optimal_split_index = 0;
  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;
    }
  }

[luken, 2014/05/08 00:00:08]

Done, although my version only computed combined_area in the event of ties.

   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.

[Peter Kasting, 2014/05/02 18:04:57]

This comment isn't necessary.

[luken, 2014/05/08 00:00:08]

Done.

   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) {
@@ skipping 177 matching lines @@
     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