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.
+
+// Provides an implementation the parts of the RTree data structure that don't
+// require knowledge of the generic key type. Don't use these objects directly,
+// rather specialize the RTree<> object in r_tree.h. This file defines the
+// internal objects of an RTree, namely Nodes (internal nodes of the tree) and
+// Records, which hold (key, rectangle) pairs.
+
+#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 {
+ protected:
+  class RecordBase;
+  typedef std::list<const RecordBase*> Records;

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

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?

[luken, 2014/05/30 16:51:04]

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?

[Peter Kasting, 2014/05/30 18:51:18]

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

[luken, 2014/05/30 19:23:39]

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

+  class NodeBase;
+  typedef ScopedVector<NodeBase> Nodes;

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

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.

[luken, 2014/05/30 16:51:04]

Done.

+
+
+  friend class RTreeTest;
+  friend class RTreeNodeTest;

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

Nit: To match the order in r_tree.h, I'd probably place these above the
typedefs.

[luken, 2014/05/30 16:51:04]

Done.

+
+  RTreeBase(size_t min_children, size_t max_children);
+  ~RTreeBase();
+
+  // Private data structure class for storing internal Nodes or leaves with

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

This class isn't actually declared "private" in RTreeBase -- either do so or fix
the comment.

[luken, 2014/05/30 16:51:04]

Done.

