[LayoutNG] Split LayoutOpportunityIterator into separate file

third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc

Index: third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc
diff --git a/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc b/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc
index c88c9aafa9ce840546bb9652ed1c20b9029fd32d..676ad16d00ea592851e80e1fe1a56db102da2bf4 100644
--- a/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc
+++ b/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc
@@ -6,9 +6,8 @@
 
 #include "core/layout/LayoutBlock.h"
 #include "core/layout/LayoutView.h"
+#include "core/layout/ng/ng_layout_opportunity_iterator.h"
 #include "core/layout/ng/ng_units.h"
-#include "wtf/NonCopyingSort.h"
-#include <climits>
 
 namespace blink {
 
@@ -171,139 +170,4 @@ String NGConstraintSpace::toString() const {
                         size_.block_size.toString().ascii().data());
 }
 
-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