OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 // Provides an implementation the parts of the RTree data structure that don't | 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, | 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 | 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 | 8 // internal objects of an RTree, namely Nodes (internal nodes of the tree) and |
9 // Records, which hold (key, rectangle) pairs. | 9 // Records, which hold (key, rectangle) pairs. |
10 | 10 |
(...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
89 | 89 |
90 DISALLOW_COPY_AND_ASSIGN(NodeBase); | 90 DISALLOW_COPY_AND_ASSIGN(NodeBase); |
91 }; | 91 }; |
92 | 92 |
93 class GFX_EXPORT RecordBase : public NodeBase { | 93 class GFX_EXPORT RecordBase : public NodeBase { |
94 public: | 94 public: |
95 explicit RecordBase(const Rect& rect); | 95 explicit RecordBase(const Rect& rect); |
96 virtual ~RecordBase(); | 96 virtual ~RecordBase(); |
97 | 97 |
98 virtual void AppendIntersectingRecords(const Rect& query_rect, | 98 virtual void AppendIntersectingRecords(const Rect& query_rect, |
99 Records* records_out) const OVERRIDE; | 99 Records* records_out) const override; |
100 virtual void AppendAllRecords(Records* records_out) const OVERRIDE; | 100 virtual void AppendAllRecords(Records* records_out) const override; |
101 virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE; | 101 virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() override; |
102 virtual int Level() const OVERRIDE; | 102 virtual int Level() const override; |
103 | 103 |
104 private: | 104 private: |
105 friend class RTreeTest; | 105 friend class RTreeTest; |
106 friend class RTreeNodeTest; | 106 friend class RTreeNodeTest; |
107 | 107 |
108 DISALLOW_COPY_AND_ASSIGN(RecordBase); | 108 DISALLOW_COPY_AND_ASSIGN(RecordBase); |
109 }; | 109 }; |
110 | 110 |
111 class GFX_EXPORT Node : public NodeBase { | 111 class GFX_EXPORT Node : public NodeBase { |
112 public: | 112 public: |
113 // Constructs an empty Node with |level_| of 0. | 113 // Constructs an empty Node with |level_| of 0. |
114 Node(); | 114 Node(); |
115 virtual ~Node(); | 115 virtual ~Node(); |
116 | 116 |
117 virtual void AppendIntersectingRecords(const Rect& query_rect, | 117 virtual void AppendIntersectingRecords(const Rect& query_rect, |
118 Records* records_out) const OVERRIDE; | 118 Records* records_out) const override; |
119 virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE; | 119 virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() override; |
120 virtual int Level() const OVERRIDE; | 120 virtual int Level() const override; |
121 virtual void AppendAllRecords(Records* matches_out) const OVERRIDE; | 121 virtual void AppendAllRecords(Records* matches_out) const override; |
122 | 122 |
123 // Constructs a new Node that is the parent of this Node and already has | 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 | 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 | 125 // Nodes with |parent_| NULL. Note that ownership of this Node is |
126 // transferred to the parent returned by this function. | 126 // transferred to the parent returned by this function. |
127 scoped_ptr<Node> ConstructParent(); | 127 scoped_ptr<Node> ConstructParent(); |
128 | 128 |
129 // Removes |number_to_remove| children from this Node, and appends them to | 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 | 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 | 131 // selected in the manner suggested in the Beckmann et al. paper, which |
(...skipping 80 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
212 | 212 |
213 // Given two vectors of Nodes sorted by vertical or horizontal bounds, | 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 | 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 | 215 // union of all bounding rectangles [i, count()) in the associated sorted |
216 // array of Nodes. | 216 // array of Nodes. |
217 static void BuildHighBounds(const std::vector<NodeBase*>& vertical_sort, | 217 static void BuildHighBounds(const std::vector<NodeBase*>& vertical_sort, |
218 const std::vector<NodeBase*>& horizontal_sort, | 218 const std::vector<NodeBase*>& horizontal_sort, |
219 Rects* vertical_bounds, | 219 Rects* vertical_bounds, |
220 Rects* horizontal_bounds); | 220 Rects* horizontal_bounds); |
221 | 221 |
222 virtual void RecomputeLocalBounds() OVERRIDE; | 222 virtual void RecomputeLocalBounds() override; |
223 | 223 |
224 // Returns the increase in overlap value, as defined in Beckmann et al. as | 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 | 225 // the sum of the areas of the intersection of all child rectangles |
226 // (excepting the candidate child) with the argument rectangle. Here the | 226 // (excepting the candidate child) with the argument rectangle. Here the |
227 // |candidate_node| is one of our |children_|, and |expanded_rect| is 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|. | 228 // already-computed union of the candidate's rect and |rect|. |
229 int OverlapIncreaseToAdd(const Rect& rect, | 229 int OverlapIncreaseToAdd(const Rect& rect, |
230 const NodeBase* candidate_node, | 230 const NodeBase* candidate_node, |
231 const Rect& expanded_rect) const; | 231 const Rect& expanded_rect) const; |
232 | 232 |
(...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
300 // The parameters used to define the shape of the RTree. | 300 // The parameters used to define the shape of the RTree. |
301 const size_t min_children_; | 301 const size_t min_children_; |
302 const size_t max_children_; | 302 const size_t max_children_; |
303 | 303 |
304 DISALLOW_COPY_AND_ASSIGN(RTreeBase); | 304 DISALLOW_COPY_AND_ASSIGN(RTreeBase); |
305 }; | 305 }; |
306 | 306 |
307 } // namespace gfx | 307 } // namespace gfx |
308 | 308 |
309 #endif // UI_GFX_GEOMETRY_R_TREE_BASE_H_ | 309 #endif // UI_GFX_GEOMETRY_R_TREE_BASE_H_ |
OLD | NEW |