Issue 269513002: readability review for luken

luken

6 years, 7 months ago (2014-04-30 21:36:01 UTC) #1

Peter Kasting

FYI, the original change here is pretty long (1910 lines including tests in the .h ...

6 years, 7 months ago (2014-04-30 23:09:21 UTC) #3

luken

Thanks for taking a look at this. Would it make sense to limit the scope ...

6 years, 7 months ago (2014-04-30 23:20:18 UTC) #4

Peter Kasting

On 2014/04/30 23:20:18, luken wrote: > Would it make sense to limit the scope to ...

6 years, 7 months ago (2014-04-30 23:21:14 UTC) #5

Peter Kasting

Thanks for participating in the readability process, especially as a Chrome contributor, where the Google ...

6 years, 7 months ago (2014-05-02 18:04:57 UTC) #6

Thanks for participating in the readability process, especially as a Chrome
contributor, where the Google "CL approval until you get readability" process is
not enforced.  Hopefully the comments below are useful, even if the number of
them is initially daunting.  Beyond just enforcing the style guide, readability
is also about suggesting the clearest, safest, and/or shortest ways to write
class APIs and implement pieces of functions.  Ultimately, the goal of this
process is to help you think through every piece of code you write, looking for
the absolute best possible representation.  This takes more time, but the
benefit to the Chrome codebase is worth it.

I did not review the unittests yet.  Before I review them, I suggest splitting
the node tests and the tree tests into two different test cases.  If you need to
use the same helper functions for both, you can avoid duplicating the fixture
class as follows:

class RTreeTest : public ::testing::Test {
  ...
};

typedef RTreeTest RTreeNodeTest;

// Probably should put Node tests first, since presumably the
// full tree tests are built atop working Node code
TEST_F(RTreeNodeTest, Foo) {
  ...
}

TEST_F(RTreeTest, Bar) {
  ...
}

You can also use inheritance in your test fixture classes if one test case needs
a superset of the helpers from the other case.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc
File ui/gfx/geometry/r_tree.cc (right):

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:12: namespace {
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:14: // Returns the center coordinates of the given
rectangle.
Nit: Comment not necessary (we can tell this from the function name)

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:15: gfx::Vector2d CenterOfRect(const gfx::Rect& rect)
{
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:28: : rect_(rect), level_(-1), parent_(NULL),
key_(key) {
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:36: // Iterate through children and delete them all.
Documenting what ScopedVector::clear() does doesn't seem necessary.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:42: base::hash_set<intptr_t>* matches_out) const {
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:45: if (!rect_.Intersects(query_rect)) {
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).

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:60: DCHECK_EQ(level_, -1);
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:63: for (size_t i = 0; i < children_.size(); ++i) {
Prefer using iterators over indexes (primarily in loops) where it's feasible to
do so.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:65: Node* node = children_[i];
This really should be a const Node* (or, if using iterators, we should use
const_iterator).

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:67: DCHECK_EQ(level_ - 1, node->level_);
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:84: DCHECK_GE(children_.size(), number_to_remove);
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).

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:87: // the center of our bounding rectangle.
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:92: // Add lowest distance nodes from our children
list to the returned vector.
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:94: nodes->end(), children_.begin(), children_.begin()
+ number_to_remove);
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:103: // Add children of child_node to the orphans
vector.
Nit: Same comments as above... I won't make notes on further instances of this
sort of thing.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:114: child_it = children_.begin() + i;
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).

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:127: if (!children_.size())
Use empty() instead of !size().

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:130: scoped_ptr<Node>
last_child(children_[children_.size() - 1]);
Use .back() instead of [children_.size() - 1].

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:131: DCHECK_EQ(last_child->parent_, this);
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:132: children_.weak_erase(children_.begin() +
children_.size() - 1);
Use children_.end() - 1 instead of children_.begin() + children_.size() - 1.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:133: // Invalidate parent, as this child may even
become the new root.
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:141: DCHECK(!key_);
The second DCHECK seems sufficient.  This method doesn't care about keys, so it
shouldn't check whether the exist.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:142: DCHECK(level_ >= 0);
DCHECK_GE

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:143: DCHECK(node);
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).

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:145: // If we are a parent of nodes on the provided
node level, we are done.
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|.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:150: DCHECK_GT(children_.size(), 0U);
Use !empty().  But really, I don't see how this function would break if this
DCHECK failed, so once again, I'd remove it.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:152: // Iterate over all children to find best
candidate for insertion.
This method doesn't iterate, so this comment doesn't belong.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:153: Node* best_candidate = NULL;
From
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Local_...
:

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

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:162: expanded_rects.push_back(expanded_rect);
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:181: RTree::Node* RTree::Node::LeastAreaEnlargement(
Keep .cc function definition order the same as the .h declaration order.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:185: int least_area_enlargement =
std::numeric_limits<int>::max();
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.)

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:188: int area_change =
expanded_rects[i].size().GetArea() -
Can area change be negative?  (I assume not.)  Maybe this should be DCHECKed?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:189: candidate_node->rect_.size().GetArea();
Nit: I believe this should be indented 4 rather than even, though the style
guide is unclear.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:194: // Ties are broken by choosing entry with least
area.
Nit Add articles ("the" two places)

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:203: DCHECK(best_node);
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:211: bool has_tied_node = false;
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:221: has_tied_node = true;
Nit: This can go below the conditional (more efficient, not that it actually
matters)

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:240: Node* candidate_node = children_[candidate];
This definitely deserves a DCHECK that |candidate| is within children_.size().

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:264: // Compare this overlap increase with best one to
date, update best.
This comment doesn't seem to be describing the code.  The lines below neither
compare nor update anything.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:265: int overlap_increase = total_expanded_overlap -
total_original_overlap;
Nit: Just return this directly, don't create a temp to return on the next line.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:271: // Sanity-check that the level of the child being
added is one more than ours.
It's actually one less.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:280: // Please don't attempt to split a record Node.
Since record nodes have no children, this DCHECK is unnecessary; the subsequent
one will catch it.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:284: // First determine if splitting along the
horizontal or vertical axis. We
Nit: splitting -> we should split

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:299: // union of all rects [0,i] in the relevant
sorted axis array.
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:339: }
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);

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:354: for (size_t i = 0; i < vertical_sort.size(); ++i)
{
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

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:372: for (int i =
static_cast<int>(vertical_sort.size()) - 1; i >= 0; --i) {
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()").

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:387: size_t max_children) {
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);

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:389: // valid split points p, min_children <= p <=
max_children - min_children, and
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?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:421: size_t split_index) {
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:426: // Our own children_ vector is unsorted, so we
wipe it out and divide the
Nit: In general, if you're writing a comment about a following block of code, I
suggest a blank line above said comment.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:436: // Fix up sibling parentage or it's gonna be an
awkward Thanksgiving.
Remove this comment; the code is clear enough.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:450: // Returns all contained record_node values for
this node and all children.
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:453: DCHECK_EQ(level_, -1);
Again, this is not necessary.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:461: DCHECK(rect_.Contains(node->rect_));
None of these three DCHECKs seems to have anything to do with this function, so
they should probably not be here.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:469: // Sort nodes by top coordinate first.
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:472: } else if (a->rect_.y() == b->rect_.y()) {
From http://dev.chromium.org/developers/coding-style :

"Don't use else after return"

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:476: return false;
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:480: bool RTree::Node::CompareHorizontal(Node* a,
Node* b) {
Similar comments apply to this function.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:493: // are only comparing the two values for sorting
purposes.
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:496: // This comparison assumes the nodes have the
same parent.
All four of the comments here simply duplicate the code, and should be removed.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:497: DCHECK(a->parent_ == b->parent_);
Nit: DCHECK_EQ

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:499: DCHECK(a->parent_);
Tiny nit: I suggest putting this DCHECK first (so they read like "|a| has a
parent, and |b| has the same parent")

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:501: DCHECK_EQ(a->level_, b->level_);
This function doesn't require either of these next two DCHECKs, so they should
probably be removed.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:505: // Find the parent.
Comment duplicates the code, remove it.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:519: const std::vector<Rect>& high_bounds) {
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:520: int smallest_overlap_area =
std::numeric_limits<int>::max();
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;
    }
  }

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:549: // Clear our rectangle, then reset it to union of
our children.
This comment isn't necessary.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h
File ui/gfx/geometry/r_tree.h (right):

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:22: // R*-tree algorithm is used to build the trees.
Based on the papers:
Note: Since I am unfamiliar with these papers, expect that my questions below
may be algorithmically dumb.  That said, this will probably also be the case for
other readers of your code :).

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:30: //
On 2014/04/30 23:20:18, luken wrote:
> On 2014/04/30 23:09:21, Peter Kasting wrote:
> > Nit: Adding a blank comment line here seems slightly unusual.
> Yeah, I needed to change something to include this file in the CL, and didn't
> know that the traditional means is to add a newline at the end of the file. I
> will remove this and replace with newline or other changes based on your
> feedback.

