[LayoutNG] Split LayoutOpportunityIterator into separate file

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

+// 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