cc: Implement tile iteration order based on pyramid sequence. [old]

cc/base/pyramid_sequence.cc

Index: cc/base/pyramid_sequence.cc
diff --git a/cc/base/pyramid_sequence.cc b/cc/base/pyramid_sequence.cc
new file mode 100644
index 0000000000000000000000000000000000000000..f0380020e7c631b5cb72c0dd692f3e94b9496cf6
--- /dev/null
+++ b/cc/base/pyramid_sequence.cc
@@ -0,0 +1,1069 @@
+// 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 "cc/base/pyramid_sequence.h"
+
+#include <algorithm>
+#include <string>
+
+#define ENUM_TO_INDEX(x) static_cast<unsigned int>(x)
+
+namespace cc {
+
+namespace {
+
+int LevelsToSkipAlongDirection(int levels) {
+  return levels > 0 ? levels : 0;
+}
+
+int LevelsToSkipCrossDirection(int levels) {
+  return levels >= 0 ? levels + 1 : 0;
+}
+
+// The following function returns default coverage as spiral order {R, T, L, B}.
+// TODO(prashant.n): Implement precedence in coverage directions instead of
+// default spiral coverage. http://crbug.com/629052.
+CoverageDirection* GetCoverageDirectionSequence() {
+  static CoverageDirection
+      spiral_coverage[ENUM_TO_INDEX(CoverageDirection::SIZE)] = {
+          CoverageDirection::RIGHT, CoverageDirection::TOP,
+          CoverageDirection::LEFT, CoverageDirection::BOTTOM};
+  return spiral_coverage;
+}
+
+int GetPositionForDirection(CoverageDirection* positions,
+                            CoverageDirection direction) {
+  for (unsigned int i = 0; i < ENUM_TO_INDEX(CoverageDirection::SIZE); ++i) {
+    if (positions[i] == direction)
+      return i;
+  }
+
+  NOTREACHED();
+  return -1;
+}
+
+}  // namespace
+
+namespace internal {
+
+// Interval implementation.
+Interval::Iterator* Interval::Begin() {
+  return new Iterator(this);
+}
+
+Interval::ReverseIterator* Interval::ReverseBegin() {
+  return new ReverseIterator(this);
+}
+
+int Interval::GetSpan() const {
+  return empty_ ? 0 : std::abs(end_ - start_) + 1;
+}
+
+int Interval::GetForwardClampedIndex(int index) const {
+  DCHECK_LE(start_, end_);
+  return (index < start_) ? start_ : ((index > end_) ? end_ : index);
+}
+
+int Interval::GetBackwardClampedIndex(int index) const {
+  DCHECK_GE(start_, end_);
+  return (index > start_) ? start_ : ((index < end_) ? end_ : index);
+}
+
+void Interval::ForwardClampTo(const Interval* other) {
+  DCHECK_LE(start_, end_);
+  DCHECK_LE(other->start_, other->end_);
+  start_ = other->GetForwardClampedIndex(start_);
+  end_ = other->GetForwardClampedIndex(end_);
+}
+
+void Interval::BackwardClampTo(const Interval* other) {
+  DCHECK_GE(start_, end_);
+  DCHECK_GE(other->start_, other->end_);
+  start_ = other->GetBackwardClampedIndex(start_);
+  end_ = other->GetBackwardClampedIndex(end_);
+}
+
+void Interval::ForwardInflate(int level, Interval* output) const {
+  output->start_ = start_ - level;
+  output->end_ = end_ + level;
+}
+
+void Interval::BackwardInflate(int level, Interval* output) const {
+  output->start_ = start_ + level;
+  output->end_ = end_ - level;
+}
+
+bool Interval::Contains(int index) const {
+  return (start_ <= end_) ? (index >= start_ && index <= end_)
+                          : (index <= start_ && index >= end_);
+}
+
+bool Interval::Intersects(const Interval* interval) const {
+  return interval->Contains(start_) || interval->Contains(end_);
+}
+
+void Interval::Intersect(const Interval* interval) {
+  DCHECK(Intersects(interval));
+  DCHECK(((start_ <= end_) && (interval->start_ <= interval->end_)) ||
+         ((start_ >= end_) && (interval->start_ >= interval->end_)));
+
+  bool forward_direction = (GetSpan() > interval->GetSpan())
+                               ? (start_ <= end_)
+                               : (interval->start_ <= interval->end_);
+
+  if (forward_direction) {
+    start_ = std::max(start_, interval->start_);
+    end_ = std::min(end_, interval->end_);
+  } else {
+    start_ = std::min(start_, interval->start_);
+    end_ = std::max(end_, interval->end_);
+  }
+}
+
+// Interval::IteratorBase implementation.
+Interval::IteratorBase::IteratorBase(Interval* interval)
+    : interval_(interval), within_bounds_(!interval->empty_), step_(0) {}
+
+Interval::IteratorBase& Interval::IteratorBase::operator++() {
+  current_index_ += step_;
+  within_bounds_ = IsWithinBounds();
+
+  return *this;
+}
+
+// Interval::Iterator implementation.
+Interval::Iterator::Iterator(Interval* interval)
+    : Interval::IteratorBase(interval) {
+  step_ = (interval_->start_ <= interval_->end_) ? 1 : -1;
+  current_index_ = interval_->start_;
+}
+
+bool Interval::Iterator::IsWithinBounds() {
+  if (step_ == 1) {
+    DCHECK(current_index_ >= interval_->start_);
+
+    if (interval_->start_ == interval_->end_ ||
+        current_index_ > interval_->end_)
+      return false;
+
+    return true;
+  } else {
+    DCHECK(current_index_ <= interval_->start_);
+
+    if (interval_->start_ == interval_->end_ ||
+        current_index_ < interval_->end_)
+      return false;
+
+    return true;
+  }
+}
+
+// Interval::ReverseIterator implementation.
+Interval::ReverseIterator::ReverseIterator(Interval* interval)
+    : Interval::IteratorBase(interval) {
+  step_ = (interval_->start_ <= interval_->end_) ? -1 : 1;
+  current_index_ = interval_->end_;
+}
+
+bool Interval::ReverseIterator::IsWithinBounds() {
+  if (step_ == 1) {
+    DCHECK(current_index_ >= interval_->end_);
+
+    if (interval_->start_ == interval_->end_ ||
+        current_index_ > interval_->start_)
+      return false;
+
+    return true;
+  } else {
+    DCHECK(current_index_ <= interval_->end_);
+
+    if (interval_->start_ == interval_->end_ ||
+        current_index_ < interval_->start_)
+      return false;
+
+    return true;
+  }
+}
+
+// LinearSequence implementation.
+LinearSequence::LinearSequence(bool forward_direction,
+                               std::unique_ptr<Interval> interval,
+                               std::unique_ptr<Interval> affinity_interval,
+                               std::unique_ptr<Interval> inflate_limit)
+    : forward_direction_(forward_direction),
+      interval_(std::move(interval)),
+      inflate_limit_(std::move(inflate_limit)),
+      affinity_interval_(std::move(affinity_interval)),
+      initial_interval_(std::unique_ptr<Interval>(
+          new Interval(interval_->start(), interval_->end()))) {
+  TrisectInterval();
+}
+
+LinearSequence::~LinearSequence() = default;
+
+LinearSequence::Iterator* LinearSequence::Begin() {
+  return new Iterator(this);
+}
+
+LinearSequence::ReverseIterator* LinearSequence::ReverseBegin() {
+  return new ReverseIterator(this);
+}
+
+void LinearSequence::InflateToLevel(int level) {
+  if (forward_direction_) {
+    initial_interval_->ForwardInflate(level, interval_.get());
+    interval_->ForwardClampTo(inflate_limit_.get());
+  } else {
+    initial_interval_->BackwardInflate(level, interval_.get());
+    interval_->BackwardClampTo(inflate_limit_.get());
+  }
+
+  TrisectInterval();
+}
+
+void LinearSequence::TrisectInterval() {
+  if (interval_->IsEmpty()) {
+    affinity_sub_interval_ = Interval();
+    before_sub_interval_ = Interval();
+    after_sub_interval_ = Interval();
+    return;
+  }
+
+  if (forward_direction_) {
+    affinity_sub_interval_ = *(affinity_interval_.get());
+    if (affinity_sub_interval_.Intersects(interval_.get())) {
+      affinity_sub_interval_.Intersect(interval_.get());
+
+      // Compute before sub-interval.
+      if (affinity_sub_interval_.start() > interval_->start())
+        before_sub_interval_ =
+            Interval(affinity_sub_interval_.start() - 1, interval_->start());
+      else if (affinity_sub_interval_.start() == interval_->start())
+        before_sub_interval_ = Interval();
+
+      // Compute after sub-interval.
+      if (affinity_sub_interval_.end() < interval_->end())
+        after_sub_interval_ =
+            Interval(affinity_sub_interval_.end() + 1, interval_->end());
+      else if (affinity_sub_interval_.end() == interval_->end())
+        after_sub_interval_ = Interval();
+    } else {
+      //  The affinity interval is either before or after the |interval_|.
+      if (affinity_sub_interval_.end() < interval_->start()) {
+        before_sub_interval_ = Interval();
+        after_sub_interval_ = *(interval_.get());
+      } else {
+        after_sub_interval_ = Interval();
+        before_sub_interval_ = Interval(interval_->end(), interval_->start());
+      }
+
+      affinity_sub_interval_ = Interval();
+    }
+  } else {
+    affinity_sub_interval_ = *(affinity_interval_.get());
+    if (affinity_sub_interval_.Intersects(interval_.get())) {
+      affinity_sub_interval_.Intersect(interval_.get());
+
+      // Compute before sub-interval.
+      if (affinity_sub_interval_.start() < interval_->start())
+        before_sub_interval_ =
+            Interval(affinity_sub_interval_.start() + 1, interval_->start());
+      else if (affinity_sub_interval_.start() == interval_->start())
+        before_sub_interval_ = Interval();
+
+      // Compute after sub-interval.
+      if (affinity_sub_interval_.end() > interval_->end())
+        after_sub_interval_ =
+            Interval(affinity_sub_interval_.end() - 1, interval_->end());
+      else if (affinity_sub_interval_.end() == interval_->end())
+        after_sub_interval_ = Interval();
+    } else {
+      //  The affinity interval is either before or after the |interval_|.
+      if (affinity_sub_interval_.end() > interval_->start()) {
+        before_sub_interval_ = Interval();
+        after_sub_interval_ = *(interval_.get());
+      } else {
+        after_sub_interval_ = Interval();
+        before_sub_interval_ = Interval(interval_->end(), interval_->start());
+      }
+
+      affinity_sub_interval_ = Interval();
+    }
+  }
+}
+
+// LinearSequence::IteratorBase implementation.
+LinearSequence::IteratorBase::IteratorBase(LinearSequence* level_sequence)
+    : level_sequence_(level_sequence), within_bounds_(true) {}
+
+LinearSequence::IteratorBase::~IteratorBase() = default;
+
+LinearSequence::IteratorBase& LinearSequence::IteratorBase::operator++() {
+  if (within_bounds_) {
+    ++(*(sub_interval_iterators_[ENUM_TO_INDEX(
+        current_sub_interval_iterator_)]));
+    current_sub_interval_iterator_ = GetCurrentSubIntervalIteratorType();
+    current_index_ =
+        sub_interval_iterators_[ENUM_TO_INDEX(current_sub_interval_iterator_)]
+            ->index();
+    within_bounds_ = IsWithinBounds();
+  }
+  return *this;
+}
+
+bool LinearSequence::IteratorBase::IsWithinBounds() {
+  return *(sub_interval_iterators_[ENUM_TO_INDEX(
+             SubIntervalIteratorType::AFFINITY)]) ||
+         *(sub_interval_iterators_[ENUM_TO_INDEX(
+             SubIntervalIteratorType::BEFORE)]) ||
+         *(sub_interval_iterators_[ENUM_TO_INDEX(
+             SubIntervalIteratorType::AFTER)]);
+}
+
+// LinearSequence::Iterator implementation.
+LinearSequence::Iterator::Iterator(LinearSequence* level_sequence)
+    : LinearSequence::IteratorBase(level_sequence), before_first_(true) {
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFFINITY)]
+      .reset(level_sequence_->affinity_sub_interval_.Begin());
+
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::BEFORE)].reset(
+      level_sequence_->before_sub_interval_.Begin());
+
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFTER)].reset(
+      level_sequence_->after_sub_interval_.Begin());
+
+  current_sub_interval_iterator_ = GetCurrentSubIntervalIteratorType();
+  current_index_ =
+      sub_interval_iterators_[ENUM_TO_INDEX(current_sub_interval_iterator_)]
+          ->index();
+}
+
+LinearSequence::Iterator::~Iterator() = default;
+
+LinearSequence::IteratorBase::SubIntervalIteratorType
+LinearSequence::Iterator::GetCurrentSubIntervalIteratorType() {
+  if (*(sub_interval_iterators_[ENUM_TO_INDEX(
+          SubIntervalIteratorType::AFFINITY)]))
+    return SubIntervalIteratorType::AFFINITY;
+
+  if (before_first_) {
+    before_first_ = false;
+    if (*(sub_interval_iterators_[ENUM_TO_INDEX(
+            SubIntervalIteratorType::BEFORE)]))
+      return SubIntervalIteratorType::BEFORE;
+
+    return SubIntervalIteratorType::AFTER;
+  } else {
+    before_first_ = true;
+    if (*(sub_interval_iterators_[ENUM_TO_INDEX(
+            SubIntervalIteratorType::AFTER)]))
+      return SubIntervalIteratorType::AFTER;
+
+    return SubIntervalIteratorType::BEFORE;
+  }
+}
+
+// LinearSequence::ReverseIterator implementation.
+LinearSequence::ReverseIterator::ReverseIterator(LinearSequence* level_sequence)
+    : LinearSequence::IteratorBase(level_sequence),
+      after_first_(true),
+      before_sub_interval_span_(
+          level_sequence_->before_sub_interval_.GetSpan()),
+      after_sub_interval_span_(level_sequence_->after_sub_interval_.GetSpan()) {
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFFINITY)]
+      .reset(level_sequence_->affinity_sub_interval_.ReverseBegin());
+
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::BEFORE)].reset(
+      level_sequence_->before_sub_interval_.ReverseBegin());
+
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFTER)].reset(
+      level_sequence_->after_sub_interval_.ReverseBegin());
+
+  current_sub_interval_iterator_ = GetCurrentSubIntervalIteratorType();
+  current_index_ =
+      sub_interval_iterators_[ENUM_TO_INDEX(current_sub_interval_iterator_)]
+          ->index();
+}
+
+LinearSequence::ReverseIterator::~ReverseIterator() = default;
+
+LinearSequence::IteratorBase::SubIntervalIteratorType
+LinearSequence::ReverseIterator::GetCurrentSubIntervalIteratorType() {
+  if (before_sub_interval_span_ > after_sub_interval_span_) {
+    --before_sub_interval_span_;
+    return SubIntervalIteratorType::BEFORE;
+  } else if (before_sub_interval_span_ < after_sub_interval_span_) {
+    --after_sub_interval_span_;
+    return SubIntervalIteratorType::AFTER;
+  } else {
+    if (after_first_) {
+      after_first_ = false;
+      if (*(sub_interval_iterators_[ENUM_TO_INDEX(
+              SubIntervalIteratorType::AFTER)]))
+        return SubIntervalIteratorType::AFTER;
+
+      if (*(sub_interval_iterators_[ENUM_TO_INDEX(
+              SubIntervalIteratorType::BEFORE)]))
+        return SubIntervalIteratorType::BEFORE;
+    } else {
+      after_first_ = true;
+      if (*(sub_interval_iterators_[ENUM_TO_INDEX(
+              SubIntervalIteratorType::BEFORE)]))
+        return SubIntervalIteratorType::BEFORE;
+
+      if (*(sub_interval_iterators_[ENUM_TO_INDEX(
+              SubIntervalIteratorType::AFTER)]))
+        return SubIntervalIteratorType::AFTER;
+    }
+  }
+
+  return SubIntervalIteratorType::AFFINITY;
+}
+
+// TriangularSequence implementation.
+TriangularSequence::TriangularSequence(
+    CoverageDirection coverage_direction,
+    std::unique_ptr<LinearSequence> traversal_sequence,
+    std::unique_ptr<Interval> level_interval,
+    bool should_swap_index_representation,
+    int levels_to_skip,
+    int distance)
+    : coverage_direction_(coverage_direction),
+      traversal_sequence_(std::move(traversal_sequence)),
+      level_interval_(std::move(level_interval)),
+      should_swap_index_representation_(should_swap_index_representation),
+      levels_to_skip_(levels_to_skip),
+      distance_(distance) {}
+
+TriangularSequence::~TriangularSequence() = default;
+
+TriangularSequence::Iterator* TriangularSequence::Begin() {
+  return new Iterator(this);
+}
+
+TriangularSequence::ReverseIterator* TriangularSequence::ReverseBegin() {
+  return new ReverseIterator(this);
+}
+
+// TriangularSequence::IteratorBase implementation.
+TriangularSequence::IteratorBase::IteratorBase(
+    TriangularSequence* triangular_sequence)
+    : should_swap_index_representation_(
+          triangular_sequence->should_swap_index_representation_) {
+  DCHECK_NE(triangular_sequence->coverage_direction_, CoverageDirection::NONE);
+  std::unique_ptr<Interval::Iterator> level_interval_it(
+      triangular_sequence->level_interval_->Begin());
+  traversal_sequence_ = triangular_sequence->traversal_sequence_.get();
+  int span = triangular_sequence->level_interval_->GetSpan();
+  DCHECK_GE(span, triangular_sequence->levels_to_skip_);
+
+  // Skip |levels_to_skip| levels in level interval.
+  for (int i = 0; i < triangular_sequence->levels_to_skip_; ++i)
+    ++(*level_interval_it);
+
+  for (int i = triangular_sequence->levels_to_skip_; i < span; ++i) {
+    level_distances_.push_back(LevelDistance(
+        i, level_interval_it->index(), triangular_sequence->distance_ * i));
+    ++(*level_interval_it);
+  }
+}
+
+TriangularSequence::IteratorBase::~IteratorBase() = default;
+
+TriangularSequence::IteratorBase& TriangularSequence::IteratorBase::
+operator++() {
+  Advance();
+  UpdateCurrent();
+
+  return *this;
+}
+
+// TriangularSequence::Iterator implementation.
+TriangularSequence::Iterator::Iterator(TriangularSequence* triangular_sequence)
+    : TriangularSequence::IteratorBase(triangular_sequence) {
+  UpdateCurrent();
+}
+
+int TriangularSequence::Iterator::GetNextDistance() const {
+  DCHECK(*this);
+  return level_distances_.front().distance;
+}
+
+void TriangularSequence::Iterator::Advance() {
+  if (!*this)
+    return;
+
+  level_distances_.erase(level_distances_.begin());
+}
+
+void TriangularSequence::Iterator::UpdateCurrent() {
+  if (!*this)
+    return;
+
+  current_level_index_ = level_distances_.front().level_index;
+  traversal_sequence_->InflateToLevel(level_distances_.front().interval_level);
+}
+
+// TriangularSequence::ReverseIterator implementation.
+TriangularSequence::ReverseIterator::ReverseIterator(
+    TriangularSequence* triangular_sequence)
+    : TriangularSequence::IteratorBase(triangular_sequence) {
+  UpdateCurrent();
+}
+
+int TriangularSequence::ReverseIterator::GetNextDistance() const {
+  DCHECK(!level_distances_.empty());
+  return level_distances_.back().distance;
+}
+
+void TriangularSequence::ReverseIterator::Advance() {
+  if (!*this)
+    return;
+
+  level_distances_.erase(level_distances_.end() - 1);
+}
+
+void TriangularSequence::ReverseIterator::UpdateCurrent() {
+  if (!*this)
+    return;
+
+  current_level_index_ = level_distances_.back().level_index;
+  traversal_sequence_->InflateToLevel(level_distances_.back().interval_level);
+}
+
+// PyramidSequence implementation.
+PyramidSequence::PyramidSequence(const IndexRect& around_index_rect,
+                                 const IndexRect& consider_index_rect,
+                                 const IndexRect& ignore_index_rect,
+                                 int width,
+                                 int height)
+    : consider_index_rect_(consider_index_rect),
+      ignore_index_rect_(ignore_index_rect) {
+  // Compute center_index_rect and if it is valid (i.e. |around_index_rect| is
+  // really around some index_rect) and both |consider_index_rect| and
+  // |ignore_index_rect| are valid, then proceed, otherwise keep the pyramid
+  // sequence empty.
+
+  IndexRect center_index_rect(around_index_rect);
+  center_index_rect.Inset(1, 1, 1, 1);
+  if (!center_index_rect.is_valid() || !consider_index_rect.is_valid() ||
+      !ignore_index_rect.is_valid())
+    return;
+
+  // Compute the max possible levels along all directions.
+  int left_levels = around_index_rect.left() - consider_index_rect_.left() + 1;
+  int right_levels =
+      consider_index_rect_.right() - around_index_rect.right() + 1;
+  int top_levels = around_index_rect.top() - consider_index_rect_.top() + 1;
+  int bottom_levels =
+      consider_index_rect_.bottom() - around_index_rect.bottom() + 1;
+
+  // When center_index_rect and consider_index_rect are non-intersecting, then
+  // we need to compute the levels to skip for avoiding traversal of levels
+  // which do not fall in consider_index_rect. The pyramid sequence adds
+  // diagonal indices to left and right directions and no diagonal indices for
+  // top and bottom directions, so while considering skip levels for top/bottom,
+  // we need to consider maximum of levels to skip "along" the top/bottom
+  // directions and levels to skip "cross" left/right directions and for
+  // considering skip levels for left/right, we need to consider maximum of
+  // levels to skip "along" the left/right directions and levels to skip "along"
+  // top/bottom directions.
+  // Compute the levels to skip along and cross all directions.
+  int skip_levels_along_left =
+      around_index_rect.left() - consider_index_rect_.right();
+  int skip_levels_along_right =
+      consider_index_rect_.left() - around_index_rect.right();
+  int skip_levels_along_top =
+      around_index_rect.top() - consider_index_rect_.bottom();
+  int skip_levels_along_bottom =
+      consider_index_rect_.top() - around_index_rect.bottom();
+  int skip_levels_cross_left =
+      LevelsToSkipCrossDirection(skip_levels_along_left);
+  int skip_levels_cross_right =
+      LevelsToSkipCrossDirection(skip_levels_along_right);
+  skip_levels_along_left = LevelsToSkipAlongDirection(skip_levels_along_left);
+  skip_levels_along_right = LevelsToSkipAlongDirection(skip_levels_along_right);
+  skip_levels_along_top = LevelsToSkipAlongDirection(skip_levels_along_top);
+  skip_levels_along_bottom =
+      LevelsToSkipAlongDirection(skip_levels_along_bottom);
+
+  DCHECK(triangular_sequences_.empty());
+  triangular_sequences_.resize(ENUM_TO_INDEX(CoverageDirection::SIZE));
+  CoverageDirection* positions = GetCoverageDirectionSequence();
+  DCHECK(positions);
+
+#define NEW_UNIQUE(type, val) std::unique_ptr<type>(new val)
+
+  // Add triangular sequences for all directions.
+  // RIGHT sequence.
+  if (right_levels > 0) {
+    int start = around_index_rect.bottom();
+    int end = around_index_rect.top();
+    int skip_levels =
+        std::max(skip_levels_along_right,
+                 std::max(skip_levels_along_bottom, skip_levels_along_top));
+    if (right_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions, CoverageDirection::RIGHT),
+          NEW_UNIQUE(
+              TriangularSequence,
+              TriangularSequence(
+                  CoverageDirection::RIGHT,
+                  NEW_UNIQUE(
+                      LinearSequence,
+                      LinearSequence(
+                          false, NEW_UNIQUE(Interval, Interval(start, end)),
+                          NEW_UNIQUE(Interval,
+                                     Interval(center_index_rect.bottom(),
+                                              center_index_rect.top())),
+                          NEW_UNIQUE(Interval,
+                                     Interval(consider_index_rect_.bottom(),
+                                              consider_index_rect_.top())))),
+                  NEW_UNIQUE(Interval, Interval(around_index_rect.right(),
+                                                consider_index_rect_.right())),
+                  true, skip_levels, width)));
+    }
+  }
+
+  // TOP sequence.
+  if (top_levels > 0) {
+    int start = around_index_rect.right() - 1;
+    int end = around_index_rect.left() + 1;
+    int skip_levels =
+        std::max(skip_levels_along_top,
+                 std::max(skip_levels_cross_right, skip_levels_cross_left));
+    if (top_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions, CoverageDirection::TOP),
+          NEW_UNIQUE(
+              TriangularSequence,
+              TriangularSequence(
+                  CoverageDirection::TOP,
+                  NEW_UNIQUE(
+                      LinearSequence,
+                      LinearSequence(
+                          false, NEW_UNIQUE(Interval, Interval(start, end)),
+                          NEW_UNIQUE(Interval,
+                                     Interval(center_index_rect.right(),
+                                              center_index_rect.left())),
+                          NEW_UNIQUE(Interval,
+                                     Interval(consider_index_rect_.right(),
+                                              consider_index_rect_.left())))),
+                  NEW_UNIQUE(Interval, Interval(around_index_rect.top(),
+                                                consider_index_rect_.top())),
+                  false, skip_levels, height)));
+    }
+  }
+
+  // LEFT sequence.
+  if (left_levels > 0) {
+    int start = around_index_rect.top();
+    int end = around_index_rect.bottom();
+    int skip_levels =
+        std::max(skip_levels_along_left,
+                 std::max(skip_levels_along_top, skip_levels_along_bottom));
+    if (left_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions, CoverageDirection::LEFT),
+          NEW_UNIQUE(
+              TriangularSequence,
+              TriangularSequence(
+                  CoverageDirection::LEFT,
+                  NEW_UNIQUE(
+                      LinearSequence,
+                      LinearSequence(
+                          true, NEW_UNIQUE(Interval, Interval(start, end)),
+                          NEW_UNIQUE(Interval,
+                                     Interval(center_index_rect.top(),
+                                              center_index_rect.bottom())),
+                          NEW_UNIQUE(Interval,
+                                     Interval(consider_index_rect_.top(),
+                                              consider_index_rect_.bottom())))),
+                  NEW_UNIQUE(Interval, Interval(around_index_rect.left(),
+                                                consider_index_rect_.left())),
+                  true, skip_levels, width)));
+    }
+  }
+
+  // BOTTOM sequence.
+  if (bottom_levels > 0) {
+    int start = around_index_rect.left() + 1;
+    int end = around_index_rect.right() - 1;
+    int skip_levels =
+        std::max(skip_levels_along_bottom,
+                 std::max(skip_levels_cross_left, skip_levels_cross_right));
+    if (bottom_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions, CoverageDirection::BOTTOM),
+          NEW_UNIQUE(
+              TriangularSequence,
+              TriangularSequence(
+                  CoverageDirection::BOTTOM,
+                  NEW_UNIQUE(
+                      LinearSequence,
+                      LinearSequence(
+                          true, NEW_UNIQUE(Interval, Interval(start, end)),
+                          NEW_UNIQUE(Interval,
+                                     Interval(center_index_rect.left(),
+                                              center_index_rect.right())),
+                          NEW_UNIQUE(Interval,
+                                     Interval(consider_index_rect_.left(),
+                                              consider_index_rect_.right())))),
+                  NEW_UNIQUE(Interval, Interval(around_index_rect.bottom(),
+                                                consider_index_rect_.bottom())),
+                  false, skip_levels, height)));
+    }
+  }
+
+  // Remove dummy triangular sequences.
+  triangular_sequences_.erase(
+      std::remove_if(
+          triangular_sequences_.begin(), triangular_sequences_.end(),
+          [](const std::unique_ptr<TriangularSequence>& triangular_sequence) {
+            return triangular_sequence.get() == nullptr;
+          }),
+      triangular_sequences_.end());
+}
+
+PyramidSequence::~PyramidSequence() = default;
+
+PyramidSequence::Iterator* PyramidSequence::Begin() {
+  return new Iterator(this);
+}
+
+PyramidSequence::ReverseIterator* PyramidSequence::ReverseBegin() {
+  return new ReverseIterator(this);
+}
+
+void PyramidSequence::EmplaceAt(
+    int position,
+    std::unique_ptr<TriangularSequence> triangular_sequence) {
+  triangular_sequences_[position] = std::move(triangular_sequence);
+}
+
+// PyramidSequence::IteratorBase implementation.
+PyramidSequence::IteratorBase::IteratorBase(
+    const IndexRect& consider_index_rect,
+    const IndexRect& ignore_index_rect)
+    : consider_index_rect_(consider_index_rect),
+      ignore_index_rect_(ignore_index_rect),
+      current_triangular_sequence_it_(nullptr) {}
+
+PyramidSequence::IteratorBase::~IteratorBase() = default;
+
+PyramidSequence::IteratorBase::operator bool() const {
+  return current_triangular_sequence_it_ && !IsEmpty();
+}
+
+PyramidSequence::IteratorBase& PyramidSequence::IteratorBase::operator++() {
+  Advance();
+  UpdateCurrent();
+
+  return *this;
+}
+
+// PyramidSequence::Iterator implementation.
+PyramidSequence::Iterator::Iterator(PyramidSequence* pyramid_sequence)
+    : PyramidSequence::IteratorBase(pyramid_sequence->consider_index_rect_,
+                                    pyramid_sequence->ignore_index_rect_) {
+  for (TriangularSequence::Vector::iterator it =
+           pyramid_sequence->triangular_sequences_.begin();
+       it != pyramid_sequence->triangular_sequences_.end(); ++it) {
+    DCHECK(it->get()->coverage_direction() != CoverageDirection::NONE);
+    triangular_sequence_iterators_.emplace_back(it->get()->Begin());
+  }
+
+  current_triangular_sequence_it_ = GetNextTriangularSequenceIterator();
+  if (current_triangular_sequence_it_) {
+    if (*current_triangular_sequence_it_) {
+      current_traversal_sequence_iterator_ =
+          current_triangular_sequence_it_->traversal_sequence()->Begin();
+    }
+
+    UpdateCurrent();
+  }
+}
+
+PyramidSequence::Iterator::~Iterator() = default;
+
+bool PyramidSequence::Iterator::IsEmpty() const {
+  return triangular_sequence_iterators_.empty();
+}
+
+void PyramidSequence::Iterator::Advance() {
+  if (!*this)
+    return;
+
+  ++(*current_traversal_sequence_iterator_);
+  if (!(*current_traversal_sequence_iterator_)) {
+    ++(*current_triangular_sequence_it_);
+    current_triangular_sequence_it_ = GetNextTriangularSequenceIterator();
+    if (current_triangular_sequence_it_) {
+      current_traversal_sequence_iterator_ =
+          current_triangular_sequence_it_->traversal_sequence()->Begin();
+    }
+  }
+}
+
+void PyramidSequence::Iterator::UpdateCurrent() {
+  while (*this) {
+    if (*current_traversal_sequence_iterator_) {
+      if (current_triangular_sequence_it_->is_index_representation_swapped()) {
+        index_x_ = current_triangular_sequence_it_->level_index();
+        index_y_ = current_traversal_sequence_iterator_->index();
+      } else {
+        index_x_ = current_traversal_sequence_iterator_->index();
+        index_y_ = current_triangular_sequence_it_->level_index();
+      }
+
+      if (consider_index_rect_.Contains(index_x_, index_y_) &&
+          !ignore_index_rect_.Contains(index_x_, index_y_))
+        break;
+    }
+
+    Advance();
+  }
+}
+
+TriangularSequence::IteratorBase*
+PyramidSequence::Iterator::GetNextTriangularSequenceIterator() {
+  // Remove traversed TriangularSequence::Iterator(s).
+  triangular_sequence_iterators_.erase(
+      std::remove_if(
+          triangular_sequence_iterators_.begin(),
+          triangular_sequence_iterators_.end(),
+          [](const std::unique_ptr<TriangularSequence::Iterator>& it) {
+            return !(*(it.get()));
+          }),
+      triangular_sequence_iterators_.end());
+
+  if (triangular_sequence_iterators_.empty())
+    return nullptr;
+
+  std::vector<std::unique_ptr<TriangularSequence::Iterator>>::iterator
+      min_distance_it = triangular_sequence_iterators_.begin();
+
+  for (std::vector<std::unique_ptr<TriangularSequence::Iterator>>::iterator it =
+           triangular_sequence_iterators_.begin();
+       it != triangular_sequence_iterators_.end(); ++it) {
+    int distance = it->get()->GetNextDistance();
+    if (distance == 0) {
+      min_distance_it = it;
+      break;
+    }
+
+    if (min_distance_it->get()->GetNextDistance() > distance)
+      min_distance_it = it;
+  }
+
+  return min_distance_it->get();
+}
+
+// PyramidSequence::ReverseIterator implementation.
+PyramidSequence::ReverseIterator::ReverseIterator(
+    PyramidSequence* pyramid_sequence)
+    : PyramidSequence::IteratorBase(pyramid_sequence->consider_index_rect_,
+                                    pyramid_sequence->ignore_index_rect_) {
+  for (TriangularSequence::Vector::iterator it =
+           pyramid_sequence->triangular_sequences_.begin();
+       it != pyramid_sequence->triangular_sequences_.end(); ++it) {
+    triangular_sequence_reverse_iterators_.emplace_back(
+        it->get()->ReverseBegin());
+  }
+
+  current_triangular_sequence_it_ = GetNextTriangularSequenceReverseIterator();
+  if (current_triangular_sequence_it_) {
+    if (*current_triangular_sequence_it_) {
+      current_traversal_sequence_reverse_iterator_ =
+          current_triangular_sequence_it_->traversal_sequence()->ReverseBegin();
+    }
+    UpdateCurrent();
+  }
+}
+
+PyramidSequence::ReverseIterator::~ReverseIterator() = default;
+
+bool PyramidSequence::ReverseIterator::IsEmpty() const {
+  return triangular_sequence_reverse_iterators_.empty();
+}
+
+void PyramidSequence::ReverseIterator::Advance() {
+  if (!*this)
+    return;
+
+  ++(*current_traversal_sequence_reverse_iterator_);
+  if (!(*current_traversal_sequence_reverse_iterator_)) {
+    ++(*current_triangular_sequence_it_);
+    current_triangular_sequence_it_ =
+        GetNextTriangularSequenceReverseIterator();
+    if (current_triangular_sequence_it_) {
+      current_traversal_sequence_reverse_iterator_ =
+          current_triangular_sequence_it_->traversal_sequence()->ReverseBegin();
+    }
+  }
+}
+
+void PyramidSequence::ReverseIterator::UpdateCurrent() {
+  while (*this) {
+    if ((*current_traversal_sequence_reverse_iterator_)) {
+      if (current_triangular_sequence_it_->is_index_representation_swapped()) {
+        index_x_ = current_triangular_sequence_it_->level_index();
+        index_y_ = current_traversal_sequence_reverse_iterator_->index();
+      } else {
+        index_x_ = current_traversal_sequence_reverse_iterator_->index();
+        index_y_ = current_triangular_sequence_it_->level_index();
+      }
+
+      if (consider_index_rect_.Contains(index_x_, index_y_) &&
+          !ignore_index_rect_.Contains(index_x_, index_y_))
+        break;
+    }
+
+    Advance();
+  }
+}
+
+TriangularSequence::IteratorBase*
+PyramidSequence::ReverseIterator::GetNextTriangularSequenceReverseIterator() {
+  // Remove traversed TriangularSequence::ReverseIterator(s).
+  triangular_sequence_reverse_iterators_.erase(
+      std::remove_if(
+          triangular_sequence_reverse_iterators_.begin(),
+          triangular_sequence_reverse_iterators_.end(),
+          [](const std::unique_ptr<TriangularSequence::ReverseIterator>& it) {
+            return !(*(it.get()));
+          }),
+      triangular_sequence_reverse_iterators_.end());
+
+  if (triangular_sequence_reverse_iterators_.empty())
+    return nullptr;
+
+  std::vector<std::unique_ptr<TriangularSequence::ReverseIterator>>::
+      reverse_iterator max_distance_it =
+          triangular_sequence_reverse_iterators_.rbegin();
+
+  for (std::vector<std::unique_ptr<TriangularSequence::ReverseIterator>>::
+           reverse_iterator it =
+               triangular_sequence_reverse_iterators_.rbegin();
+       it != triangular_sequence_reverse_iterators_.rend(); ++it) {
+    int distance = it->get()->GetNextDistance();
+
+    if (max_distance_it->get()->GetNextDistance() < distance)
+      max_distance_it = it;
+  }
+
+  return max_distance_it->get();
+}
+
+}  // namespace internal
+
+PyramidSequence::PyramidSequence() {}
+
+PyramidSequence::PyramidSequence(const IndexRect& around_index_rect,
+                                 const IndexRect& consider_index_rect,
+                                 const IndexRect& ignore_index_rect,
+                                 int width,
+                                 int height)
+    : ptr_(new internal::PyramidSequence(around_index_rect,
+                                         consider_index_rect,
+                                         ignore_index_rect,
+                                         width,
+                                         height)) {}
+
+PyramidSequence::PyramidSequence(const PyramidSequence& other) = default;
+
+PyramidSequence::PyramidSequence(PyramidSequence&& other) = default;
+
+PyramidSequence::~PyramidSequence() = default;
+
+PyramidSequence& PyramidSequence::operator=(const PyramidSequence& other) =
+    default;
+
+PyramidSequence& PyramidSequence::operator=(PyramidSequence&& other) = default;
+
+PyramidSequence::Iterator PyramidSequence::Begin() {
+  return Iterator(ptr_->Begin());
+}
+
+PyramidSequence::ReverseIterator PyramidSequence::ReverseBegin() {
+  return ReverseIterator(ptr_->ReverseBegin());
+}
+
+// iterator
+PyramidSequence::Iterator::Iterator() {}
+
+PyramidSequence::Iterator::Iterator(internal::PyramidSequence::Iterator* ptr)
+    : ptr_(ptr) {}
+
+PyramidSequence::Iterator::Iterator(const PyramidSequence::Iterator& other) =
+    default;
+
+PyramidSequence::Iterator::Iterator(PyramidSequence::Iterator&& other) =
+    default;
+
+PyramidSequence::Iterator::~Iterator() = default;
+
+PyramidSequence::Iterator& PyramidSequence::Iterator::operator=(
+    const PyramidSequence::Iterator& other) = default;
+
+PyramidSequence::Iterator& PyramidSequence::Iterator::operator=(
+    PyramidSequence::Iterator&& other) = default;
+
+PyramidSequence::Iterator::operator bool() const {
+  return *ptr_;
+}
+
+PyramidSequence::Iterator& PyramidSequence::Iterator::operator++() {
+  ++(*ptr_);
+  return *this;
+}
+
+int PyramidSequence::Iterator::index_x() const {
+  return ptr_->index_x();
+}
+
+int PyramidSequence::Iterator::index_y() const {
+  return ptr_->index_y();
+}
+
+// reverse
+PyramidSequence::ReverseIterator::ReverseIterator() {}
+
+PyramidSequence::ReverseIterator::ReverseIterator(
+    internal::PyramidSequence::ReverseIterator* ptr)
+    : ptr_(ptr) {}
+
+PyramidSequence::ReverseIterator::ReverseIterator(
+    const PyramidSequence::ReverseIterator& other) = default;
+
+PyramidSequence::ReverseIterator::ReverseIterator(
+    PyramidSequence::ReverseIterator&& other) = default;
+
+PyramidSequence::ReverseIterator::~ReverseIterator() = default;
+
+PyramidSequence::ReverseIterator& PyramidSequence::ReverseIterator::operator=(
+    const PyramidSequence::ReverseIterator& other) = default;
+
+PyramidSequence::ReverseIterator& PyramidSequence::ReverseIterator::operator=(
+    PyramidSequence::ReverseIterator&& other) = default;
+
+PyramidSequence::ReverseIterator::operator bool() const {
+  return *ptr_;
+}
+
+PyramidSequence::ReverseIterator& PyramidSequence::ReverseIterator::
+operator++() {
+  ++(*ptr_);
+  return *this;
+}
+
+int PyramidSequence::ReverseIterator::index_x() const {
+  return ptr_->index_x();
+}
+
+int PyramidSequence::ReverseIterator::index_y() const {
+  return ptr_->index_y();
+}
+
+}  // namespace cc