| OLD | NEW |
| 1 // Copyright (c) 2015 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2015 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 #ifndef CC_BASE_RTREE_H_ | 5 #ifndef CC_BASE_RTREE_H_ |
| 6 #define CC_BASE_RTREE_H_ | 6 #define CC_BASE_RTREE_H_ |
| 7 | 7 |
| 8 #include <stddef.h> | 8 #include <stddef.h> |
| 9 #include <stdint.h> | 9 #include <stdint.h> |
| 10 | 10 |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 45 DCHECK_EQ(0u, num_data_elements_); | 45 DCHECK_EQ(0u, num_data_elements_); |
| 46 | 46 |
| 47 std::vector<Branch> branches; | 47 std::vector<Branch> branches; |
| 48 branches.reserve(items.size()); | 48 branches.reserve(items.size()); |
| 49 | 49 |
| 50 for (size_t i = 0; i < items.size(); i++) { | 50 for (size_t i = 0; i < items.size(); i++) { |
| 51 const gfx::Rect& bounds = bounds_getter(items[i]); | 51 const gfx::Rect& bounds = bounds_getter(items[i]); |
| 52 if (bounds.IsEmpty()) | 52 if (bounds.IsEmpty()) |
| 53 continue; | 53 continue; |
| 54 | 54 |
| 55 branches.push_back(Branch()); | 55 branches.emplace_back(i, bounds); |
| 56 Branch& branch = branches.back(); | |
| 57 branch.bounds = bounds; | |
| 58 branch.index = i; | |
| 59 } | 56 } |
| 60 | 57 |
| 61 num_data_elements_ = branches.size(); | 58 num_data_elements_ = branches.size(); |
| 62 if (num_data_elements_ == 1u) { | 59 if (num_data_elements_ == 1u) { |
| 63 nodes_.reserve(1); | 60 nodes_.reserve(1); |
| 64 Node* node = AllocateNodeAtLevel(0); | 61 Node* node = AllocateNodeAtLevel(0); |
| 65 node->num_children = 1; | 62 node->num_children = 1; |
| 66 node->children[0] = branches[0]; | 63 node->children[0] = branches[0]; |
| 67 root_.subtree = node; | 64 root_.subtree = node; |
| 68 root_.bounds = branches[0].bounds; | 65 root_.bounds = branches[0].bounds; |
| (...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 108 struct Branch { | 105 struct Branch { |
| 109 // When the node level is 0, then the node is a leaf and the branch has a | 106 // When the node level is 0, then the node is a leaf and the branch has a |
| 110 // valid index pointing to an element in the vector that was used to build | 107 // valid index pointing to an element in the vector that was used to build |
| 111 // this rtree. When the level is not 0, it's an internal node and it has a | 108 // this rtree. When the level is not 0, it's an internal node and it has a |
| 112 // valid subtree pointer. | 109 // valid subtree pointer. |
| 113 union { | 110 union { |
| 114 Node* subtree; | 111 Node* subtree; |
| 115 size_t index; | 112 size_t index; |
| 116 }; | 113 }; |
| 117 gfx::Rect bounds; | 114 gfx::Rect bounds; |
| 115 |
| 116 Branch() {} |
| 117 Branch(size_t index, const gfx::Rect& bounds) |
| 118 : index(index), bounds(bounds) {} |
| 118 }; | 119 }; |
| 119 | 120 |
| 120 struct Node { | 121 struct Node { |
| 121 uint16_t num_children; | 122 uint16_t num_children; |
| 122 uint16_t level; | 123 uint16_t level; |
| 123 Branch children[kMaxChildren]; | 124 Branch children[kMaxChildren]; |
| 125 |
| 126 explicit Node(uint16_t level) : num_children(0), level(level) {} |
| 124 }; | 127 }; |
| 125 | 128 |
| 126 void SearchRecursive(Node* root, | 129 void SearchRecursive(Node* root, |
| 127 const gfx::Rect& query, | 130 const gfx::Rect& query, |
| 128 std::vector<size_t>* results) const; | 131 std::vector<size_t>* results) const; |
| 129 | 132 |
| 130 // Consumes the input array. | 133 // Consumes the input array. |
| 131 Branch BuildRecursive(std::vector<Branch>* branches, int level); | 134 Branch BuildRecursive(std::vector<Branch>* branches, int level); |
| 132 Node* AllocateNodeAtLevel(int level); | 135 Node* AllocateNodeAtLevel(int level); |
| 133 | 136 |
| 134 // This is the count of data elements (rather than total nodes in the tree) | 137 // This is the count of data elements (rather than total nodes in the tree) |
| 135 size_t num_data_elements_; | 138 size_t num_data_elements_; |
| 136 Branch root_; | 139 Branch root_; |
| 137 std::vector<Node> nodes_; | 140 std::vector<Node> nodes_; |
| 138 | 141 |
| 139 DISALLOW_COPY_AND_ASSIGN(RTree); | 142 DISALLOW_COPY_AND_ASSIGN(RTree); |
| 140 }; | 143 }; |
| 141 | 144 |
| 142 } // namespace cc | 145 } // namespace cc |
| 143 | 146 |
| 144 #endif // CC_BASE_RTREE_H_ | 147 #endif // CC_BASE_RTREE_H_ |
| OLD | NEW |