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..5b33fda82806c27d1f21cb19880f63df7a77b6b4
--- /dev/null
+++ b/cc/base/pyramid_sequence.cc
@@ -0,0 +1,1058 @@
+// 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>
+
+namespace cc {
+
+namespace {
+
+int ClampNumberInForwardInterval(int number,
+                                 int interval_start,
+                                 int interval_end) {
+  DCHECK_LE(interval_start, interval_end);
+  if (number < interval_start)
+    return interval_start;
+  if (number > interval_end)
+    return interval_end;
+  return number;
+}
+
+int ClampNumberInBackwardInterval(int number,
+                                  int interval_start,
+                                  int interval_end) {
+  DCHECK_GE(interval_start, interval_end);
+  if (number > interval_start)
+    return interval_start;
+  if (number < interval_end)
+    return interval_end;
+  return number;
+}
+
+int LevelsToSkipAlongDirection(int levels) {
+  return levels > 0 ? levels : 0;
+}
+
+int LevelsToSkipPerpendicularToDirection(int levels) {
+  return levels >= 0 ? levels + 1 : 0;
+}
+
+enum class TilingCoverageDirection : uint8_t {
+  RIGHT = 0,
+  TOP_RIGHT,
+  TOP,
+  TOP_LEFT,
+  LEFT,
+  BOTTOM_LEFT,
+  BOTTOM,
+  BOTTOM_RIGHT
+};
+
+// The pyramid sequence covers following 8 directions while iterating.
+//
+//  TL  T  TR
+//   L  *   R    --->
+//  BL  B  BR
+//
+// The pyramid sequence can yeild better iteration order, if the positions of
+// its inlined level distance sequences are properly considered. Suppose primary
+// direction for coverage is right, then it can have inclination either to top
+// right or bottom right. This inclination is input by secondary direction.
+// The positions for right and inclined to bottom right (which is now considered
+// as default) is R, BR, TR, B, T, BL, TL, L.
+// This function returns the positions for different directions.

[prashant.n, 2016/07/20 03:10:49]

This function will play important role in giving better iteration order when
content is flowing either by means of scrolling, zooming or animation. I'll
write another CL, which will give us benefit of this. http://crbug.com/629052.

Currently only RIGHT with BOTTOM_RIGHT inclined is supported.

+TilingCoverageDirection* GetCoverageDirectionSequenceForDirections(
+    TilingCoverageDirection primary_direction,
+    TilingCoverageDirection secondary_direction) {
+  switch (primary_direction) {
+    case TilingCoverageDirection::RIGHT:
+      switch (secondary_direction) {
+        case TilingCoverageDirection::TOP_RIGHT:
+          static TilingCoverageDirection right_top_right[] = {
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::LEFT};
+          return right_top_right;
+        case TilingCoverageDirection::BOTTOM_RIGHT:
+          static TilingCoverageDirection right_bottom_right[] = {
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::LEFT};
+          return right_bottom_right;
+        default:
+          NOTREACHED();
+      }
+      break;
+
+    case TilingCoverageDirection::TOP_RIGHT:
+      switch (secondary_direction) {
+        case TilingCoverageDirection::TOP:
+          static TilingCoverageDirection top_right_top[] = {
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::BOTTOM_LEFT};
+          return top_right_top;
+        case TilingCoverageDirection::RIGHT:
+          static TilingCoverageDirection top_right_right[] = {
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::BOTTOM_LEFT};
+          return top_right_right;
+        default:
+          NOTREACHED();
+      }
+      break;
+
+    case TilingCoverageDirection::TOP:
+      switch (secondary_direction) {
+        case TilingCoverageDirection::TOP_RIGHT:
+          static TilingCoverageDirection top_top_right[] = {
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::BOTTOM};
+          return top_top_right;
+        case TilingCoverageDirection::TOP_LEFT:
+          static TilingCoverageDirection top_top_left[] = {
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::BOTTOM};
+          return top_top_left;
+        default:
+          NOTREACHED();
+      }
+      break;
+
+    case TilingCoverageDirection::TOP_LEFT:
+      switch (secondary_direction) {
+        case TilingCoverageDirection::TOP:
+          static TilingCoverageDirection top_left_top[] = {
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::BOTTOM_RIGHT};
+          return top_left_top;
+        case TilingCoverageDirection::LEFT:
+          static TilingCoverageDirection top_left_left[] = {
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::BOTTOM_RIGHT};
+          return top_left_left;
+        default:
+          NOTREACHED();
+      }
+      break;
+
+    case TilingCoverageDirection::LEFT:
+      switch (secondary_direction) {
+        case TilingCoverageDirection::TOP_LEFT:
+          static TilingCoverageDirection left_top_left[] = {
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::RIGHT};
+          return left_top_left;
+        case TilingCoverageDirection::BOTTOM_LEFT:
+          static TilingCoverageDirection left_bottom_left[] = {
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::RIGHT};
+          return left_bottom_left;
+        default:
+          NOTREACHED();
+      }
+      break;
+
+    case TilingCoverageDirection::BOTTOM_LEFT:
+      switch (secondary_direction) {
+        case TilingCoverageDirection::LEFT:
+          static TilingCoverageDirection bottom_left_left[] = {
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::TOP_RIGHT};
+          return bottom_left_left;
+        case TilingCoverageDirection::BOTTOM:
+          static TilingCoverageDirection bottom_left_bottom[] = {
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::TOP_RIGHT};
+          return bottom_left_bottom;
+        default:
+          NOTREACHED();
+      }
+      break;
+
+    case TilingCoverageDirection::BOTTOM:
+      switch (secondary_direction) {
+        case TilingCoverageDirection::BOTTOM_LEFT:
+          static TilingCoverageDirection bottom_bottom_left[] = {
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::TOP};
+          return bottom_bottom_left;
+        case TilingCoverageDirection::BOTTOM_RIGHT:
+          static TilingCoverageDirection bottom_bottom_right[] = {
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::TOP_LEFT,
+              TilingCoverageDirection::TOP};
+          return bottom_bottom_right;
+        default:
+          NOTREACHED();
+      }
+      break;
+
+    case TilingCoverageDirection::BOTTOM_RIGHT:
+      switch (secondary_direction) {
+        case TilingCoverageDirection::BOTTOM:
+          static TilingCoverageDirection bottom_right_bottom[] = {
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::TOP_LEFT};
+          return bottom_right_bottom;
+        case TilingCoverageDirection::RIGHT:
+          static TilingCoverageDirection bottom_right_right[] = {
+              TilingCoverageDirection::BOTTOM_RIGHT,
+              TilingCoverageDirection::RIGHT,
+              TilingCoverageDirection::BOTTOM,
+              TilingCoverageDirection::TOP_RIGHT,
+              TilingCoverageDirection::BOTTOM_LEFT,
+              TilingCoverageDirection::TOP,
+              TilingCoverageDirection::LEFT,
+              TilingCoverageDirection::TOP_LEFT};
+          return bottom_right_right;
+        default:
+          NOTREACHED();
+      }
+      break;
+  }
+
+  return nullptr;
+}
+
+int GetPositionForDirection(TilingCoverageDirection* positions,
+                            TilingCoverageDirection direction) {
+  for (int i = 0; i < 8; ++i) {
+    if (positions[i] == direction)
+      return i;
+  }
+
+  NOTREACHED();
+  return -1;
+}
+
+}  // namespace
+
+// TriangularSequence implementation.
+TriangularSequence::TriangularSequence(std::string&& name,
+                                       Type type,
+                                       Interval&& interval,
+                                       Interval&& interval_inflate_limit,
+                                       int levels,
+                                       int levels_to_skip,
+                                       bool reverse)
+    : name_(std::move(name)),
+      type_(type),
+      interval_(std::move(interval)),
+      interval_inflate_limit_(std::move(interval_inflate_limit)),
+      initial_interval_(interval_),
+      levels_(levels),
+      levels_traversed_(0),
+      levels_limit_(levels),
+      reverse_(reverse),
+      within_bounds_(true),
+      inflate_(nullptr),
+      is_within_bounds_(nullptr) {
+  DCHECK_GE(levels, 0);
+  Init(type);
+  (this->*inflate_)(levels_to_skip);
+
+  if (reverse) {
+    levels_limit_ = levels_traversed_;
+    int last_level = levels - levels_to_skip - 1;
+    (this->*inflate_)(last_level);
+  }
+}
+
+TriangularSequence::TriangularSequence(const TriangularSequence& other) =
+    default;
+
+TriangularSequence::TriangularSequence(TriangularSequence&& other) = default;
+
+TriangularSequence::~TriangularSequence() {
+  inflate_ = nullptr;
+  is_within_bounds_ = nullptr;
+}
+
+TriangularSequence& TriangularSequence::operator=(
+    const TriangularSequence& other) = default;
+
+TriangularSequence& TriangularSequence::operator=(TriangularSequence&& other) =
+    default;
+
+int TriangularSequence::GetInitialIntervalSpan() {
+  return step_ == 1 ? initial_interval_.end - initial_interval_.start + 1
+                    : initial_interval_.start - initial_interval_.end + 1;
+}
+
+int TriangularSequence::GetCurrentSequenceNumber() {
+  DCHECK(inflate_);
+  if (levels_traversed_ < levels_limit_ && !within_bounds_)
+    (this->*inflate_)(1);
+
+  return current_sequence_number_;
+}
+
+int TriangularSequence::GetReverseCurrentSequenceNumber() {
+  DCHECK(inflate_);
+  if (levels_traversed_ >= levels_limit_ && !within_bounds_)
+    (this->*inflate_)(-1);
+
+  return current_sequence_number_;
+}
+
+void TriangularSequence::Advance() {
+  DCHECK(is_within_bounds_);
+  current_sequence_number_ += step_;
+  within_bounds_ = (this->*is_within_bounds_)();
+}
+
+void TriangularSequence::Init(TriangularSequence::Type type) {
+  switch (type) {
+    case TriangularSequence::Type::FORWARD:
+      inflate_ = &TriangularSequence::InflateForward;
+      is_within_bounds_ = &TriangularSequence::IsWithinBoundsForward;
+      step_ = reverse_ ? -1 : 1;
+      break;
+    case TriangularSequence::Type::BACKWARD:
+      inflate_ = &TriangularSequence::InflateBackward;
+      is_within_bounds_ = &TriangularSequence::IsWithinBoundsBackward;
+      step_ = reverse_ ? 1 : -1;
+      break;
+    case TriangularSequence::Type::DIAGONAL_FORWARD:
+      DCHECK_EQ(interval_.start, interval_.end);
+      inflate_ = &TriangularSequence::InflateDiagonalForward;
+      is_within_bounds_ = &TriangularSequence::IsWithinBoundsDiagonal;
+      step_ = reverse_ ? -1 : 1;
+      break;
+    case TriangularSequence::Type::DIAGONAL_BACKWARD:
+      DCHECK_EQ(interval_.start, interval_.end);
+      inflate_ = &TriangularSequence::InflateDiagonalBackward;
+      is_within_bounds_ = &TriangularSequence::IsWithinBoundsDiagonal;
+      step_ = reverse_ ? 1 : -1;
+      break;
+  }
+}
+
+void TriangularSequence::Reset() {
+  current_sequence_number_ = reverse_ ? interval_.end : interval_.start;
+  within_bounds_ = true;
+}
+
+void TriangularSequence::InflateForward(int levels) {
+  levels_traversed_ += levels;
+  interval_.start = initial_interval_.start - levels_traversed_;
+  interval_.end = initial_interval_.end + levels_traversed_;
+
+  interval_.start = ClampNumberInForwardInterval(interval_.start,
+                                                 interval_inflate_limit_.start,
+                                                 interval_inflate_limit_.end);
+  interval_.end =
+      ClampNumberInForwardInterval(interval_.end, interval_inflate_limit_.start,
+                                   interval_inflate_limit_.end);
+
+  Reset();
+}
+
+void TriangularSequence::InflateBackward(int levels) {
+  levels_traversed_ += levels;
+  interval_.start = initial_interval_.start + levels_traversed_;
+  interval_.end = initial_interval_.end - levels_traversed_;
+  interval_.start = ClampNumberInBackwardInterval(interval_.start,
+                                                  interval_inflate_limit_.start,
+                                                  interval_inflate_limit_.end);
+  interval_.end = ClampNumberInBackwardInterval(interval_.end,
+                                                interval_inflate_limit_.start,
+                                                interval_inflate_limit_.end);
+
+  Reset();
+}
+
+void TriangularSequence::InflateDiagonalForward(int levels) {
+  levels_traversed_ += levels;
+  interval_.start = initial_interval_.start + levels_traversed_;
+  interval_.end = initial_interval_.end + levels_traversed_;
+
+  Reset();
+}
+
+void TriangularSequence::InflateDiagonalBackward(int levels) {
+  levels_traversed_ += levels;
+  interval_.start = initial_interval_.start - levels_traversed_;
+  interval_.end = initial_interval_.end - levels_traversed_;
+
+  Reset();
+}
+
+bool TriangularSequence::IsWithinBoundsForward() {
+  DCHECK(reverse_ ? current_sequence_number_ <= interval_.end
+                  : current_sequence_number_ >= interval_.start);
+
+  if (interval_.start == interval_.end ||
+      (reverse_ ? current_sequence_number_ < interval_.start
+                : current_sequence_number_ > interval_.end))
+    return false;
+
+  return true;
+}
+
+bool TriangularSequence::IsWithinBoundsBackward() {
+  DCHECK(reverse_ ? current_sequence_number_ >= interval_.end
+                  : current_sequence_number_ <= interval_.start);
+
+  if (interval_.start == interval_.end ||
+      (reverse_ ? current_sequence_number_ > interval_.start
+                : current_sequence_number_ < interval_.end))
+    return false;
+
+  return true;
+}
+
+bool TriangularSequence::IsWithinBoundsDiagonal() {
+  DCHECK_EQ(interval_.start, interval_.end);
+  if (current_sequence_number_ != interval_.start)
+    return false;
+
+  return true;
+}
+
+// LevelDistanceSequence implementation.
+LevelDistanceSequence::LevelDistanceSequence()
+    : traversal_sequence_(TriangularSequence(std::string("dummy"),
+                                             TriangularSequence::Type::FORWARD,
+                                             TriangularSequence::Interval(0, 0),
+                                             TriangularSequence::Interval(0, 0),
+                                             0,
+                                             0,
+                                             false)),
+      swapped_(false),
+      reverse_(false),
+      current_sequence_index_(-1),
+      current_level_index_(-1) {}
+
+LevelDistanceSequence::LevelDistanceSequence(
+    TriangularSequence&& traversal_sequence,
+    TriangularSequence&& level_sequence,
+    bool swapped,
+    int levels_to_skip,
+    int levels_delta,
+    int distance,
+    bool reverse)
+    : traversal_sequence_(std::move(traversal_sequence)),
+      swapped_(swapped),
+      reverse_(reverse) {
+  for (int i = levels_to_skip; i < level_sequence.GetInitialIntervalSpan();
+       ++i) {
+    int d = distance * i;
+    int l = level_sequence.GetCurrentSequenceNumber() + levels_delta;
+
+    level_distances_.push_back(LevelDistance(l, d));
+    level_sequence.Advance();
+  }
+  if (IsValid())
+    Reset();
+}
+
+LevelDistanceSequence::LevelDistanceSequence(
+    const LevelDistanceSequence& other) = default;
+
+LevelDistanceSequence::LevelDistanceSequence(LevelDistanceSequence&& other) =
+    default;
+
+LevelDistanceSequence::~LevelDistanceSequence() {
+  level_distances_.clear();
+}
+
+LevelDistanceSequence& LevelDistanceSequence::operator=(
+    const LevelDistanceSequence& other) = default;
+
+LevelDistanceSequence& LevelDistanceSequence::operator=(
+    LevelDistanceSequence&& other) = default;
+
+int LevelDistanceSequence::GetCurrentIndexX() const {
+  return swapped_ ? current_level_index_ : current_sequence_index_;
+}
+
+int LevelDistanceSequence::GetCurrentIndexY() const {
+  return swapped_ ? current_sequence_index_ : current_level_index_;
+}
+
+int LevelDistanceSequence::GetMinimumDistance() const {
+  DCHECK(!level_distances_.empty());
+  return level_distances_.front().distance;
+}
+
+int LevelDistanceSequence::GetMaximumDistance() const {
+  DCHECK(!level_distances_.empty());
+  return level_distances_.back().distance;
+}
+
+bool LevelDistanceSequence::Advance() {
+  traversal_sequence_.Advance();
+  if (!traversal_sequence_.is_within_bounds()) {
+    level_distances_.erase(level_distances_.begin());
+    if (IsValid())
+      Reset();
+
+    return false;
+  }
+
+  current_sequence_index_ = traversal_sequence_.GetCurrentSequenceNumber();
+  return true;
+}
+
+bool LevelDistanceSequence::ReverseAdvance() {
+  traversal_sequence_.Advance();
+  if (!traversal_sequence_.is_within_bounds()) {
+    level_distances_.erase(level_distances_.end() - 1);
+    if (IsValid())
+      Reset();
+
+    return false;
+  }
+
+  current_sequence_index_ =
+      traversal_sequence_.GetReverseCurrentSequenceNumber();
+  return true;
+}
+
+void LevelDistanceSequence::Reset() {
+  DCHECK(!level_distances_.empty());
+  if (reverse_) {
+    current_sequence_index_ =
+        traversal_sequence_.GetReverseCurrentSequenceNumber();
+    current_level_index_ = level_distances_.back().level;
+  } else {
+    current_sequence_index_ = traversal_sequence_.GetCurrentSequenceNumber();
+    current_level_index_ = level_distances_.front().level;
+  }
+}
+
+// PyramidSequence implementation.
+PyramidSequence::PyramidSequence(bool reverse)
+    : reverse_(reverse),
+      current_level_distance_sequence_(nullptr),
+      index_x_(-1),
+      index_y_(-1) {}
+
+PyramidSequence::PyramidSequence(const PyramidSequence& other) = default;
+
+PyramidSequence::PyramidSequence(PyramidSequence&& other) = default;
+
+PyramidSequence::~PyramidSequence() {
+  level_distance_sequences_.clear();
+  current_level_distance_sequence_ = nullptr;
+}
+
+PyramidSequence& PyramidSequence::operator=(const PyramidSequence& other) =
+    default;
+
+PyramidSequence& PyramidSequence::operator=(PyramidSequence&& other) = default;
+
+bool PyramidSequence::IsTraversed() {
+  if (!current_level_distance_sequence_)
+    return true;
+
+  return level_distance_sequences_.empty();
+}
+
+void PyramidSequence::Init(int around_left,
+                           int around_right,
+                           int around_top,
+                           int around_bottom,
+                           int consider_left,
+                           int consider_right,
+                           int consider_top,
+                           int consider_bottom,
+                           int ignore_left,
+                           int ignore_right,
+                           int ignore_top,
+                           int ignore_bottom,
+                           int width,
+                           int height) {
+  consider_left_ = consider_left;
+  consider_right_ = consider_right;
+  consider_top_ = consider_top;
+  consider_bottom_ = consider_bottom;
+  ignore_left_ = ignore_left;
+  ignore_right_ = ignore_right;
+  ignore_top_ = ignore_top;
+  ignore_bottom_ = ignore_bottom;
+
+  int left_levels = around_left - consider_left + 1;
+  int right_levels = consider_right - around_right + 1;
+  int top_levels = around_top - consider_top + 1;
+  int bottom_levels = consider_bottom - around_bottom + 1;
+
+  int skip_left_levels = around_left - consider_right;
+  int skip_right_levels = consider_left - around_right;
+  int skip_top_levels = around_top - consider_bottom;
+  int skip_bottom_levels = consider_top - around_bottom;
+
+  int skip_left_levels_perp =
+      LevelsToSkipPerpendicularToDirection(skip_left_levels);
+  int skip_right_levels_perp =
+      LevelsToSkipPerpendicularToDirection(skip_right_levels);
+  int skip_top_levels_perp =
+      LevelsToSkipPerpendicularToDirection(skip_top_levels);
+  int skip_bottom_levels_perp =
+      LevelsToSkipPerpendicularToDirection(skip_bottom_levels);
+
+  skip_left_levels = LevelsToSkipAlongDirection(skip_left_levels);
+  skip_right_levels = LevelsToSkipAlongDirection(skip_right_levels);
+  skip_top_levels = LevelsToSkipAlongDirection(skip_top_levels);
+  skip_bottom_levels = LevelsToSkipAlongDirection(skip_bottom_levels);
+
+  int diagonal_length = std::max(width, height);
+
+  DCHECK(level_distance_sequences_.empty());
+  level_distance_sequences_.resize(8);
+  // TODO(prashant.n): Implement direction of movement for this instead of
+  // default right direction. http://crbug.com/629052.
+  TilingCoverageDirection* positions =
+      GetCoverageDirectionSequenceForDirections(
+          TilingCoverageDirection::RIGHT,
+          TilingCoverageDirection::BOTTOM_RIGHT);
+  DCHECK(positions);
+
+  // RIGHT seq
+  if (right_levels > 0) {
+    int start = around_bottom - 1;
+    int end = around_top + 1;
+    int skip_levels =
+        std::max(skip_right_levels,
+                 std::max(skip_bottom_levels_perp, skip_top_levels_perp));
+    if (right_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions, TilingCoverageDirection::RIGHT),
+          LevelDistanceSequence(
+              TriangularSequence(
+                  std::string("r.seq"), TriangularSequence::Type::BACKWARD,
+                  TriangularSequence::Interval(start, end),
+                  TriangularSequence::Interval(consider_bottom, consider_top),
+                  right_levels, skip_levels, reverse_),
+              TriangularSequence(
+                  std::string("r.lev"), TriangularSequence::Type::FORWARD,
+                  TriangularSequence::Interval(around_right, consider_right),
+                  TriangularSequence::Interval(consider_left, consider_right),
+                  1, 0, false),
+              true, skip_levels, skip_levels - skip_right_levels, width,
+              reverse_));
+    }
+  }
+
+  // TOP_RIGHT seq
+  if (right_levels > 0 && top_levels > 0) {
+    int skip_levels = std::max(skip_right_levels, skip_top_levels);
+    int diagonal_levels = std::min(right_levels, top_levels);
+    if (diagonal_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions,
+                                  TilingCoverageDirection::TOP_RIGHT),
+          LevelDistanceSequence(
+              TriangularSequence(
+                  std::string("tr.seq"),
+                  TriangularSequence::Type::DIAGONAL_FORWARD,
+                  TriangularSequence::Interval(around_right, around_right),
+                  TriangularSequence::Interval(consider_left, consider_right),
+                  diagonal_levels, skip_levels, reverse_),
+              TriangularSequence(
+                  std::string("tr.lev"), TriangularSequence::Type::BACKWARD,
+                  TriangularSequence::Interval(
+                      around_top, around_top - diagonal_levels + 1),
+                  TriangularSequence::Interval(consider_bottom, consider_top),
+                  1, 0, false),
+              false, skip_levels, skip_levels - skip_top_levels,
+              diagonal_length, reverse_));
+    }
+  }
+
+  // TOP seq
+  if (top_levels > 0) {
+    int start = around_right - 1;
+    int end = around_left + 1;
+    int skip_levels =
+        std::max(skip_top_levels,
+                 std::max(skip_right_levels_perp, skip_left_levels_perp));
+    if (top_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions, TilingCoverageDirection::TOP),
+          LevelDistanceSequence(
+              TriangularSequence(
+                  std::string("t.seq"), TriangularSequence::Type::BACKWARD,
+                  TriangularSequence::Interval(start, end),
+                  TriangularSequence::Interval(consider_right, consider_left),
+                  top_levels, skip_levels, reverse_),
+              TriangularSequence(
+                  std::string("t.lev"), TriangularSequence::Type::BACKWARD,
+                  TriangularSequence::Interval(around_top, consider_top),
+                  TriangularSequence::Interval(consider_bottom, consider_top),
+                  1, 0, false),
+              false, skip_levels, skip_levels - skip_top_levels, height,
+              reverse_));
+    }
+  }
+
+  // TOP_LEFT seq
+  if (top_levels > 0 && left_levels > 0) {
+    int skip_levels = std::max(skip_top_levels, skip_left_levels);
+    int diagonal_levels = std::min(top_levels, left_levels);
+    if (diagonal_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions, TilingCoverageDirection::TOP_LEFT),
+          LevelDistanceSequence(
+              TriangularSequence(
+                  std::string("tl.seq"),
+                  TriangularSequence::Type::DIAGONAL_BACKWARD,
+                  TriangularSequence::Interval(around_left, around_left),
+                  TriangularSequence::Interval(consider_right, consider_left),
+                  diagonal_levels, skip_levels, reverse_),
+              TriangularSequence(
+                  std::string("tl.lev"), TriangularSequence::Type::BACKWARD,
+                  TriangularSequence::Interval(
+                      around_top, around_top - diagonal_levels + 1),
+                  TriangularSequence::Interval(consider_bottom, consider_top),
+                  1, 0, false),
+              false, skip_levels, skip_levels - skip_top_levels,
+              diagonal_length, reverse_));
+    }
+  }
+
+  // LEFT seq
+  if (left_levels > 0) {
+    int start = around_top + 1;
+    int end = around_bottom - 1;
+    int skip_levels =
+        std::max(skip_left_levels,
+                 std::max(skip_top_levels_perp, skip_bottom_levels_perp));
+    if (left_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions, TilingCoverageDirection::LEFT),
+          LevelDistanceSequence(
+              TriangularSequence(
+                  std::string("l.seq"), TriangularSequence::Type::FORWARD,
+                  TriangularSequence::Interval(start, end),
+                  TriangularSequence::Interval(consider_top, consider_bottom),
+                  left_levels, skip_levels, reverse_),
+              TriangularSequence(
+                  std::string("l.lev"), TriangularSequence::Type::BACKWARD,
+                  TriangularSequence::Interval(around_left, consider_left),
+                  TriangularSequence::Interval(consider_right, consider_left),
+                  1, 0, false),
+              true, skip_levels, skip_levels - skip_left_levels, width,
+              reverse_));
+    }
+  }
+
+  // BOTTOM_LEFT seq
+  if (left_levels > 0 && bottom_levels > 0) {
+    int skip_levels = std::max(skip_left_levels, skip_bottom_levels);
+    int diagonal_levels = std::min(left_levels, bottom_levels);
+    if (diagonal_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions,
+                                  TilingCoverageDirection::BOTTOM_LEFT),
+          LevelDistanceSequence(
+              TriangularSequence(
+                  std::string("bl.seq"),
+                  TriangularSequence::Type::DIAGONAL_BACKWARD,
+                  TriangularSequence::Interval(around_left, around_left),
+                  TriangularSequence::Interval(consider_right, consider_left),
+                  diagonal_levels, skip_levels, reverse_),
+              TriangularSequence(
+                  std::string("bl.lev"), TriangularSequence::Type::FORWARD,
+                  TriangularSequence::Interval(
+                      around_bottom, around_bottom + diagonal_levels - 1),
+                  TriangularSequence::Interval(consider_top, consider_bottom),
+                  1, 0, false),
+              false, skip_levels, skip_levels - skip_bottom_levels,
+              diagonal_length, reverse_));
+    }
+  }
+
+  // BOTTOM seq
+  if (bottom_levels > 0) {
+    int start = around_left + 1;
+    int end = around_right - 1;
+    int skip_levels =
+        std::max(skip_bottom_levels,
+                 std::max(skip_left_levels_perp, skip_right_levels_perp));
+    if (bottom_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions, TilingCoverageDirection::BOTTOM),
+          LevelDistanceSequence(
+              TriangularSequence(
+                  std::string("b.seq"), TriangularSequence::Type::FORWARD,
+                  TriangularSequence::Interval(start, end),
+                  TriangularSequence::Interval(consider_left, consider_right),
+                  bottom_levels, skip_levels, reverse_),
+              TriangularSequence(
+                  std::string("b.lev"), TriangularSequence::Type::FORWARD,
+                  TriangularSequence::Interval(around_bottom, consider_bottom),
+                  TriangularSequence::Interval(consider_top, consider_bottom),
+                  1, 0, false),
+              false, skip_levels, skip_levels - skip_bottom_levels, height,
+              reverse_));
+    }
+  }
+
+  // BOTTOM_RIGHT seq
+  if (bottom_levels > 0 && right_levels > 0) {
+    int skip_levels = std::max(skip_bottom_levels, skip_right_levels);
+    int diagonal_levels = std::min(bottom_levels, right_levels);
+    if (diagonal_levels > skip_levels) {
+      EmplaceAt(
+          GetPositionForDirection(positions,
+                                  TilingCoverageDirection::BOTTOM_RIGHT),
+          LevelDistanceSequence(
+              TriangularSequence(
+                  std::string("br.seq"),
+                  TriangularSequence::Type::DIAGONAL_FORWARD,
+                  TriangularSequence::Interval(around_right, around_right),
+                  TriangularSequence::Interval(consider_left, consider_right),
+                  diagonal_levels, skip_levels, reverse_),
+              TriangularSequence(
+                  std::string("br.lev"), TriangularSequence::Type::FORWARD,
+                  TriangularSequence::Interval(
+                      around_bottom, around_bottom + diagonal_levels - 1),
+                  TriangularSequence::Interval(consider_top, consider_bottom),
+                  1, 0, false),
+              false, skip_levels, skip_levels - skip_bottom_levels,
+              diagonal_length, reverse_));
+    }
+  }
+
+  current_level_distance_sequence_ = GetNextLevelDistanceSequence();
+  UpdateCurrent();
+}
+
+void PyramidSequence::EmplaceAt(
+    int position,
+    LevelDistanceSequence&& level_distance_sequence) {
+  LevelDistanceSequence::Iterator it = level_distance_sequences_.begin();
+  std::advance(it, position);
+  level_distance_sequences_.emplace(it, std::move(level_distance_sequence));
+  LevelDistanceSequence::Iterator erase_it = level_distance_sequences_.begin();
+  std::advance(erase_it, position + 1);
+  level_distance_sequences_.erase(erase_it);
+}
+
+void PyramidSequence::UpdateCurrent() {
+  while (!IsTraversed()) {
+    DCHECK(current_level_distance_sequence_->IsValid());
+
+    index_x_ = current_level_distance_sequence_->GetCurrentIndexX();
+    index_y_ = current_level_distance_sequence_->GetCurrentIndexY();
+
+    if (InConsiderRect() && !InIgnoreRect())
+      break;
+
+    Advance();
+  }
+}
+
+bool PyramidSequence::InConsiderRect() const {
+  return index_x_ >= consider_left_ && index_x_ <= consider_right_ &&
+         index_y_ >= consider_top_ && index_y_ <= consider_bottom_;
+}
+
+bool PyramidSequence::InIgnoreRect() const {
+  return index_x_ >= ignore_left_ && index_x_ <= ignore_right_ &&
+         index_y_ >= ignore_top_ && index_y_ <= ignore_bottom_;
+}
+
+void PyramidSequence::RemoveEmptyLevelDistanceSequences() {
+  level_distance_sequences_.erase(
+      std::remove_if(
+          level_distance_sequences_.begin(), level_distance_sequences_.end(),
+          [](const LevelDistanceSequence& seq) { return !seq.IsValid(); }),
+      level_distance_sequences_.end());
+}
+
+// TopDownPyramidSequence implementation.
+TopDownPyramidSequence::TopDownPyramidSequence() : PyramidSequence(false) {}
+
+TopDownPyramidSequence::TopDownPyramidSequence(
+    const TopDownPyramidSequence& other) = default;
+
+TopDownPyramidSequence::TopDownPyramidSequence(TopDownPyramidSequence&& other) =
+    default;
+
+TopDownPyramidSequence::~TopDownPyramidSequence() {}
+
+TopDownPyramidSequence& TopDownPyramidSequence::operator=(
+    const TopDownPyramidSequence& other) = default;
+
+TopDownPyramidSequence& TopDownPyramidSequence::operator=(
+    TopDownPyramidSequence&& other) = default;
+
+void TopDownPyramidSequence::Advance() {
+  if (IsTraversed())
+    return;
+
+  if (!current_level_distance_sequence_->Advance())
+    current_level_distance_sequence_ = GetNextLevelDistanceSequence();
+}
+
+LevelDistanceSequence* TopDownPyramidSequence::GetNextLevelDistanceSequence() {
+  RemoveEmptyLevelDistanceSequences();
+
+  if (level_distance_sequences_.empty())
+    return nullptr;
+
+  LevelDistanceSequence::Iterator min_distance_it =
+      level_distance_sequences_.begin();
+
+  for (LevelDistanceSequence::Iterator it = level_distance_sequences_.begin();
+       it != level_distance_sequences_.end(); ++it) {
+    int distance = it->GetMinimumDistance();
+    if (distance == 0)
+      return &(*it);
+
+    if (min_distance_it->GetMinimumDistance() > distance)
+      min_distance_it = it;
+  }
+
+  return &(*min_distance_it);
+}
+
+// BottomUpPyramidSequence implementation.
+BottomUpPyramidSequence::BottomUpPyramidSequence() : PyramidSequence(true) {}
+
+BottomUpPyramidSequence::BottomUpPyramidSequence(
+    const BottomUpPyramidSequence& other)
+    : PyramidSequence(other) {}
+
+BottomUpPyramidSequence::BottomUpPyramidSequence(
+    BottomUpPyramidSequence&& other)
+    : PyramidSequence(std::move(other)) {}
+
+BottomUpPyramidSequence::~BottomUpPyramidSequence() {}
+
+BottomUpPyramidSequence& BottomUpPyramidSequence::operator=(
+    const BottomUpPyramidSequence& other) {
+  PyramidSequence::operator=(other);
+  return *this;
+}
+
+BottomUpPyramidSequence& BottomUpPyramidSequence::operator=(
+    BottomUpPyramidSequence&& other) {
+  PyramidSequence::operator=(std::move(other));
+  return *this;
+}
+
+void BottomUpPyramidSequence::Advance() {
+  if (IsTraversed())
+    return;
+
+  if (!current_level_distance_sequence_->ReverseAdvance())
+    current_level_distance_sequence_ = GetNextLevelDistanceSequence();
+}
+
+LevelDistanceSequence* BottomUpPyramidSequence::GetNextLevelDistanceSequence() {
+  RemoveEmptyLevelDistanceSequences();
+
+  if (level_distance_sequences_.empty())
+    return nullptr;
+
+  LevelDistanceSequence::ReverseIterator max_distance_it =
+      level_distance_sequences_.rbegin();
+
+  for (LevelDistanceSequence::ReverseIterator it =
+           level_distance_sequences_.rbegin();
+       it != level_distance_sequences_.rend(); ++it) {
+    int distance = it->GetMaximumDistance();
+
+    if (max_distance_it->GetMaximumDistance() < distance)
+      max_distance_it = it;
+  }
+
+  return &(*max_distance_it);
+}
+
+}  // namespace cc