ps test.

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..4be597aa53391c68bd10a641aa494225535f9158
--- /dev/null
+++ b/cc/base/pyramid_sequence.cc
@@ -0,0 +1,1218 @@
+// 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
+
+// Interval implementation.
+Interval::Iterator Interval::Begin() {
+  return Iterator(this);
+}
+
+Interval::ReverseIterator Interval::ReverseBegin() {
+  return 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_);
+}
+
+Interval Interval::GetForwardInflatedInterval(int level) const {
+  return Interval(start_ - level, end_ + level);
+}
+
+Interval Interval::GetBackwardInflatedInterval(int level) const {
+  return Interval(start_ + level, 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() : within_bounds_(false), step_(0) {}
+
+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::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::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() {}
+
+LinearSequence::LinearSequence(bool forward_direction,
+                               Interval interval,
+                               Interval affinity_interval,
+                               Interval inflate_limit)
+    : forward_direction_(forward_direction),
+      interval_(interval),
+      inflate_limit_(inflate_limit),
+      affinity_interval_(affinity_interval),
+      initial_interval_(interval) {
+  TrisectInterval();
+}
+
+LinearSequence::LinearSequence(const LinearSequence& other) = default;
+
+LinearSequence::LinearSequence(LinearSequence&& other) = default;
+
+LinearSequence::~LinearSequence() = default;
+
+LinearSequence& LinearSequence::operator=(const LinearSequence& other) =
+    default;
+
+LinearSequence& LinearSequence::operator=(LinearSequence&& other) = default;
+
+LinearSequence::Iterator LinearSequence::Begin() {
+  return Iterator(this);
+}
+
+LinearSequence::ReverseIterator LinearSequence::ReverseBegin() {
+  return ReverseIterator(this);
+}
+
+void LinearSequence::InflateToLevel(int level) {
+  if (forward_direction_) {
+    interval_ = initial_interval_.GetForwardInflatedInterval(level);
+    interval_.ForwardClampTo(inflate_limit_);
+  } else {
+    interval_ = initial_interval_.GetBackwardInflatedInterval(level);
+    interval_.BackwardClampTo(inflate_limit_);
+  }
+
+  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_;
+    if (affinity_sub_interval_.Intersects(interval_)) {
+      affinity_sub_interval_.Intersect(interval_);
+
+      // 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_;
+      } else {
+        after_sub_interval_ = Interval();
+        before_sub_interval_ = Interval(interval_.end(), interval_.start());
+      }
+
+      affinity_sub_interval_ = Interval();
+    }
+  } else {
+    affinity_sub_interval_ = affinity_interval_;
+    if (affinity_sub_interval_.Intersects(interval_)) {
+      affinity_sub_interval_.Intersect(interval_);
+
+      // 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_;
+      } else {
+        after_sub_interval_ = Interval();
+        before_sub_interval_ = Interval(interval_.end(), interval_.start());
+      }
+
+      affinity_sub_interval_ = Interval();
+    }
+  }
+}
+
+// LinearSequence::IteratorBase implementation.
+LinearSequence::IteratorBase::IteratorBase() : within_bounds_(false) {}
+
+LinearSequence::IteratorBase::IteratorBase(LinearSequence* level_sequence)
+    : level_sequence_(level_sequence), within_bounds_(true) {}
+
+LinearSequence::IteratorBase::IteratorBase(
+    const LinearSequence::IteratorBase& other) = default;
+LinearSequence::IteratorBase::IteratorBase(
+    LinearSequence::IteratorBase&& other) = default;
+
+LinearSequence::IteratorBase::~IteratorBase() = default;
+
+LinearSequence::IteratorBase& LinearSequence::IteratorBase::operator=(
+    const LinearSequence::IteratorBase& other) = default;
+LinearSequence::IteratorBase& LinearSequence::IteratorBase::operator=(
+    LinearSequence::IteratorBase&& other) = 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;
+}
+
+// LinearSequence::Iterator implementation.
+LinearSequence::Iterator::Iterator() {}
+
+LinearSequence::Iterator::Iterator(LinearSequence* level_sequence)
+    : LinearSequence::IteratorBase(level_sequence),
+      affinity_sub_interval_iterator_(
+          level_sequence_->affinity_sub_interval_.Begin()),
+      before_sub_interval_iterator_(
+          level_sequence_->before_sub_interval_.Begin()),
+      after_sub_interval_iterator_(
+          level_sequence_->after_sub_interval_.Begin()),
+      before_first_(true) {
+  Setup();
+
+  current_sub_interval_iterator_ = GetCurrentSubIntervalIteratorType();
+  current_index_ =
+      sub_interval_iterators_[ENUM_TO_INDEX(current_sub_interval_iterator_)]
+          ->index();
+}
+
+LinearSequence::Iterator::Iterator(const LinearSequence::Iterator& other)
+    : IteratorBase(other),
+      affinity_sub_interval_iterator_(other.affinity_sub_interval_iterator_),
+      before_sub_interval_iterator_(other.before_sub_interval_iterator_),
+      after_sub_interval_iterator_(other.after_sub_interval_iterator_),
+      before_first_(other.before_first_) {
+  Setup();
+}
+
+LinearSequence::Iterator::Iterator(LinearSequence::Iterator&& other)
+    : IteratorBase(std::move(other)),
+      affinity_sub_interval_iterator_(
+          std::move(other.affinity_sub_interval_iterator_)),
+      before_sub_interval_iterator_(
+          std::move(other.before_sub_interval_iterator_)),
+      after_sub_interval_iterator_(
+          std::move(other.after_sub_interval_iterator_)),
+      before_first_(other.before_first_) {
+  Setup();
+}
+
+LinearSequence::Iterator::~Iterator() = default;
+
+LinearSequence::Iterator& LinearSequence::Iterator::operator=(
+    const LinearSequence::Iterator& other) {
+  IteratorBase::operator=(other);
+  affinity_sub_interval_iterator_ = other.affinity_sub_interval_iterator_;
+  before_sub_interval_iterator_ = other.before_sub_interval_iterator_;
+  after_sub_interval_iterator_ = other.after_sub_interval_iterator_;
+  before_first_ = other.before_first_;
+
+  Setup();
+
+  return *this;
+}
+LinearSequence::Iterator& LinearSequence::Iterator::operator=(
+    LinearSequence::Iterator&& other) {
+  IteratorBase::operator=(std::move(other));
+  affinity_sub_interval_iterator_ =
+      std::move(other.affinity_sub_interval_iterator_);
+  before_sub_interval_iterator_ =
+      std::move(other.before_sub_interval_iterator_);
+  after_sub_interval_iterator_ = std::move(other.after_sub_interval_iterator_);
+  before_first_ = other.before_first_;
+
+  Setup();
+
+  return *this;
+}
+
+void LinearSequence::Iterator::Setup() {
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFFINITY)] =
+      &affinity_sub_interval_iterator_;
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::BEFORE)] =
+      &before_sub_interval_iterator_;
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFTER)] =
+      &after_sub_interval_iterator_;
+}
+
+LinearSequence::IteratorBase::SubIntervalIteratorType
+LinearSequence::Iterator::GetCurrentSubIntervalIteratorType() {
+  if (affinity_sub_interval_iterator_)
+    return SubIntervalIteratorType::AFFINITY;
+
+  if (before_first_) {
+    before_first_ = false;
+    if (before_sub_interval_iterator_)
+      return SubIntervalIteratorType::BEFORE;
+
+    return SubIntervalIteratorType::AFTER;
+  } else {
+    before_first_ = true;
+    if (after_sub_interval_iterator_)
+      return SubIntervalIteratorType::AFTER;
+
+    return SubIntervalIteratorType::BEFORE;
+  }
+}
+
+bool LinearSequence::Iterator::IsWithinBounds() {
+  return affinity_sub_interval_iterator_ || before_sub_interval_iterator_ ||
+         after_sub_interval_iterator_;
+}
+
+// LinearSequence::ReverseIterator implementation.
+LinearSequence::ReverseIterator::ReverseIterator() {}
+
+LinearSequence::ReverseIterator::ReverseIterator(LinearSequence* level_sequence)
+    : LinearSequence::IteratorBase(level_sequence),
+      affinity_sub_interval_reverse_iterator_(
+          level_sequence_->affinity_sub_interval_.ReverseBegin()),
+      before_sub_interval_reverse_iterator_(
+          level_sequence_->before_sub_interval_.ReverseBegin()),
+      after_sub_interval_reverse_iterator_(
+          level_sequence_->after_sub_interval_.ReverseBegin()),
+      after_first_(true),
+      before_sub_interval_span_(
+          level_sequence_->before_sub_interval_.GetSpan()),
+      after_sub_interval_span_(level_sequence_->after_sub_interval_.GetSpan()) {
+  Setup();
+
+  current_sub_interval_iterator_ = GetCurrentSubIntervalIteratorType();
+  current_index_ =
+      sub_interval_iterators_[ENUM_TO_INDEX(current_sub_interval_iterator_)]
+          ->index();
+}
+
+LinearSequence::ReverseIterator::ReverseIterator(
+    const LinearSequence::ReverseIterator& other)
+    : IteratorBase(other),
+      affinity_sub_interval_reverse_iterator_(
+          other.affinity_sub_interval_reverse_iterator_),
+      before_sub_interval_reverse_iterator_(
+          other.before_sub_interval_reverse_iterator_),
+      after_sub_interval_reverse_iterator_(
+          other.after_sub_interval_reverse_iterator_),
+      after_first_(other.after_first_),
+      before_sub_interval_span_(other.before_sub_interval_span_),
+      after_sub_interval_span_(other.after_sub_interval_span_) {
+  Setup();
+}
+
+LinearSequence::ReverseIterator::ReverseIterator(
+    LinearSequence::ReverseIterator&& other)
+    : IteratorBase(std::move(other)),
+      affinity_sub_interval_reverse_iterator_(
+          std::move(other.affinity_sub_interval_reverse_iterator_)),
+      before_sub_interval_reverse_iterator_(
+          std::move(other.before_sub_interval_reverse_iterator_)),
+      after_sub_interval_reverse_iterator_(
+          std::move(other.after_sub_interval_reverse_iterator_)),
+      after_first_(other.after_first_),
+      before_sub_interval_span_(other.before_sub_interval_span_),
+      after_sub_interval_span_(other.after_sub_interval_span_) {
+  Setup();
+}
+
+LinearSequence::ReverseIterator::~ReverseIterator() = default;
+
+LinearSequence::ReverseIterator& LinearSequence::ReverseIterator::operator=(
+    const LinearSequence::ReverseIterator& other) {
+  IteratorBase::operator=(other);
+  affinity_sub_interval_reverse_iterator_ =
+      other.affinity_sub_interval_reverse_iterator_;
+  before_sub_interval_reverse_iterator_ =
+      other.before_sub_interval_reverse_iterator_;
+  after_sub_interval_reverse_iterator_ =
+      other.after_sub_interval_reverse_iterator_;
+  after_first_ = other.after_first_;
+  before_sub_interval_span_ = other.before_sub_interval_span_;
+  after_sub_interval_span_ = other.after_sub_interval_span_;
+
+  Setup();
+
+  return *this;
+}
+LinearSequence::ReverseIterator& LinearSequence::ReverseIterator::operator=(
+    LinearSequence::ReverseIterator&& other) {
+  IteratorBase::operator=(std::move(other));
+  affinity_sub_interval_reverse_iterator_ =
+      std::move(other.affinity_sub_interval_reverse_iterator_);
+  before_sub_interval_reverse_iterator_ =
+      std::move(other.before_sub_interval_reverse_iterator_);
+  after_sub_interval_reverse_iterator_ =
+      std::move(other.after_sub_interval_reverse_iterator_);
+  after_first_ = other.after_first_;
+  before_sub_interval_span_ = other.before_sub_interval_span_;
+  after_sub_interval_span_ = other.after_sub_interval_span_;
+
+  Setup();
+
+  return *this;
+}
+
+void LinearSequence::ReverseIterator::Setup() {
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFFINITY)] =
+      &affinity_sub_interval_reverse_iterator_;
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::BEFORE)] =
+      &before_sub_interval_reverse_iterator_;
+  sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFTER)] =
+      &after_sub_interval_reverse_iterator_;
+}
+
+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 (after_sub_interval_reverse_iterator_)
+        return SubIntervalIteratorType::AFTER;
+
+      if (before_sub_interval_reverse_iterator_)
+        return SubIntervalIteratorType::BEFORE;
+    } else {
+      after_first_ = true;
+      if (before_sub_interval_reverse_iterator_)
+        return SubIntervalIteratorType::BEFORE;
+
+      if (after_sub_interval_reverse_iterator_)
+        return SubIntervalIteratorType::AFTER;
+    }
+  }
+
+  return SubIntervalIteratorType::AFFINITY;
+}
+
+bool LinearSequence::ReverseIterator::IsWithinBounds() {
+  return affinity_sub_interval_reverse_iterator_ ||
+         before_sub_interval_reverse_iterator_ ||
+         after_sub_interval_reverse_iterator_;
+}
+
+// TriangularSequence implementation.
+TriangularSequence::TriangularSequence()
+    : coverage_direction_(CoverageDirection::NONE),
+      traversal_sequence_(true, Interval(), Interval(), Interval()),
+      level_interval_(),
+      should_swap_index_representation_(false),
+      levels_to_skip_(0),
+      distance_(0) {}
+
+TriangularSequence::TriangularSequence(CoverageDirection coverage_direction,
+                                       LinearSequence&& traversal_sequence,
+                                       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(const TriangularSequence& other) =
+    default;
+
+TriangularSequence::TriangularSequence(TriangularSequence&& other) = default;
+
+TriangularSequence::~TriangularSequence() {}
+
+TriangularSequence& TriangularSequence::operator=(
+    const TriangularSequence& other) = default;
+
+TriangularSequence& TriangularSequence::operator=(TriangularSequence&& other) =
+    default;
+
+TriangularSequence::Iterator TriangularSequence::Begin() {
+  return Iterator(this);
+}
+
+TriangularSequence::ReverseIterator TriangularSequence::ReverseBegin() {
+  return ReverseIterator(this);
+}
+
+// TriangularSequence::IteratorBase implementation.
+TriangularSequence::IteratorBase::IteratorBase() {}
+
+TriangularSequence::IteratorBase::IteratorBase(
+    TriangularSequence* triangular_sequence)
+    : should_swap_index_representation_(
+          triangular_sequence->should_swap_index_representation_) {
+  DCHECK_NE(triangular_sequence->coverage_direction_, CoverageDirection::NONE);
+  Interval::Iterator level_interval_it =
+      triangular_sequence->level_interval_.Begin();
+  traversal_sequence_ = triangular_sequence->traversal_sequence_;
+  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(
+    const TriangularSequence::IteratorBase& other) = default;
+TriangularSequence::IteratorBase::IteratorBase(
+    TriangularSequence::IteratorBase&& other) = default;
+
+TriangularSequence::IteratorBase::~IteratorBase() = default;
+
+TriangularSequence::IteratorBase& TriangularSequence::IteratorBase::operator=(
+    const TriangularSequence::IteratorBase& other) = default;
+TriangularSequence::IteratorBase& TriangularSequence::IteratorBase::operator=(
+    TriangularSequence::IteratorBase&& other) = default;
+
+TriangularSequence::IteratorBase& TriangularSequence::IteratorBase::
+operator++() {
+  Advance();
+  UpdateCurrent();
+
+  return *this;
+}
+
+// TriangularSequence::Iterator implementation.
+TriangularSequence::Iterator::Iterator() {}
+
+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::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()
+    : consider_index_rect_(-1, -1, -1, -1),
+      ignore_index_rect_(-1, -1, -1, -1) {}
+
+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);
+
+  // 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),
+          TriangularSequence(
+              CoverageDirection::RIGHT,
+              LinearSequence(
+                  false, Interval(start, end),
+                  Interval(center_index_rect.bottom(), center_index_rect.top()),
+                  Interval(consider_index_rect_.bottom(),
+                           consider_index_rect_.top())),
+              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),
+          TriangularSequence(
+              CoverageDirection::TOP,
+              LinearSequence(
+                  false, Interval(start, end),
+                  Interval(center_index_rect.right(), center_index_rect.left()),
+                  Interval(consider_index_rect_.right(),
+                           consider_index_rect_.left())),
+              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),
+          TriangularSequence(
+              CoverageDirection::LEFT,
+              LinearSequence(
+                  true, Interval(start, end),
+                  Interval(center_index_rect.top(), center_index_rect.bottom()),
+                  Interval(consider_index_rect_.top(),
+                           consider_index_rect_.bottom())),
+              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),
+                TriangularSequence(
+                    CoverageDirection::BOTTOM,
+                    LinearSequence(true, Interval(start, end),
+                                   Interval(center_index_rect.left(),
+                                            center_index_rect.right()),
+                                   Interval(consider_index_rect_.left(),
+                                            consider_index_rect_.right())),
+                    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 TriangularSequence& triangular_sequence) {
+                       return triangular_sequence.coverage_direction() ==
+                              CoverageDirection::NONE;
+                     }),
+      triangular_sequences_.end());
+}
+
+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(this);
+}
+
+PyramidSequence::ReverseIterator PyramidSequence::ReverseBegin() {
+  return ReverseIterator(this);
+}
+
+void PyramidSequence::EmplaceAt(int position,
+                                TriangularSequence&& triangular_sequence) {
+  TriangularSequence::Vector::iterator it = triangular_sequences_.begin();
+  std::advance(it, position);
+  triangular_sequences_.emplace(it, std::move(triangular_sequence));
+  TriangularSequence::Vector::iterator erase_it = triangular_sequences_.begin();
+  std::advance(erase_it, position + 1);
+  triangular_sequences_.erase(erase_it);
+}
+
+// PyramidSequence::IteratorBase implementation.
+PyramidSequence::IteratorBase::IteratorBase()
+    : consider_index_rect_(-1, -1, -1, -1),
+      ignore_index_rect_(-1, -1, -1, -1),
+      current_triangular_sequence_it_(nullptr) {}
+
+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(
+    const PyramidSequence::IteratorBase& other) = default;
+
+PyramidSequence::IteratorBase::IteratorBase(
+    PyramidSequence::IteratorBase&& other) = default;
+
+PyramidSequence::IteratorBase::~IteratorBase() = default;
+
+PyramidSequence::IteratorBase& PyramidSequence::IteratorBase::operator=(
+    const PyramidSequence::IteratorBase& other) = default;
+
+PyramidSequence::IteratorBase& PyramidSequence::IteratorBase::operator=(
+    PyramidSequence::IteratorBase&& other) = 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::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->coverage_direction() != CoverageDirection::NONE);
+    triangular_sequence_iterators_.emplace_back(it->Begin());
+  }
+
+  Setup();
+}
+
+PyramidSequence::Iterator::Iterator(const PyramidSequence::Iterator& other)
+    : IteratorBase(other),
+      triangular_sequence_iterators_(other.triangular_sequence_iterators_) {
+  Setup();
+}
+
+PyramidSequence::Iterator::Iterator(PyramidSequence::Iterator&& other)
+    : IteratorBase(std::move(other)),
+      triangular_sequence_iterators_(
+          std::move(other.triangular_sequence_iterators_)) {
+  Setup();
+}
+
+PyramidSequence::Iterator::~Iterator() = default;
+
+PyramidSequence::Iterator& PyramidSequence::Iterator::operator=(
+    const PyramidSequence::Iterator& other) {
+  IteratorBase::operator=(other);
+  triangular_sequence_iterators_ = other.triangular_sequence_iterators_;
+
+  Setup();
+
+  return *this;
+}
+
+PyramidSequence::Iterator& PyramidSequence::Iterator::operator=(
+    PyramidSequence::Iterator&& other) {
+  IteratorBase::operator=(std::move(other));
+  triangular_sequence_iterators_ =
+      std::move(other.triangular_sequence_iterators_);
+
+  Setup();
+
+  return *this;
+}
+
+void PyramidSequence::Iterator::Setup() {
+  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();
+  }
+}
+
+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 TriangularSequence::Iterator& it) { return !it; }),
+      triangular_sequence_iterators_.end());
+
+  if (triangular_sequence_iterators_.empty())
+    return nullptr;
+
+  std::vector<TriangularSequence::Iterator>::iterator min_distance_it =
+      triangular_sequence_iterators_.begin();
+
+  for (std::vector<TriangularSequence::Iterator>::iterator it =
+           triangular_sequence_iterators_.begin();
+       it != triangular_sequence_iterators_.end(); ++it) {
+    int distance = it->GetNextDistance();
+    if (distance == 0) {
+      min_distance_it = it;
+      break;
+    }
+
+    if (min_distance_it->GetNextDistance() > distance)
+      min_distance_it = it;
+  }
+
+  return &(*min_distance_it);
+}
+
+// PyramidSequence::ReverseIterator implementation.
+PyramidSequence::ReverseIterator::ReverseIterator() {}
+
+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->ReverseBegin());
+  }
+
+  Setup();
+}
+
+PyramidSequence::ReverseIterator::ReverseIterator(
+    const PyramidSequence::ReverseIterator& other)
+    : IteratorBase(other),
+      triangular_sequence_reverse_iterators_(
+          other.triangular_sequence_reverse_iterators_) {
+  Setup();
+}
+
+PyramidSequence::ReverseIterator::ReverseIterator(
+    PyramidSequence::ReverseIterator&& other)
+    : IteratorBase(std::move(other)),
+      triangular_sequence_reverse_iterators_(
+          std::move(other.triangular_sequence_reverse_iterators_)) {
+  Setup();
+}
+
+PyramidSequence::ReverseIterator::~ReverseIterator() = default;
+
+PyramidSequence::ReverseIterator& PyramidSequence::ReverseIterator::operator=(
+    const PyramidSequence::ReverseIterator& other) {
+  IteratorBase::operator=(other);
+  triangular_sequence_reverse_iterators_ =
+      other.triangular_sequence_reverse_iterators_;
+  Setup();
+  return *this;
+}
+
+PyramidSequence::ReverseIterator& PyramidSequence::ReverseIterator::operator=(
+    PyramidSequence::ReverseIterator&& other) {
+  IteratorBase::operator=(std::move(other));
+  triangular_sequence_reverse_iterators_ =
+      std::move(other.triangular_sequence_reverse_iterators_);
+  Setup();
+  return *this;
+}
+
+void PyramidSequence::ReverseIterator::Setup() {
+  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();
+  }
+}
+
+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 TriangularSequence::ReverseIterator& it) { return !it; }),
+      triangular_sequence_reverse_iterators_.end());
+
+  if (triangular_sequence_reverse_iterators_.empty())
+    return nullptr;
+
+  std::vector<TriangularSequence::ReverseIterator>::reverse_iterator
+      max_distance_it = triangular_sequence_reverse_iterators_.rbegin();
+
+  for (std::vector<TriangularSequence::ReverseIterator>::reverse_iterator it =
+           triangular_sequence_reverse_iterators_.rbegin();
+       it != triangular_sequence_reverse_iterators_.rend(); ++it) {
+    int distance = it->GetNextDistance();
+
+    if (max_distance_it->GetNextDistance() < distance)
+      max_distance_it = it;
+  }
+
+  return &(*max_distance_it);
+}
+
+}  // namespace cc