readability review for luken

ui/gfx/geometry/r_tree.h

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef UI_GFX_GEOMETRY_R_TREE_H_
 #define UI_GFX_GEOMETRY_R_TREE_H_
 
 #include <vector>
 
 #include "base/containers/hash_tables.h"
 #include "base/gtest_prod_util.h"
 #include "base/macros.h"
 #include "base/memory/scoped_ptr.h"
 #include "base/memory/scoped_vector.h"
 #include "ui/gfx/geometry/rect.h"
 #include "ui/gfx/gfx_export.h"
 
 namespace gfx {
 
 // Defines a heirarchical bounding rectangle data structure for Rect objects,
 // associated with a generic unique key K for efficient spatial queries. The
 // R*-tree algorithm is used to build the trees. Based on the papers:

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

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

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

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?

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

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.

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

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.

 //
 // A Guttman 'R-trees:  a dynamic index structure for spatial searching', Proc
 // ACM SIGMOD Int Conf on Management of Data, 47-57, 1984
 //
 // N Beckmann, H-P Kriegel, R Schneider, B Seeger 'The R*-tree: an efficient and
 // robust access method for points and rectangles', Proc ACM SIGMOD Int Conf on
 // Management of Data, 322-331, 1990
+//

[Peter Kasting, 2014/04/30 23:09:21]

Nit: Adding a blank comment line here seems slightly unusual.

[luken, 2014/04/30 23:20:18]

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.

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

Cool, no worries.

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

Removed the blank comment line.

 class GFX_EXPORT RTree {
  public:
   RTree(size_t min_children, size_t max_children);
   ~RTree();
 
   // Insert a new rect into the tree, associated with provided key. Note that if
   // rect is empty, this rect will not actually be inserted. Duplicate keys
   // overwrite old entries.
   void Insert(const Rect& rect, intptr_t key);
 
   // If present, remove the supplied key from the tree.
   void Remove(intptr_t key);
 
   // Fills a supplied list matches_out with all keys having bounding rects
   // intersecting query_rect.
   void Query(const Rect& query_rect,
              base::hash_set<intptr_t>* matches_out) const;
 
   // Removes all objects from the tree.
   void Clear();
 
  private:
   // Private data structure class for storing internal nodes or leaves with keys
   // of R-Trees. Note that "leaf" nodes can still have children, the children
   // will all be Nodes with non-NULL record pointers.

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

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.

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

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?

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

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.

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

Done.

   class GFX_EXPORT Node {

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

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.

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

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?

    public:
     // Level counts from -1 for "record" Nodes, that is Nodes that wrap key
     // values, to 0 for leaf Nodes, that is Nodes that only have record
     // children, up to the root Node, which has level equal to the height of the
     // tree.

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

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.

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

Your assumption is correct. I made it explicit in the comment, which I moved to
the level_ member variable as this ctor is deprecated.

     explicit Node(int level);

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

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.

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

I've made this constructor only for level 0 nodes, and added two methods
MakeParent() and MakeSibling().

 
     // Builds a new record Node.
     Node(const Rect& rect, intptr_t key);

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

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.

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

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.

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

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.

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

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.

 
     virtual ~Node();
 
     // Deletes all children and any attached record.
     void Clear();

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

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.

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

Agreed, removed.

 
     // Recursive call to build a list of rects that intersect the query_rect.

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

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.

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

Ah, I thought it was only for member variables. I choose to try to apply it
consistently.

     void Query(const Rect& query_rect,
                base::hash_set<intptr_t>* matches_out) const;

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

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.

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

Done.

 
     // Recompute our bounds by taking the union of all children rects. Will then
     // call RecomputeBounds() on our parent for recursive bounds recalculation
     // up to the root.
     void RecomputeBounds();

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

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.

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

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()?

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

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.

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

Done.

 
     // Removes number_to_remove nodes from this Node, and appends them to the
     // supplied list. Does not repair bounds upon completion.

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

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.

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

Done.

     void RemoveNodesForReinsert(size_t number_to_remove,

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

Since the function name says "ForReinsert", consider commenting above what
reinsertion is and why it's in the name here.

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

Done.

                                 ScopedVector<Node>* nodes);
 
     // Given a pointer to a child node within this Node, remove it from our

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

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.

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

Done.

     // list. If that child had any children, append them to the supplied orphan
     // list. Returns the new count of this node after removal. Does not

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

I assume we do not recurse, so the orphans may be entire subtrees?

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

Yup.

     // recompute bounds, as this node itself may be removed if it now has too
     // few children.

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

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.

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

Done.

     size_t RemoveChild(Node* child_node, ScopedVector<Node>* orphans);
 
     // Does what it says on the tin. Returns NULL if no children. Does not

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

Nit: Remove first sentence.

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

Done.

     // recompute bounds.
     scoped_ptr<Node> RemoveAndReturnLastChild();
 
     // Given a node, returns the best fit node for insertion of that node at
     // the nodes level().

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

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?

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

Reworded.

     Node* ChooseSubtree(Node* node);
 
     // Adds the provided node to this Node. Returns the new count of records

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

Nit: to -> as a child of

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

Done.

     // stored in the Node. Will recompute the bounds of this node after

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

Nit: Will recompute -> Recomputes (but better yet, attach this to the first
sentence with "and")

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

Done.

     // addition.
     size_t AddChild(Node* node);

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

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

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

Done.

 
     // Returns a sibling to this Node with at least min_children and no greater
     // than max_children of this Node's children assigned to it, and having the
     // same parent. Bounds will be valid on both Nodes after this call.
     Node* Split(size_t min_children, size_t max_children);
 
     // For record nodes only, to support re-insert, allows setting the rect.
     void SetRect(const Rect& rect);
 
     // Returns a pointer to the parent of this Node, or NULL if no parent.
     Node* parent() const { return parent_; }

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

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)

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

Done.

 
     // 0 level() would mean that this Node is a leaf. 1 would mean that this
     // Node has children that are leaves. Calling level() on root_ returns the
     // height of the tree - 1. A level of -1 means that this is a Record node.

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

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.

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

Done.

     int level() const { return level_; }
 
     const Rect& rect() const { return rect_; }
 
     size_t count() const { return children_.size(); }
 
     intptr_t key() const { return key_; }
 
    private:
     // Returns all records stored in this node and its children.

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

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?

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

Done.

     void GetAllValues(base::hash_set<intptr_t>* matches_out) const;
 
     // Used for sorting Nodes along vertical and horizontal axes

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

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.

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

Done.

     static bool CompareVertical(Node* a, Node* b);

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

Prefer file-scoped helper functions in the .cc file over private statics where
possible.

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

I have unit tests for all three, so needed to leave them here, unless you know
of a workaround for that?

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

Nit: If the comment above applies to both these functions, no blank line here.

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

Done.

     static bool CompareHorizontal(Node* a, Node* b);
 
     static bool CompareCenterDistanceFromParent(Node* a, Node* b);
 
     // Returns the increase in overlap value, as defined in Beckmann et al as

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

Super-tiny nit: et al as -> et al. as

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

Done.

     // the sum of the areas of the intersection of each |children_| rectangle

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

Nit: each |children_| rectangle -> all child rectangles?

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

Done.

     // (excepting the candidate child) with the argument rectangle. The
     // expanded_rect argument is computed as the union of the candidate child
     // rect and the argument rect, and is included here to avoid recomputation.
     // Here the candidate child is indicated by index in |children_|, and
     // expanded_rect is the alread-computed union of candidate's rect and
     // rect.

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

You describe |expanded_rect| twice.  Only describe it once.

Can this method be const?

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

Yes, it can. Done.

     int OverlapIncreaseToAdd(const Rect& rect,
                              size_t candidate,
                              const Rect& expanded_rect);
 
     // Bounds recomputation without calling parents to do the same.
     void RecomputeBoundsNoParents();
 
     // Split() helper methods.
     //
     // Given two vectors of Nodes sorted by vertical or horizontal bounds, this
     // function populates two vectors of Rectangles in which the ith element is
     // the Union of all bounding rectangles [0,i] in the associated sorted array

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

Nit: Capitalizing Union here and below is odd

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

Done.

     // of Nodes.
     static void BuildLowBounds(const std::vector<Node*>& vertical_sort,

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

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.

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

Done.

                                const std::vector<Node*>& horizontal_sort,
                                std::vector<Rect>* vertical_bounds,

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

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.

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

Done.

                                std::vector<Rect>* horizontal_bounds);
 
     // Given two vectors of Nodes sorted by vertical or horizontal bounds, this
     // function populates two vectors of Rectangles in which the ith element is
     // the Union of all bounding rectangles [i, count()) in the associated
     // sorted array of Nodes.
     static void BuildHighBounds(const std::vector<Node*>& vertical_sort,
                                 const std::vector<Node*>& horizontal_sort,
                                 std::vector<Rect>* vertical_bounds,
                                 std::vector<Rect>* horizontal_bounds);
 
     // Returns true if this is a vertical split, false if a horizontal one.
     // Based on ChooseSplitAxis algorithm in Beckmann et al. Chooses the axis
     // with the lowest sum of margin values of bounding boxes.

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

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.

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

Done.

     static bool ChooseSplitAxis(const std::vector<Rect>& low_vertical_bounds,
                                 const std::vector<Rect>& high_vertical_bounds,
                                 const std::vector<Rect>& low_horizontal_bounds,
                                 const std::vector<Rect>& high_horizontal_bounds,
                                 size_t min_children,
                                 size_t max_children);
 
     // Used by SplitNode to calculate optimal index of split, after determining

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

There doesn't seem to be a function called SplitNode().

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

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

     // along which axis to sort and split the children rectangles. Returns the
     // index to the first element in the split children as sorted by the bounds
     // vectors.
     static size_t ChooseSplitIndex(size_t min_children,
                                    size_t max_children,
                                    const std::vector<Rect>& low_bounds,
                                    const std::vector<Rect>& high_bounds);
 
     // Takes our children_ and divides them into a new node, starting at index
     // split_index in sorted_children.

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

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

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

Done.

     Node* DivideChildren(const std::vector<Rect>& low_bounds,
                          const std::vector<Rect>& high_bounds,
                          const std::vector<Node*>& sorted_children,
                          size_t split_index);
 
     // Returns a pointer to the child node that will result in the least overlap
     // increase with the addition of node_rect, as defined in the Beckmann et al
     // paper, or NULL if there's a tie found. Requires a precomputed vector of

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

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.

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

Done.

     // expanded rectangles where the ith rectangle in the vector is the union of
     // |children_|[i] and node_rect.

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

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.

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

Done.

     Node* LeastOverlapIncrease(const Rect& node_rect,
                                const std::vector<Rect>& expanded_rects);
 
     // Returns a pointer to the child node that will result in the least area
     // enlargement if the argument node rectangle were to be added to that
     // nodes' bounding box. Requires a precomputed vector of expanded rectangles
     // where the ith rectangle in the vector is the union of |children_|[i] and
     // node_rect.
     Node* LeastAreaEnlargement(const Rect& node_rect,
                                const std::vector<Rect>& expanded_rects);
 
     // This Node's bounding rectangle.
     Rect rect_;
 
     // The height of the node in the tree, counting from -1 at the record node
     // to 0 at the leaf up to the root node which has level equal to the height
     // of the tree.
     int level_;

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

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.

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

Done.

 
     // Pointers to all of our children Nodes.

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

Nit: children -> child

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

Done.

     ScopedVector<Node> children_;

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

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"

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

Done.

 
     // A weak pointer to our parent Node in the RTree. The root node will have a
     // NULL value for |parent_|.
     Node* parent_;
 
     // If this is a record Node, then |key_| will be non-NULL and will contain
     // the key data. Otherwise, NULL.

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

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.

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

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

     intptr_t key_;
 
     friend class RTreeTest;
     FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildHighBounds);

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

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, 2014/05/08 00:00:08]

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, 2014/05/08 18:08:21]

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, 2014/05/14 00:12:04]

Oh I didn't know that! Done.

     FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildLowBounds);
     FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSplitAxisAndIndex);
     FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSubtree);
     FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareCenterDistanceFromParent);
     FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareHorizontal);
     FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareVertical);
     FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeDivideChildren);
     FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastAreaEnlargement);
     FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastOverlapIncrease);
     FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeOverlapIncreaseToAdd);
@@ skipping 41 matching lines @@
   FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildOrphans);
   FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveNodesForReinsert);
   FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeSplit);
 
   DISALLOW_COPY_AND_ASSIGN(RTree);
 };
 
 }  // namespace gfx
 
 #endif  // UI_GFX_GEOMETRY_R_TREE_H_