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..a9c7ba97b98aa37cffa98c6d426cab78237b5828
--- /dev/null
+++ b/cc/base/pyramid_sequence.h
@@ -0,0 +1,353 @@
+// 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 <list>
+#include <vector>
+
+#include "base/logging.h"
+#include "cc/base/cc_export.h"
+
+namespace cc {
+
+// This class provides interating mechanism for the mathematical interval

[vmpstr, 2016/08/16 00:40:48]

iterating

+// [start, end] with functionality for inflating the interval. The interval
+// inflation means expanding the start and end by 1 step. Expanding interval
+// [3, 4] by 1 step would give [2, 5], and by 2 steps would give [1, 6].
+// The iterating mechanism could be used as given below.
+//
+// for (Interval it(FORWARD, 3, 4, 0, 6, false), it; ++it)

[vmpstr, 2016/08/16 00:40:48]

I'm not sure what this example is demonstrating, can you elaborate on the
inputs?

+//   int index = it.index();
+//
+// The output for the above example would be 3, 4.
+class CC_EXPORT Interval {
+ public:
+  // The types give below decide how to inflate the interval. Suppose the
+  // interval is [3, 3] i.e. start = 3 and end = 3. The inflated intervals for
+  // different types would be as given below.
+  //   FORWARD            [2, 4]

[vmpstr, 2016/08/16 00:40:48]

Can we always have just one direction (ie FORWARD), and just iterate the range
using some sort of a reverse iterator if we need to go in the opposite
direction?

+  //   BACKWARD           [4, 2]
+  //   DIAGONAL_FORWARD   [4, 4]

[vmpstr, 2016/08/16 00:40:48]

Why is [4, 4] a valid interval? It seems to not encompass the initial given
sequence.

+  //   DIAGONAL_BACKWARD  [2, 2]
+  enum class Type : uint16_t {
+    FORWARD,
+    BACKWARD,
+    DIAGONAL_FORWARD,
+    DIAGONAL_BACKWARD

[vmpstr, 2016/08/16 00:40:48]

If these are not currently used, please remove them. 

+  };
+
+  // |reverse_order| decides the direction of iteration order, i.e.
+  // from start to end or from end to start (called as reverse direction).
+  Interval(Type type,
+           int start,
+           int end,
+           int start_inflate_limit,
+           int end_inflate_limit,
+           bool reverse_order);

[vmpstr, 2016/08/16 00:40:48]

As I mentioned in my previous comment, I don't understand why you have FORWARD
and BACKWARD as well as reverse_order bool. That seems like too many controls.

+  Interval(const Interval& other);
+  Interval(Interval&& other);
+  ~Interval();
+
+  Interval& operator=(const Interval& other);
+  Interval& operator=(Interval&& other);
+
+  operator bool() const { return within_bounds_; }
+  Interval& operator++();
+
+  int index() { return current_index_; }
+  // This function converts the current interval to level (level >= 0) given.
+  void InflateToLevel(int level);
+  // Returns the distance between |start_| and |end_| which includes both
+  // |start_| and |end_|.
+  int GetSpan();
+
+ private:
+  using InflateToLevelFnPtr = void (Interval::*)(int level);
+  using IsWithinBoundsFnPtr = bool (Interval::*)();
+
+  void Init(Type type);
+  void Reset();
+
+  // Interval inflating functions for different Interval types.
+  void InflateToLevelForward(int levels);
+  void InflateToLevelBackward(int levels);
+  void InflateToLevelDiagonalForward(int levels);
+  void InflateToLevelDiagonalBackward(int levels);
+
+  // Functions for checking the bounds for different Interval types.
+  bool IsWithinBoundsForward();
+  bool IsWithinBoundsBackward();
+  bool IsWithinBoundsDiagonal();
+
+  int start_;
+  int end_;
+  int initial_start_;
+  int initial_end_;
+  int start_inflate_limit_;
+  int end_inflate_limit_;
+  bool reverse_order_;
+  bool within_bounds_;
+  int current_index_;
+  int step_;
+
+  InflateToLevelFnPtr inflate_to_level_ptr_;
+  IsWithinBoundsFnPtr is_within_bounds_ptr_;
+};

[vmpstr, 2016/08/16 00:40:48]

As far as I understand it, this class is just a pair of ints with operator++
that essentially just iterates from one int to the other one...

+
+// This class implements the 2D sequence (x, y) which uses two intervals, one
+// for traversing the actual interval, called as traversal interval and other
+// for computing the number of levels in the traversal interval. The indices of
+// these two intervals represent the x and y indices.
+// LevelDistance means each level has some distance value associated with it.
+// This distance is the distance from the index of the interest. If there are 5
+// levels and distance is 10, then the levels would have distances as given
+// below. 0, 10, 20, 30, 40. The first level starts with 0, so as to represent
+// the minimum distance for that level. The distances are stored in sorted
+// order in the vector, so that distance at front is minimum and 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 interval is [3, 4], number of levels is 3 and distance is
+// 10, then the triagular sequence would give following data.
+//
+//   traversal_interval   level index
+//         [3, 4]              0
+//         [2, 5]              1
+//         [1, 6]              2
+//
+// If the |reverse_order| is true, then the iteration sequence would be -
+//
+//   traversal_interval   level index
+//         [1, 6]              2
+//         [2, 5]              1
+//         [3, 4]              0
+//
+// The indices (x, y) for the normal order would be 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)
+//
+// The layout as given below looks like a triangle in co-ordinate space and
+// hence the name "TriangularSequence".
+//
+//   x 0 1 2 3 4 5 6 7
+//  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| . . . . . . . .
+class CC_EXPORT TriangularSequence {
+ public:
+  typedef std::list<TriangularSequence> List;
+  typedef List::iterator Iterator;
+  typedef List::reverse_iterator ReverseIterator;
+
+  TriangularSequence();
+  // If |swapped| is false, then the indices in |traversal_interval| represent
+  // the x indice and level indices in |level_interval| represent the y indices,
+  // otherwise vice-versa.
+  TriangularSequence(std::string&& name,
+                     Interval&& traversal_interval,
+                     Interval&& level_interval,
+                     bool swapped,
+                     int levels_to_skip,
+                     int distance,
+                     bool reverse_order);
+  TriangularSequence(const TriangularSequence& other);
+  TriangularSequence(TriangularSequence&& other);
+  ~TriangularSequence();
+
+  TriangularSequence& operator=(const TriangularSequence& other);
+  TriangularSequence& operator=(TriangularSequence&& other);
+
+  operator bool() const { return !level_distances_.empty(); }
+  TriangularSequence& operator++();
+
+  bool is_swapped() { return swapped_; }
+  Interval* traversal_interval() {
+    DCHECK(*this);
+    return &traversal_interval_;
+  }
+  int level_index() {
+    DCHECK(*this);
+    return current_level_index_;
+  }
+  // Get minimum/maximum distance.
+  int GetMinimumDistance() const;
+  int GetMaximumDistance() const;
+
+ private:
+  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;
+  };
+
+  void Advance();
+  void UpdateCurrent();
+
+  std::string name_;
+  Interval traversal_interval_;
+  bool swapped_;
+  bool reverse_order_;
+  int current_level_index_;
+  std::vector<LevelDistance> level_distances_;
+};
+
+// The pyramid sequence is list of 8 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 8 directions.
+//
+//                          2 T T T T T 1
+//                          L 2 T T T 1 R
+//                          L L 2 T 1 R R
+//                          L L L * R R R
+//                          L L 3 B 4 R R
+//                          L 3 B B B 4 R
+//                          3 B B B B B 4
+//
+// The different triangular sequences for the above pyramid sequence are shown
+// below.
+//
+//                            (T = top)
+//                                |
+//         (2 = top-left)     T T T T T     (1 = top-right)
+//                        2     T T T     1
+//                    L     2     T     1     R
+//                    L L     2       1     R R
+//     (L = left) --> L L L       *       R R R <-- (R = right)
+//                    L L     3       4     R R
+//                    L     3     B     4     R
+//                        3     B B B     4
+//      (3 = bottom-left)     B B B B B     (4 = bottom-right)
+//                                |
+//                         (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 is called as TopDownPyramidSequence, while the decreasubg order
+// of distances is called as BottomUpPyramidSequence. The iteration sequence
+// generated by top down pyramid sequence is as given below. (Iteration is
+// considered counter-clockwise.)
+//
+//   x  0  1  2  3  4  5  6
+//  y.---------------------
+//  0| 36 35 34 33 32 31 30
+//  1| 37 16 15 14 13 12 29
+//  2| 38 17  4  3  2 11 28
+//  3| 39 18  5  *  1 10 27
+//  4| 40 19  6  7  8  9 26
+//  5| 41 20 21 22 23 24 25
+//  6| 42 43 44 45 46 47 48
+//
+// The iteration sequence generated by bottom up pyramid sequence is as given
+// below. (Iteration is considered clockwise.)
+//
+//   x  0  1  2  3  4  5  6
+//  y.----------------------
+//  0| 13 14 15 16 17 18 19
+//  1| 12 33 34 35 36 37 20
+//  2| 11 32 45 46 47 38 21
+//  3| 10 31 44  * 48 39 22
+//  4|  9 30 43 42 41 40 23
+//  5|  8 29 28 27 26 25 24
+//  6|  7  6  5  4  3  2  1
+class CC_EXPORT PyramidSequence {
+ public:
+  explicit PyramidSequence(bool reverse_order);
+  PyramidSequence(const PyramidSequence& other);
+  PyramidSequence(PyramidSequence&& other);
+  virtual ~PyramidSequence();
+
+  PyramidSequence& operator=(const PyramidSequence& other);
+  PyramidSequence& operator=(PyramidSequence&& other);
+
+  virtual void 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);
+  operator bool() const;
+  PyramidSequence& operator++();
+
+  int index_x() const { return index_x_; }
+  int index_y() const { return index_y_; }
+
+ protected:
+  void EmplaceAt(int position, TriangularSequence&& triangular_sequence);
+
+  void Advance();
+  void UpdateCurrent();
+
+  void RemoveEmptyTriangularSequences();
+  virtual TriangularSequence* GetNextTriangularSequence() = 0;
+
+  bool InConsiderRect() const;
+  bool InIgnoreRect() const;
+
+  bool reverse_order_;
+  TriangularSequence* current_triangular_sequence_;
+  Interval* current_traversal_interval_;
+  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 index_x_;
+  int index_y_;
+  TriangularSequence::List triangular_sequences_;
+};
+
+class CC_EXPORT TopDownPyramidSequence : public PyramidSequence {
+ public:
+  TopDownPyramidSequence();
+  TopDownPyramidSequence(const TopDownPyramidSequence& other);
+  TopDownPyramidSequence(TopDownPyramidSequence&& other);
+  ~TopDownPyramidSequence() override;
+
+  TopDownPyramidSequence& operator=(const TopDownPyramidSequence& other);
+  TopDownPyramidSequence& operator=(TopDownPyramidSequence&& other);
+
+ private:
+  TriangularSequence* GetNextTriangularSequence() override;
+};
+
+class CC_EXPORT BottomUpPyramidSequence : public PyramidSequence {
+ public:
+  BottomUpPyramidSequence();
+  BottomUpPyramidSequence(const BottomUpPyramidSequence& other);
+  BottomUpPyramidSequence(BottomUpPyramidSequence&& other);
+  ~BottomUpPyramidSequence() override;
+
+  BottomUpPyramidSequence& operator=(const BottomUpPyramidSequence& other);
+  BottomUpPyramidSequence& operator=(BottomUpPyramidSequence&& other);
+
+ private:
+  TriangularSequence* GetNextTriangularSequence() override;
+};
+
+}  // namespace cc
+
+#endif  // CC_BASE_PYRAMID_SEQUENCE_H_