readability review for luken

ui/gfx/geometry/r_tree_base.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_BASE_H_
+#define UI_GFX_GEOMETRY_R_TREE_BASE_H_
+
+#include <list>
+#include <vector>
+
+#include "base/containers/hash_tables.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 {
+
+class GFX_EXPORT RTreeBase {
+ public:
+  RTreeBase(size_t min_children, size_t max_children);
+  virtual ~RTreeBase();

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

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.

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

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.

[Peter Kasting, 2014/05/21 20:26:44]

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.

+
+ protected:
+  class RecordBase;
+  typedef std::list<const RecordBase*> Records;
+
+  // Private data structure class for storing internal nodes or leaves with keys

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

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.

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

Done.

+  // of R-Trees. Note that "leaf" Nodes can still have children, the children
+  // will all be Records.
+  class GFX_EXPORT NodeBase {
+   public:
+    virtual ~NodeBase();
+    virtual void Query(const Rect& query_rect, Records* records_out) const = 0;

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

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)

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

Done.

+
+    // Recompute our bounds by taking the union of all children rects. Will then

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

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.

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

Done.

+    // call RecomputeBoundsUpToRoot() on our parent for recursive bounds
+    // recalculation up to the root.
+    void RecomputeBoundsUpToRoot();
+
+    // Returns NULL if no children. Does not recompute bounds.
+    virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() = 0;
+    virtual void GetAllValues(Records* records_out) const = 0;

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

Nit: Put a blank line above this if the comment above doesn't apply to it.

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

Done.

+
+    void SetParent(NodeBase* parent) { parent_ = parent; }

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

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

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

Done.

+
+    const Rect& rect() const { return rect_; }
+    NodeBase* parent() { return parent_; }
+    virtual const int level() const = 0;

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

Virtual functions should never be named unix_hacker()-style.

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

Done.

+
+   protected:
+    friend class RTreeTest;
+    friend class RTreeNodeTest;
+
+    NodeBase(const Rect& rect, NodeBase* parent);
+
+    // Bounds recomputation without calling parents to do the same.
+    virtual void RecomputeLocalBounds() = 0;
+
+    // This Node's bounding rectangle.
+    Rect rect_;

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

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)

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

Done.

+
+    // A weak pointer to our parent Node in the RTree. The root node will have a
+    // NULL value for |parent_|.
+    NodeBase* parent_;
+  };

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

DISALLOW_COPY_AND_ASSIGN (every class in this file)

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

Done.

