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..5f13eb821f79c1090b67a0b8b2cc2d7026999655
--- /dev/null
+++ b/cc/base/pyramid_sequence.cc
@@ -0,0 +1,722 @@
+// 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 start_limit, int end_limit) {
+  DCHECK_LE(start_limit, end_limit);
+  if (number < start_limit)
+    return start_limit;
+  if (number > end_limit)
+    return end_limit;
+  return number;
+}
+
+int ClampNumberInBackwardInterval(int number, int start_limit, int end_limit) {
+  DCHECK_GE(start_limit, end_limit);
+  if (number > start_limit)
+    return start_limit;
+  if (number < end_limit)
+    return end_limit;
+  return number;
+}
+
+int LevelsToSkipAlongDirection(int levels) {
+  return levels > 0 ? levels : 0;
+}
+
+int LevelsToSkipPerpendicularToDirection(int levels) {
+  return levels >= 0 ? levels + 1 : 0;
+}
+
+enum class CoverageDirection : 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
+//
+// where -
+//   R  = right
+//   TR = top right
+//   T  = top
+//   TL = top left
+//   L  = left
+//   BL = bottom left
+//   B  = bottom
+//   BR = bottom right
+//
+// The following function returns the spiral order {R, TR, T, TL, L, BL, B, BR}.
+CoverageDirection* GetCoverageDirectionSequence() {
+  static CoverageDirection right_top_right[8] = {
+      CoverageDirection::RIGHT,  CoverageDirection::TOP_RIGHT,
+      CoverageDirection::TOP,    CoverageDirection::TOP_LEFT,
+      CoverageDirection::LEFT,   CoverageDirection::BOTTOM_LEFT,
+      CoverageDirection::BOTTOM, CoverageDirection::BOTTOM_RIGHT};
+  return right_top_right;
+}
+
+int GetPositionForDirection(CoverageDirection* positions,
+                            CoverageDirection direction) {
+  for (int i = 0; i < 8; ++i) {
+    if (positions[i] == direction)
+      return i;
+  }
+
+  NOTREACHED();
+  return -1;
+}
+
+}  // namespace
+
+// Interval implementation.
+Interval::Interval(Type type,
+                   int start,
+                   int end,
+                   int start_inflate_limit,
+                   int end_inflate_limit,
+                   bool reverse_order)
+    : start_(start),
+      end_(end),
+      initial_start_(start),
+      initial_end_(end),
+      start_inflate_limit_(start_inflate_limit),
+      end_inflate_limit_(end_inflate_limit),
+      reverse_order_(reverse_order),
+      within_bounds_(true),
+      inflate_to_level_ptr_(nullptr),
+      is_within_bounds_ptr_(nullptr) {
+  Init(type);
+  Reset();
+}
+
+Interval::Interval(const Interval& other) = default;
+
+Interval::Interval(Interval&& other) = default;
+
+Interval::~Interval() {
+  inflate_to_level_ptr_ = nullptr;
+  is_within_bounds_ptr_ = nullptr;
+}
+
+Interval& Interval::operator=(const Interval& other) = default;
+
+Interval& Interval::operator=(Interval&& other) = default;
+
+Interval& Interval::operator++() {
+  DCHECK(is_within_bounds_ptr_);
+  current_index_ += step_;
+  within_bounds_ = (this->*is_within_bounds_ptr_)();
+
+  return *this;
+}
+
+void Interval::InflateToLevel(int level) {
+  DCHECK(inflate_to_level_ptr_);
+  (this->*inflate_to_level_ptr_)(level);
+}
+
+int Interval::GetSpan() {
+  return std::abs(end_ - start_) + 1;
+}
+
+void Interval::Init(Interval::Type type) {
+  switch (type) {
+    case Interval::Type::FORWARD:
+      inflate_to_level_ptr_ = &Interval::InflateToLevelForward;
+      is_within_bounds_ptr_ = &Interval::IsWithinBoundsForward;
+      step_ = reverse_order_ ? -1 : 1;
+      break;
+    case Interval::Type::BACKWARD:
+      inflate_to_level_ptr_ = &Interval::InflateToLevelBackward;
+      is_within_bounds_ptr_ = &Interval::IsWithinBoundsBackward;
+      step_ = reverse_order_ ? 1 : -1;
+      break;
+    case Interval::Type::DIAGONAL_FORWARD:
+      DCHECK_EQ(start_, end_);
+      inflate_to_level_ptr_ = &Interval::InflateToLevelDiagonalForward;
+      is_within_bounds_ptr_ = &Interval::IsWithinBoundsDiagonal;
+      step_ = reverse_order_ ? -1 : 1;
+      break;
+    case Interval::Type::DIAGONAL_BACKWARD:
+      DCHECK_EQ(start_, end_);
+      inflate_to_level_ptr_ = &Interval::InflateToLevelDiagonalBackward;
+      is_within_bounds_ptr_ = &Interval::IsWithinBoundsDiagonal;
+      step_ = reverse_order_ ? 1 : -1;
+      break;
+  }
+}
+
+void Interval::Reset() {
+  current_index_ = reverse_order_ ? end_ : start_;
+  within_bounds_ = true;
+}
+
+void Interval::InflateToLevelForward(int level) {
+  start_ = initial_start_ - level;
+  end_ = initial_end_ + level;
+
+  start_ = ClampNumberInForwardInterval(start_, start_inflate_limit_,
+                                        end_inflate_limit_);
+  end_ = ClampNumberInForwardInterval(end_, start_inflate_limit_,
+                                      end_inflate_limit_);
+
+  Reset();
+}
+
+void Interval::InflateToLevelBackward(int level) {
+  start_ = initial_start_ + level;
+  end_ = initial_end_ - level;
+  start_ = ClampNumberInBackwardInterval(start_, start_inflate_limit_,
+                                         end_inflate_limit_);
+  end_ = ClampNumberInBackwardInterval(end_, start_inflate_limit_,
+                                       end_inflate_limit_);
+
+  Reset();
+}
+
+void Interval::InflateToLevelDiagonalForward(int level) {
+  start_ = initial_start_ + level;
+  end_ = initial_end_ + level;
+
+  Reset();
+}
+
+void Interval::InflateToLevelDiagonalBackward(int level) {
+  start_ = initial_start_ - level;
+  end_ = initial_end_ - level;
+
+  Reset();
+}
+
+bool Interval::IsWithinBoundsForward() {
+  DCHECK(reverse_order_ ? current_index_ <= end_ : current_index_ >= start_);
+
+  if (start_ == end_ ||
+      (reverse_order_ ? current_index_ < start_ : current_index_ > end_))
+    return false;
+
+  return true;
+}
+
+bool Interval::IsWithinBoundsBackward() {
+  DCHECK(reverse_order_ ? current_index_ >= end_ : current_index_ <= start_);
+
+  if (start_ == end_ ||
+      (reverse_order_ ? current_index_ > start_ : current_index_ < end_))
+    return false;
+
+  return true;
+}
+
+bool Interval::IsWithinBoundsDiagonal() {
+  DCHECK_EQ(start_, end_);
+  if (current_index_ != start_)
+    return false;
+
+  return true;
+}
+
+// TriangularSequence implementation.
+TriangularSequence::TriangularSequence()
+    : name_(std::string("dummy")),
+      traversal_interval_(Interval::Type::FORWARD, 0, 0, 0, 0, false),
+      swapped_(false),
+      reverse_order_(false),
+      current_level_index_(-1) {}
+
+TriangularSequence::TriangularSequence(std::string&& name,
+                                       Interval&& traversal_interval,
+                                       Interval&& level_interval,
+                                       bool swapped,
+                                       int levels_to_skip,
+                                       int distance,
+                                       bool reverse_order)
+    : name_(std::move(name)),
+      traversal_interval_(std::move(traversal_interval)),
+      swapped_(swapped),
+      reverse_order_(reverse_order) {
+  int span = level_interval.GetSpan();
+  DCHECK_GE(span, levels_to_skip);
+
+  // Skip |levels_to_skip| levels in level interval.
+  for (int i = 0; i < levels_to_skip; ++i)
+    ++level_interval;
+
+  for (int i = levels_to_skip; i < span; ++i) {
+    level_distances_.push_back(
+        LevelDistance(i, level_interval.index(), distance * i));
+    ++level_interval;
+  }
+
+  UpdateCurrent();
+}
+
+TriangularSequence::TriangularSequence(const TriangularSequence& other) =
+    default;
+
+TriangularSequence::TriangularSequence(TriangularSequence&& other) = default;
+
+TriangularSequence::~TriangularSequence() {
+  level_distances_.clear();
+}
+
+TriangularSequence& TriangularSequence::operator=(
+    const TriangularSequence& other) = default;
+
+TriangularSequence& TriangularSequence::operator=(TriangularSequence&& other) =
+    default;
+
+TriangularSequence& TriangularSequence::operator++() {
+  Advance();
+  UpdateCurrent();
+
+  return *this;
+}
+
+int TriangularSequence::GetMinimumDistance() const {
+  DCHECK(!level_distances_.empty());
+  return level_distances_.front().distance;
+}
+
+int TriangularSequence::GetMaximumDistance() const {
+  DCHECK(!level_distances_.empty());
+  return level_distances_.back().distance;
+}
+
+void TriangularSequence::Advance() {
+  if (!*this)
+    return;
+
+  if (reverse_order_)
+    level_distances_.erase(level_distances_.end() - 1);
+  else
+    level_distances_.erase(level_distances_.begin());
+}
+
+void TriangularSequence::UpdateCurrent() {
+  if (!*this)
+    return;
+
+  if (reverse_order_) {
+    current_level_index_ = level_distances_.back().level_index;
+    traversal_interval_.InflateToLevel(level_distances_.back().interval_level);
+  } else {
+    current_level_index_ = level_distances_.front().level_index;
+    traversal_interval_.InflateToLevel(level_distances_.front().interval_level);
+  }
+}
+
+// PyramidSequence implementation.
+PyramidSequence::PyramidSequence(bool reverse_order)
+    : reverse_order_(reverse_order),
+      current_triangular_sequence_(nullptr),
+      index_x_(-1),
+      index_y_(-1) {}
+
+PyramidSequence::PyramidSequence(const PyramidSequence& other) = default;
+
+PyramidSequence::PyramidSequence(PyramidSequence&& other) = default;
+
+PyramidSequence::~PyramidSequence() {
+  triangular_sequences_.clear();
+  current_triangular_sequence_ = nullptr;
+}
+
+PyramidSequence& PyramidSequence::operator=(const PyramidSequence& other) =
+    default;
+
+PyramidSequence& PyramidSequence::operator=(PyramidSequence&& other) = default;
+
+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_distance = std::max(width, height);
+
+  DCHECK(triangular_sequences_.empty());
+  triangular_sequences_.resize(8);
+  // TODO(prashant.n): Implement precedence in coverage directions instead of
+  // default right direction. http://crbug.com/629052.
+  CoverageDirection* positions = GetCoverageDirectionSequence();
+  DCHECK(positions);
+
+  // RIGHT sequence.
+  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, CoverageDirection::RIGHT),
+          TriangularSequence(
+              std::string("r.seq"),
+              Interval(Interval::Type::BACKWARD, start, end, consider_bottom,
+                       consider_top, reverse_order_),
+              Interval(Interval::Type::FORWARD, around_right, consider_right,
+                       consider_left, consider_right, false),
+              true, skip_levels, width, reverse_order_));
+    }
+  }
+
+  // TOP_RIGHT sequence.
+  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, CoverageDirection::TOP_RIGHT),
+          TriangularSequence(std::string("tr.seq"),
+                             Interval(Interval::Type::DIAGONAL_FORWARD,
+                                      around_right, around_right, consider_left,
+                                      consider_right, reverse_order_),
+                             Interval(Interval::Type::BACKWARD, around_top,
+                                      around_top - diagonal_levels + 1,
+                                      consider_bottom, consider_top, false),
+                             false, skip_levels, diagonal_distance,
+                             reverse_order_));
+    }
+  }
+
+  // TOP sequence.
+  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, CoverageDirection::TOP),
+                TriangularSequence(
+                    std::string("t.seq"),
+                    Interval(Interval::Type::BACKWARD, start, end,
+                             consider_right, consider_left, reverse_order_),
+                    Interval(Interval::Type::BACKWARD, around_top, consider_top,
+                             consider_bottom, consider_top, false),
+                    false, skip_levels, height, reverse_order_));
+    }
+  }
+
+  // TOP_LEFT sequence.
+  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, CoverageDirection::TOP_LEFT),
+                TriangularSequence(
+                    std::string("tl.seq"),
+                    Interval(Interval::Type::DIAGONAL_BACKWARD, around_left,
+                             around_left, consider_right, consider_left,
+                             reverse_order_),
+                    Interval(Interval::Type::BACKWARD, around_top,
+                             around_top - diagonal_levels + 1, consider_bottom,
+                             consider_top, false),
+                    false, skip_levels, diagonal_distance, reverse_order_));
+    }
+  }
+
+  // LEFT sequence.
+  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, CoverageDirection::LEFT),
+          TriangularSequence(
+              std::string("l.seq"),
+              Interval(Interval::Type::FORWARD, start, end, consider_top,
+                       consider_bottom, reverse_order_),
+              Interval(Interval::Type::BACKWARD, around_left, consider_left,
+                       consider_right, consider_left, false),
+              true, skip_levels, width, reverse_order_));
+    }
+  }
+
+  // BOTTOM_LEFT sequence.
+  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, CoverageDirection::BOTTOM_LEFT),
+          TriangularSequence(std::string("bl.seq"),
+                             Interval(Interval::Type::DIAGONAL_BACKWARD,
+                                      around_left, around_left, consider_right,
+                                      consider_left, reverse_order_),
+                             Interval(Interval::Type::FORWARD, around_bottom,
+                                      around_bottom + diagonal_levels - 1,
+                                      consider_top, consider_bottom, false),
+                             false, skip_levels, diagonal_distance,
+                             reverse_order_));
+    }
+  }
+
+  // BOTTOM sequence.
+  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, CoverageDirection::BOTTOM),
+          TriangularSequence(
+              std::string("b.seq"),
+              Interval(Interval::Type::FORWARD, start, end, consider_left,
+                       consider_right, reverse_order_),
+              Interval(Interval::Type::FORWARD, around_bottom, consider_bottom,
+                       consider_top, consider_bottom, false),
+              false, skip_levels, height, reverse_order_));
+    }
+  }
+
+  // BOTTOM_RIGHT sequence.
+  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, CoverageDirection::BOTTOM_RIGHT),
+          TriangularSequence(std::string("br.seq"),
+                             Interval(Interval::Type::DIAGONAL_FORWARD,
+                                      around_right, around_right, consider_left,
+                                      consider_right, reverse_order_),
+                             Interval(Interval::Type::FORWARD, around_bottom,
+                                      around_bottom + diagonal_levels - 1,
+                                      consider_top, consider_bottom, false),
+                             false, skip_levels, diagonal_distance,
+                             reverse_order_));
+    }
+  }
+
+  current_triangular_sequence_ = GetNextTriangularSequence();
+  if (current_triangular_sequence_) {
+    if (*current_triangular_sequence_)
+      current_traversal_interval_ =
+          current_triangular_sequence_->traversal_interval();
+    UpdateCurrent();
+  }
+}
+
+PyramidSequence::operator bool() const {
+  return current_triangular_sequence_ && !triangular_sequences_.empty();
+}
+
+PyramidSequence& PyramidSequence::operator++() {
+  Advance();
+  UpdateCurrent();
+
+  return *this;
+}
+
+void PyramidSequence::EmplaceAt(int position,
+                                TriangularSequence&& triangular_sequence) {
+  TriangularSequence::Iterator it = triangular_sequences_.begin();
+  std::advance(it, position);
+  triangular_sequences_.emplace(it, std::move(triangular_sequence));
+  TriangularSequence::Iterator erase_it = triangular_sequences_.begin();
+  std::advance(erase_it, position + 1);
+  triangular_sequences_.erase(erase_it);
+}
+
+void PyramidSequence::Advance() {
+  if (!*this)
+    return;
+
+  ++(*current_traversal_interval_);
+  if (!*current_traversal_interval_) {
+    ++(*current_triangular_sequence_);
+    current_triangular_sequence_ = GetNextTriangularSequence();
+    if (current_triangular_sequence_) {
+      current_traversal_interval_ =
+          current_triangular_sequence_->traversal_interval();
+    }
+  }
+}
+
+void PyramidSequence::UpdateCurrent() {
+  while (*this) {
+    if (current_traversal_interval_ && (*current_traversal_interval_)) {
+      if (current_triangular_sequence_->is_swapped()) {
+        index_x_ = current_triangular_sequence_->level_index();
+        index_y_ = current_traversal_interval_->index();
+      } else {
+        index_x_ = current_traversal_interval_->index();
+        index_y_ = current_triangular_sequence_->level_index();
+      }
+
+      if (InConsiderRect() && !InIgnoreRect())
+        break;
+    }
+
+    Advance();
+  }
+}
+
+void PyramidSequence::RemoveEmptyTriangularSequences() {
+  triangular_sequences_.erase(
+      std::remove_if(triangular_sequences_.begin(), triangular_sequences_.end(),
+                     [](const TriangularSequence& seq) { return !seq; }),
+      triangular_sequences_.end());
+}
+
+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_;
+}
+
+// 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;
+
+TriangularSequence* TopDownPyramidSequence::GetNextTriangularSequence() {
+  RemoveEmptyTriangularSequences();
+
+  if (triangular_sequences_.empty())
+    return nullptr;
+
+  TriangularSequence::Iterator min_distance_it = triangular_sequences_.begin();
+
+  for (TriangularSequence::Iterator it = triangular_sequences_.begin();
+       it != triangular_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;
+}
+
+TriangularSequence* BottomUpPyramidSequence::GetNextTriangularSequence() {
+  RemoveEmptyTriangularSequences();
+
+  if (triangular_sequences_.empty())
+    return nullptr;
+
+  TriangularSequence::ReverseIterator max_distance_it =
+      triangular_sequences_.rbegin();
+
+  for (TriangularSequence::ReverseIterator it = triangular_sequences_.rbegin();
+       it != triangular_sequences_.rend(); ++it) {
+    int distance = it->GetMaximumDistance();
+
+    if (max_distance_it->GetMaximumDistance() < distance)
+      max_distance_it = it;
+  }
+
+  return &(*max_distance_it);
+}
+
+}  // namespace cc