Cool, no worries.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:55: // will all be Nodes with non-NULL record pointers.
Why call things leaves when they're technically not leaves?  Why not just keep
the same tree structure as today, but make the record nodes height 0, the layer
above them 1, and so forth upwards?  Practically speaking this would be the
same, but things would be numbered more like in a traditional tree, and thus
readers would be less likely to be confused or make off-by-one errors.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:56: class GFX_EXPORT Node {
From
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Nested_Classes :

"Nested classes can be forward declared within the enclosing class and then
defined in the .cc file to avoid including the nested class definition in the
enclosing class declaration, since the nested class definition is usually only
relevant to the implementation."

It looks like you only use Node* or scoped_ptr<Node> below, so I'd imagine
forward-declaring Node here should be possible.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:61: // tree.
I assume this means that all branches of the tree must have equal height, rather
than that a parent is height "1 + std::max(child_heights)".  It might be nice to
call this out explicitly in the comments.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:62: explicit Node(int level);
It seems strange that this API allows one to construct a random node, declared
to be at some level within the tree, which isn't actually parented into the tree
anywhere (nor has any children).

I would be less surprised if the API always created new nodes as parents or
children of existing nodes (or as the root), and automatically set/updated the
level as necessary.  It seems like this API allows callers to easily construct
inconsistent trees, which one hopes would be hard or impossible to do.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:65: Node(const Rect& rect, intptr_t key);
It's a bit surprising that the key type is intptr_t.  If this were actually a
pointer, I might expect Rect*.  If it's simply a unique identifier, then if its
meaning refers to an object within some set or array, size_t would be
appropriate; otherwise int, or if a particular size is critically important
int32_t/int64_t, would seem like better choices.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:70: void Clear();
Why is this method necessary?  It seems to be called only by the destructor, and
in that case it doesn't perform any important function.

There are two reasons to remove this function if it's not needed:

(1) Doing so would allow making |key_| const (see comment on |level_| below
(2) Use of this function puts the node, and transitively its parents, into an
inconsistent state, because it no longer has children, but its level is left
unchanged.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:72: // Recursive call to build a list of rects that
intersect the query_rect.
Nit: list -> set; rects -> rects within this subtree (?)

In Chromium code, we often surround identifier names with pipes, e.g.
|query_rect|, to make reading sentences with them clearer (especially if the
variable name looks like an English word).  This isn't a rule anywhere, so it's
up to you whether you want to follow this practice consistently or not.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:74: base::hash_set<intptr_t>* matches_out) const;
Consider a typedef for "base::hash_set<intptr_t>".  For example, maybe at some
point you'd decide that a std::set<> was perfectly reasonable, or change the key
type from intptr_t.  Using a typedef everywhere can help minimize the pain of
these changes.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:79: void RecomputeBounds();
It's a bit odd that calling RecomputeBounds() also affects all parents.

I would have expected an API where RecomputeBounds() instead calls
RecomputeBounds() on all children, and then computes the updated bounds for
|this| based on the new child bounds.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:82: // supplied list. Does not repair bounds upon
completion.
Removes these nodes how?  I assume you mean child nodes, but are these direct
children?  Leaf (record) nodes? chosen from the end or the start of the list? 
etc.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:83: void RemoveNodesForReinsert(size_t
number_to_remove,
Since the function name says "ForReinsert", consider commenting above what
reinsertion is and why it's in the name here.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:86: // Given a pointer to a child node within this
Node, remove it from our
From
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Function_Comments
:

"[Function] comments should be descriptive ("Opens the file") rather than
imperative ("Open the file")"

So, remove -> removes, and similarly elsewhere in this comment and others.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:88: // list. Returns the new count of this node after
removal. Does not
I assume we do not recurse, so the orphans may be entire subtrees?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:90: // few children.
This last sentence is confusing.  It seems to be describing what a caller might
do after calling this function?  Even just something like "Does not both to
recompute bounds yet, since the caller might subsequently remove this node as
well, meaning the recomputation would be wasted work." would be a bit clearer.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:93: // Does what it says on the tin. Returns NULL if no
children. Does not
Nit: Remove first sentence.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:98: // the nodes level().
Nit: nodes -> node's

The comment here is somewhat unclear.  Is this returning the node that |node|
should be made a child of?  Sibling of?  Something else?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:101: // Adds the provided node to this Node. Returns
the new count of records
Nit: to -> as a child of

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:102: // stored in the Node. Will recompute the bounds
of this node after
Nit: Will recompute -> Recomputes (but better yet, attach this to the first
sentence with "and")

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:104: size_t AddChild(Node* node);
Is the caller passing in ownership?  If not, who owns the node, and how is it
that the Remove calls above return ownership?  If so, use a scoped_ptr<>.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:115: Node* parent() const { return parent_; }
From
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Use_of...
:

"...methods should be const if they ...do not return a non-const pointer"

In general, it's almost always unsafe from a logical constness perspective to
have a const method return a non-const pointer, so as a rule of thumb I always
ask that people make the returned pointer const, or make the method non-const.

(Further discussion available on request)

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:119: // height of the tree - 1. A level of -1 means
that this is a Record node.
Nit: These sorts of comments should go on the member variable (where you already
have most of them).

Ultimately I would wind up making all these accessors uncommented and in a
single block:

    Node* parent() { return parent_; }
    int level() const { return level_; }
    const Rect& rect() const { return rect_; }
    ...

The extra whitespace otherwise just reduces the obviousness that these are all
simple accessors.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:129: // Returns all records stored in this node and its
children.
Nit: Since records shouldn't ever be stored in both "this node and its
children", perhaps "stored in the subtree rooted at this node" would be better?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:132: // Used for sorting Nodes along vertical and
horizontal axes
From
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Punctu...
:

"Comments should be as readable as narrative text, with proper capitalization
and punctuation."

Trailing period here.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:133: static bool CompareVertical(Node* a, Node* b);
Prefer file-scoped helper functions in the .cc file over private statics where
possible.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:134: 
Nit: If the comment above applies to both these functions, no blank line here.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:139: // Returns the increase in overlap value, as
defined in Beckmann et al as
Super-tiny nit: et al as -> et al. as

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:140: // the sum of the areas of the intersection of
each |children_| rectangle
Nit: each |children_| rectangle -> all child rectangles?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:146: // rect.
You describe |expanded_rect| twice.  Only describe it once.

Can this method be const?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:158: // the Union of all bounding rectangles [0,i] in
the associated sorted array
Nit: Capitalizing Union here and below is odd

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:160: static void BuildLowBounds(const
std::vector<Node*>& vertical_sort,
Nit: It's not a rule, but I tend to prefer listing all static methods in a group
above or below (usually above) non-static methods, just to be a little clearer
about the division between the groups.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:162: std::vector<Rect>* vertical_bounds,
Also consider a "typedef std::vector<Rect> Rects" to make the many uses here and
below (and in the .cc file) shorter and more readable, as well as easier to
change the type of.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:176: // with the lowest sum of margin values of
bounding boxes.
Nit: It would be nice if this comment were just a little more descriptive, so I
didn't feel like I had to go read Beckmann just to know what it was talking
about.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:184: // Used by SplitNode to calculate optimal index of
split, after determining
There doesn't seem to be a function called SplitNode().

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:194: // split_index in sorted_children.
Nit: Your comment sort of says this already, but it wasn't 100% clear to me that
this means "Children [0, split_index) remain with this node, while children
[split_index, count()) are assigned to the new node."

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:202: // paper, or NULL if there's a tie found. Requires
a precomputed vector of
Again, this comment is relatively opaque to someone not intimately familiar with
Beckmann.  It would be nice if the comments here and/or on this class were
sufficient to outline the basics and one only needed to refer to the mentioned
papers for detail or rationale.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:204: // |children_|[i] and node_rect.
Nit: Once you have a full expression using a variable name instead of just the
name (children_[i]), I normally prefer to leave off the pipes, as they just make
reading the expression more difficult.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:222: int level_;
From http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Use_of_const
:

"Consider making data members const whenever they do not need to be modified
after construction."

It seems like |level_| is a candidate for this.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:224: // Pointers to all of our children Nodes.
Nit: children -> child

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:225: ScopedVector<Node> children_;
This is another place I suggest a typedef; it will make using iterators in the
.cc file (see comments there) nicer.

  typedef ScopedVector<Node> Nodes;  // Or "Children"

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:232: // the key data. Otherwise, NULL.
You refer to NULL here, but the code in the .cc file uses 0.  This is really a
continuation of the comment above wondering about the meaning of this value and
whether intptr_t is truly correct to begin with.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:236: FRIEND_TEST_ALL_PREFIXES(RTreeTest,
NodeBuildHighBounds);
If you already declare RTreeTest a friend class, it generally shouldn't be
necessary to declare very many tests within it as friend tests.  Prefer to hoist
the accessors you need onto protected methods in RTreeTest and then use those
accessors in the individual tests.

luken

PTAL, thanks for taking so much time and giving this such careful attention and feedback! ...

6 years, 7 months ago (2014-05-08 00:00:07 UTC) #7

PTAL, thanks for taking so much time and giving this such careful attention and
feedback!

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc
File ui/gfx/geometry/r_tree.cc (right):

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:12: namespace {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:14: // Returns the center coordinates of the given
rectangle.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: Comment not necessary (we can tell this from the function name)

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:15: gfx::Vector2d CenterOfRect(const gfx::Rect& rect)
{
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:28: : rect_(rect), level_(-1), parent_(NULL),
key_(key) {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

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

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:36: // Iterate through children and delete them all.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Documenting what ScopedVector::clear() does doesn't seem necessary.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:42: base::hash_set<intptr_t>* matches_out) const {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:45: if (!rect_.Intersects(query_rect)) {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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).

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:60: DCHECK_EQ(level_, -1);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

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

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:63: for (size_t i = 0; i < children_.size(); ++i) {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Prefer using iterators over indexes (primarily in loops) where it's feasible
to
> do so.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:65: Node* node = children_[i];
On 2014/05/02 18:04:57, Peter Kasting wrote:
> This really should be a const Node* (or, if using iterators, we should use
> const_iterator).

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:67: DCHECK_EQ(level_ - 1, node->level_);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:84: DCHECK_GE(children_.size(), number_to_remove);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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).

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:87: // the center of our bounding rectangle.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:92: // Add lowest distance nodes from our children
list to the returned vector.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:94: nodes->end(), children_.begin(), children_.begin()
+ number_to_remove);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:103: // Add children of child_node to the orphans
vector.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: Same comments as above... I won't make notes on further instances of this
> sort of thing.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:114: child_it = children_.begin() + i;
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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).

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:127: if (!children_.size())
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Use empty() instead of !size().

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:130: scoped_ptr<Node>
last_child(children_[children_.size() - 1]);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Use .back() instead of [children_.size() - 1].

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:131: DCHECK_EQ(last_child->parent_, this);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:132: children_.weak_erase(children_.begin() +
children_.size() - 1);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Use children_.end() - 1 instead of children_.begin() + children_.size() - 1.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:133: // Invalidate parent, as this child may even
become the new root.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:141: DCHECK(!key_);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> The second DCHECK seems sufficient.  This method doesn't care about keys, so
it
> shouldn't check whether the exist.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:142: DCHECK(level_ >= 0);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> DCHECK_GE

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:143: DCHECK(node);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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).

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:145: // If we are a parent of nodes on the provided
node level, we are done.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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|.
It does, I corrected the DCHECK above to account, and fixed the comment.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:150: DCHECK_GT(children_.size(), 0U);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Use !empty().  But really, I don't see how this function would break if this
> DCHECK failed, so once again, I'd remove it.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:152: // Iterate over all children to find best
candidate for insertion.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> This method doesn't iterate, so this comment doesn't belong.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:153: Node* best_candidate = NULL;
On 2014/05/02 18:04:57, Peter Kasting wrote:
> From
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Local_...
> :
> 
> "...declare [variables]... as close to the first use as possible."

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:162: expanded_rects.push_back(expanded_rect);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:185: int least_area_enlargement =
std::numeric_limits<int>::max();
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.)

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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:188: int area_change =
expanded_rects[i].size().GetArea() -
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Can area change be negative?  (I assume not.)  Maybe this should be DCHECKed?
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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:189: candidate_node->rect_.size().GetArea();
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: I believe this should be indented 4 rather than even, though the style
> guide is unclear.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:194: // Ties are broken by choosing entry with least
area.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit Add articles ("the" two places)

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:203: DCHECK(best_node);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:211: bool has_tied_node = false;
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:221: has_tied_node = true;
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: This can go below the conditional (more efficient, not that it actually
> matters)

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:240: Node* candidate_node = children_[candidate];
On 2014/05/02 18:04:57, Peter Kasting wrote:
> This definitely deserves a DCHECK that |candidate| is within children_.size().

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:264: // Compare this overlap increase with best one to
date, update best.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> This comment doesn't seem to be describing the code.  The lines below neither
> compare nor update anything.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:271: // Sanity-check that the level of the child being
added is one more than ours.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> It's actually one less.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:280: // Please don't attempt to split a record Node.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Since record nodes have no children, this DCHECK is unnecessary; the
subsequent
> one will catch it.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:284: // First determine if splitting along the
horizontal or vertical axis. We
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: splitting -> we should split

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:299: // union of all rects [0,i] in the relevant
sorted axis array.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:339: }
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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);

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:354: for (size_t i = 0; i < vertical_sort.size(); ++i)
{
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:372: for (int i =
static_cast<int>(vertical_sort.size()) - 1; i >= 0; --i) {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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()").

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:387: size_t max_children) {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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);

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:389: // valid split points p, min_children <= p <=
max_children - min_children, and
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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?

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.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:421: size_t split_index) {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:426: // Our own children_ vector is unsorted, so we
wipe it out and divide the
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: In general, if you're writing a comment about a following block of code,
I
> suggest a blank line above said comment.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:436: // Fix up sibling parentage or it's gonna be an
awkward Thanksgiving.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Remove this comment; the code is clear enough.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:450: // Returns all contained record_node values for
this node and all children.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:453: DCHECK_EQ(level_, -1);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Again, this is not necessary.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:461: DCHECK(rect_.Contains(node->rect_));
On 2014/05/02 18:04:57, Peter Kasting wrote:
> None of these three DCHECKs seems to have anything to do with this function,
so
> they should probably not be here.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:469: // Sort nodes by top coordinate first.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:472: } else if (a->rect_.y() == b->rect_.y()) {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> From http://dev.chromium.org/developers/coding-style :
> 
> "Don't use else after return"

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:476: return false;
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:480: bool RTree::Node::CompareHorizontal(Node* a,
Node* b) {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Similar comments apply to this function.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:493: // are only comparing the two values for sorting
purposes.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:496: // This comparison assumes the nodes have the
same parent.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> All four of the comments here simply duplicate the code, and should be
removed.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:497: DCHECK(a->parent_ == b->parent_);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: DCHECK_EQ

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:499: DCHECK(a->parent_);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Tiny nit: I suggest putting this DCHECK first (so they read like "|a| has a
> parent, and |b| has the same parent")

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:501: DCHECK_EQ(a->level_, b->level_);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> This function doesn't require either of these next two DCHECKs, so they should
> probably be removed.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:505: // Find the parent.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Comment duplicates the code, remove it.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:519: const std::vector<Rect>& high_bounds) {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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.

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 :).

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:520: int smallest_overlap_area =
std::numeric_limits<int>::max();
On 2014/05/02 18:04:57, Peter Kasting wrote:
> 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;
>     }
>   }

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

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:549: // Clear our rectangle, then reset it to union of
our children.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> This comment isn't necessary.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h
File ui/gfx/geometry/r_tree.h (right):

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:22: // R*-tree algorithm is used to build the trees.
Based on the papers:
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Note: Since I am unfamiliar with these papers, expect that my questions below
> may be algorithmically dumb.  That said, this will probably also be the case
for
> other readers of your code :).
I guess I had assumed that people who were planning on making substantive edits
to this code, like to Node, would have to have read through these papers at
least once. In your opinion, do you think I should be doing more to teach the
reader about the content of these papers?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:30: //
On 2014/05/02 18:04:57, Peter Kasting wrote:
> On 2014/04/30 23:20:18, luken wrote:
> > On 2014/04/30 23:09:21, Peter Kasting wrote:
> > > Nit: Adding a blank comment line here seems slightly unusual.
> > Yeah, I needed to change something to include this file in the CL, and
didn't
> > know that the traditional means is to add a newline at the end of the file.
I
> > will remove this and replace with newline or other changes based on your
> > feedback.
> 
> Cool, no worries.
Removed the blank comment line.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:55: // will all be Nodes with non-NULL record pointers.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Why call things leaves when they're technically not leaves?  Why not just keep
> the same tree structure as today, but make the record nodes height 0, the
layer
> above them 1, and so forth upwards?  Practically speaking this would be the
> same, but things would be numbered more like in a traditional tree, and thus
> readers would be less likely to be confused or make off-by-one errors.
Calling the nodes that only have "record node" children leaves is consistent
with the literature about R-Trees. My hope was to avoid confusion when moving
between the literature and the code. An alternative might be to make record
nodes a different class, but they have many similar semantics to Node. My choice
to give record nodes a level of -1 was to indicate that they are special
instances of Node. I could see RecordNode as a subclass of Node, what do you
think?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:56: class GFX_EXPORT Node {
On 2014/05/02 18:04:57, Peter Kasting wrote:
> From
> http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Nested_Classes
:
> 
> "Nested classes can be forward declared within the enclosing class and then
> defined in the .cc file to avoid including the nested class definition in the
> enclosing class declaration, since the nested class definition is usually only
> relevant to the implementation."
> 
> It looks like you only use Node* or scoped_ptr<Node> below, so I'd imagine
> forward-declaring Node here should be possible.

I agree it would be cleaner and clearer to move this to the .cc, but this breaks
the unit tests which need to know about Node. Do you know of a workaround to
that?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:61: // tree.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> I assume this means that all branches of the tree must have equal height,
rather
> than that a parent is height "1 + std::max(child_heights)".  It might be nice
to
> call this out explicitly in the comments.
Your assumption is correct. I made it explicit in the comment, which I moved to
the level_ member variable as this ctor is deprecated.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:62: explicit Node(int level);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> It seems strange that this API allows one to construct a random node, declared
> to be at some level within the tree, which isn't actually parented into the
tree
> anywhere (nor has any children).
> 
> I would be less surprised if the API always created new nodes as parents or
> children of existing nodes (or as the root), and automatically set/updated the
> level as necessary.  It seems like this API allows callers to easily construct
> inconsistent trees, which one hopes would be hard or impossible to do.
I've made this constructor only for level 0 nodes, and added two methods
MakeParent() and MakeSibling().

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:65: Node(const Rect& rect, intptr_t key);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> It's a bit surprising that the key type is intptr_t.  If this were actually a
> pointer, I might expect Rect*.  If it's simply a unique identifier, then if
its
> meaning refers to an object within some set or array, size_t would be
> appropriate; otherwise int, or if a particular size is critically important
> int32_t/int64_t, would seem like better choices.
So the R-Tree CL was originally spun out from another CL where the key type was
first a generic type, and both RTree and Node were templatized classes with one
specialization (key is View*). Based on feedback the type changed to a void*,
but that doesn't hash well without providing a separate hash function or it was
suggested I could use intptr_t. So I chose intptr_t. Ultimately this code will
be used with key = View* at first. I think there were code-size concerns about
the generic implementation. It is possible to coerce a View* into an intptr_t,
but I will accept any type suggestion you think is appropriate so long as I can
coerce a View* in to it.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:70: void Clear();
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Why is this method necessary?  It seems to be called only by the destructor,
and
> in that case it doesn't perform any important function.
> 
> There are two reasons to remove this function if it's not needed:
> 
> (1) Doing so would allow making |key_| const (see comment on |level_| below
> (2) Use of this function puts the node, and transitively its parents, into an
> inconsistent state, because it no longer has children, but its level is left
> unchanged.
Agreed, removed.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:72: // Recursive call to build a list of rects that
intersect the query_rect.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: list -> set; rects -> rects within this subtree (?)
> 
> In Chromium code, we often surround identifier names with pipes, e.g.
> |query_rect|, to make reading sentences with them clearer (especially if the
> variable name looks like an English word).  This isn't a rule anywhere, so
it's
> up to you whether you want to follow this practice consistently or not.
Ah, I thought it was only for member variables. I choose to try to apply it
consistently.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:74: base::hash_set<intptr_t>* matches_out) const;
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Consider a typedef for "base::hash_set<intptr_t>".  For example, maybe at some
> point you'd decide that a std::set<> was perfectly reasonable, or change the
key
> type from intptr_t.  Using a typedef everywhere can help minimize the pain of
> these changes.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:79: void RecomputeBounds();
On 2014/05/02 18:04:57, Peter Kasting wrote:
> It's a bit odd that calling RecomputeBounds() also affects all parents.
> 
> I would have expected an API where RecomputeBounds() instead calls
> RecomputeBounds() on all children, and then computes the updated bounds for
> |this| based on the new child bounds.
This is a side effect of the way that the algorithm works, that the insertion of
a new Node changes the parent's bounding box, which change its parent's bounding
box, etc. How do you feel about a rename, something like
RecomputeBoundsUpToRoot()?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:82: // supplied list. Does not repair bounds upon
completion.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Removes these nodes how?  I assume you mean child nodes, but are these direct
> children?  Leaf (record) nodes? chosen from the end or the start of the list? 
> etc.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:83: void RemoveNodesForReinsert(size_t
number_to_remove,
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Since the function name says "ForReinsert", consider commenting above what
> reinsertion is and why it's in the name here.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:86: // Given a pointer to a child node within this
Node, remove it from our
On 2014/05/02 18:04:57, Peter Kasting wrote:
> From
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Function_Comments
> :
> 
> "[Function] comments should be descriptive ("Opens the file") rather than
> imperative ("Open the file")"
> 
> So, remove -> removes, and similarly elsewhere in this comment and others.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:88: // list. Returns the new count of this node after
removal. Does not
On 2014/05/02 18:04:57, Peter Kasting wrote:
> I assume we do not recurse, so the orphans may be entire subtrees?

Yup.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:90: // few children.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> This last sentence is confusing.  It seems to be describing what a caller
might
> do after calling this function?  Even just something like "Does not both to
> recompute bounds yet, since the caller might subsequently remove this node as
> well, meaning the recomputation would be wasted work." would be a bit clearer.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:93: // Does what it says on the tin. Returns NULL if no
children. Does not
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: Remove first sentence.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:98: // the nodes level().
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: nodes -> node's
> 
> The comment here is somewhat unclear.  Is this returning the node that |node|
> should be made a child of?  Sibling of?  Something else?
Reworded.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:101: // Adds the provided node to this Node. Returns
the new count of records
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: to -> as a child of

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:102: // stored in the Node. Will recompute the bounds
of this node after
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: Will recompute -> Recomputes (but better yet, attach this to the first
> sentence with "and")

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:104: size_t AddChild(Node* node);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Is the caller passing in ownership?  If not, who owns the node, and how is it
> that the Remove calls above return ownership?  If so, use a scoped_ptr<>.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:115: Node* parent() const { return parent_; }
On 2014/05/02 18:04:57, Peter Kasting wrote:
> From
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Use_of...
> :
> 
> "...methods should be const if they ...do not return a non-const pointer"
> 
> In general, it's almost always unsafe from a logical constness perspective to
> have a const method return a non-const pointer, so as a rule of thumb I always
> ask that people make the returned pointer const, or make the method non-const.
> 
> (Further discussion available on request)

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:119: // height of the tree - 1. A level of -1 means
that this is a Record node.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: These sorts of comments should go on the member variable (where you
already
> have most of them).
> 
> Ultimately I would wind up making all these accessors uncommented and in a
> single block:
> 
>     Node* parent() { return parent_; }
>     int level() const { return level_; }
>     const Rect& rect() const { return rect_; }
>     ...
> 
> The extra whitespace otherwise just reduces the obviousness that these are all
> simple accessors.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:129: // Returns all records stored in this node and its
children.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: Since records shouldn't ever be stored in both "this node and its
> children", perhaps "stored in the subtree rooted at this node" would be
better?

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:132: // Used for sorting Nodes along vertical and
horizontal axes
On 2014/05/02 18:04:57, Peter Kasting wrote:
> From
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Punctu...
> :
> 
> "Comments should be as readable as narrative text, with proper capitalization
> and punctuation."
> 
> Trailing period here.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:133: static bool CompareVertical(Node* a, Node* b);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Prefer file-scoped helper functions in the .cc file over private statics where
> possible.
I have unit tests for all three, so needed to leave them here, unless you know
of a workaround for that?

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:134: 
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: If the comment above applies to both these functions, no blank line here.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:139: // Returns the increase in overlap value, as
defined in Beckmann et al as
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Super-tiny nit: et al as -> et al. as

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:140: // the sum of the areas of the intersection of
each |children_| rectangle
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: each |children_| rectangle -> all child rectangles?

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:146: // rect.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> You describe |expanded_rect| twice.  Only describe it once.
> 
> Can this method be const?
Yes, it can. Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:158: // the Union of all bounding rectangles [0,i] in
the associated sorted array
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: Capitalizing Union here and below is odd

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:160: static void BuildLowBounds(const
std::vector<Node*>& vertical_sort,
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: It's not a rule, but I tend to prefer listing all static methods in a
group
> above or below (usually above) non-static methods, just to be a little clearer
> about the division between the groups.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:162: std::vector<Rect>* vertical_bounds,
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Also consider a "typedef std::vector<Rect> Rects" to make the many uses here
and
> below (and in the .cc file) shorter and more readable, as well as easier to
> change the type of.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:176: // with the lowest sum of margin values of
bounding boxes.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: It would be nice if this comment were just a little more descriptive, so
I
> didn't feel like I had to go read Beckmann just to know what it was talking
> about.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:184: // Used by SplitNode to calculate optimal index of
split, after determining
On 2014/05/02 18:04:57, Peter Kasting wrote:
> There doesn't seem to be a function called SplitNode().

Split()'s old name. Fixed up the comment.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:194: // split_index in sorted_children.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: Your comment sort of says this already, but it wasn't 100% clear to me
that
> this means "Children [0, split_index) remain with this node, while children
> [split_index, count()) are assigned to the new node."

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:202: // paper, or NULL if there's a tie found. Requires
a precomputed vector of
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Again, this comment is relatively opaque to someone not intimately familiar
with
> Beckmann.  It would be nice if the comments here and/or on this class were
> sufficient to outline the basics and one only needed to refer to the mentioned
> papers for detail or rationale.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:204: // |children_|[i] and node_rect.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: Once you have a full expression using a variable name instead of just the
> name (children_[i]), I normally prefer to leave off the pipes, as they just
make
> reading the expression more difficult.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:222: int level_;
On 2014/05/02 18:04:57, Peter Kasting wrote:
> From
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Use_of_const
> :
> 
> "Consider making data members const whenever they do not need to be modified
> after construction."
> 
> It seems like |level_| is a candidate for this.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:224: // Pointers to all of our children Nodes.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: children -> child

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:225: ScopedVector<Node> children_;
On 2014/05/02 18:04:57, Peter Kasting wrote:
> This is another place I suggest a typedef; it will make using iterators in the
> .cc file (see comments there) nicer.
> 
>   typedef ScopedVector<Node> Nodes;  // Or "Children"

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:232: // the key data. Otherwise, NULL.
On 2014/05/02 18:04:57, Peter Kasting wrote:
> You refer to NULL here, but the code in the .cc file uses 0.  This is really a
> continuation of the comment above wondering about the meaning of this value
and
> whether intptr_t is truly correct to begin with.

Yeah I'm not in love with it either. Perhaps moving back to a void* and writing
a simple hash function would be better.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:236: FRIEND_TEST_ALL_PREFIXES(RTreeTest,
NodeBuildHighBounds);
On 2014/05/02 18:04:57, Peter Kasting wrote:
> If you already declare RTreeTest a friend class, it generally shouldn't be
> necessary to declare very many tests within it as friend tests.  Prefer to
hoist
> the accessors you need onto protected methods in RTreeTest and then use those
> accessors in the individual tests.
Well certainly possible to hoist value access, like calling private accessors or
even returning values of private member variables directly to RTreeTest, I'm not
sure I can hoist types this way.

Meaning I can't represent an RTree::Node in a RTreeNodeTest that isn't
explicitly declared as a friend. Hence the awkward construction.

Peter Kasting

(Replies to particular responses you had) https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc File ui/gfx/geometry/r_tree.cc (right): https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#newcode185 ui/gfx/geometry/r_tree.cc:185: int least_area_enlargement = ...

6 years, 7 months ago (2014-05-08 18:08:21 UTC) #8

(Replies to particular responses you had)

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc
File ui/gfx/geometry/r_tree.cc (right):

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:185: int least_area_enlargement =
std::numeric_limits<int>::max();
On 2014/05/08 00:00:08, luken wrote:
> On 2014/05/02 18:04:57, Peter Kasting wrote:
> > 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?").
> 
> 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?

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

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:389: // valid split points p, min_children <= p <=
max_children - min_children, and
On 2014/05/08 00:00:08, luken wrote:
> On 2014/05/02 18:04:57, Peter Kasting wrote:
> > 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?
> 
> 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.

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

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h
File ui/gfx/geometry/r_tree.h (right):

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:22: // R*-tree algorithm is used to build the trees.
Based on the papers:
On 2014/05/08 00:00:08, luken wrote:
> On 2014/05/02 18:04:57, Peter Kasting wrote:
> > Note: Since I am unfamiliar with these papers, expect that my questions
below
> > may be algorithmically dumb.  That said, this will probably also be the case
> for
> > other readers of your code :).
> I guess I had assumed that people who were planning on making substantive
edits
> to this code, like to Node, would have to have read through these papers at
> least once. In your opinion, do you think I should be doing more to teach the
> reader about the content of these papers?

It's a judgment call.  The line I would try to draw would be between "this is
how the algorithm works" versus "this is why the algorithm is the best" or "this
is how we derived/proved this algorithm".  And of course one shouldn't write
10,000-line comments.

I think it's likely your code will have future editors or maintainers who have
not read these papers and need to be quickly brought up to speed on what you're
trying to do.  So if it's possible, I would probably try to summarize the
salient points of the algorithm in a way that would let readers at least
understand what your code is trying to do, but I wouldn't go into excruciating
detail.

If it's simply not possible to do this, then it's not possible, and don't sweat
it.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:55: // will all be Nodes with non-NULL record pointers.
On 2014/05/08 00:00:08, luken wrote:
> On 2014/05/02 18:04:57, Peter Kasting wrote:
> > Why call things leaves when they're technically not leaves?  Why not just
keep
> > the same tree structure as today, but make the record nodes height 0, the
> layer
> > above them 1, and so forth upwards?  Practically speaking this would be the
> > same, but things would be numbered more like in a traditional tree, and thus
> > readers would be less likely to be confused or make off-by-one errors.
> Calling the nodes that only have "record node" children leaves is consistent
> with the literature about R-Trees. My hope was to avoid confusion when moving
> between the literature and the code. An alternative might be to make record
> nodes a different class, but they have many similar semantics to Node. My
choice
> to give record nodes a level of -1 was to indicate that they are special
> instances of Node. I could see RecordNode as a subclass of Node, what do you
> think?

You're in a better position to do this design than I am.  My instinct would
probably be to use separate classes.  I might use a partly-abstract base class
with concrete record and non-record Node subclasses depending on what in
non-record nodes is not present in record nodes (e.g. |children_|).  This could
replace some of the assertions the code now makes with compile-time typechecking
of args, which is always nice.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:65: Node(const Rect& rect, intptr_t key);
On 2014/05/08 00:00:08, luken wrote:
> On 2014/05/02 18:04:57, Peter Kasting wrote:
> > It's a bit surprising that the key type is intptr_t.  If this were actually
a
> > pointer, I might expect Rect*.  If it's simply a unique identifier, then if
> its
> > meaning refers to an object within some set or array, size_t would be
> > appropriate; otherwise int, or if a particular size is critically important
> > int32_t/int64_t, would seem like better choices.
> So the R-Tree CL was originally spun out from another CL where the key type
was
> first a generic type, and both RTree and Node were templatized classes with
one
> specialization (key is View*). Based on feedback the type changed to a void*,
> but that doesn't hash well without providing a separate hash function or it
was
> suggested I could use intptr_t. So I chose intptr_t. Ultimately this code will
> be used with key = View* at first. I think there were code-size concerns about
> the generic implementation. It is possible to coerce a View* into an intptr_t,
> but I will accept any type suggestion you think is appropriate so long as I
can
> coerce a View* in to it.

What were the concerns about the generic implementation?  I would think the
templated original design would be clearer and better than the current design,
and shouldn't suffer from codesize penalties.  If someday you have RTrees of
multiple specializations, that would result in a codesize hit, but even that is
likely small (since most of the methods in the classes don't need to be
specialized, I don't think -- just a few of them).  I would tend to prefer the
clearer code over the slightly-smaller binary in that case.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:79: void RecomputeBounds();
On 2014/05/08 00:00:08, luken wrote:
> On 2014/05/02 18:04:57, Peter Kasting wrote:
> > It's a bit odd that calling RecomputeBounds() also affects all parents.
> > 
> > I would have expected an API where RecomputeBounds() instead calls
> > RecomputeBounds() on all children, and then computes the updated bounds for
> > |this| based on the new child bounds.
> This is a side effect of the way that the algorithm works, that the insertion
of
> a new Node changes the parent's bounding box, which change its parent's
bounding
> box, etc. How do you feel about a rename, something like
> RecomputeBoundsUpToRoot()?

I think my thought was that the caller should, after inserting a node, ask the
root to recompute its bounds.  But maybe that's not sensible.  A name change
would be OK.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:236: FRIEND_TEST_ALL_PREFIXES(RTreeTest,
NodeBuildHighBounds);
On 2014/05/08 00:00:08, luken wrote:
> On 2014/05/02 18:04:57, Peter Kasting wrote:
> > If you already declare RTreeTest a friend class, it generally shouldn't be
> > necessary to declare very many tests within it as friend tests.  Prefer to
> hoist
> > the accessors you need onto protected methods in RTreeTest and then use
those
> > accessors in the individual tests.
> Well certainly possible to hoist value access, like calling private accessors
or
> even returning values of private member variables directly to RTreeTest, I'm
not
> sure I can hoist types this way.
> 
> Meaning I can't represent an RTree::Node in a RTreeNodeTest that isn't
> explicitly declared as a friend. Hence the awkward construction.

I believe you can do this via typedefs:

class RTree {
  class Node {
    friend class RTreeNodeTest;  // Might have to be in RTree, I forget
  };
};

class RTreeNodeTest {
 public:
  typedef RTree::Node RTreeNode;
};

TEST(RTreeNodeTest, Foo) {
  RTreeNode n;
}

luken

PTAL https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc File ui/gfx/geometry/r_tree.cc (right): https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#newcode185 ui/gfx/geometry/r_tree.cc:185: int least_area_enlargement = std::numeric_limits<int>::max(); On 2014/05/08 18:08:21, Peter ...

6 years, 7 months ago (2014-05-14 00:12:04 UTC) #9

PTAL

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc
File ui/gfx/geometry/r_tree.cc (right):

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:185: int least_area_enlargement =
std::numeric_limits<int>::max();
On 2014/05/08 18:08:21, Peter Kasting wrote:
> On 2014/05/08 00:00:08, luken wrote:
> > On 2014/05/02 18:04:57, Peter Kasting wrote:
> > > 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?").
> > 
> > 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?
> 
> Ah, sorry, I think I missed that.  Using an index is OK.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:265: int overlap_increase = total_expanded_overlap -
total_original_overlap;
On 2014/05/02 18:04:57, Peter Kasting wrote:
> Nit: Just return this directly, don't create a temp to return on the next
line.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.cc#ne...
ui/gfx/geometry/r_tree.cc:389: // valid split points p, min_children <= p <=
max_children - min_children, and
On 2014/05/08 18:08:21, Peter Kasting wrote:
> On 2014/05/08 00:00:08, luken wrote:
> > On 2014/05/02 18:04:57, Peter Kasting wrote:
> > > 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?
> > 
> > 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.
> 
> 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...
It's assumed to have max_children + 1 nodes, but yes this code is deprecated per
your suggestion to refactor it to SmallestMarginSum.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h
File ui/gfx/geometry/r_tree.h (right):

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:22: // R*-tree algorithm is used to build the trees.
Based on the papers:
On 2014/05/08 18:08:21, Peter Kasting wrote:
> On 2014/05/08 00:00:08, luken wrote:
> > On 2014/05/02 18:04:57, Peter Kasting wrote:
> > > Note: Since I am unfamiliar with these papers, expect that my questions
> below
> > > may be algorithmically dumb.  That said, this will probably also be the
case
> > for
> > > other readers of your code :).
> > I guess I had assumed that people who were planning on making substantive
> edits
> > to this code, like to Node, would have to have read through these papers at
> > least once. In your opinion, do you think I should be doing more to teach
the
> > reader about the content of these papers?
> 
> It's a judgment call.  The line I would try to draw would be between "this is
> how the algorithm works" versus "this is why the algorithm is the best" or
"this
> is how we derived/proved this algorithm".  And of course one shouldn't write
> 10,000-line comments.
> 
> I think it's likely your code will have future editors or maintainers who have
> not read these papers and need to be quickly brought up to speed on what
you're
> trying to do.  So if it's possible, I would probably try to summarize the
> salient points of the algorithm in a way that would let readers at least
> understand what your code is trying to do, but I wouldn't go into excruciating
> detail.
> 
> If it's simply not possible to do this, then it's not possible, and don't
sweat
> it.

I think it's a good idea to try and describe these algorithms in more detail,
and to make the code clear enough that maintainers wouldn't have to read the
papers. I have tried to do this while refactoring.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:55: // will all be Nodes with non-NULL record pointers.
On 2014/05/08 18:08:21, Peter Kasting wrote:
> On 2014/05/08 00:00:08, luken wrote:
> > On 2014/05/02 18:04:57, Peter Kasting wrote:
> > > Why call things leaves when they're technically not leaves?  Why not just
> keep
> > > the same tree structure as today, but make the record nodes height 0, the
> > layer
> > > above them 1, and so forth upwards?  Practically speaking this would be
the
> > > same, but things would be numbered more like in a traditional tree, and
thus
> > > readers would be less likely to be confused or make off-by-one errors.
> > Calling the nodes that only have "record node" children leaves is consistent
> > with the literature about R-Trees. My hope was to avoid confusion when
moving
> > between the literature and the code. An alternative might be to make record
> > nodes a different class, but they have many similar semantics to Node. My
> choice
> > to give record nodes a level of -1 was to indicate that they are special
> > instances of Node. I could see RecordNode as a subclass of Node, what do you
> > think?
> 
> You're in a better position to do this design than I am.  My instinct would
> probably be to use separate classes.  I might use a partly-abstract base class
> with concrete record and non-record Node subclasses depending on what in
> non-record nodes is not present in record nodes (e.g. |children_|).  This
could
> replace some of the assertions the code now makes with compile-time
typechecking
> of args, which is always nice.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:65: Node(const Rect& rect, intptr_t key);
On 2014/05/08 18:08:21, Peter Kasting wrote:
> On 2014/05/08 00:00:08, luken wrote:
> > On 2014/05/02 18:04:57, Peter Kasting wrote:
> > > It's a bit surprising that the key type is intptr_t.  If this were
actually
> a
> > > pointer, I might expect Rect*.  If it's simply a unique identifier, then
if
> > its
> > > meaning refers to an object within some set or array, size_t would be
> > > appropriate; otherwise int, or if a particular size is critically
important
> > > int32_t/int64_t, would seem like better choices.
> > So the R-Tree CL was originally spun out from another CL where the key type
> was
> > first a generic type, and both RTree and Node were templatized classes with
> one
> > specialization (key is View*). Based on feedback the type changed to a
void*,
> > but that doesn't hash well without providing a separate hash function or it
> was
> > suggested I could use intptr_t. So I chose intptr_t. Ultimately this code
will
> > be used with key = View* at first. I think there were code-size concerns
about
> > the generic implementation. It is possible to coerce a View* into an
intptr_t,
> > but I will accept any type suggestion you think is appropriate so long as I
> can
> > coerce a View* in to it.
> 
> What were the concerns about the generic implementation?  I would think the
> templated original design would be clearer and better than the current design,
> and shouldn't suffer from codesize penalties.  If someday you have RTrees of
> multiple specializations, that would result in a codesize hit, but even that
is
> likely small (since most of the methods in the classes don't need to be
> specialized, I don't think -- just a few of them).  I would tend to prefer the
> clearer code over the slightly-smaller binary in that case.
By splitting the Node class into Record and Node classes I've been able to
separate out the parts of RTree that need to be generic into a derived and
specialized descendant of RTreeBase. I'm happy with the new design, curious to
hear your feedback.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:79: void RecomputeBounds();
On 2014/05/08 18:08:21, Peter Kasting wrote:
> On 2014/05/08 00:00:08, luken wrote:
> > On 2014/05/02 18:04:57, Peter Kasting wrote:
> > > It's a bit odd that calling RecomputeBounds() also affects all parents.
> > > 
> > > I would have expected an API where RecomputeBounds() instead calls
> > > RecomputeBounds() on all children, and then computes the updated bounds
for
> > > |this| based on the new child bounds.
> > This is a side effect of the way that the algorithm works, that the
insertion
> of
> > a new Node changes the parent's bounding box, which change its parent's
> bounding
> > box, etc. How do you feel about a rename, something like
> > RecomputeBoundsUpToRoot()?
> 
> I think my thought was that the caller should, after inserting a node, ask the
> root to recompute its bounds.  But maybe that's not sensible.  A name change
> would be OK.

Done.

https://codereview.chromium.org/269513002/diff/1/ui/gfx/geometry/r_tree.h#new...
ui/gfx/geometry/r_tree.h:236: FRIEND_TEST_ALL_PREFIXES(RTreeTest,
NodeBuildHighBounds);
On 2014/05/08 18:08:21, Peter Kasting wrote:
> On 2014/05/08 00:00:08, luken wrote:
> > On 2014/05/02 18:04:57, Peter Kasting wrote:
> > > If you already declare RTreeTest a friend class, it generally shouldn't be
> > > necessary to declare very many tests within it as friend tests.  Prefer to
> > hoist
> > > the accessors you need onto protected methods in RTreeTest and then use
> those
> > > accessors in the individual tests.
> > Well certainly possible to hoist value access, like calling private
accessors
> or
> > even returning values of private member variables directly to RTreeTest, I'm
> not
> > sure I can hoist types this way.
> > 
> > Meaning I can't represent an RTree::Node in a RTreeNodeTest that isn't
> > explicitly declared as a friend. Hence the awkward construction.
> 
> I believe you can do this via typedefs:
> 
> class RTree {
>   class Node {
>     friend class RTreeNodeTest;  // Might have to be in RTree, I forget
>   };
> };
> 
> class RTreeNodeTest {
>  public:
>   typedef RTree::Node RTreeNode;
> };
> 
> TEST(RTreeNodeTest, Foo) {
>   RTreeNode n;
> }
Oh I didn't know that! Done.

Peter Kasting

Again, I have not reviewed the unittests. This seems saner than the old code. https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree.h ...

6 years, 7 months ago (2014-05-16 01:41:04 UTC) #10

luken

PTAL, thanks! https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree.h File ui/gfx/geometry/r_tree.h (right): https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree.h#newcode26 ui/gfx/geometry/r_tree.h:26: : RTreeBase(min_children, max_children) {} On 2014/05/16 01:41:05, ...

6 years, 7 months ago (2014-05-21 20:19:36 UTC) #11

PTAL, thanks!

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree.h
File ui/gfx/geometry/r_tree.h (right):

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:26: : RTreeBase(min_children, max_children) {}
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Based on
>
http://dev.chromium.org/developers/coding-style/cpp-dos-and-donts#TOC-Stop-in....
> : Don't inline this constructor, since it's actually nontrivial.  Define it
> out-of-line below.  Same with the destructor.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:27: virtual ~RTree() {}
On 2014/05/16 01:41:05, Peter Kasting wrote:
> This destructor, and RTreeBase's destructor, should probably not be virtual. 
> You're not intending RTreeBase to be used polymorphically, so external classes
> shouldn't be holding pointers to it.  So it should be safe to use a
non-virtual
> destructor, and save yourself the otherwise-unneeded vtable.  See the end of
> Effective C++ Item 7 for more detail on this.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:37: // Fills a supplied ResultSet matches_out with all
keys having bounding rects
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: "ResultSet" is not the correct type name.
> 
> Consider surrounding param names in the comment with pipes.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:47: Record(const Rect& rect, Key key) :
RecordBase(rect), key_(key) {}
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Again, avoid defining these inline.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:49: const Key key() const { return key_; }
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Did you mean to instead return a const ref?

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:53: };
On 2014/05/16 01:41:05, Peter Kasting wrote:
> DISALLOW_COPY_ANY_ASSIGN, unless you intend record nodes to be copyable.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:61: friend class RTreeNodeTest;
On 2014/05/16 01:41:05, Peter Kasting wrote:
> The Google style guide doesn't make it clear where member class and friend
> declarations should go within the section, but AFAIK Chrome code typically
lists
> the friends first, then member classes, then the other pieces of the private
> section.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:70: typename RecordMap::iterator it =
record_map_.find(key);
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Are the "typename"s actually necessary for compilation here and below?
> 
> Nit: Also, this isn't a rule, but for clarity, I personally prefer to use
> constructor-style init ("()") over assignment-style ("=") for non-basic types,
> so the reader immediately knows this isn't going to use operator=().

Yes, clang will warn without them, which is treated as an error in our build.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:74: // If the new rect and the current rect are
identical we can skip rest of
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: rest -> the rest

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:96: // Build a new record Node for insertion in to
tree.
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: These next two comments don't seem to add anything to the code.  I'd omit
> them.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:102: // Call internal Insert with this new node and
allowing all re-inserts.
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Another comment that doesn't seem to add anything to the code.  Assume
> readers can look up function declarations to find out more about the meaning
of
> different parameters.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:103: int starting_level = -1;
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Might be clearer to name this |highest_reinsert_level|.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:117: // If not in the map it's not in the tree, we're
done.
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: The next three comments seem to add nothing to the code, I'd remove them.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:131: root_ = scoped_ptr<Node>(
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Use reset() instead of "= scoped_ptr<Node>()" for a slight efficiency
win.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:140: for (RTreeBase::Records::iterator it =
matching_records.begin();
On 2014/05/16 01:41:05, Peter Kasting wrote:
> I think this can be a const_iterator?

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.cc (right):

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:14: 
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Either eliminate this blank line, or add one below the end-of-namespace
> brace below.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:19: gfx::Vector2d(rect.width() / 2, rect.height()
/ 2);
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:38: : rect_(rect), parent_(parent) {
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:51: rect_ = rect;
On 2014/05/16 01:41:05, Peter Kasting wrote:
> This should probably be inlined into the header as "set_rect()".

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:56: if (!rect_.Intersects(query_rect))
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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);

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:72: }
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Perhaps the base class should define this empty implementation, meaning
> RecordBase doesn't need to?

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:81: RTreeBase::Node::Node() : Node(0) {
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Isn't calling one constructor from another C++11-only?  I don't believe
Chromium
> code can use C++11 yet.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:115: for (Nodes::const_iterator i =
children_.begin(); i != children_.end(); ++i) {
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:124: std::sort(children_.begin(),
On 2014/05/16 01:41:05, Peter Kasting wrote:
> You can use partial_sort() instead of sort() here for a slight efficiency
gain.

Neat, didn't know about that. Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:135: DCHECK_EQ(child_node->parent(), this);
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: (expected, actual)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:137: scoped_ptr<NodeBase> orphan =
child_node->RemoveAndReturnLastChild();
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: See previous comment suggesting constructor-style init for non-BTs

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:140: orphan =
child_node->RemoveAndReturnLastChild();
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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?
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.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:143: for (Nodes::iterator i = children_.begin();
i != children_.end(); ++i) {
On 2014/05/16 01:41:05, Peter Kasting wrote:
> How about using std::find?  It ought to make this slightly shorter and
clearer.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:173: // Precompute a vector of expanded rects,
used both by LeastOverlapIncrease
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: both by -> by both

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:175: std::vector<Rect> expanded_rects;
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Use your Rects typedef (many places across the file)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:214: std::vector<NodeBase*>
vertical_sort(children_.get());
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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?

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

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:237: size_t end_index = max_children -
min_children;
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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.
That's a good point. This code only ever gets called when children_.size() ==
max_children + 1, so I tightened the DCHECK to that.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:244: min_children, end_index,
low_vertical_bounds, high_vertical_bounds);
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Wrap and indent both calls the same way.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:248: : low_horizontal_bounds);
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:288: const NodeBase* p = a->parent();
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: You can put this above the DCHECKs and then use it in them.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:355: size_t max_children,
On 2014/05/16 01:41:05, Peter Kasting wrote:
> |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.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:365: .GetArea();
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:367: high_bounds[min_children].size().GetArea();
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Again, I'd indent this 4, not even.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:427: NodeBase* candidate_node =
children_[candidate];
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:429: // Early-out option for when rect is
contained completely within candidate.
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: rect -> |rect|, candidate -> the candidate

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:443: Rect overlap_rect = candidate_node->rect();
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:465: rect_ = low_bounds[split_index - 1];
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Looks like this requires an assertion that split_index is greater than 0.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:518: expanded_rects[0].size().GetArea() -
best_node->rect().size().GetArea();
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Seems like we also should have an assertion that |expanded_rects| has the same
> size as |children_|?

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:529: DCHECK(best_node);
On 2014/05/16 01:41:05, Peter Kasting wrote:
> 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.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:541: 
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Two blank lines here, if you're using two blank lines similarly
elsewhere.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:542: // RTree
----------------------------------------------------------------------
On 2014/05/16 01:41:05, Peter Kasting wrote:
> RTreeBase

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:548: // R-Trees require min_children >= 2
On 2014/05/16 01:41:05, Peter Kasting wrote:
> These two comments merely duplicate the code; remove them.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:566: ScopedVector<NodeBase> reinserts;
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Use Node::Nodes as the type here to match the type used in the declaration of
> the function you call below.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:569:
insert_parent->AddChild(scoped_ptr<NodeBase>(insert_node)) >
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Consider using make_scoped_ptr(insert_node) to avoid listing the type
> explicitly (2 places)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:595: // insert_node
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Trailing period.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:598: root_ = old_root->MakeParent();
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Could just be
> 
>     root_ = root_.release()->MakeParent();

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:608: for (size_t i = 0; i < reinserts.size();
++i) {
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Prefer iterators to indexes where possible.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:624: DCHECK_EQ(parent->level(), 0);
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: (expected, actual)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.h (right):

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:23: virtual ~RTreeBase();
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Can both of these be protected also?  In general, it would be nice to make
> everything in this file non-public except where necessary.  Random example: I
> think NodeBase::GetAllValues() can be protected.  The same is probably true of
> other functions.
RTreeBase ctor and dtor can be made protected and have. I wasn't able to find
anything else in NodeBase or RecordBase that could be made private. Recall that
a lot of tree operations which apply generically to Nodes and Records use
NodeBase methods. For example NodeBase::GetAllValues() is used in
RTree::Node::GetAllValues(), which maintains a list of NodeBase* as children_.
And in fact the way I built that class was by starting with everything protected
and then only incrementally adding those methods that had to be public.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:29: // Private data structure class for storing
internal nodes or leaves with keys
On 2014/05/16 01:41:05, Peter Kasting wrote:
> You use "key" three times in this file, all in comments, and all the comments
> are somewhat confusing.
> 
> Related,
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=File_C...
> says "Every file should have a comment at the top describing its contents. 
> Generally a .h file will describe the classes that are declared in the file
with
> an overview of what they are for and how they are used."
> 
> If you wrote a file comment noting the classes declared in the file and the
> overall structure they're trying to implement, then the per-class comments
could
> just be about details specific to those classes that don't have to do with the
> relationship of the classes to each other.  I think this would be clearer.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:35: virtual void Query(const Rect& query_rect,
Records* records_out) const = 0;
On 2014/05/16 01:41:05, Peter Kasting wrote:
> This function should have a comment indicating what it's supposed to do.
> 
> I also suggest a blank line between each section: constructor/destructor,
> virtual functions, non-virtual functions, accessors, etc.  (Multiple classes
in
> this file)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:37: // Recompute our bounds by taking the union of
all children rects. Will then
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: How about:
> 
> Recomputes our bounds by taking the union of all child rects, then calls
> recursively on our parent so that ultimately all nodes up to the root
recompute
> their bounds.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:44: virtual void GetAllValues(Records*
records_out) const = 0;
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Put a blank line above this if the comment above doesn't apply to it.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:46: void SetParent(NodeBase* parent) { parent_ =
parent; }
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Based on
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Functi...
> , name this "set_parent".
> 
> Also, put this in the set of accessors below, next to (I suggest below)
> parent().

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:50: virtual const int level() const = 0;
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Virtual functions should never be named unix_hacker()-style.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:62: Rect rect_;
On 2014/05/16 01:41:05, Peter Kasting wrote:
> From
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Access...
> : "Make data members private".  Except in test fixtures, you shouldn't be
using
> protected data members.  (Multiple classes)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:67: };
On 2014/05/16 01:41:05, Peter Kasting wrote:
> DISALLOW_COPY_AND_ASSIGN (every class in this file)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:88: class GFX_EXPORT Node : public NodeBase {
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Can this class be forward-declared here, and then defined entirely in the .cc
> file?
> 
> I realize that RecordBase, and thus NodeBase, need to be defined in this
header
> if RecordBase is going to be a parent of Record in r_tree.h, but maybe Node
can
> be pulled out.
> 
> Another way to do this would be to forward-declare almost everything here, but
> then put the definitions of classes like RecordBase in their own headers, so
> they're at least split into a couple of different headers for greater
> readability.  (Of course, then one should also consider whether these should
> remain member classes; but I'm personally a fan of private member classes to
> prevent external classes from attempting to use them.)

Unfortunately, no. r_tree.h relies on knowing what a Node is and the special
methods it has.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:97: // to the returned parent by this function.
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: returned parent -> parent returned

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:98: scoped_ptr<Node> MakeParent();
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Perhaps this function and the next should be called "ConstructXXX", as
"MakeXXX"
> sounds like "turns this node into an XXX".

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:102: // will not have been added to the |parent_|
as its bounds are still empty.
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Either it has the same parent or it doesn't have the same parent.
> 
> But in looking, it doesn't seem like you actually use this function, so it
> should be removed.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:106: // intersect the |query_rect| in this
subtree. Appends to |matches_out|
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Maybe:
> 
> Appends to |records_out| the set of Records in this subtree with rects that
> intersect |query_rect|.  Avoids clearing |records_out| so that it can be
called
> recursively.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:111: typedef ScopedVector<NodeBase> Nodes;
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Based on
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...
> , typedefs should be atop the section.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:144: Node* Split(size_t min_children, size_t
max_children);
On 2014/05/16 01:41:05, Peter Kasting wrote:
> This seems to return a new Node the caller is expected to take ownership of,
so
> it should return a scoped_ptr.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:151: Node(int level);
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: I suggest a blank line above this

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:156: // vectors.
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Sadly, I just don't really understand what this function does from reading the
> comment.  Perhaps write out, or refer to something that's written elsewhere,
the
> overall algorithm for splitting.
Reworked the comment.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:163: // same index within |low_bounds| and
|high_bounds|.
On 2014/05/16 01:41:05, Peter Kasting wrote:
> My brain exploded trying to parse this sentence.  Perhaps a much longer
comment,
> which defines terms like "margins" (which here apparently means a rectangle's
> width plus its height?).

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:169: // Sort nodes primarily by increasing y
coordinates, and secondarily by
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Sort -> Sorts, or "Used to sort" (several functions)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:182: // function populates two vectors of
Rectangles in which the ith element is
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: Remove "this function" (also in next comment)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:202: // |matches_out| without clearing.
On 2014/05/16 01:41:05, Peter Kasting wrote:
> This sort of comment should be on the base class function.  In general,
> OVERRIDEs should only have comments when they're needed to describe something
> specific to this class' implementation.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:208: // candidate child is indicated by index in
|children_|, and expanded_rect
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: "...Here |candidate| is the index of the candidate child within
> |children_|, ..."

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:209: // is the already-computed union of
candidate's rect and rect.
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: candidate's -> the candidate's; also put pipes around "|rect|" at least
(a
> good example of a sentence where we want to use the same word to mean two
> different things in close proximity, and thus the motivation for
pipe-notation)

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:215: // node, while children [split_index,
count()) are assigned to the new node.
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: How about:
> 
> Returns a new node containing children [split_index, count()) within
> |sorted_children|.  Children before |split_index| remain with |this|.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:216: Node* DivideChildren(const Rects& low_bounds,
On 2014/05/16 01:41:05, Peter Kasting wrote:
> This seems to return a new Node the caller is expected to take ownership of,
so
> it should return a scoped_ptr.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:236: // nodes' bounding box. Requires a
precomputed vector of expanded rectangles
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: nodes -> node's

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:242: // Level counts from -1 for "record" Nodes,
that is Nodes that wrap key
On 2014/05/16 01:41:05, Peter Kasting wrote:
> This level can't ever be -1, because this class is a Node, not a Record or one
> of its parent classes.
> 
> This whole comment should probably move to the level() function on the root
> class.
> 
> I might also use parentheticals in place of ", that is" just to reduce
verbiage.

Done.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:259: void InsertNode(NodeBase* node, int*
highset_reinsert_level);
On 2014/05/16 01:41:05, Peter Kasting wrote:
> Nit: You might want to note what -1 would mean for the second param.

Done.

Peter Kasting

(Have not re-reviewed, just replying to a few of your comments) https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_base.h File ui/gfx/geometry/r_tree_base.h (right): ...

6 years, 7 months ago (2014-05-21 20:26:44 UTC) #12

(Have not re-reviewed, just replying to a few of your comments)

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.h (right):

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:23: virtual ~RTreeBase();
On 2014/05/21 20:19:36, luken wrote:
> On 2014/05/16 01:41:05, Peter Kasting wrote:
> > Can both of these be protected also?  In general, it would be nice to make
> > everything in this file non-public except where necessary.  Random example:
I
> > think NodeBase::GetAllValues() can be protected.  The same is probably true
of
> > other functions.
> RTreeBase ctor and dtor can be made protected and have. I wasn't able to find
> anything else in NodeBase or RecordBase that could be made private. Recall
that
> a lot of tree operations which apply generically to Nodes and Records use
> NodeBase methods. For example NodeBase::GetAllValues() is used in
> RTree::Node::GetAllValues(), which maintains a list of NodeBase* as children_.

Yeah, but Node is a subclass of NodeBase, so it should be able to call protected
methods on it, no?  Sure, GetAllValues() can't be private, but I don't see where
it needs to be public.

https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:88: class GFX_EXPORT Node : public NodeBase {
On 2014/05/21 20:19:36, luken wrote:
> On 2014/05/16 01:41:05, Peter Kasting wrote:
> > Can this class be forward-declared here, and then defined entirely in the
.cc
> > file?
> > 
> > I realize that RecordBase, and thus NodeBase, need to be defined in this
> header
> > if RecordBase is going to be a parent of Record in r_tree.h, but maybe Node
> can
> > be pulled out.
> > 
> > Another way to do this would be to forward-declare almost everything here,
but
> > then put the definitions of classes like RecordBase in their own headers, so
> > they're at least split into a couple of different headers for greater
> > readability.  (Of course, then one should also consider whether these should
> > remain member classes; but I'm personally a fan of private member classes to
> > prevent external classes from attempting to use them.)
> 
> Unfortunately, no. r_tree.h relies on knowing what a Node is and the special
> methods it has.

I still wonder if there isn't some possibility of splitting these into separate
.h/.cc pairs, one for each class, even if in the end r_tree.h needs to #include
all the headers.  The rationale for this is simply to reduce the amount of code
in each file, making each file shorter and easier to scan, and so a reader knows
that everything in that file has to do with exactly one class.

luken

On 2014/05/21 20:26:44, Peter Kasting wrote: > (Have not re-reviewed, just replying to a few ...

6 years, 7 months ago (2014-05-21 22:50:33 UTC) #13

On 2014/05/21 20:26:44, Peter Kasting wrote:
> (Have not re-reviewed, just replying to a few of your comments)
> 
>
https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
> File ui/gfx/geometry/r_tree_base.h (right):
> 
>
https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
> ui/gfx/geometry/r_tree_base.h:23: virtual ~RTreeBase();
> On 2014/05/21 20:19:36, luken wrote:
> > On 2014/05/16 01:41:05, Peter Kasting wrote:
> > > Can both of these be protected also?  In general, it would be nice to make
> > > everything in this file non-public except where necessary.  Random
example:
> I
> > > think NodeBase::GetAllValues() can be protected.  The same is probably
true
> of
> > > other functions.
> > RTreeBase ctor and dtor can be made protected and have. I wasn't able to
find
> > anything else in NodeBase or RecordBase that could be made private. Recall
> that
> > a lot of tree operations which apply generically to Nodes and Records use
> > NodeBase methods. For example NodeBase::GetAllValues() is used in
> > RTree::Node::GetAllValues(), which maintains a list of NodeBase* as
children_.
> 
> Yeah, but Node is a subclass of NodeBase, so it should be able to call
protected
> methods on it, no?  Sure, GetAllValues() can't be private, but I don't see
where
> it needs to be public.

Because I need Node to be able to call GetAllValues() on _other_ NodeBase
objects, namely its children. Protected access only gives Node access to its own
base functions.

> 
>
https://codereview.chromium.org/269513002/diff/200001/ui/gfx/geometry/r_tree_...
> ui/gfx/geometry/r_tree_base.h:88: class GFX_EXPORT Node : public NodeBase {
> On 2014/05/21 20:19:36, luken wrote:
> > On 2014/05/16 01:41:05, Peter Kasting wrote:
> > > Can this class be forward-declared here, and then defined entirely in the
> .cc
> > > file?
> > > 
> > > I realize that RecordBase, and thus NodeBase, need to be defined in this
> > header
> > > if RecordBase is going to be a parent of Record in r_tree.h, but maybe
Node
> > can
> > > be pulled out.
> > > 
> > > Another way to do this would be to forward-declare almost everything here,
> but
> > > then put the definitions of classes like RecordBase in their own headers,
so
> > > they're at least split into a couple of different headers for greater
> > > readability.  (Of course, then one should also consider whether these
should
> > > remain member classes; but I'm personally a fan of private member classes
to
> > > prevent external classes from attempting to use them.)
> > 
> > Unfortunately, no. r_tree.h relies on knowing what a Node is and the special
> > methods it has.
> 
> I still wonder if there isn't some possibility of splitting these into
separate
> .h/.cc pairs, one for each class, even if in the end r_tree.h needs to
#include
> all the headers.  The rationale for this is simply to reduce the amount of
code
> in each file, making each file shorter and easier to scan, and so a reader
knows
> that everything in that file has to do with exactly one class.

But wouldn't this be confusing in that these are internal objects of RTree? If I
see an object in a separate file I usually make the assumption that it is fair
for use. I think it's clearer to keep internal objects where the reader would
expect them to be - internal to the file. At least now r_tree.h has very little
internal cruft in it, you have to dig to r_tree_base.h in order to get to the
longer file with more complexity.

Peter Kasting

On 2014/05/21 22:50:33, luken wrote: > On 2014/05/21 20:26:44, Peter Kasting wrote: > > Yeah, ...

6 years, 7 months ago (2014-05-21 23:01:13 UTC) #14

On 2014/05/21 22:50:33, luken wrote:
> On 2014/05/21 20:26:44, Peter Kasting wrote:
> > Yeah, but Node is a subclass of NodeBase, so it should be able to call
> protected
> > methods on it, no?  Sure, GetAllValues() can't be private, but I don't see
> where
> > it needs to be public.
> 
> Because I need Node to be able to call GetAllValues() on _other_ NodeBase
> objects, namely its children. Protected access only gives Node access to its
own
> base functions.

I feel embarrassed that I forgot this is how C++ works -- I actually had to
write myself a test program to verify this.

> > I still wonder if there isn't some possibility of splitting these into
> separate
> > .h/.cc pairs, one for each class, even if in the end r_tree.h needs to
> #include
> > all the headers.  The rationale for this is simply to reduce the amount of
> code
> > in each file, making each file shorter and easier to scan, and so a reader
> knows
> > that everything in that file has to do with exactly one class.
> 
> But wouldn't this be confusing in that these are internal objects of RTree? If
I
> see an object in a separate file I usually make the assumption that it is fair
> for use. I think it's clearer to keep internal objects where the reader would
> expect them to be - internal to the file. At least now r_tree.h has very
little
> internal cruft in it, you have to dig to r_tree_base.h in order to get to the
> longer file with more complexity.

Since each class would still very clearly be a member class in the first line of
the declaration:

class RTreeBase::NodeBase { ...

...it doesn't seem like it would be hard to realize these are member classes.

As for keeping things "internal", my definition of "internal" would be "class is
fully declared in the .cc file" -- as long as the declaration is in the .h file,
it doesn't seem like it makes much difference whether there is 1 .h, or 2, or 6.

There aren't rules on this, so in the end it's up to you to do what you think
best; I just think headers with lots of classes in them get unwieldy to read.

Peter Kasting

This is getting pretty close. Most of the remaining comments are minor. I've now reviewed ...

6 years, 6 months ago (2014-05-29 00:32:25 UTC) #15

luken

PTAL, thanks https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree.h File ui/gfx/geometry/r_tree.h (right): https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree.h#newcode26 ui/gfx/geometry/r_tree.h:26: RTree(size_t min_children, size_t max_children); On 2014/05/29 00:32:26, ...

6 years, 6 months ago (2014-05-30 16:51:03 UTC) #16

PTAL, thanks

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree.h
File ui/gfx/geometry/r_tree.h (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:26: RTree(size_t min_children, size_t max_children);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Consider describing more about what these mean in terms of what
> externally-observable properties are affected by different values, and/or how
a
> user of this class could decide what values to supply.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:39: typedef base::hash_set<Key> Matches;
On 2014/05/29 00:32:26, Peter Kasting wrote:
> From
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...
> : Typedefs and enums go atop the section.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:155: RTree<Key>::Record::Record(const Rect& rect, const
Key& key)
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Since you're defining functions from multiple classes in this file, you
> could consider divider comments above each class' definitions like the ones
you
> put in r_tree_base.cc.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:156: : RecordBase(rect), key_(key) {
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Indent 4, not 2
> 
> Also, as I noted elsewhere in the previous comment round, my reading of the
> style guide (not everyone agrees) is to require one initializer per line when
> the whole list isn't on the same line as the function name.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.cc (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:198: DCHECK_EQ(children_.size(), max_children +
1);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: (expected, actual)

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:353: high_bounds[start_index]).size().GetArea();
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: I would probably indent this line even, or perhaps do:
> 
>   int smallest_overlap_area = UnionRects(
>       low_bounds[start_index], high_bounds[start_index]).size().GetArea();

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:397: for (size_t i = 0; i < children_.size();
++i) {
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: No {} (since you don't use it everywhere within the file)

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:448: Node* sibling = new Node(level_);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Declare |sibling| as a scoped_ptr here rather than a raw pointer.  This would
be
> safer if we used exceptions, and in general is a more RAII-correct way to
code.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:514: candidate_node->rect().size().GetArea() <
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: I would probably indent this line 4 rather than even (because these lines
> are not function args)

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:577: root_ = root_.release()->ConstructParent();
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Because this is subtle, it's probably worth a comment, like "Note that we
> must release() the root since ConstructParent() will take ownership of it."
> 
> Though if you think the existing note at the end of the declaration of
> ConstructParent() is sufficient, you can omit this.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:588: InsertNode(*it, highest_reinsert_level);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> So, passing |highest_reinsert_level| by pointer means that as we iterate
through
> this loop, one invocation of InsertNode() will change the value passed to
future
> invocations.  Is this what you really want?  If so, you should consider adding
a
> comment noting that this happens and explaining why it's important.
That is what I want. I added a comment in the declaration of InsertNode() that
elaborates on why. I'll add a little blurb here too.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:624: if (parent) {
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: No {}
really? even with the else below? if you say so..

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.h (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:29: typedef std::list<const RecordBase*> Records;
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Are you sure you want a list rather than a vector?  Are you going to be doing
> insertion in the beginning/middle, and no random access?
I don't need any random access. I don't do any insertions or deletions in the
middle of the list. I went with list because if you don't need random access it
will generally be faster than vector on insertions and deletions yes? Or is that
not so?

Based on feedback from this and other reviews, it seems that senior Chrome
engineers have a strong preference for vector over list, even when random access
isn't needed. I'm happy to change this to a vector - but can you please tell me
why you think that is?

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:31: typedef ScopedVector<NodeBase> Nodes;
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Tiny nit: I'd probably place the forward-decls in alphabetical or file order
(in
> this case, the two are the same) above the typedefs.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:35: friend class RTreeNodeTest;
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: To match the order in r_tree.h, I'd probably place these above the
> typedefs.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:40: // Private data structure class for storing
internal Nodes or leaves with
On 2014/05/29 00:32:26, Peter Kasting wrote:
> This class isn't actually declared "private" in RTreeBase -- either do so or
fix
> the comment.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:49: virtual void Query(const Rect& query_rect,
Records* records_out) const = 0;
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Would it be any clearer to name this AppendIntersectingRecords()?

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:56: virtual void GetAllValues(Records*
records_out) const = 0;
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Would it be any clearer to name this AppendAllRecords()?
> 
> This function should perhaps be listed next to Query() (or whatever it gets
> named), since they do similar things.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:61: // branches of the tree must have equal
height.
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: This is pretty good, I wonder if the following would be any clearer:
> 
> Returns -1 for Records, or the height of this subtree for Nodes.  The height
of
> a leaf Node (a Node containing only Records) is 0, a leaf's parent is 1, etc. 
> Note that in an R*-Tree, all branches from the root Node will be the same
> height.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:96: RecordBase(const Rect& rect);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> From
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Explic...
> : Declare single-arg constructors "explicit".

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:110: DISALLOW_COPY_AND_ASSIGN(RecordBase);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> This declaration must always be private.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:126: // Nodes with |parent_| NULL. Note that
ownership of this Node is transfered
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: transferred

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:166: Node(int level);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: explicit

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:169: // and BuildHighBounds() returns the index of
the element in those arrays
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Comma before "returns"

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:171: // overlap (area of interesection) in the two
groups.
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: intersection

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:182: // to equality, or is the most square. When
splitting we decide to split
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: "to equality, or" -> "i.e."

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:223: 
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: I'd remove blank lines between uncommented functions in an OVERRIDE group

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:229: // |candidate_node| child is indicated by
index in |children_|, and
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: This seems slightly out-of-date as the function no longer takes an
argument
> that is an index.  Perhaps just "Here |candidate_node| is one of our
> |children_|,"?

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:275: // Supports re-insertion of Nodes based on
the strategies outlined in
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Maybe:
> 
> Re-inserts |node| into the tree.  The reinsertion point is chosen based on the
> strategies outlined in Beckmann et al.  ...
> 
> (Or you can replace the second sentence with a brief description of the
> strategy)

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:278: // recommended value for all initial calls to
InsertNode.
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Maybe this last sentence should be: "This should always be set to -1
except
> by recursive calls from within InsertNode()."

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:279: void InsertNode(NodeBase* node, int*
highset_reinsert_level);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: highest

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:281: // Supports removal of nodes for tree without
deletion.
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Maybe:
> 
> Removes |node| from the tree without deleting it.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:285: scoped_ptr<Node> root_;
On 2014/05/29 00:32:26, Peter Kasting wrote:
> I don't believe there was a "private:" declaration above this line, so all
these
> members, and the DISALLOW... macro functions, are actually being declared
> protected.  These should be private, with accessors as needed by RTree.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_unittest.cc (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:35: // root's potential inconsistencies.
On 2014/05/29 00:32:26, Peter Kasting wrote:
> I don't actually know what this comment means.
I explained it better in the comments above, removed this comment.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:36: for (size_t i = 0; i <
rt->root_->children_.size(); ++i) {
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Use count() (many places)

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:38: rt->root_->children_[i],
rt->min_children_, rt->max_children_);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Use child() (many places)

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:52: for (size_t i = 0; i <
node->children_.size(); ++i) {
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Unlike r_tree_base.cc, this file consistently uses {} on one-line loop
> bodies, so it's not necessary to remove them; but I might consider removing
them
> to be consistent with that file (and the majority of Chrome code).

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:80: // Given an unordered list of matching
keys, verify that it contains all
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: verifies

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:82: void VerifyAllKeys(const
base::hash_set<int>& keys) {
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Use the RT::Matches typedef in place of hash_set<> everywhere (many
places)

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:90: // ith element of the rectangle is union
of the recangle of the ith child of
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: element of the rectangle -> element of the list

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:118: RTreeNode* NewNodeAtLevel(size_t level)
{ return new RTreeBase::Node(level); }
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Since the caller must take ownership, return a scoped_ptr.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:213: // Should have gotten back 1 node
pointers.
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: pointer

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:240: // One rect with lower y than another
should always sort lower than higher y.
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Remove "than higher y"

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:325: // It should not add any overlap to add
this to the first child at (0, 0);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Trailing period, not semicolon.  Similarly, the subsequent comments
should
> all end with periods.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:380: EXPECT_EQ(Rect(0, 0, i + 1, i + 1),
vertical_bounds[i]);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Seems like this first arg is equivalent to "records[i]->rect()" -- would it
make
> any more sense to compare against this?

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:396: EXPECT_EQ(Rect(i, i, 25 - i, 25 - i),
vertical_bounds[i]);
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Similar comment.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:463: // Clear out old bounds first.
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Perhaps the remainder of this function should be in a second test since
it
> doesn't really want to preserve any state from the code above.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:537: RTreeRecord* child_one(new
RTreeRecord(Rect(0, 0, 1, 1), 1));
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Use scoped_ptrs instead of raw pointers in all cases where you call "new".
(Many
> places in this file)
> 
> Note that in this case, that means your RemoveChild() calls will have to
> reference child(i) instead of a raw pointer you have sitting around.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:625: // This prevents a crash due to
double-delete on test exit, as no node should
On 2014/05/29 00:32:26, Peter Kasting wrote:
> What would double-free otherwise?  Seems like we should never be in a state
> where there's double ownership.

By not using raw pointers to wrap these objects. |nodes| owns all the Node
objects, but nodes[0] also owns nodes[1] and nodes[2] as they are currently
children of nodes[0].

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:942: // Add the nodes back in.
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Nit: Maybe blank line above this?

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:978: // Add 100 positive stacked squares.
On 2014/05/29 00:32:26, Peter Kasting wrote:
> Similarly, maybe blank lines above the commented code blocks in this function.

Done.

Peter Kasting

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_base.cc File ui/gfx/geometry/r_tree_base.cc (right): https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_base.cc#newcode624 ui/gfx/geometry/r_tree_base.cc:624: if (parent) { On 2014/05/30 16:51:04, luken wrote: > ...

6 years, 6 months ago (2014-05-30 18:51:17 UTC) #17

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.cc (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:624: if (parent) {
On 2014/05/30 16:51:04, luken wrote:
> On 2014/05/29 00:32:26, Peter Kasting wrote:
> > Nit: No {}
> really? even with the else below? if you say so..

There are two legal options:
(1) Braces on all loops/conditionals
(2) Braces omitted on loops/conditionals where all arms are one physical line

Since the file doesn't consistently do (1), option (2) means removing braces
here, since both arms of the conditional are just one line.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.h (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:29: typedef std::list<const RecordBase*> Records;
On 2014/05/30 16:51:04, luken wrote:
> On 2014/05/29 00:32:26, Peter Kasting wrote:
> > Are you sure you want a list rather than a vector?  Are you going to be
doing
> > insertion in the beginning/middle, and no random access?
> I don't need any random access. I don't do any insertions or deletions in the
> middle of the list. I went with list because if you don't need random access
it
> will generally be faster than vector on insertions and deletions yes? Or is
that
> not so?

I don't think it's clear-cut.  A list needs to heap-allocate a new node every
time you do an insertion, and free that node upon deletion.  A vector can
insert/delete at the end with only some bookkeeping cost if the reservation is
larger than the current size, but if it grows too large, needs to re-allocate
and move all the elements.

So a list is slightly more expensive in the common case, and a vector is
noticeably more expensive occasionally.

Complicating things, because a vector uses a contiguous block of memory, access
to elements often hits the processor data cache.  A list's nodes aren't
necessarily localized in memory, so access may trigger more cache misses.

> Based on feedback from this and other reviews, it seems that senior Chrome
> engineers have a strong preference for vector over list, even when random
access
> isn't needed. I'm happy to change this to a vector - but can you please tell
me
> why you think that is?

According to Effective STL, the C++ Standard itself suggests using vector by
default, and list when insertion in the middle is desired.  (I haven't been able
to pull up the standard to verify this.)  Google searches for the question of
vector versus list lead to benchmarks showing that, in general, appending many
elements to a list is slower than a vector.  Finally, because there's such a
common convention that a vector is the right "generic container", using
something else suggests to the reader that your code needs the particular
advantages of a list, which you don't here.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_unittest.cc (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:625: // This prevents a crash due to
double-delete on test exit, as no node should
On 2014/05/30 16:51:04, luken wrote:
> On 2014/05/29 00:32:26, Peter Kasting wrote:
> > What would double-free otherwise?  Seems like we should never be in a state
> > where there's double ownership.
> 
> By not using raw pointers to wrap these objects. |nodes| owns all the Node
> objects, but nodes[0] also owns nodes[1] and nodes[2] as they are currently
> children of nodes[0].

That indicates that this test is buggy.  Because AddChild() causes the parent to
take ownership of the child, we should never be doing an AddChild() followed by
placing the same node pointer into a ScopedVector.

It looks to me as if the code should look more like this (but with comments):

  scoped_ptr<RTreeNode> root_node(NewNodeAtLevel(2));

  std::vector<RTreeNode*> level_one_nodes;
  std::vector<RTreeRecord*> records;
  int record_counter = 0;
  for (size_t i = 0; i < 2; ++i) {
    scoped_ptr<RTreeNode> level_one_node(NewNodeAtLevel(1));
    level_one_nodes.push_back(level_one_node.get());
    for (size_t j = 0; j < 2; ++j) {
      scoped_ptr<RTreeNode> level_zero_node(new RTreeNode);
      for (size_t k = 0; k < 2; ++k) {
        scoped_ptr<RTreeRecord> record(new RTreeRecord(
            Rect(0, 0, record_counter, record_counter), record_counter + 1));
        records.push_back(record.get());
        level_zero_node->AddChild(record.PassAs<RTreeNodeBase>());
        ++record_counter;
      }
      level_one_node->AddChild(level_zero_node.Pass());
    }
    root_node->AddChild(level_one_node.Pass());
  }

  ValidateNode(root_node.get(), 2U, 2U);

  ScopedVector<RTreeNodeBase> orphans;
  for (std::vector<RTreeNode*>::iterator i(level_one_nodes.begin());
       i != level_one_nodes.end(); ++i) {
    EXPECT_EQ(1U, (*i)->RemoveChild((*i)->child(0), &orphans));
    EXPECT_EQ(0U, (*i)->RemoveChild((*i)->child(0), &orphans));
  }

  ...rest of test continues here

This ensures that heap-allocated objects are always owned by exactly one other
object at all times.

luken

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_base.cc File ui/gfx/geometry/r_tree_base.cc (right): https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_base.cc#newcode624 ui/gfx/geometry/r_tree_base.cc:624: if (parent) { On 2014/05/30 18:51:18, Peter Kasting wrote: ...

6 years, 6 months ago (2014-05-30 19:23:38 UTC) #18

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.cc (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:624: if (parent) {
On 2014/05/30 18:51:18, Peter Kasting wrote:
> On 2014/05/30 16:51:04, luken wrote:
> > On 2014/05/29 00:32:26, Peter Kasting wrote:
> > > Nit: No {}
> > really? even with the else below? if you say so..
> 
> There are two legal options:
> (1) Braces on all loops/conditionals
> (2) Braces omitted on loops/conditionals where all arms are one physical line
> 
> Since the file doesn't consistently do (1), option (2) means removing braces
> here, since both arms of the conditional are just one line.

Done.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.h (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:29: typedef std::list<const RecordBase*> Records;
On 2014/05/30 18:51:18, Peter Kasting wrote:
> On 2014/05/30 16:51:04, luken wrote:
> > On 2014/05/29 00:32:26, Peter Kasting wrote:
> > > Are you sure you want a list rather than a vector?  Are you going to be
> doing
> > > insertion in the beginning/middle, and no random access?
> > I don't need any random access. I don't do any insertions or deletions in
the
> > middle of the list. I went with list because if you don't need random access
> it
> > will generally be faster than vector on insertions and deletions yes? Or is
> that
> > not so?
> 
> I don't think it's clear-cut.  A list needs to heap-allocate a new node every
> time you do an insertion, and free that node upon deletion.  A vector can
> insert/delete at the end with only some bookkeeping cost if the reservation is
> larger than the current size, but if it grows too large, needs to re-allocate
> and move all the elements.
> 
> So a list is slightly more expensive in the common case, and a vector is
> noticeably more expensive occasionally.
> 
> Complicating things, because a vector uses a contiguous block of memory,
access
> to elements often hits the processor data cache.  A list's nodes aren't
> necessarily localized in memory, so access may trigger more cache misses.
> 
> > Based on feedback from this and other reviews, it seems that senior Chrome
> > engineers have a strong preference for vector over list, even when random
> access
> > isn't needed. I'm happy to change this to a vector - but can you please tell
> me
> > why you think that is?
> 
> According to Effective STL, the C++ Standard itself suggests using vector by
> default, and list when insertion in the middle is desired.  (I haven't been
able
> to pull up the standard to verify this.)  Google searches for the question of
> vector versus list lead to benchmarks showing that, in general, appending many
> elements to a list is slower than a vector.  Finally, because there's such a
> common convention that a vector is the right "generic container", using
> something else suggests to the reader that your code needs the particular
> advantages of a list, which you don't here.

I changed it to a vector. Thanks for the detailed explanation.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_unittest.cc (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:625: // This prevents a crash due to
double-delete on test exit, as no node should
On 2014/05/30 18:51:18, Peter Kasting wrote:
> On 2014/05/30 16:51:04, luken wrote:
> > On 2014/05/29 00:32:26, Peter Kasting wrote:
> > > What would double-free otherwise?  Seems like we should never be in a
state
> > > where there's double ownership.
> > 
> > By not using raw pointers to wrap these objects. |nodes| owns all the Node
> > objects, but nodes[0] also owns nodes[1] and nodes[2] as they are currently
> > children of nodes[0].
> 
> That indicates that this test is buggy.  Because AddChild() causes the parent
to
> take ownership of the child, we should never be doing an AddChild() followed
by
> placing the same node pointer into a ScopedVector.
> 
> It looks to me as if the code should look more like this (but with comments):
> 
>   scoped_ptr<RTreeNode> root_node(NewNodeAtLevel(2));
> 
>   std::vector<RTreeNode*> level_one_nodes;
>   std::vector<RTreeRecord*> records;
>   int record_counter = 0;
>   for (size_t i = 0; i < 2; ++i) {
>     scoped_ptr<RTreeNode> level_one_node(NewNodeAtLevel(1));
>     level_one_nodes.push_back(level_one_node.get());
>     for (size_t j = 0; j < 2; ++j) {
>       scoped_ptr<RTreeNode> level_zero_node(new RTreeNode);
>       for (size_t k = 0; k < 2; ++k) {
>         scoped_ptr<RTreeRecord> record(new RTreeRecord(
>             Rect(0, 0, record_counter, record_counter), record_counter + 1));
>         records.push_back(record.get());
>         level_zero_node->AddChild(record.PassAs<RTreeNodeBase>());
>         ++record_counter;
>       }
>       level_one_node->AddChild(level_zero_node.Pass());
>     }
>     root_node->AddChild(level_one_node.Pass());
>   }
> 
>   ValidateNode(root_node.get(), 2U, 2U);
> 
>   ScopedVector<RTreeNodeBase> orphans;
>   for (std::vector<RTreeNode*>::iterator i(level_one_nodes.begin());
>        i != level_one_nodes.end(); ++i) {
>     EXPECT_EQ(1U, (*i)->RemoveChild((*i)->child(0), &orphans));
>     EXPECT_EQ(0U, (*i)->RemoveChild((*i)->child(0), &orphans));
>   }
> 
>   ...rest of test continues here
> 
> This ensures that heap-allocated objects are always owned by exactly one other
> object at all times.

So storage of raw pointer values is OK within vectors but not individually? What
is the rule here?

luken

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_unittest.cc File ui/gfx/geometry/r_tree_unittest.cc (right): https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_unittest.cc#newcode625 ui/gfx/geometry/r_tree_unittest.cc:625: // This prevents a crash due to double-delete on ...

6 years, 6 months ago (2014-05-30 19:39:33 UTC) #19

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_unittest.cc (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:625: // This prevents a crash due to
double-delete on test exit, as no node should
On 2014/05/30 19:23:39, luken wrote:
> On 2014/05/30 18:51:18, Peter Kasting wrote:
> > On 2014/05/30 16:51:04, luken wrote:
> > > On 2014/05/29 00:32:26, Peter Kasting wrote:
> > > > What would double-free otherwise?  Seems like we should never be in a
> state
> > > > where there's double ownership.
> > > 
> > > By not using raw pointers to wrap these objects. |nodes| owns all the Node
> > > objects, but nodes[0] also owns nodes[1] and nodes[2] as they are
currently
> > > children of nodes[0].
> > 
> > That indicates that this test is buggy.  Because AddChild() causes the
parent
> to
> > take ownership of the child, we should never be doing an AddChild() followed
> by
> > placing the same node pointer into a ScopedVector.
> > 
> > It looks to me as if the code should look more like this (but with
comments):
> > 
> >   scoped_ptr<RTreeNode> root_node(NewNodeAtLevel(2));
> > 
> >   std::vector<RTreeNode*> level_one_nodes;
> >   std::vector<RTreeRecord*> records;
> >   int record_counter = 0;
> >   for (size_t i = 0; i < 2; ++i) {
> >     scoped_ptr<RTreeNode> level_one_node(NewNodeAtLevel(1));
> >     level_one_nodes.push_back(level_one_node.get());
> >     for (size_t j = 0; j < 2; ++j) {
> >       scoped_ptr<RTreeNode> level_zero_node(new RTreeNode);
> >       for (size_t k = 0; k < 2; ++k) {
> >         scoped_ptr<RTreeRecord> record(new RTreeRecord(
> >             Rect(0, 0, record_counter, record_counter), record_counter +
1));
> >         records.push_back(record.get());
> >         level_zero_node->AddChild(record.PassAs<RTreeNodeBase>());
> >         ++record_counter;
> >       }
> >       level_one_node->AddChild(level_zero_node.Pass());
> >     }
> >     root_node->AddChild(level_one_node.Pass());
> >   }
> > 
> >   ValidateNode(root_node.get(), 2U, 2U);
> > 
> >   ScopedVector<RTreeNodeBase> orphans;
> >   for (std::vector<RTreeNode*>::iterator i(level_one_nodes.begin());
> >        i != level_one_nodes.end(); ++i) {
> >     EXPECT_EQ(1U, (*i)->RemoveChild((*i)->child(0), &orphans));
> >     EXPECT_EQ(0U, (*i)->RemoveChild((*i)->child(0), &orphans));
> >   }
> > 
> >   ...rest of test continues here
> > 
> > This ensures that heap-allocated objects are always owned by exactly one
other
> > object at all times.
> 
> So storage of raw pointer values is OK within vectors but not individually?
What
> is the rule here?
Additionally, how should I delete the nodes in level_one_nodes? With a for loop?
Or put them back in scoped_ptr somewhere after the call to RemoveChild()?

Peter Kasting

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_unittest.cc File ui/gfx/geometry/r_tree_unittest.cc (right): https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_unittest.cc#newcode625 ui/gfx/geometry/r_tree_unittest.cc:625: // This prevents a crash due to double-delete on ...

6 years, 6 months ago (2014-05-30 19:49:30 UTC) #20

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_unittest.cc (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:625: // This prevents a crash due to
double-delete on test exit, as no node should
On 2014/05/30 19:23:39, luken wrote:
> On 2014/05/30 18:51:18, Peter Kasting wrote:
> > This ensures that heap-allocated objects are always owned by exactly one
other
> > object at all times.
> 
> So storage of raw pointer values is OK within vectors but not individually?
What
> is the rule here?

The key is in my previous comment: heap-allocated objects should always be owned
by exactly one other object at all times.

As long as such an object is owned, you can have an arbitrarily large number of
additional raw pointers pointing to it (but must make sure no one uses those
pointers after the object is destroyed).  What you don't want is _only_ raw
pointers to an object, or more than one object thinking it owns the pointer.

BAD:

  Foo* f = new Foo();
  Foo* g = f;
  std::vector<Foo*> foo_vec;
  foo_vec.push_back(f);
  // Three pointers to the object, but none owns it.
  // It will leak unless we manually delete one of the pointers.

ALSO BAD:

  scoped_ptr<Foo> f(new Foo());
  ScopedVector<Foo> foo_vec;
  foo_vec.push_back(f.get());
  // Two objects that both think they own the same Foo.
  // It will be double-freed unless we eliminate one of the
  // owning relationships.

GOOD:

  scoped_ptr<Foo> f(new Foo());
  Foo* raw_f = f.get();
  std::vector<Foo*> foo_vec;
  foo_vec.push_back(raw_f);
  // Three different references to the Foo, but only one owns it.
  // The others are weak (raw), we merely need to ensure they're
  // not used after the Foo is deleted.

ALSO GOOD:

  scoped_ptr<Foo> f(new Foo());
  ScopedVector<Foo> foo_vec;
  foo_vec.push_back(f.release());
  // Again, only one object owns the Foo.

In other words, whether raw pointers are OK has nothing to do with whether
they're alone or in a container; it's all about ensuring that an object is owned
by exactly one thing.  Your existing code double-owns the objects.

> Additionally, how should I delete the nodes in level_one_nodes? With a for
loop?
> Or put them back in scoped_ptr somewhere after the call to RemoveChild()?

Ah, I missed the fact that RemoveChild() removes the child in question from the
ownership hierarchy, but neither frees it nor explicitly returns ownership of it
to the caller.  That means the code I wrote leaks the removed children.  This is
really a symptom of the problem that the RemoveChild() API is easy to misuse.

If RemoveChild() makes the child in question no longer owned, but doesn't free
it outright, it should pass ownership back to the caller, like so:

scoped_ptr<NodeBase> RemoveChild(NodeBase* child, Nodes* orphans);

This way, callers who wish to preserve the child can do so, and callers who
ignore the return value will cause the child to be deleted, avoiding a memory
leak.

This does force callers who want to know the number of remaining children to
explicitly call count(); I don't think that's too bad, but if you viewed it as a
huge problem, you could pass a size_t outparam.

Once this API change is made, this unittest code should be pretty
straightforward.

luken

PTAL, thanks. https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_unittest.cc File ui/gfx/geometry/r_tree_unittest.cc (right): https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_unittest.cc#newcode625 ui/gfx/geometry/r_tree_unittest.cc:625: // This prevents a crash due to ...

6 years, 6 months ago (2014-06-03 21:04:58 UTC) #21

PTAL, thanks.

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_unittest.cc (right):

https://codereview.chromium.org/269513002/diff/250001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:625: // This prevents a crash due to
double-delete on test exit, as no node should
On 2014/05/30 19:49:31, Peter Kasting wrote:
> On 2014/05/30 19:23:39, luken wrote:
> > On 2014/05/30 18:51:18, Peter Kasting wrote:
> > > This ensures that heap-allocated objects are always owned by exactly one
> other
> > > object at all times.
> > 
> > So storage of raw pointer values is OK within vectors but not individually?
> What
> > is the rule here?
> 
> The key is in my previous comment: heap-allocated objects should always be
owned
> by exactly one other object at all times.
> 
> As long as such an object is owned, you can have an arbitrarily large number
of
> additional raw pointers pointing to it (but must make sure no one uses those
> pointers after the object is destroyed).  What you don't want is _only_ raw
> pointers to an object, or more than one object thinking it owns the pointer.
> 
> BAD:
> 
>   Foo* f = new Foo();
>   Foo* g = f;
>   std::vector<Foo*> foo_vec;
>   foo_vec.push_back(f);
>   // Three pointers to the object, but none owns it.
>   // It will leak unless we manually delete one of the pointers.
> 
> ALSO BAD:
> 
>   scoped_ptr<Foo> f(new Foo());
>   ScopedVector<Foo> foo_vec;
>   foo_vec.push_back(f.get());
>   // Two objects that both think they own the same Foo.
>   // It will be double-freed unless we eliminate one of the
>   // owning relationships.
> 
> GOOD:
> 
>   scoped_ptr<Foo> f(new Foo());
>   Foo* raw_f = f.get();
>   std::vector<Foo*> foo_vec;
>   foo_vec.push_back(raw_f);
>   // Three different references to the Foo, but only one owns it.
>   // The others are weak (raw), we merely need to ensure they're
>   // not used after the Foo is deleted.
> 
> ALSO GOOD:
> 
>   scoped_ptr<Foo> f(new Foo());
>   ScopedVector<Foo> foo_vec;
>   foo_vec.push_back(f.release());
>   // Again, only one object owns the Foo.
> 
> In other words, whether raw pointers are OK has nothing to do with whether
> they're alone or in a container; it's all about ensuring that an object is
owned
> by exactly one thing.  Your existing code double-owns the objects.
> 
> > Additionally, how should I delete the nodes in level_one_nodes? With a for
> loop?
> > Or put them back in scoped_ptr somewhere after the call to RemoveChild()?
> 
> Ah, I missed the fact that RemoveChild() removes the child in question from
the
> ownership hierarchy, but neither frees it nor explicitly returns ownership of
it
> to the caller.  That means the code I wrote leaks the removed children.  This
is
> really a symptom of the problem that the RemoveChild() API is easy to misuse.
> 
> If RemoveChild() makes the child in question no longer owned, but doesn't free
> it outright, it should pass ownership back to the caller, like so:
> 
> scoped_ptr<NodeBase> RemoveChild(NodeBase* child, Nodes* orphans);
> 
> This way, callers who wish to preserve the child can do so, and callers who
> ignore the return value will cause the child to be deleted, avoiding a memory
> leak.
> 
> This does force callers who want to know the number of remaining children to
> explicitly call count(); I don't think that's too bad, but if you viewed it as
a
> huge problem, you could pass a size_t outparam.
> 
> Once this API change is made, this unittest code should be pretty
> straightforward.
The refactor is done. I had a question about a technique, which I've left as a
comment in the review on the latest patch set.

https://codereview.chromium.org/269513002/diff/310001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.cc (right):

https://codereview.chromium.org/269513002/diff/310001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:592: InsertNode(reinsert_node.Pass(),
highest_reinsert_level);
so this technique of extracting a pointer from a ScopedVector and placing it in
a scoped_ptr is also repeated below in RemoveNode. It results in
double-ownership of the pointer for 1 line of code. The alternative I could
think of was no ownership for one line:

NodeBase* temp_ptr(*last_element);
reinserts.weak_erase(last_element);
InsertNode(scoped_ptr<NodeBase>(temp_ptr), ...);

Which do you think is best? Or is there another, more elegant way to do this?

Peter Kasting

(Re-review is still TBD) https://codereview.chromium.org/269513002/diff/310001/ui/gfx/geometry/r_tree_base.cc File ui/gfx/geometry/r_tree_base.cc (right): https://codereview.chromium.org/269513002/diff/310001/ui/gfx/geometry/r_tree_base.cc#newcode592 ui/gfx/geometry/r_tree_base.cc:592: InsertNode(reinsert_node.Pass(), highest_reinsert_level); On 2014/06/03 21:04:59, ...

6 years, 6 months ago (2014-06-03 21:20:57 UTC) #22

luken

https://codereview.chromium.org/269513002/diff/310001/ui/gfx/geometry/r_tree_base.cc File ui/gfx/geometry/r_tree_base.cc (right): https://codereview.chromium.org/269513002/diff/310001/ui/gfx/geometry/r_tree_base.cc#newcode592 ui/gfx/geometry/r_tree_base.cc:592: InsertNode(reinsert_node.Pass(), highest_reinsert_level); On 2014/06/03 21:20:57, Peter Kasting wrote: > ...

6 years, 6 months ago (2014-06-03 21:25:00 UTC) #23

Peter Kasting

I think this is pretty much done. No huge issues remain. Many of the things ...

6 years, 6 months ago (2014-06-03 23:52:19 UTC) #24

luken

PTAL, thanks https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree.h File ui/gfx/geometry/r_tree.h (right): https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree.h#newcode39 ui/gfx/geometry/r_tree.h:39: // that. On 2014/06/03 23:52:18, Peter Kasting ...

6 years, 6 months ago (2014-06-04 18:12:02 UTC) #25

PTAL, thanks

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree.h
File ui/gfx/geometry/r_tree.h (right):

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:39: // that.
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Wow, this comment is awesome.  Just wanted to give you kudos for it.

Thanks!

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:54: const Rect& query_rect, Matches* matches_out)
const;
On 2014/06/03 23:52:17, Peter Kasting wrote:
> Nit: This is completely legal style, but it's a bit more common in Chrome to
> wrap like:
> 
>   void AppendIntersectingRecords(const Rect& query_rect,
>                                  Matches* matches_out) const;
> 
> Up to you.  (Same comment a few places in the other files.)
Yeah I prefer the aligned arguments style, and I'll switch to that where I can.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree....
ui/gfx/geometry/r_tree.h:171: : RecordBase(rect),
On 2014/06/03 23:52:17, Peter Kasting wrote:
> Nit: Still needs to be indented 4 before the colon (not 2)

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.cc (right):

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:358: high_bounds[start_index]).size().GetArea();
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Heh, the indenting you did here is the one indenting that isn't correct :). 
> Lines of args should always start at the same place, so you can do any of
these:
> 
>   int smallest_overlap_area = UnionRects(
>       low_bounds[start_index], high_bounds[start_index]).size().GetArea();
> 
>   int smallest_overlap_area = UnionRects(
>       low_bounds[start_index],
>       high_bounds[start_index]).size().GetArea();
> 
>   int smallest_overlap_area =
>       UnionRects(low_bounds[start_index],
>                  high_bounds[start_index]).size().GetArea();
> 
>   int smallest_overlap_area =
>       UnionRects(
>           low_bounds[start_index], high_bounds[start_index]).size().GetArea();
> 
> Personally, I prefer the first (because it's shorter) or the third over the
> others, but they're all legal.

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:393: for (; i != (low_bounds.begin() +
end_index); ++i, ++j)
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Nit: You do need {} on this because the body is more than one physical line
> (even though it's only one logical statement).
Ah, so it's physical line, not logical line. Good to know, thanks.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:514: best_node->rect().size().GetArea()) {
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Nit: I'm not sure of the rule on this, but for clarity, I'd probably indent
this
> a further 4 as a continuation of the previous line.

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:588: while (reinserts.size()) {
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Nit: Prefer "!empty()" to using "size()" as a boolean (2 places)

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:621: scoped_ptr<NodeBase>
removed_child(parent->RemoveChild(child, &orphans));
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Seems like you can just call parent->RemoveChild() without putting the result
> into a temporary scoped_ptr that will just be deleted anyway.

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:643: void RTreeBase::PruneRoot() {
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Should we perhaps DCHECK that the root has exactly one child, and the child is
a
> Node and not a Record?
> 
> It might be even better to name this something like PruneRootIfNecessary() and
> move the conditional from the lone callsite (that guarantees the above) into
> this method, so the method cannot be misused.
Yeah I like that. Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:644: root_.reset(
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Nit: Perhaps say that the ugly reset(cast(release)) pattern here is because
> there's no better way to downcast the scoped_ptr from
RemoveAndReturnLastChild()
> from NodeBase to Node.

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.cc:645:
static_cast<Node*>(root_->RemoveAndReturnLastChild().release()));
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Nit: Indent 4, not 6

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.h (right):

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:68: const NodeBase* const_parent() const { return
parent_; }
On 2014/06/03 23:52:18, Peter Kasting wrote:
> From
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Functi...
> :
> 
> "Accessors ... should match the name of the variable they are getting and
> setting."  So name this parent() instead of const_parent().  (It won't collide
> with the non-const symbol name.)
Cool, I like your construction better. Question - how does this fit with our
policy about overloads? I thought all overloading was verboten?

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:75: friend class RTreeNodeTest;
On 2014/06/03 23:52:18, Peter Kasting wrote:
> From
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...
> :
> 
> "Friend declarations should always be in the private section"

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:141: // list. Returns the |child_node| in a
scoped_ptr as the node is
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Nit: This sentence can just be "Returns the removed child."  The bit about
> ownership is clear from the signature.

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:161: const NodeBase* const_child(size_t i) const {
return children_[i]; }
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Nit: See comment above

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:183: // to equality, or is the most square. When
splitting we decide to split
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Nit: I would still substitute "i.e." for "or" since you're restating your
> previous statement as opposed to providing an alternative.  Or just drop this
> clause.
> 
> I would probably also so "width and height differ the least" since that seems
> clearer to me than "closest to equality", but up to you, this is trivial
> nitpicking level :)

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:289: // Deletes the current |root_| and replaces
it with an empty Node.
On 2014/06/03 23:52:18, Peter Kasting wrote:
> This has the side effect of deleting the entire existing tree, right?  Perhaps
> the name/comment should reflect that more (they sound as if they act narrowly
on
> just the root node).

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_unittest.cc (right):

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:34: for (size_t i = 0; i <
rt->root()->count(); ++i)
On 2014/06/03 23:52:18, Peter Kasting wrote:
> Nit: {} (body is two physical lines)

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:114: return scoped_ptr<RTreeNode>(new
RTreeBase::Node(level));
On 2014/06/03 23:52:19, Peter Kasting wrote:
> Nit: RTreeBase::Node -> RTreeNode
> 
> Maybe use make_scoped_ptr()?
Sure, can you please tell me why the preference for that function? Is it that it
infers the type?

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:209: ScopedVector<RTreeNodeBase> removals;
On 2014/06/03 23:52:19, Peter Kasting wrote:
> Nit: The places you use this type would more correctly use RTreeBase::Nodes,
so
> that if you change the type in RTreeBase, the test code here will
automatically
> follow; I suggest making that typedef public within RTreeBase or forwarding it
> in the test fixture class.  (several places)

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:536: scoped_ptr<RTreeRecord>(new
RTreeRecord(Rect(0, 0, 1, 1), 1)));
On 2014/06/03 23:52:19, Peter Kasting wrote:
> Nit: Doesn't this need to use scoped_ptr<RTreeNodeBase>, as you do elsewhere? 
> (3 places)

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:576: records.reserve(8);
On 2014/06/03 23:52:19, Peter Kasting wrote:
> Nit: I wouldn't bother with these three reserve() calls for a couple reasons:
> (1) They're not going to do much since I believe in most STL implementations
> vectors start with a reservation of 10 or so.
> (2) Even if (1) is untrue, adding 8 elements isn't a noticeable perf cost.
> (3) Also, we don't really care about perf in this test (at least not to that
> level).
> (4) Given that (1)-(3) suggest that these don't help much, it's always better
to
> omit verbosity than have it, all else equal.

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:584: int id = (i << 2) + (j << 1) + k + 1;
On 2014/06/03 23:52:19, Peter Kasting wrote:
> Nit: This seems significantly less readable than simply declaring |id| at
> function scope, initialized to 0 or 1, and having a "++id" in this scope
before
> or after the use of |id| (depending).  Such code wouldn't even need a
clarifying
> comment.

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:605: for (size_t i = 0; i <
level_0_children.size(); ++i) {
On 2014/06/03 23:52:19, Peter Kasting wrote:
> Nit: No {}

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:613: ScopedVector<RTreeNodeBase>::iterator
svit = std::find(
On 2014/06/03 23:52:19, Peter Kasting wrote:
> Nit: I'd probably call this "orphan" (and maybe also call |it| "record").  If
> you're truly wedded to including "it" in the name, consider "orphans_it" or
> something like that.

Done.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:631: scoped_ptr<RTreeNodeBase>
last_child(test_parent->child(2));
On 2014/06/03 23:52:18, Peter Kasting wrote:
> This makes me uneasy, because if for some reason RemoveAndReturnLastChild() in
> the next line removed a different child than you expected, that child would
> leak, and this one would get freed while still being owned.
> 
> I would do this instead:
> 
>   RTreeNodeBase* child = test_parent->child(2);
>   scoped_ptr<RTreeNodeBase>
last_child(test_parent->RemoveAndReturnLastChild());
>   EXPECT_EQ(child, last_child.get());
> 
> (You can then continue to use |child| and |last_child| in the blocks below if
> you want.)

Done.

Peter Kasting

(Re-review TBD) https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_base.h File ui/gfx/geometry/r_tree_base.h (right): https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_base.h#newcode68 ui/gfx/geometry/r_tree_base.h:68: const NodeBase* const_parent() const { return parent_; ...

6 years, 6 months ago (2014-06-04 18:21:39 UTC) #26

(Re-review TBD)

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_base.h (right):

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_base.h:68: const NodeBase* const_parent() const { return
parent_; }
On 2014/06/04 18:12:03, luken wrote:
> On 2014/06/03 23:52:18, Peter Kasting wrote:
> > From
> >
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Functi...
> > :
> > 
> > "Accessors ... should match the name of the variable they are getting and
> > setting."  So name this parent() instead of const_parent().  (It won't
collide
> > with the non-const symbol name.)
> Cool, I like your construction better. Question - how does this fit with our
> policy about overloads? I thought all overloading was verboten?

Nope, overloading is OK when it doesn't cause confusion.  See
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Functi...
.  In particular, unless it is extraordinarily important to the reader to know
whether a const or non-const version of a method is being called, overloads that
only differ by constness are basically always OK.

Operator overloading is much more restricted.

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
File ui/gfx/geometry/r_tree_unittest.cc (right):

https://codereview.chromium.org/269513002/diff/330001/ui/gfx/geometry/r_tree_...
ui/gfx/geometry/r_tree_unittest.cc:114: return scoped_ptr<RTreeNode>(new
RTreeBase::Node(level));
On 2014/06/04 18:12:03, luken wrote:
> On 2014/06/03 23:52:19, Peter Kasting wrote:
> > Nit: RTreeBase::Node -> RTreeNode
> > 
> > Maybe use make_scoped_ptr()?
> Sure, can you please tell me why the preference for that function? Is it that
it
> infers the type?

It's a very minor preference.  It infers the type, which is slightly nicer for
maintenance.  It's usually slightly shorter and fractionally more plain-English
to read.  Other than that there's no difference, so it's certainly not required.

It's a little unfortunate IMO that make_scoped_ptr() doesn't work like C++11's
make_unique(), which has some exception-safety benefits that make_scoped_ptr()
doesn't confer.  Of course, Google C++ doesn't use exceptions, but it's always
better to be in the habit of writing theoretically-exception-safe code where
possible.

Peter Kasting

On 2014/06/11 18:19:06, luken wrote: > ping, PTAL, thanks! Oops, this fell off my stack. ...

6 years, 6 months ago (2014-06-11 18:21:30 UTC) #28

Peter Kasting

LGTM. Congrats! Hopefully you feel like the end result here is a more readable, maintainable ...

6 years, 6 months ago (2014-06-11 18:58:56 UTC) #29

luken

Thanks for all your hard work on this review! I learned a lot. https://codereview.chromium.org/269513002/diff/350001/ui/gfx/geometry/r_tree_unittest.cc File ...

6 years, 6 months ago (2014-06-11 21:06:31 UTC) #30

commit-bot: I haz the power

CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/luken@chromium.org/269513002/360001

6 years, 6 months ago (2014-06-12 16:18:14 UTC) #34

commit-bot: I haz the power

CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/luken@chromium.org/269513002/380001

6 years, 6 months ago (2014-06-12 18:10:10 UTC) #37

Message was sent while issue was closed.

Change committed as 276827

Issue 269513002: readability review for luken (Closed)

Description

Patch Set 1 #

Patch Set 2 : [WIP] - response to first round of comments #

Patch Set 3 : upload for wfh #

Patch Set 4 : [WIP] mostly there #

Patch Set 5 : first round of feedback done. #

Patch Set 6 : unit tests now hoist #

Patch Set 7 : work on Node/Record split. #

Patch Set 8 : checkpoint before templatizing #

Patch Set 9 : #

Patch Set 10 : uploading for read-through #

Patch Set 11 : ready for next round of feedbac #

Patch Set 12 : rebased #

Patch Set 13 : [WIP] checkpoint #

Patch Set 14 : #

Patch Set 15 : ready for next round of feedback, thanks #

Patch Set 16 : change Records typedef to vector #

Patch Set 17 : Remove*() returns a scoped ptr #

Patch Set 18 : switch to no owners #

Patch Set 19 : responding to latest round of feedback, thanks #

Patch Set 20 : some clang fixes #

Patch Set 21 : clang repairs #

Messages