Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(953)

Unified Diff: ui/gfx/geometry/r_tree_base.h

Issue 269513002: readability review for luken (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: clang repairs Created 6 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « ui/gfx/geometry/r_tree.cc ('k') | ui/gfx/geometry/r_tree_base.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: ui/gfx/geometry/r_tree_base.h
diff --git a/ui/gfx/geometry/r_tree_base.h b/ui/gfx/geometry/r_tree_base.h
new file mode 100644
index 0000000000000000000000000000000000000000..21dc86b2d4d8b5f4f0783dcb55a5ce0b52275cb1
--- /dev/null
+++ b/ui/gfx/geometry/r_tree_base.h
@@ -0,0 +1,309 @@
+// 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 NodeBase;
+ class RecordBase;
+
+ typedef std::vector<const RecordBase*> Records;
+ typedef ScopedVector<NodeBase> Nodes;
+
+ RTreeBase(size_t min_children, size_t max_children);
+ ~RTreeBase();
+
+ // Protected data structure class for storing internal Nodes or leaves with
+ // 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 AppendIntersectingRecords(const Rect& query_rect,
+ Records* records_out) const = 0;
+
+ // Returns all records stored in the subtree rooted at this node. Appends to
+ // |matches_out| without clearing.
+ virtual void AppendAllRecords(Records* records_out) const = 0;
+
+ // Returns NULL if no children. Does not recompute bounds.
+ virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() = 0;
+
+ // 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.
+ virtual 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_; }
+ const NodeBase* parent() const { return parent_; }
+ void set_parent(NodeBase* parent) { parent_ = parent; }
+ const Rect& rect() const { return rect_; }
+ void set_rect(const Rect& rect) { rect_ = rect; }
+
+ protected:
+ NodeBase(const Rect& rect, NodeBase* parent);
+
+ // Bounds recomputation without calling parents to do the same.
+ virtual void RecomputeLocalBounds();
+
+ private:
+ friend class RTreeTest;
+ friend class RTreeNodeTest;
+
+ // 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:
+ explicit RecordBase(const Rect& rect);
+ virtual ~RecordBase();
+
+ virtual void AppendIntersectingRecords(const Rect& query_rect,
+ Records* records_out) const OVERRIDE;
+ virtual void AppendAllRecords(Records* records_out) const OVERRIDE;
+ virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE;
+ virtual int Level() const OVERRIDE;
+
+ private:
+ friend class RTreeTest;
+ friend class RTreeNodeTest;
+
+ DISALLOW_COPY_AND_ASSIGN(RecordBase);
+ };
+
+ class GFX_EXPORT Node : public NodeBase {
+ public:
+ // Constructs an empty Node with |level_| of 0.
+ Node();
+ virtual ~Node();
+
+ virtual void AppendIntersectingRecords(const Rect& query_rect,
+ Records* records_out) const OVERRIDE;
+ virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE;
+ virtual int Level() const OVERRIDE;
+ virtual void AppendAllRecords(Records* matches_out) 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
+ // transferred 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 rectangle,
+ // 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 removed child. Does not recompute bounds, as the caller
+ // might subsequently remove this node as well, meaning the recomputation
+ // would be wasted work.
+ scoped_ptr<NodeBase> 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);
+
+ size_t count() const { return children_.size(); }
+ const NodeBase* child(size_t i) const { return children_[i]; }
+ NodeBase* child(size_t i) { return children_[i]; }
+
+ private:
+ typedef std::vector<Rect> Rects;
+
+ explicit Node(int level);
+
+ // Given two arrays of bounds rectangles as computed by BuildLowBounds()
+ // and BuildHighBounds(), returns the index of the element in those arrays
+ // along which a split of the arrays would result in a minimum amount of
+ // overlap (area of intersection) in the two groups.
+ 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 whose width and height differ the
+ // least. When splitting we decide to split 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(const NodeBase* a, const NodeBase* b);
+
+ // Sorts nodes primarily by increasing x coordinates, and secondarily by
+ // increasing width.
+ static bool CompareHorizontal(const NodeBase* a, const NodeBase* b);
+
+ // Sorts nodes by the distance of the center of their rectangles to the
+ // center of their parent's rectangles.
+ static bool CompareCenterDistanceFromParent(
+ const NodeBase* a, const 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;
+
+ // 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| is one of our |children_|, and |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);
+ };
+
+ // Inserts |node| into the tree. The |highest_reinsert_level| supports
+ // re-insertion as described by Beckmann et al. As Node overflows progagate
+ // up the tree the algorithm performs a reinsertion of the overflow Nodes
+ // (instead of a split) at most once per level of the tree. A starting value
+ // of -1 for |highest_reinsert_level| means that reinserts are permitted for
+ // every level of the tree. This should always be set to -1 except by
+ // recursive calls from within InsertNode().
+ void InsertNode(scoped_ptr<NodeBase> node, int* highest_reinsert_level);
+
+ // Removes |node| from the tree without deleting it.
+ scoped_ptr<NodeBase> RemoveNode(NodeBase* node);
+
+ // If |root_| has only one child, deletes the |root_| Node and replaces it
+ // with its only descendant child. Otherwise does nothing.
+ void PruneRootIfNecessary();
+
+ // Deletes the entire current tree and replaces it with an empty Node.
+ void ResetRoot();
+
+ const Node* root() const { return root_.get(); }
+
+ private:
+ friend class RTreeTest;
+ friend class RTreeNodeTest;
+
+ // A pointer to the root node in the RTree.
+ scoped_ptr<Node> root_;
+
+ // The parameters used to define the shape of the RTree.
+ const size_t min_children_;
+ const size_t max_children_;
+
+ DISALLOW_COPY_AND_ASSIGN(RTreeBase);
+};
+
+} // namespace gfx
+
+#endif // UI_GFX_GEOMETRY_R_TREE_BASE_H_
« no previous file with comments | « ui/gfx/geometry/r_tree.cc ('k') | ui/gfx/geometry/r_tree_base.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698