Index: third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc |
diff --git a/third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc b/third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc |
new file mode 100644 |
index 0000000000000000000000000000000000000000..b5db6a685177a34b8ea5f1832280175f52c4a43f |
--- /dev/null |
+++ b/third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc |
@@ -0,0 +1,148 @@ |
+// Copyright 2016 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#include "core/layout/ng/ng_layout_opportunity_iterator.h" |
+ |
+#include "core/layout/ng/ng_physical_constraint_space.h" |
+#include "core/layout/ng/ng_units.h" |
+#include "wtf/NonCopyingSort.h" |
+ |
+namespace blink { |
+ |
+static inline bool AscendingTopCompare(const NGExclusion& a, |
+ const NGExclusion& b) { |
+ return a.Top() > b.Top(); |
+} |
+ |
+NGLayoutOpportunityIterator::NGLayoutOpportunityIterator( |
+ NGConstraintSpace* space, |
+ unsigned clear, |
+ bool for_inline_or_bfc) |
+ : constraint_space_(space), |
+ clear_(clear), |
+ for_inline_or_bfc_(for_inline_or_bfc), |
+ current_exclusion_idx_(0) { |
+ for (const auto& item : constraint_space_->PhysicalSpace()->Exclusions()) |
+ filtered_exclusions_.append(item); |
+ |
+ nonCopyingSort(filtered_exclusions_.begin(), filtered_exclusions_.end(), |
+ AscendingTopCompare); |
+ |
+ // TODO(eae): Set based on offset. |
+ LayoutUnit left; |
+ LayoutUnit top; |
+ |
+ unsigned i = filtered_exclusions_.size(); |
+ while (i--) { |
+ const NGExclusion& exclusion = filtered_exclusions_[i]; |
+ |
+ // Remove items above OR to the left of the start offset as they have no |
+ // effect on layout opportunities within this view. |
+ if (exclusion.Right() <= left || exclusion.Bottom() <= top) { |
+ filtered_exclusions_.remove(i); |
+ continue; |
+ } |
+ |
+ // Remove items below AND to the right of the current exclusions as they're |
+ // occluded and won't affect the layout opportunities. |
+ for (unsigned j = filtered_exclusions_.size() - 1; j > i; j--) { |
+ const NGExclusion& item = filtered_exclusions_[j]; |
+ if (item.Top() > exclusion.Top() && item.Left() > exclusion.Left()) |
+ filtered_exclusions_.remove(j); |
+ } |
+ } |
+} |
+ |
+NGConstraintSpace* NGLayoutOpportunityIterator::Next() { |
+ if (current_opportunities_.isEmpty() && |
+ current_exclusion_idx_ < filtered_exclusions_.size()) { |
+ computeForExclusion(current_exclusion_idx_); |
+ current_exclusion_idx_++; |
+ } |
+ |
+ if (!current_opportunities_.isEmpty()) { |
+ NGConstraintSpace* opportunity = current_opportunities_.last(); |
+ current_opportunities_.removeLast(); |
+ return opportunity; |
+ } |
+ |
+ if (filtered_exclusions_.isEmpty() && current_exclusion_idx_ == 0) { |
+ current_exclusion_idx_++; |
+ return new NGConstraintSpace(constraint_space_->WritingMode(), |
+ constraint_space_->PhysicalSpace()); |
+ } |
+ |
+ return nullptr; |
+} |
+ |
+static inline bool DescendingWidthCompare(const NGConstraintSpace* a, |
+ const NGConstraintSpace* b) { |
+ return a->Size().inline_size > b->Size().inline_size; |
+} |
+ |
+void NGLayoutOpportunityIterator::computeForExclusion(unsigned index) { |
+ current_opportunities_.clear(); |
+ |
+ // TODO(eae): Set based on index. |
+ LayoutUnit left; |
+ LayoutUnit top; |
+ |
+ // TODO(eae): Writing modes. |
+ LayoutUnit right = constraint_space_->Size().inline_size; |
+ LayoutUnit bottom = constraint_space_->Size().block_size; |
+ |
+ // TODO(eae): Filter based on clear_ and for_inline_or_bfc_. Return early for |
+ // now to make it clear neither are supported yet. |
+ if (clear_ != NGClearNone || !for_inline_or_bfc_) |
+ return; |
+ |
+ // Compute opportunity for the full width from the start position to the right |
+ // edge of the NGConstraintSpace. |
+ LayoutUnit opportunityHeight = heightForOpportunity(left, top, right, bottom); |
+ if (opportunityHeight && right > left) |
+ addLayoutOpportunity(left, top, right - left, opportunityHeight); |
+ |
+ // Compute the maximum available height between the current position and the |
+ // left edge of each exclusion. The distance between the current horizontal |
+ // position and the left edge of the exclusion determines the width of the |
+ // opportunity. |
+ for (const NGExclusion& exclusion : filtered_exclusions_) { |
+ opportunityHeight = |
+ heightForOpportunity(left, top, exclusion.Left(), bottom); |
+ if (opportunityHeight && exclusion.Left() > left) |
+ addLayoutOpportunity(left, top, exclusion.Left() - left, |
+ opportunityHeight); |
+ } |
+ |
+ nonCopyingSort(current_opportunities_.begin(), current_opportunities_.end(), |
+ DescendingWidthCompare); |
+} |
+ |
+// For the given 2D range (opportunity), this will return a height which makes |
+// it bounded by the highest exclusion in the filtered exclusion list within the |
+// range. Returns 0-height for an invalid opportunity (which has zero area). |
+LayoutUnit NGLayoutOpportunityIterator::heightForOpportunity( |
+ LayoutUnit left, |
+ LayoutUnit top, |
+ LayoutUnit right, |
+ LayoutUnit bottom) { |
+ LayoutUnit lowestBottom = bottom; |
+ for (const NGExclusion& exclusion : filtered_exclusions_) { |
+ if (exclusion.Left() < right && exclusion.Right() > left && |
+ exclusion.Bottom() > top && exclusion.Top() <= lowestBottom) |
+ lowestBottom = exclusion.Top(); |
+ } |
+ return std::max(lowestBottom - top, LayoutUnit()); |
+} |
+ |
+void NGLayoutOpportunityIterator::addLayoutOpportunity(LayoutUnit left, |
+ LayoutUnit top, |
+ LayoutUnit right, |
+ LayoutUnit bottom) { |
+ current_opportunities_.append( |
+ new NGConstraintSpace(*constraint_space_, NGLogicalOffset(left, top), |
+ NGLogicalSize(right - left, bottom - top))); |
+} |
+ |
+} // namespace blink |