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

cc/base/pyramid_sequence.h

Index: cc/base/pyramid_sequence.h
diff --git a/cc/base/pyramid_sequence.h b/cc/base/pyramid_sequence.h
new file mode 100644
index 0000000000000000000000000000000000000000..6524bacc9bc0a5a9c33b49afac3f4e3f1d67766e
--- /dev/null
+++ b/cc/base/pyramid_sequence.h
@@ -0,0 +1,735 @@
+// 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.
+
+#ifndef CC_BASE_PYRAMID_SEQUENCE_H_
+#define CC_BASE_PYRAMID_SEQUENCE_H_
+
+#include <memory>
+#include <vector>
+
+#include "base/logging.h"
+#include "base/macros.h"
+#include "cc/base/cc_export.h"
+#include "cc/base/index_rect.h"
+
+namespace cc {
+
+// The pyramid sequence covers following 4 directions while iterating, where R
+// is right, T is top, L is left and B is bottom.
+//       T
+//    L  *  R
+//       B
+enum class CoverageDirection : int {
+  NONE = -1,
+  RIGHT = 0,
+  TOP,
+  LEFT,
+  BOTTOM,
+  SIZE
+};
+
+namespace internal {
+
+// This class provides iterating mechanism for numbers between defined bounds.
+// e.g. For interval having bounds 3 as start and 6 as end, represented as
+// [3, 6], the interval returns 3, 4, 5, 6 sequence for Iterator traversal and
+// returns 6, 5, 4, 3 for ReverseIterator traversal.
+//
+//   start        end
+//     |           |
+//     V           V
+//   ┌───┬───┬───┬───┐
+//   │ 3 │ 4 │ 5 │ 6 │
+//   └───┴───┴───┴───┘
+class CC_EXPORT Interval {
+ public:
+  class Iterator;
+  class ReverseIterator;
+
+  Interval() : empty_(true) {}
+  Interval(int start, int end) : empty_(false), start_(start), end_(end) {}
+
+  Iterator* Begin();
+  ReverseIterator* ReverseBegin();
+
+  // Return the bounds of the interval.
+  int start() const { return start_; }
+  int end() const { return end_; }
+
+  // Returns true if interval is empty. Empty interval does not return any
+  // index on traversing.
+  bool IsEmpty() const { return empty_; }
+
+  // Returns the distance between |start_| and |end_| which includes both
+  // |start_| and |end_|.
+  int GetSpan() const;
+
+  // Return clamped indices for the given indices.
+  int GetForwardClampedIndex(int index) const;
+  int GetBackwardClampedIndex(int index) const;
+
+  // Clamp this interval to the given interval. For these functions, interval
+  // and other interval to which this interval is to be clammped should be in
+  // the same direction, i.e. both intervals should have either
+  // |start_| <= |end_| or |start_| >= |end_|.
+  void ForwardClampTo(const Interval* other);
+  void BackwardClampTo(const Interval* other);
+
+  // Return the inflated intervals for the given |level|.
+  void ForwardInflate(int level, Interval* output) const;
+  void BackwardInflate(int level, Interval* output) const;
+
+  // Returns true if interval contains the given index.
+  bool Contains(int index) const;
+
+  // For these functions, interval and other interval to which first one is to
+  // be intersected should be in the same direction, i.e. both intervals should
+  // have |start_| <= |end_| or |start_| >= |end_|.
+  bool Intersects(const Interval* interval) const;
+  void Intersect(const Interval* interval);
+
+  // Iterators.
+  class IteratorBase {
+   public:
+    operator bool() const { return within_bounds_; }
+    IteratorBase& operator++();
+    int index() { return current_index_; }
+
+   protected:
+    explicit IteratorBase(Interval* interval);
+
+    virtual bool IsWithinBounds() = 0;
+
+    Interval* interval_;
+    bool within_bounds_;
+    int step_;
+    int current_index_;
+
+   private:
+    DISALLOW_COPY_AND_ASSIGN(IteratorBase);
+  };
+
+  class Iterator : public IteratorBase {
+   private:
+    explicit Iterator(Interval* interval);
+
+    bool IsWithinBounds() override;
+
+    friend class Interval;
+
+    DISALLOW_COPY_AND_ASSIGN(Iterator);
+  };
+
+  class ReverseIterator : public IteratorBase {
+   private:
+    explicit ReverseIterator(Interval* interval);
+
+    bool IsWithinBounds() override;
+
+    friend class Interval;
+
+    DISALLOW_COPY_AND_ASSIGN(ReverseIterator);
+  };
+
+ private:
+  bool empty_;
+  int start_;
+  int end_;
+};
+
+// This class provides affinity based interating mechanism for the given
+// |interval| [start, end] with functionality of inflating the |interval|.
+// The interval inflation means expanding the start and end by n steps forward
+// or backward, based on |forward_direction| argument provided. Suppose the
+// LinearSequence has interval [3, 3] i.e. start = 3 and end = 3, the interval
+// inflated by 1 step in forward direction would be [2, 4] and that of in
+// backward direction would be [4, 2].
+// The affinity based traversing means portion of |interval| that intersects
+// with |affinity_interval| is traversed before remaining two portions of
+// |interval|. Internally the |interval| is split up into three sub-intervals
+// before traversing as |affinity_sub_interval_|, |before_sub_interval_| and
+// |after_sub_interval_|. These sub-intervals are traversed instead of directly
+// traversing |interval|. First |affinity_sub_interval_| is traversed fully,
+// then remaining two sub-intervals are traversed in alternative fashion.
+//
+// e.g. Suppose LinearSequence has interval [0, 9] and affinity interval
+// [4, 6], then the interval is splitted into three sub-intervals viz. [4, 6],
+// [3, 0], [7, 9].
+//
+//               affinity_sub_interval
+//                   ┌─────^─────┐
+//   ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
+//   │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
+//   └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
+//   └───────v───────┘           └─────v─────┘
+//  before_sub_interval        after_sub_interval
+//
+// On traversal, Iterator returns the sequence as 4, 5, 6, 3, 7, 2, 8, 1, 9, 0
+// and RerverseIterator returns the sequence as 0, 9, 1, 8, 2, 7, 3, 6, 5, 4.
+class CC_EXPORT LinearSequence {
+ public:
+  class Iterator;
+  class ReverseIterator;
+
+  // The |interval| is used for actual traversal. The |affinity_interval| is
+  // used for defining affinity in the |interval|. While traversing portion of
+  // |interval| which intersects |affinity_interval| is traversed before
+  // remaining portions of the interval. The |inflate_limit| is used to clamp
+  // the |interval|, when it is inflated to any given |level|.
+  LinearSequence(bool forward_direction,
+                 std::unique_ptr<Interval> interval,
+                 std::unique_ptr<Interval> affinity_interval,
+                 std::unique_ptr<Interval> inflate_limit);
+  ~LinearSequence();
+
+  Iterator* Begin();
+  ReverseIterator* ReverseBegin();
+
+  // This function inflates the original |interval| to the given |level|,
+  // where level >= 0.
+  void InflateToLevel(int level);
+
+  // Iterators.
+  class IteratorBase {
+   public:
+    ~IteratorBase();
+
+    operator bool() const { return within_bounds_; }
+    IteratorBase& operator++();
+    int index() { return current_index_; }
+
+   protected:
+    enum class SubIntervalIteratorType : unsigned int {
+      AFFINITY,
+      BEFORE,
+      AFTER
+    };
+
+    explicit IteratorBase(LinearSequence* level_sequence);
+
+    bool IsWithinBounds();
+    virtual SubIntervalIteratorType GetCurrentSubIntervalIteratorType() = 0;
+
+    LinearSequence* level_sequence_;
+    bool within_bounds_;
+    int current_index_;
+    std::unique_ptr<Interval::IteratorBase> sub_interval_iterators_[3];
+    SubIntervalIteratorType current_sub_interval_iterator_;
+
+   private:
+    DISALLOW_COPY_AND_ASSIGN(IteratorBase);
+  };
+
+  class Iterator : public IteratorBase {
+   public:
+    ~Iterator();
+
+   private:
+    explicit Iterator(LinearSequence* level_sequence);
+
+    SubIntervalIteratorType GetCurrentSubIntervalIteratorType() override;
+
+    bool before_first_;
+
+    friend class LinearSequence;
+
+    DISALLOW_COPY_AND_ASSIGN(Iterator);
+  };
+
+  class ReverseIterator : public IteratorBase {
+   public:
+    ~ReverseIterator();
+
+   private:
+    explicit ReverseIterator(LinearSequence* level_sequence);
+
+    SubIntervalIteratorType GetCurrentSubIntervalIteratorType() override;
+
+    bool after_first_;
+    int before_sub_interval_span_;
+    int after_sub_interval_span_;
+
+    friend class LinearSequence;
+
+    DISALLOW_COPY_AND_ASSIGN(ReverseIterator);
+  };
+
+ private:
+  void TrisectInterval();
+
+  bool forward_direction_;
+  std::unique_ptr<Interval> interval_;
+  std::unique_ptr<Interval> inflate_limit_;
+  std::unique_ptr<Interval> affinity_interval_;
+
+  std::unique_ptr<Interval> initial_interval_;
+
+  // The |interval_| is split up into following sub-intervals such a way that
+  // they are non-intersecting, adjacent and union of these three sub-intervals
+  // is |interval_|.
+  Interval affinity_sub_interval_;
+  Interval before_sub_interval_;
+  Interval after_sub_interval_;
+
+  DISALLOW_COPY_AND_ASSIGN(LinearSequence);
+};
+
+// This class implements the 2D sequence (x, y) which uses LinearSequence and
+// Interval to represent the co-ordinates. The linear sequence
+// |traversal_sequence| is used for traversing the actual sequence cross the
+// direction and |level_interval| is used for computing the number of levels in
+// the |traversal_sequence|. The interval in |traversal_sequence| can be
+// inflated max to the levels given by |level_interval|.
+// This class uses LevelDistance structure to represent the distance associated
+// with the level. The first level has distance 0, to represent the minimum
+// distance for the origin level, and increments by the step of |distance|
+// given in LevelDistance for every level. Suppose there are 5 levels and
+// distance is 10, then the levels would have distances as 0, 10, 20, 30, 40.
+// The distances are stored in the sorted order in vector, so that the distance
+// at front is minimum, while the distance at back is maximum. The layout of
+// the level distance vector for the example would be (0, 0), (1, 10), (2, 20),
+// (3, 30), (4, 40).
+//
+// e.g. If traversal sequence has interval [3, 4], number of levels is 3 and
+// distance is 10, then the Iterator would give following data on traversal.
+//
+//   traversal_sequence   level_index
+//         [3, 4]              0
+//         [2, 5]              1
+//         [1, 6]              2
+//
+// The order of iteration for ReverseIterator would be as given below.
+//
+//   traversal_sequence   level index
+//         [1, 6]              2
+//         [2, 5]              1
+//         [3, 4]              0
+//
+// The indices (x, y) for the iterator are as given below.
+//
+// (3, 0), (4, 0)                                    (level 1)
+// (2, 1), (3, 1), (4, 1), (5, 1),                   (level 2)
+// (1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 2)    (level 3)
+//
+// In a way the original interval in |traversal_sequence| and inflated
+// intervals form triangular geometry in co-ordinate space as given below,
+// hence the name TriangularSequence.
+//
+//   x  0   1   2   3   4   5   6
+//  y ┌───┬───┬───┬───┬───┬───┬───┐
+//  0 │   │   │   │ 3 │ 4 │   │   │  (level 1, distance 0)
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  1 │   │   │ 2 │ 3 │ 4 │ 5 │   │  (level 2, distance 10)
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  2 │   │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │  (level 3, distance 20)
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  3 │   │   │   │   │   │   │   │
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  4 │   │   │   │   │   │   │   │
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  5 │   │   │   │   │   │   │   │
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  6 │   │   │   │   │   │   │   │
+//    └───┴───┴───┴───┴───┴───┴───┘
+class CC_EXPORT TriangularSequence {
+ public:
+  class Iterator;
+  class ReverseIterator;
+
+  // The |traversal_sequence| defines the sequence for traversal and
+  // |level_interval| defines the number of levels for |traversal_sequence|.
+  // If |should_swap_index_representation| is false, then the indices in
+  // |traversal_sequence| represent the x indices and level indices in
+  // |level_interval| represent the y indices, otherwise vice-versa. The
+  // |levels_to_skip| defines the number of levels which should be skipped to
+  // avoid unnecessary traversing. Check PyramidSequence::PyramidSequence() for
+  // more details on level skipping. The |distance| defines the length for the
+  // index.
+  TriangularSequence(CoverageDirection coverage_direction,
+                     std::unique_ptr<LinearSequence> traversal_sequence,
+                     std::unique_ptr<Interval> level_interval,
+                     bool should_swap_index_representation,
+                     int levels_to_skip,
+                     int distance);
+  ~TriangularSequence();
+
+  Iterator* Begin();
+  ReverseIterator* ReverseBegin();
+
+  CoverageDirection coverage_direction() const { return coverage_direction_; }
+
+  struct LevelDistance {
+    LevelDistance(int interval_level, int level_index, int distance)
+        : interval_level(interval_level),
+          level_index(level_index),
+          distance(distance) {}
+
+    int interval_level;
+    int level_index;
+    int distance;
+  };
+
+  class IteratorBase {
+   public:
+    IteratorBase();
+    ~IteratorBase();
+
+    operator bool() const { return !level_distances_.empty(); }
+    IteratorBase& operator++();
+    LinearSequence* traversal_sequence() {
+      DCHECK(*this);
+      return traversal_sequence_;
+    }
+    int level_index() {
+      DCHECK(*this);
+      return current_level_index_;
+    }
+
+    bool is_index_representation_swapped() const {
+      return should_swap_index_representation_;
+    }
+
+    virtual int GetNextDistance() const = 0;
+
+   protected:
+    explicit IteratorBase(TriangularSequence* triangular_sequence);
+
+    virtual void Advance() = 0;
+    virtual void UpdateCurrent() = 0;
+
+    LinearSequence* traversal_sequence_;
+    bool should_swap_index_representation_;
+    std::vector<LevelDistance> level_distances_;
+    int current_level_index_;
+
+   private:
+    DISALLOW_COPY_AND_ASSIGN(IteratorBase);
+  };
+
+  class Iterator : public IteratorBase {
+   public:
+    Iterator();
+
+    // Returns next minimum distance.
+    int GetNextDistance() const override;
+
+   private:
+    explicit Iterator(TriangularSequence* triangular_sequence);
+
+    void Advance() override;
+    void UpdateCurrent() override;
+
+    friend class TriangularSequence;
+
+    DISALLOW_COPY_AND_ASSIGN(Iterator);
+  };
+
+  class ReverseIterator : public IteratorBase {
+   public:
+    ReverseIterator();
+
+    // Returns next maximum distance.
+    int GetNextDistance() const override;
+
+   private:
+    explicit ReverseIterator(TriangularSequence* triangular_sequence);
+
+    void Advance() override;
+    void UpdateCurrent() override;
+
+    friend class TriangularSequence;
+
+    DISALLOW_COPY_AND_ASSIGN(ReverseIterator);
+  };
+
+  typedef std::vector<std::unique_ptr<TriangularSequence>> Vector;
+  typedef std::vector<TriangularSequence::IteratorBase> IteratorVector;
+
+ private:
+  CoverageDirection coverage_direction_;
+  std::unique_ptr<LinearSequence> traversal_sequence_;
+  std::unique_ptr<Interval> level_interval_;
+  bool should_swap_index_representation_;
+  int levels_to_skip_;
+  int distance_;
+
+  DISALLOW_COPY_AND_ASSIGN(TriangularSequence);
+};
+
+// The pyramid sequence consists of 4 triangular sequences, one for each of
+// the directions considered counter-clockwise or clockwise. The ideal pyramid
+// sequence is as given below where it has all triangular sequences in 4
+// directions.
+//
+//                  ┌───┬───┬───┬───┬───┬───┬───┐
+//                  │ L │ T │ T │ T │ T │ T │ R │
+//                  ├───┼───┼───┼───┼───┼───┼───┤
+//                  │ L │ L │ T │ T │ T │ R │ R │
+//                  ├───┼───┼───┼───┼───┼───┼───┤
+//                  │ L │ L │ L │ T │ R │ R │ R │
+//                  ├───┼───┼───┼───┼───┼───┼───┤
+//                  │ L │ L │ L │ * │ R │ R │ R │
+//                  ├───┼───┼───┼───┼───┼───┼───┤
+//                  │ L │ L │ L │ B │ R │ R │ R │
+//                  ├───┼───┼───┼───┼───┼───┼───┤
+//                  │ L │ L │ B │ B │ B │ R │ R │
+//                  ├───┼───┼───┼───┼───┼───┼───┤
+//                  │ L │ B │ B │ B │ B │ B │ R │
+//                  └───┴───┴───┴───┴───┴───┴───┘
+//
+// The triangular sequences for the above pyramid sequence are shown below.
+// * represents the center.
+//
+//                            (T = top)
+//                      ┌───┬───┬───┬───┬───┐
+//                      │ T │ T │ T │ T │ T │
+//              ┌───┐   └───┼───┼───┼───┼───┘   ┌───┐
+//              │ L │       │ T │ T │ T │       │ R │
+//              ├───┼───┐   └───┼───┼───┘   ┌───┼───┤
+//              │ L │ L │       │ T │       │ R │ R │
+//              ├───┼───┼───┐   └───┘   ┌───┼───┼───┤
+//              │ L │ L │ L │           │ R │ R │ R │
+//              ├───┼───┼───┤   ┌───┐   ├───┼───┼───┤
+//  (L = left)  │ L │ L │ L │   │ * │   │ R │ R │ R │  (R = right)
+//              ├───┼───┼───┤   └───┘   ├───┼───┼───┤
+//              │ L │ L │ L │           │ R │ R │ R │
+//              ├───┼───┼───┘   ┌───┐   └───┼───┼───┤
+//              │ L │ L │       │ B │       │ R │ R │
+//              ├───┼───┘   ┌───┼───┼───┐   └───┼───┤
+//              │ L │       │ B │ B │ B │       │ R │
+//              └───┘   ┌───┼───┼───┼───┼───┐   └───┘
+//                      │ B │ B │ B │ B │ B │
+//                      └───┴───┴───┴───┴───┘
+//                           (B = bottom)
+//
+// This sequence iterates over all the underlined triangular sequences level by
+// level in increasing or decreasing order of distances. The increasing order of
+// distances can be iterated using Iterator, while the decreasing order of
+// distances can be iterated using ReverseIterator. The default coverage for
+// internal triangular sequences is R, T, L, B forming spiral order.
+// The iteration sequence generated by Iterator is as given below.
+// (Iteration is considered counter-clockwise.)
+//
+//   x  0   1   2   3   4   5   6
+//  y ┌───┬───┬───┬───┬───┬───┬───┐
+//  0 │ 42│ 36│ 34│ 32│ 33│ 35│ 31│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  1 │ 40│ 20│ 16│ 14│ 15│ 13│ 29│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  2 │ 38│ 18│  6│  4│  3│ 11│ 27│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  3 │ 37│ 17│  5│  *│  1│  9│ 25│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  4 │ 39│ 19│  7│  8│  2│ 10│ 26│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  5 │ 41│ 21│ 23│ 22│ 24│ 12│ 28│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  6 │ 43│ 47│ 45│ 44│ 46│ 48│ 30│
+//    └───┴───┴───┴───┴───┴───┴───┘
+//
+// The iteration sequence generated by ReverseIterator is as given below.
+// (Iteration is considered clockwise.)
+//
+//   x  0   1   2   3   4   5   6
+//  y ┌───┬───┬───┬───┬───┬───┬───┐
+//  0 │  7│ 13│ 15│ 17│ 16│ 14│ 18│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  1 │  9│ 29│ 33│ 35│ 34│ 36│ 20│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  2 │ 11│ 31│ 43│ 45│ 46│ 38│ 22│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  3 │ 12│ 32│ 44│  *│ 48│ 40│ 24│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  4 │ 10│ 30│ 42│ 41│ 47│ 39│ 23│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  5 │  8│ 28│ 26│ 27│ 25│ 37│ 21│
+//    ├───┼───┼───┼───┼───┼───┼───┤
+//  6 │  6│  2│  4│  5│  3│  1│ 19│
+//    └───┴───┴───┴───┴───┴───┴───┘
+class CC_EXPORT PyramidSequence {
+ public:
+  class Iterator;
+  class ReverseIterator;
+
+  // The |around_index_rect| is the index rect computed around some index rect,
+  // called as center index rect. In the above example, center index rect is
+  // (3, 3, 3, 3), so around index rect for it is (2, 4, 2, 4).
+  // The |consider_index_rect| is used to limit the coverage and the
+  // |ignore_index_rect| is used to ignore the indices from coverage. For above
+  // example consider index rect is (0, 6, 0, 6) and ignore index rect is
+  // (-1, -1, -1, -1).
+  // The width and height specify the width and height of the single index. This
+  // is used for traversing indices based on their distances from center index
+  // rect.
+  PyramidSequence(const IndexRect& around_index_rect,
+                  const IndexRect& consider_index_rect,
+                  const IndexRect& ignore_index_rect,
+                  int width,
+                  int height);
+  ~PyramidSequence();
+
+  Iterator* Begin();
+  ReverseIterator* ReverseBegin();
+
+  class IteratorBase {
+   public:
+    IteratorBase();
+    ~IteratorBase();
+
+    operator bool() const;
+    IteratorBase& operator++();
+    int index_x() const { return index_x_; }
+    int index_y() const { return index_y_; }
+
+   protected:
+    explicit IteratorBase(const IndexRect& consider_index_rect,
+                          const IndexRect& ignore_index_rect);
+
+    virtual bool IsEmpty() const = 0;
+    virtual void Advance() = 0;
+    virtual void UpdateCurrent() = 0;
+
+    IndexRect consider_index_rect_;
+    IndexRect ignore_index_rect_;
+    int index_x_;
+    int index_y_;
+
+    TriangularSequence::IteratorBase* current_triangular_sequence_it_;
+
+   private:
+    DISALLOW_COPY_AND_ASSIGN(IteratorBase);
+  };
+
+  class Iterator : public IteratorBase {
+   public:
+    Iterator();
+    ~Iterator();
+
+   private:
+    explicit Iterator(PyramidSequence* pyramid_sequence);
+
+    bool IsEmpty() const override;
+    void Advance() override;
+    void UpdateCurrent() override;
+
+    TriangularSequence::IteratorBase* GetNextTriangularSequenceIterator();
+
+    LinearSequence::Iterator* current_traversal_sequence_iterator_;
+    std::vector<std::unique_ptr<TriangularSequence::Iterator>>
+        triangular_sequence_iterators_;
+
+    friend class PyramidSequence;
+
+    DISALLOW_COPY_AND_ASSIGN(Iterator);
+  };
+
+  class ReverseIterator : public IteratorBase {
+   public:
+    ReverseIterator();
+    ~ReverseIterator();
+
+   private:
+    explicit ReverseIterator(PyramidSequence* pyramid_sequence);
+
+    bool IsEmpty() const override;
+    void Advance() override;
+    void UpdateCurrent() override;
+
+    TriangularSequence::IteratorBase*
+    GetNextTriangularSequenceReverseIterator();
+
+    LinearSequence::ReverseIterator*
+        current_traversal_sequence_reverse_iterator_;
+    std::vector<std::unique_ptr<TriangularSequence::ReverseIterator>>
+        triangular_sequence_reverse_iterators_;
+
+    friend class PyramidSequence;
+
+    DISALLOW_COPY_AND_ASSIGN(ReverseIterator);
+  };
+
+ private:
+  void EmplaceAt(int position,
+                 std::unique_ptr<TriangularSequence> triangular_sequence);
+
+  IndexRect consider_index_rect_;
+  IndexRect ignore_index_rect_;
+  TriangularSequence::Vector triangular_sequences_;
+
+  DISALLOW_COPY_AND_ASSIGN(PyramidSequence);
+};
+
+}  // namespace internal
+
+class PyramidSequence {
+ public:
+  PyramidSequence();
+  PyramidSequence(const IndexRect& around_index_rect,
+                  const IndexRect& consider_index_rect,
+                  const IndexRect& ignore_index_rect,
+                  int width,
+                  int height);
+  PyramidSequence(const PyramidSequence& other);
+  PyramidSequence(PyramidSequence&& other);
+  ~PyramidSequence();
+
+  PyramidSequence& operator=(const PyramidSequence& other);
+  PyramidSequence& operator=(PyramidSequence&& other);
+
+  class Iterator {
+   public:
+    Iterator();
+    Iterator(const Iterator& other);
+    Iterator(Iterator&& other);
+    ~Iterator();
+
+    Iterator& operator=(const Iterator& other);
+    Iterator& operator=(Iterator&& other);
+
+    operator bool() const;
+    Iterator& operator++();
+    int index_x() const;
+    int index_y() const;
+
+   public:
+    explicit Iterator(internal::PyramidSequence::Iterator* ptr);
+
+    std::shared_ptr<internal::PyramidSequence::Iterator> ptr_;
+
+    friend class PyramidSequence;
+  };
+
+  class ReverseIterator {
+   public:
+    ReverseIterator();
+    ReverseIterator(const ReverseIterator& other);
+    ReverseIterator(ReverseIterator&& other);
+    ~ReverseIterator();
+
+    ReverseIterator& operator=(const ReverseIterator& other);
+    ReverseIterator& operator=(ReverseIterator&& other);
+
+    operator bool() const;
+    ReverseIterator& operator++();
+    int index_x() const;
+    int index_y() const;
+
+   private:
+    explicit ReverseIterator(internal::PyramidSequence::ReverseIterator* ptr);
+
+    std::shared_ptr<internal::PyramidSequence::ReverseIterator> ptr_;
+
+    friend class PyramidSequence;
+  };
+
+  Iterator Begin();
+  ReverseIterator ReverseBegin();
+
+ private:
+  std::shared_ptr<internal::PyramidSequence> ptr_;
+};
+
+}  // namespace cc
+
+#endif  // CC_BASE_PYRAMID_SEQUENCE_H_