+
+  class GFX_EXPORT RecordBase : public NodeBase {
+   public:
+    RecordBase(const Rect& rect);
+    virtual ~RecordBase();
+    // For record nodes only, to support re-insert, allows setting the rect.
+    void SetRect(const Rect& rect);
+    virtual void Query(const Rect& query_rect,
+                       Records* records_out) const OVERRIDE;
+    virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE;
+    virtual const int level() const OVERRIDE;
+
+   protected:
+    friend class RTreeTest;
+    friend class RTreeNodeTest;
+
+    virtual void RecomputeLocalBounds() OVERRIDE;
+    virtual void GetAllValues(Records* records_out) const OVERRIDE;
+  };
+
+  class GFX_EXPORT Node : public NodeBase {

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

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

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

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

[Peter Kasting, 2014/05/21 20:26:44]

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.

+   public:
+    // Constructs an empty Node with |level_| of 0.
+    Node();
+    virtual ~Node();
+
+    // Constructs a new Node that is the parent of this Node and already has
+    // this Node as its sole child. Valid to call only on root Nodes, meaning
+    // Nodes with |parent_| NULL. Note that ownership of this Node is transfered
+    // to the returned parent by this function.

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

Nit: returned parent -> parent returned

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

Done.

+    scoped_ptr<Node> MakeParent();

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

Perhaps this function and the next should be called "ConstructXXX", as "MakeXXX"
sounds like "turns this node into an XXX".

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

Done.

+
+    // Constucts a new Node that is the sibling of this Node which already
+    // has the same |parent_| and |level_| as this Node. Note that the new node
+    // will not have been added to the |parent_| as its bounds are still empty.

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

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.

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

Done.

+    scoped_ptr<Node> MakeSibling();
+
+    // Recursive call to build a set of keys from record Nodes with rects that
+    // intersect the |query_rect| in this subtree. Appends to |matches_out|

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

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.

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

Done.

+    // without clearing.
+    virtual void Query(const Rect& query_rect,
+                       Records* records_out) const OVERRIDE;
+
+    typedef ScopedVector<NodeBase> Nodes;

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

Based on
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...
, typedefs should be atop the section.

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

Done.

+
+    // Removes |number_to_remove| children from this Node, and appends them to
+    // the supplied list. Does not repair bounds upon completion. Nodes are
+    // selected in the manner suggested in the Beckmann et al. paper, which
+    // suggests that the children should be sorted by the distance from the
+    // center of their bounding rectangle to their parent's bounding retangle,
+    // and then the n closest children should be removed for re-insertion. This
+    // removal occurs at most once on each level of the tree when overflowing
+    // nodes that have exceeded the maximum number of children during an Insert.
+    void RemoveNodesForReinsert(size_t number_to_remove, Nodes* nodes);
+
+    // Given a pointer to a child node within this Node, removes it from our
+    // list. If that child had any children, appends them to the supplied orphan
+    // list. Returns the new count of this node after removal. Does not
+    // recompute bounds, as the caller might subsequently remove this node as
+    // well, meaning the recomputation would be wasted work.
+    size_t RemoveChild(NodeBase* child_node, Nodes* orphans);
+
+    // Returns NULL if no children. Does not recompute bounds.
+    virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE;
+
+    // Returns the best parent for insertion of the provided |node| as a child.
+    Node* ChooseSubtree(NodeBase* node);
+
+    // Adds |node| as a child of this Node, and recomputes the bounds of this
+    // node after the addition of the child. Returns the new count of children
+    // stored in this Node. This node becomes the owner of |node|.
+    size_t AddChild(scoped_ptr<NodeBase> node);
+
+    // 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);

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

This seems to return a new Node the caller is expected to take ownership of, so
it should return a scoped_ptr.

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

Done.

+
+    virtual const int level() const OVERRIDE;
+    const size_t count() const { return children_.size(); }
+
+   private:
+    typedef std::vector<Rect> Rects;
+    Node(int level);

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

Nit: I suggest a blank line above this

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

Done.

+
+    // Used by Split to calculate optimal index of split, after determining
+    // 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.

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

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.

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

Reworked the comment.

+    static size_t ChooseSplitIndex(size_t min_children,
+                                   size_t max_children,
+                                   const Rects& low_bounds,
+                                   const Rects& high_bounds);
+
+    // Returns the smallest sum of the margins of the pairs of rectangles at the
+    // same index within |low_bounds| and |high_bounds|.

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

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

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

Done.

+    static int SmallestMarginSum(size_t start_index,
+                                 size_t end_index,
+                                 const Rects& low_bounds,
+                                 const Rects& high_bounds);
+
+    // Sort nodes primarily by increasing y coordinates, and secondarily by

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

Nit: Sort -> Sorts, or "Used to sort" (several functions)

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

Done.

+    // increasing height.
+    static bool CompareVertical(NodeBase* a, NodeBase* b);
+
+    // Sort nodes primarily by increasing x coordinates, and secondarily by
+    // increasing width.
+    static bool CompareHorizontal(NodeBase* a, NodeBase* b);
+
+    // Sort nodes by the distance of the center of their rectangles to the
+    // center of their parent's rectangles.
+    static bool CompareCenterDistanceFromParent(NodeBase* a, NodeBase* b);
+
+    // Given two vectors of Nodes sorted by vertical or horizontal bounds, this
+    // function populates two vectors of Rectangles in which the ith element is

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

Nit: Remove "this function" (also in next comment)

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

Done.

+    // the union of all bounding rectangles [0,i] in the associated sorted array
+    // of Nodes.
+    static void BuildLowBounds(const std::vector<NodeBase*>& vertical_sort,
+                               const std::vector<NodeBase*>& horizontal_sort,
+                               Rects* vertical_bounds,
+                               Rects* 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<NodeBase*>& vertical_sort,
+                                const std::vector<NodeBase*>& horizontal_sort,
+                                Rects* vertical_bounds,
+                                Rects* horizontal_bounds);
+
+    virtual void RecomputeLocalBounds() OVERRIDE;
+
+    // Returns all records stored in the subtree rooted at this node. Appends to
+    // |matches_out| without clearing.

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

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.

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

Done.

+    virtual void GetAllValues(Records* matches_out) const OVERRIDE;
+
+    // Returns the increase in overlap value, as defined in Beckmann et al. as
+    // the sum of the areas of the intersection of all child rectangles
+    // (excepting the candidate child) with the argument rectangle. Here the
+    // candidate child is indicated by index in |children_|, and expanded_rect

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

Nit: "...Here |candidate| is the index of the candidate child within
|children_|, ..."

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

Done.

+    // is the already-computed union of candidate's rect and rect.

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

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)

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

