OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 1 // Copyright 2016 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 #include "core/layout/ng/ng_layout_opportunity_iterator.h" | 5 #include "core/layout/ng/ng_layout_opportunity_iterator.h" |
6 | 6 |
7 #include "core/layout/ng/ng_physical_constraint_space.h" | 7 #include "core/layout/ng/ng_physical_constraint_space.h" |
8 #include "core/layout/ng/ng_units.h" | 8 #include "core/layout/ng/ng_units.h" |
9 #include "wtf/NonCopyingSort.h" | 9 #include "wtf/NonCopyingSort.h" |
10 | 10 |
11 namespace blink { | 11 namespace blink { |
12 namespace { | 12 namespace { |
13 | 13 |
14 // Collects all opportunities from leaves of Layout Opportunity spatial tree. | 14 // Collects all opportunities from leaves of Layout Opportunity spatial tree. |
15 void CollectAllOpportunities(const NGLayoutOpportunityTreeNode* node, | 15 void CollectAllOpportunities(const NGLayoutOpportunityTreeNode* node, |
16 NGLayoutOpportunities& opportunities) { | 16 NGLayoutOpportunities& opportunities) { |
17 if (!node) | 17 if (!node) |
18 return; | 18 return; |
19 if (node->IsLeafNode()) | 19 if (node->IsLeafNode()) |
20 opportunities.append(node->opportunity); | 20 opportunities.append(node->opportunity); |
21 CollectAllOpportunities(node->left, opportunities); | 21 CollectAllOpportunities(node->left, opportunities); |
22 CollectAllOpportunities(node->bottom, opportunities); | 22 CollectAllOpportunities(node->bottom, opportunities); |
23 CollectAllOpportunities(node->right, opportunities); | 23 CollectAllOpportunities(node->right, opportunities); |
24 } | 24 } |
25 | 25 |
| 26 // Creates layout opportunity from the provided space and the origin point. |
| 27 NGLayoutOpportunity CreateLayoutOpportunityFromConstraintSpace( |
| 28 const NGConstraintSpace& space, |
| 29 const NGLogicalOffset& origin_point) { |
| 30 NGLayoutOpportunity opportunity; |
| 31 opportunity.offset = space.Offset(); |
| 32 opportunity.size = space.Size(); |
| 33 |
| 34 // adjust to the origin_point. |
| 35 opportunity.offset += origin_point; |
| 36 opportunity.size.inline_size -= origin_point.inline_offset; |
| 37 opportunity.size.block_size -= origin_point.block_offset; |
| 38 return opportunity; |
| 39 } |
| 40 |
26 // Whether 2 edges overlap with each other. | 41 // Whether 2 edges overlap with each other. |
27 bool IsOverlapping(const NGEdge& edge1, const NGEdge& edge2) { | 42 bool IsOverlapping(const NGEdge& edge1, const NGEdge& edge2) { |
28 return std::max(edge1.start, edge2.start) <= std::min(edge1.end, edge2.end); | 43 return std::max(edge1.start, edge2.start) <= std::min(edge1.end, edge2.end); |
29 } | 44 } |
30 | 45 |
31 // Whether the exclusion is out of bounds of the LayoutNG constraint space. | 46 // Whether the exclusion is out of bounds of the LayoutNG constraint space. |
32 bool IsExclusionWithinSpace(const NGLayoutOpportunity& opportunity, | 47 bool IsExclusionWithinSpace(const NGLayoutOpportunity& opportunity, |
33 const NGExclusion& exclusion) { | 48 const NGExclusion& exclusion) { |
34 LayoutUnit left = opportunity.offset.inline_offset; | 49 LayoutUnit left = opportunity.offset.inline_offset; |
35 LayoutUnit top = opportunity.offset.block_offset; | 50 LayoutUnit top = opportunity.offset.block_offset; |
(...skipping 162 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
198 } | 213 } |
199 | 214 |
200 // TOP and LEFT are the same -> Sort by width | 215 // TOP and LEFT are the same -> Sort by width |
201 return rhs.size.inline_size < lhs.size.inline_size; | 216 return rhs.size.inline_size < lhs.size.inline_size; |
202 } | 217 } |
203 | 218 |
204 } // namespace | 219 } // namespace |
205 | 220 |
206 NGLayoutOpportunityIterator::NGLayoutOpportunityIterator( | 221 NGLayoutOpportunityIterator::NGLayoutOpportunityIterator( |
207 NGConstraintSpace* space, | 222 NGConstraintSpace* space, |
208 const NGLogicalOrigin origin_point, | 223 const NGLogicalOffset origin_point, |
209 const NGLogicalLeader leader_point) | 224 const NGLogicalOffset leader_point) |
210 : constraint_space_(space), | 225 : constraint_space_(space), leader_point_(leader_point) { |
211 origin_point_(origin_point), | |
212 leader_point_(leader_point) { | |
213 // TODO(chrome-layout-team): Combine exclusions that shadow each other. | 226 // TODO(chrome-layout-team): Combine exclusions that shadow each other. |
214 auto exclusions = constraint_space_->PhysicalSpace()->Exclusions(); | 227 auto exclusions = constraint_space_->PhysicalSpace()->Exclusions(); |
215 DCHECK(std::is_sorted(exclusions.begin(), exclusions.end(), | 228 DCHECK(std::is_sorted(exclusions.begin(), exclusions.end(), |
216 &CompareNGExclusionsByTopAsc)) | 229 &CompareNGExclusionsByTopAsc)) |
217 << "Exclusions are expected to be sorted by TOP"; | 230 << "Exclusions are expected to be sorted by TOP"; |
218 | 231 |
219 opportunity_tree_root_ = new NGLayoutOpportunityTreeNode(NGLayoutOpportunity( | 232 NGLayoutOpportunity initial_opportunity = |
220 space->Offset().inline_offset, space->Offset().block_offset, | 233 CreateLayoutOpportunityFromConstraintSpace(*space, origin_point); |
221 space->Size().inline_size, space->Size().block_size)); | 234 opportunity_tree_root_ = new NGLayoutOpportunityTreeNode(initial_opportunity); |
222 | 235 |
223 for (const auto exclusion : exclusions) { | 236 for (const auto exclusion : exclusions) { |
224 InsertExclusion(MutableOpportunityTreeRoot(), exclusion, opportunities_); | 237 InsertExclusion(MutableOpportunityTreeRoot(), exclusion, opportunities_); |
225 } | 238 } |
226 CollectAllOpportunities(OpportunityTreeRoot(), opportunities_); | 239 CollectAllOpportunities(OpportunityTreeRoot(), opportunities_); |
227 std::sort(opportunities_.begin(), opportunities_.end(), | 240 std::sort(opportunities_.begin(), opportunities_.end(), |
228 &CompareNGLayoutOpportunitesByStartPoint); | 241 &CompareNGLayoutOpportunitesByStartPoint); |
| 242 |
229 opportunity_iter_ = opportunities_.begin(); | 243 opportunity_iter_ = opportunities_.begin(); |
230 } | 244 } |
231 | 245 |
232 const NGLayoutOpportunity NGLayoutOpportunityIterator::Next() { | 246 const NGLayoutOpportunity NGLayoutOpportunityIterator::Next() { |
233 if (opportunity_iter_ == opportunities_.end()) | 247 if (opportunity_iter_ == opportunities_.end()) |
234 return NGLayoutOpportunity(); | 248 return NGLayoutOpportunity(); |
235 auto* opportunity = opportunity_iter_; | 249 auto* opportunity = opportunity_iter_; |
236 opportunity_iter_++; | 250 opportunity_iter_++; |
237 return NGLayoutOpportunity(*opportunity); | 251 return NGLayoutOpportunity(*opportunity); |
238 } | 252 } |
239 | 253 |
240 } // namespace blink | 254 } // namespace blink |
OLD | NEW |