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