Done.

+    int OverlapIncreaseToAdd(const Rect& rect,
+                             size_t candidate,
+                             const Rect& expanded_rect) const;
+
+    // Children [0, split_index) within |sorted_children| remain within this
+    // node, while children [split_index, count()) are assigned to the new node.

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

Nit: How about:

Returns a new node containing children [split_index, count()) within
|sorted_children|.  Children before |split_index| remain with |this|.

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

Done.

+    Node* DivideChildren(const Rects& low_bounds,

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

This seems to return a new Node the caller is expected to take ownership of, so
it should return a scoped_ptr.

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

Done.

+                         const Rects& high_bounds,
+                         const std::vector<NodeBase*>& 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, or NULL if there's a tie found.
+    // Requires a precomputed vector of expanded rectangles where the ith
+    // rectangle in the vector is the union of |children_|[i] and node_rect.
+    // Overlap is defined in Beckmann et al. as the sum of the areas of
+    // intersection of all child rectangles with the |node_rect| argument
+    // rectangle.  This heuristic attempts to choose the node for which adding
+    // the new rectangle to their bounding box will result in the least overlap
+    // with the other rectangles, thus trying to preserve the usefulness of the
+    // bounding rectangle by keeping it from covering too much redundant area.
+    Node* LeastOverlapIncrease(const Rect& node_rect,
+                               const Rects& 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

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

Nit: nodes -> node's

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

Done.

+    // where the ith rectangle in the vector is the union of children_[i] and
+    // |node_rect|.
+    Node* LeastAreaEnlargement(const Rect& node_rect,
+                               const Rects& expanded_rects);
+
+    // Level counts from -1 for "record" Nodes, that is Nodes that wrap key

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

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.

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

Done.

+    // 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. For an R*-Tree to be considered well-formed all branches of the
+    // tree must have equal height.
+    const int level_;
+
+    Nodes children_;
+
+    friend class RTreeTest;
+    friend class RTreeNodeTest;
+
+    DISALLOW_COPY_AND_ASSIGN(Node);
+  };
+
+  // Supports re-insertion of Nodes based on the strategies outlined in
+  // Beckmann et al.
+  void InsertNode(NodeBase* node, int* highset_reinsert_level);

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

Nit: You might want to note what -1 would mean for the second param.

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

Done.

+
+  // Supports removal of nodes for tree without deletion.
+  void RemoveNode(NodeBase* node);
+
+  // A pointer to the root node in the RTree.
+  scoped_ptr<Node> root_;
+
+  // The parameters used to define the shape of the RTree.
+  size_t min_children_;
+  size_t max_children_;
+
+  friend class RTreeTest;
+  friend class RTreeNodeTest;
+
+  DISALLOW_COPY_AND_ASSIGN(RTreeBase);
+};
+
+}  // namespace gfx
+
+#endif  // UI_GFX_GEOMETRY_R_TREE_BASE_H_