+  // Records.
+  class GFX_EXPORT NodeBase {
+   public:
+    virtual ~NodeBase();
+
+    // 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.
+    virtual void Query(const Rect& query_rect, Records* records_out) const = 0;

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

Nit: Would it be any clearer to name this AppendIntersectingRecords()?

[luken, 2014/05/30 16:51:04]

Done.

+
+    // Returns NULL if no children. Does not recompute bounds.
+    virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() = 0;
+
+    // Returns all records stored in the subtree rooted at this node. Appends to
+    // |matches_out| without clearing.
+    virtual void GetAllValues(Records* records_out) const = 0;

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

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.

[luken, 2014/05/30 16:51:04]

Done.

+
+    // Level counts from -1 for Records to 0 for leaf Nodes, 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.

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

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.

[luken, 2014/05/30 16:51:04]

Done.

+    virtual const int Level() const = 0;
+
+    // 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.
+    void RecomputeBoundsUpToRoot();
+
+    NodeBase* parent() { return parent_; }
+    void set_parent(NodeBase* parent) { parent_ = parent; }
+    const Rect& rect() const { return rect_; }
+    void set_rect(const Rect& rect) { rect_ = rect; }
+
+   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();
+
+   private:
+    // This Node's bounding rectangle.
+    Rect rect_;
+
+    // A weak pointer to our parent Node in the RTree. The root node will have a
+    // NULL value for |parent_|.
+    NodeBase* parent_;
+
+    DISALLOW_COPY_AND_ASSIGN(NodeBase);
+  };
+
+  class GFX_EXPORT RecordBase : public NodeBase {
+   public:
+    RecordBase(const Rect& rect);

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

From
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Explic...
: Declare single-arg constructors "explicit".

[luken, 2014/05/30 16:51:04]

Done.

+    virtual ~RecordBase();
+
+    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 GetAllValues(Records* records_out) const OVERRIDE;
+
+    DISALLOW_COPY_AND_ASSIGN(RecordBase);

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

This declaration must always be private.

[luken, 2014/05/30 16:51:04]

Done.

+  };
+
+  class GFX_EXPORT Node : public NodeBase {
+   public:
+    // Constructs an empty Node with |level_| of 0.
+    Node();
+    virtual ~Node();
+
+    virtual void Query(const Rect& query_rect,
+                       Records* records_out) const OVERRIDE;
+    virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE;
+    virtual const int Level() const OVERRIDE;
+
+    // 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

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

Nit: transferred

[luken, 2014/05/30 16:51:04]

Done.

+    // to the parent returned by this function.
+    scoped_ptr<Node> ConstructParent();
+
+    // 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 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.
+    scoped_ptr<NodeBase> Split(size_t min_children, size_t max_children);
+
+    const size_t count() const { return children_.size(); }
+    const NodeBase* child(size_t i) const { return children_[i]; }
+
+   private:
+    typedef std::vector<Rect> Rects;
+
+    Node(int level);

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

Nit: explicit

[luken, 2014/05/30 16:51:04]

Done.

+
+    // Given two arrays of bounds rectangles as computed by BuildLowBounds()
+    // and BuildHighBounds() returns the index of the element in those arrays

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

Nit: Comma before "returns"

[luken, 2014/05/30 16:51:04]

Done.

+    // along which a split of the arrays would result in a minimum amount of
+    // overlap (area of interesection) in the two groups.

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

Nit: intersection

[luken, 2014/05/30 16:51:04]

Done.

+    static size_t ChooseSplitIndex(size_t start_index,
+                                   size_t end_index,
+                                   const Rects& low_bounds,
+                                   const Rects& high_bounds);
+
+    // R*-Tree attempts to keep groups of rectangles that are roughly square
+    // in shape. It does this by comparing the "margins" of different bounding
+    // boxes, where margin is defined as the sum of the length of all four sides
+    // of a rectangle. For two rectangles of equal area, the one with the
+    // smallest margin will be the rectangle that has width and height closest,
+    // to equality, or is the most square. When splitting we decide to split

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

Nit: "to equality, or" -> "i.e."

[luken, 2014/05/30 16:51:04]

Done.

+    // along an axis chosen from the rectangles either sorted vertically or
+    // horizontally by finding the axis that would result in the smallest sum of
+    // margins between the two bounding boxes of the resulting split. Returns
+    // the smallest sum computed given the sorted bounding boxes and a range to
+    // look within.
+    static int SmallestMarginSum(size_t start_index,
+                                 size_t end_index,
+                                 const Rects& low_bounds,
+                                 const Rects& high_bounds);
+
+    // Sorts nodes primarily by increasing y coordinates, and secondarily by
+    // increasing height.
+    static bool CompareVertical(NodeBase* a, NodeBase* b);
+
+    // Sorts nodes primarily by increasing x coordinates, and secondarily by
+    // increasing width.
+    static bool CompareHorizontal(NodeBase* a, NodeBase* b);
+
+    // Sorts 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,
+    // populates two vectors of Rectangles in which the ith element is 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,
+    // 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;
+

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

Nit: I'd remove blank lines between uncommented functions in an OVERRIDE group

[luken, 2014/05/30 16:51:04]

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_node| child is indicated by index in |children_|, and

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

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_|,"?

[luken, 2014/05/30 16:51:04]

Done.

+    // |expanded_rect| is the already-computed union of the candidate's rect and
+    // |rect|.
+    int OverlapIncreaseToAdd(const Rect& rect,
+                             const NodeBase* candidate_node,
+                             const Rect& expanded_rect) const;
+
+    // Returns a new node containing children [split_index, count()) within
+    // |sorted_children|.  Children before |split_index| remain with |this|.
+    scoped_ptr<NodeBase> DivideChildren(
+        const Rects& low_bounds,
+        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
+    // node's 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 Rects& expanded_rects);
+
+    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

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

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)

[luken, 2014/05/30 16:51:04]

Done.

+  // Beckmann et al. A value of -1 for |highest_reinsert_level| means that
+  // reinserts are permitted for every level of the tree. This is the
+  // recommended value for all initial calls to InsertNode.

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

Nit: Maybe this last sentence should be: "This should always be set to -1 except
by recursive calls from within InsertNode()."

[luken, 2014/05/30 16:51:04]

Done.

+  void InsertNode(NodeBase* node, int* highset_reinsert_level);

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

Nit: highest

[luken, 2014/05/30 16:51:04]

Done.

+
+  // Supports removal of nodes for tree without deletion.

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

Nit: Maybe:

Removes |node| from the tree without deleting it.

[luken, 2014/05/30 16:51:04]

Done.

+  void RemoveNode(NodeBase* node);
+
+  // A pointer to the root node in the RTree.
+  scoped_ptr<Node> root_;

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

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.

[luken, 2014/05/30 16:51:04]

Done.

+
+  // The parameters used to define the shape of the RTree.
+  size_t min_children_;
+  size_t max_children_;
+
+  DISALLOW_COPY_AND_ASSIGN(RTreeBase);
+};
+
+}  // namespace gfx
+
+#endif  // UI_GFX_GEOMETRY_R_TREE_BASE_H_