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

Side by Side Diff: trunk/src/ui/gfx/geometry/r_tree_base.h

Issue 338833004: Revert 276827 "readability review for luken" (Closed) Base URL: svn://svn.chromium.org/chrome/
Patch Set: 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 unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « trunk/src/ui/gfx/geometry/r_tree.cc ('k') | trunk/src/ui/gfx/geometry/r_tree_base.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright 2014 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // Provides an implementation the parts of the RTree data structure that don't
6 // require knowledge of the generic key type. Don't use these objects directly,
7 // rather specialize the RTree<> object in r_tree.h. This file defines the
8 // internal objects of an RTree, namely Nodes (internal nodes of the tree) and
9 // Records, which hold (key, rectangle) pairs.
10
11 #ifndef UI_GFX_GEOMETRY_R_TREE_BASE_H_
12 #define UI_GFX_GEOMETRY_R_TREE_BASE_H_
13
14 #include <list>
15 #include <vector>
16
17 #include "base/containers/hash_tables.h"
18 #include "base/macros.h"
19 #include "base/memory/scoped_ptr.h"
20 #include "base/memory/scoped_vector.h"
21 #include "ui/gfx/geometry/rect.h"
22 #include "ui/gfx/gfx_export.h"
23
24 namespace gfx {
25
26 class GFX_EXPORT RTreeBase {
27 protected:
28 class NodeBase;
29 class RecordBase;
30
31 typedef std::vector<const RecordBase*> Records;
32 typedef ScopedVector<NodeBase> Nodes;
33
34 RTreeBase(size_t min_children, size_t max_children);
35 ~RTreeBase();
36
37 // Protected data structure class for storing internal Nodes or leaves with
38 // Records.
39 class GFX_EXPORT NodeBase {
40 public:
41 virtual ~NodeBase();
42
43 // Appends to |records_out| the set of Records in this subtree with rects
44 // that intersect |query_rect|. Avoids clearing |records_out| so that it
45 // can be called recursively.
46 virtual void AppendIntersectingRecords(const Rect& query_rect,
47 Records* records_out) const = 0;
48
49 // Returns all records stored in the subtree rooted at this node. Appends to
50 // |matches_out| without clearing.
51 virtual void AppendAllRecords(Records* records_out) const = 0;
52
53 // Returns NULL if no children. Does not recompute bounds.
54 virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() = 0;
55
56 // Returns -1 for Records, or the height of this subtree for Nodes. The
57 // height of a leaf Node (a Node containing only Records) is 0, a leaf's
58 // parent is 1, etc. Note that in an R*-Tree, all branches from the root
59 // Node will be the same height.
60 virtual int Level() const = 0;
61
62 // Recomputes our bounds by taking the union of all child rects, then calls
63 // recursively on our parent so that ultimately all nodes up to the root
64 // recompute their bounds.
65 void RecomputeBoundsUpToRoot();
66
67 NodeBase* parent() { return parent_; }
68 const NodeBase* parent() const { return parent_; }
69 void set_parent(NodeBase* parent) { parent_ = parent; }
70 const Rect& rect() const { return rect_; }
71 void set_rect(const Rect& rect) { rect_ = rect; }
72
73 protected:
74 NodeBase(const Rect& rect, NodeBase* parent);
75
76 // Bounds recomputation without calling parents to do the same.
77 virtual void RecomputeLocalBounds();
78
79 private:
80 friend class RTreeTest;
81 friend class RTreeNodeTest;
82
83 // This Node's bounding rectangle.
84 Rect rect_;
85
86 // A weak pointer to our parent Node in the RTree. The root node will have a
87 // NULL value for |parent_|.
88 NodeBase* parent_;
89
90 DISALLOW_COPY_AND_ASSIGN(NodeBase);
91 };
92
93 class GFX_EXPORT RecordBase : public NodeBase {
94 public:
95 explicit RecordBase(const Rect& rect);
96 virtual ~RecordBase();
97
98 virtual void AppendIntersectingRecords(const Rect& query_rect,
99 Records* records_out) const OVERRIDE;
100 virtual void AppendAllRecords(Records* records_out) const OVERRIDE;
101 virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE;
102 virtual int Level() const OVERRIDE;
103
104 private:
105 friend class RTreeTest;
106 friend class RTreeNodeTest;
107
108 DISALLOW_COPY_AND_ASSIGN(RecordBase);
109 };
110
111 class GFX_EXPORT Node : public NodeBase {
112 public:
113 // Constructs an empty Node with |level_| of 0.
114 Node();
115 virtual ~Node();
116
117 virtual void AppendIntersectingRecords(const Rect& query_rect,
118 Records* records_out) const OVERRIDE;
119 virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE;
120 virtual int Level() const OVERRIDE;
121 virtual void AppendAllRecords(Records* matches_out) const OVERRIDE;
122
123 // Constructs a new Node that is the parent of this Node and already has
124 // this Node as its sole child. Valid to call only on root Nodes, meaning
125 // Nodes with |parent_| NULL. Note that ownership of this Node is
126 // transferred to the parent returned by this function.
127 scoped_ptr<Node> ConstructParent();
128
129 // Removes |number_to_remove| children from this Node, and appends them to
130 // the supplied list. Does not repair bounds upon completion. Nodes are
131 // selected in the manner suggested in the Beckmann et al. paper, which
132 // suggests that the children should be sorted by the distance from the
133 // center of their bounding rectangle to their parent's bounding rectangle,
134 // and then the n closest children should be removed for re-insertion. This
135 // removal occurs at most once on each level of the tree when overflowing
136 // nodes that have exceeded the maximum number of children during an Insert.
137 void RemoveNodesForReinsert(size_t number_to_remove, Nodes* nodes);
138
139 // Given a pointer to a child node within this Node, removes it from our
140 // list. If that child had any children, appends them to the supplied orphan
141 // list. Returns the removed child. Does not recompute bounds, as the caller
142 // might subsequently remove this node as well, meaning the recomputation
143 // would be wasted work.
144 scoped_ptr<NodeBase> RemoveChild(NodeBase* child_node, Nodes* orphans);
145
146 // Returns the best parent for insertion of the provided |node| as a child.
147 Node* ChooseSubtree(NodeBase* node);
148
149 // Adds |node| as a child of this Node, and recomputes the bounds of this
150 // node after the addition of the child. Returns the new count of children
151 // stored in this Node. This node becomes the owner of |node|.
152 size_t AddChild(scoped_ptr<NodeBase> node);
153
154 // Returns a sibling to this Node with at least min_children and no greater
155 // than max_children of this Node's children assigned to it, and having the
156 // same parent. Bounds will be valid on both Nodes after this call.
157 scoped_ptr<NodeBase> Split(size_t min_children, size_t max_children);
158
159 size_t count() const { return children_.size(); }
160 const NodeBase* child(size_t i) const { return children_[i]; }
161 NodeBase* child(size_t i) { return children_[i]; }
162
163 private:
164 typedef std::vector<Rect> Rects;
165
166 explicit Node(int level);
167
168 // Given two arrays of bounds rectangles as computed by BuildLowBounds()
169 // and BuildHighBounds(), returns the index of the element in those arrays
170 // along which a split of the arrays would result in a minimum amount of
171 // overlap (area of intersection) in the two groups.
172 static size_t ChooseSplitIndex(size_t start_index,
173 size_t end_index,
174 const Rects& low_bounds,
175 const Rects& high_bounds);
176
177 // R*-Tree attempts to keep groups of rectangles that are roughly square
178 // in shape. It does this by comparing the "margins" of different bounding
179 // boxes, where margin is defined as the sum of the length of all four sides
180 // of a rectangle. For two rectangles of equal area, the one with the
181 // smallest margin will be the rectangle whose width and height differ the
182 // least. When splitting we decide to split along an axis chosen from the
183 // rectangles either sorted vertically or horizontally by finding the axis
184 // that would result in the smallest sum of margins between the two bounding
185 // boxes of the resulting split. Returns the smallest sum computed given the
186 // sorted bounding boxes and a range to look within.
187 static int SmallestMarginSum(size_t start_index,
188 size_t end_index,
189 const Rects& low_bounds,
190 const Rects& high_bounds);
191
192 // Sorts nodes primarily by increasing y coordinates, and secondarily by
193 // increasing height.
194 static bool CompareVertical(const NodeBase* a, const NodeBase* b);
195
196 // Sorts nodes primarily by increasing x coordinates, and secondarily by
197 // increasing width.
198 static bool CompareHorizontal(const NodeBase* a, const NodeBase* b);
199
200 // Sorts nodes by the distance of the center of their rectangles to the
201 // center of their parent's rectangles.
202 static bool CompareCenterDistanceFromParent(
203 const NodeBase* a, const NodeBase* b);
204
205 // Given two vectors of Nodes sorted by vertical or horizontal bounds,
206 // populates two vectors of Rectangles in which the ith element is the union
207 // of all bounding rectangles [0,i] in the associated sorted array of Nodes.
208 static void BuildLowBounds(const std::vector<NodeBase*>& vertical_sort,
209 const std::vector<NodeBase*>& horizontal_sort,
210 Rects* vertical_bounds,
211 Rects* horizontal_bounds);
212
213 // Given two vectors of Nodes sorted by vertical or horizontal bounds,
214 // populates two vectors of Rectangles in which the ith element is the
215 // union of all bounding rectangles [i, count()) in the associated sorted
216 // array of Nodes.
217 static void BuildHighBounds(const std::vector<NodeBase*>& vertical_sort,
218 const std::vector<NodeBase*>& horizontal_sort,
219 Rects* vertical_bounds,
220 Rects* horizontal_bounds);
221
222 virtual void RecomputeLocalBounds() OVERRIDE;
223
224 // Returns the increase in overlap value, as defined in Beckmann et al. as
225 // the sum of the areas of the intersection of all child rectangles
226 // (excepting the candidate child) with the argument rectangle. Here the
227 // |candidate_node| is one of our |children_|, and |expanded_rect| is the
228 // already-computed union of the candidate's rect and |rect|.
229 int OverlapIncreaseToAdd(const Rect& rect,
230 const NodeBase* candidate_node,
231 const Rect& expanded_rect) const;
232
233 // Returns a new node containing children [split_index, count()) within
234 // |sorted_children|. Children before |split_index| remain with |this|.
235 scoped_ptr<NodeBase> DivideChildren(
236 const Rects& low_bounds,
237 const Rects& high_bounds,
238 const std::vector<NodeBase*>& sorted_children,
239 size_t split_index);
240
241 // Returns a pointer to the child node that will result in the least overlap
242 // increase with the addition of node_rect, or NULL if there's a tie found.
243 // Requires a precomputed vector of expanded rectangles where the ith
244 // rectangle in the vector is the union of |children_|[i] and node_rect.
245 // Overlap is defined in Beckmann et al. as the sum of the areas of
246 // intersection of all child rectangles with the |node_rect| argument
247 // rectangle. This heuristic attempts to choose the node for which adding
248 // the new rectangle to their bounding box will result in the least overlap
249 // with the other rectangles, thus trying to preserve the usefulness of the
250 // bounding rectangle by keeping it from covering too much redundant area.
251 Node* LeastOverlapIncrease(const Rect& node_rect,
252 const Rects& expanded_rects);
253
254 // Returns a pointer to the child node that will result in the least area
255 // enlargement if the argument node rectangle were to be added to that
256 // node's bounding box. Requires a precomputed vector of expanded rectangles
257 // where the ith rectangle in the vector is the union of children_[i] and
258 // |node_rect|.
259 Node* LeastAreaEnlargement(const Rect& node_rect,
260 const Rects& expanded_rects);
261
262 const int level_;
263
264 Nodes children_;
265
266 friend class RTreeTest;
267 friend class RTreeNodeTest;
268
269 DISALLOW_COPY_AND_ASSIGN(Node);
270 };
271
272 // Inserts |node| into the tree. The |highest_reinsert_level| supports
273 // re-insertion as described by Beckmann et al. As Node overflows progagate
274 // up the tree the algorithm performs a reinsertion of the overflow Nodes
275 // (instead of a split) at most once per level of the tree. A starting value
276 // of -1 for |highest_reinsert_level| means that reinserts are permitted for
277 // every level of the tree. This should always be set to -1 except by
278 // recursive calls from within InsertNode().
279 void InsertNode(scoped_ptr<NodeBase> node, int* highest_reinsert_level);
280
281 // Removes |node| from the tree without deleting it.
282 scoped_ptr<NodeBase> RemoveNode(NodeBase* node);
283
284 // If |root_| has only one child, deletes the |root_| Node and replaces it
285 // with its only descendant child. Otherwise does nothing.
286 void PruneRootIfNecessary();
287
288 // Deletes the entire current tree and replaces it with an empty Node.
289 void ResetRoot();
290
291 const Node* root() const { return root_.get(); }
292
293 private:
294 friend class RTreeTest;
295 friend class RTreeNodeTest;
296
297 // A pointer to the root node in the RTree.
298 scoped_ptr<Node> root_;
299
300 // The parameters used to define the shape of the RTree.
301 const size_t min_children_;
302 const size_t max_children_;
303
304 DISALLOW_COPY_AND_ASSIGN(RTreeBase);
305 };
306
307 } // namespace gfx
308
309 #endif // UI_GFX_GEOMETRY_R_TREE_BASE_H_
OLDNEW
« no previous file with comments | « trunk/src/ui/gfx/geometry/r_tree.cc ('k') | trunk/src/ui/gfx/geometry/r_tree_base.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698