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 |