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..c98e673294ebb31fa3a07bf21d26551822b3fe33
--- /dev/null
+++ b/cc/base/pyramid_sequence.h
@@ -0,0 +1,389 @@
+// 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 {
+
+// Triangular sequence is the representation of numbers in triangular form. This
+// takes initial |interval| (start <= number <= end), and inflates that interval
+// by the |levels| given, keeping the interval limit defined by the
+// |interval_inflate_limit|.
+//
+// e.g. With intial interval of [3, 4] and levels 4, the triagular sequence
+// would be as given below.
+//        3 4            (level 1)
+//      2 3 4 5          (level 2)
+//    1 2 3 4 5 6        (level 3)
+//  0 1 2 3 4 5 6 7      (level 4)

[vmpstr, 2016/07/19 20:28:28]

What would level 5 look like here?

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

-1 0 1 2 3 4 5 6 7 8

The inflation of intervals happens non-restrictively meaning it can flow in all
quadrants of the co-ordinate system.

Our interest is for positive quadrant meaning both x and y to be positive, which
we take care by passing interval_limit.

+//
+// With inflate limit of interval [2, 5] defined for the above example, the
+// sequence would be as given below.
+//        3 4
+//      2 3 4 5
+//      2 3 4 5
+//      2 3 4 5
+//
+// With inflate limit of interval [3, 10] defined for the above example, the
+// sequence would be as given below.
+//        3 4
+//        3 4 5
+//        3 4 5 6
+//        3 4 5 6 7
+// The triangular sequence can be of four different types as given below.
+// 1. FORWARD - start <= end as depicted in above example.
+// 2. BACKWARD - start >= end, e.g. initial interval [4, 3]
+//        4 3
+//      5 4 3 2
+// 3. DIAGONAL_FORWARD - start == end, in this case inflation happens in
+//    positive direction.
+//    e.g. 2, 3, 4, 5
+// 4. DIAGONAL_BACKWARD - start == end, in this case inflation happens in
+//    negative direction.
+//    e.g. 5, 4, 3, 2
+class CC_EXPORT TriangularSequence {

[vmpstr, 2016/07/19 20:28:28]

I think this class is conflating too many settings into one.

First, is this class returning Intervals or numbers within intervals? I'm not
clear what "Advance" does. Does this iterate over individual numbers and then
advance to the next level when appropriate?

If that's the case, I would prefer two separate classes. One to generate
Intervals so it would just have operator++ and operator* where operator* would
return the current interval and operator++ would advance the level. Then, you
can iterate over the given interval to iterate specific numbers. The caller of
this class can handle the double nesting. 

Second, I don't understand forward/backward/diagonal split. As far as I can
tell, you can just deal with forward case and iterate the interval backwards if
so desired. Diagonal seems to be a special case of start == end, but it's no
different than a regular forward with [start, start], so why the special case? 

At a high level, I'm also very confused by the naming.. why is this a pyramid
sequence? Why is start == end called "diagonal"?

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

This is to cater different portions of the pyramid sequence. Pyramid sequence is
list of 8 different level distance sequence.
All of the classes in this file, be it TriagularSequence, LevelDistanceSequence
or PyramidSequence return the next sequence and to advance or point to next
sequence, user should call Advance() method. To check whether sequence is
finished or not IsTravesed() method should be used.

** TriagularSequence is 1 dimensional sequence returns the numbers in inflated
or deflated order (decided by reverse variable)

** LevelDistanceSequence encapsulates the TriagularSequence to give 2
dimentional sequence, current level being traversed and sequence number in
current interval. It traverses one level at a time based on distance assigned to
the level, hence the name LevelDistanceSequence.

** PyramidSequence - It is the list of 8 different level distance sequences
which cover the given rectangle. As it has octgonal base (8 sequences) and these
8 faces are triangular (yeilding sequences in triangular fashion), this is a
kind of octagonal pyramid. This sequence traverses level by level each its
underlined LevelDistanceSequence based on distance, it is more like a slicing
the Pyramid level by level. If we slice this Pyramid from top to down fashion it
yeilds us what Spiral iterator should do and if sliced from bottom to up
fashion, it yeilds us what Reverse Spiral iterator should do.
I guess returning iterval will complicate the interface further. The
TriagularSequence should give next sequence number until it finishes all the
levels. So we need 3 simple interfaces -
1. IsTraversed() (this is current not implemented as it was handled by
is_within_bounds(), but for readability we should have this function),
2. Advance() - go to next sequence number
3. GetCurrent

Let me check how can we handle forward sequence and backward sequence in better
way based on your comments.
This is to have less and only needed computations respective to indivual case,
i.e. to avoid checking what is a case each time we inflate or check where it is
within limits/bounds.

That's why we have different function definitions for below function pointers.

using InflateFn = void (TriangularSequence::*)(int levels);
using IsWithinBoundsFn = bool (TriangularSequence::*)();
If we make start == end it will give us only one sequence number in
TriagularSequence at each level, so in a way it is linear sequence and we use it
here to cover diagonal portions of the pyramid as given in pyramid split -up
diagram. Hence the name.

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

For this I'll check if we can have container <-> iterator kind of separation.

+ public:
+  enum class Type : uint16_t {
+    FORWARD,
+    BACKWARD,
+    DIAGONAL_FORWARD,
+    DIAGONAL_BACKWARD
+  };
+
+  // Interval representing start and end, mathematical interval [start, end].
+  struct Interval {
+    Interval(int start, int end) : start(start), end(end) {}
+    Interval(const Interval& other) = default;

[vmpstr, 2016/07/19 20:28:28]

You don't need to specify copy/move operations here. 

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

When I tested on Windows (Visual Studio 2013) it was calling copy constructor
instead of move constructor when object is passed as an argument.

I wanted all in-place construction to be move construction, so that we have
minimal overhead when we assign an object to another object.

I'll check if we can skip move constructor and move assignment for simple
classes like these.

At
https://cs.chromium.org/chromium/src/cc/tiles/tiling_set_raster_queue_all.cc?...
we assign the object from newly constructed object, so there we can take benefit
of move assignment.

+    Interval(Interval&& other) = default;
+    Interval& operator=(const Interval& other) = default;
+    Interval& operator=(Interval&& other) = default;
+
+    int start;
+    int end;
+  };
+
+  // |name| - Name for the sequence.
+  // |type| - Type of the sequence.
+  // |interval| - Initial interval.
+  // |interval_inflate_limit| - Inflating limit for interval.
+  // |levels| - Number of times inflation should happen.
+  // |levels_to_skip| - Number of levels to skip. The inital interval is
+  // inflated to this value, so that the interval to start the sequence is
+  // pointed to the required level.
+  // |reverse| - If true the initial interval is inflated to the last level and
+  // sequence is continued from |levels| to |levels_to_skip|.
+  TriangularSequence(std::string&& name,
+                     Type type,
+                     Interval&& interval,
+                     Interval&& interval_inflate_limit,
+                     int levels,
+                     int levels_to_skip,
+                     bool reverse);
+  TriangularSequence(const TriangularSequence& other);
+  TriangularSequence(TriangularSequence&& other);
+  ~TriangularSequence();
+
+  TriangularSequence& operator=(const TriangularSequence& other);
+  TriangularSequence& operator=(TriangularSequence&& other);
+
+  // Returns whether the sequence at the current level is overflowing the limits
+  // of the current interval.
+  bool is_within_bounds() { return within_bounds_; }
+
+  int GetInitialIntervalSpan();
+
+  // Get the current sequence number, if the number has overflown the current
+  // level's interval, then interval is inflated and number starting at the next
+  // interval is returned. If all levels have been traversed, then it returns
+  // last number in the sequence.
+  int GetCurrentSequenceNumber();
+  // Same like above, but in reverse direction.

[vmpstr, 2016/07/19 20:28:28]

This is not clear at all. GetCurrentSequenceNumber's comment is pretty
complicated; simply saying "but in reverse" breaks my understanding even more. 

My confusion is exacerbated by the fact that you already have a
backwards/forward split in the Type, and now you have a reverse getter as well.
So, if I have a backward sequence and use GetReverseCurrentSequenceNumber is
that equivalent to using a forward sequence with GetCurrentSequenceNumber?

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

Hmm. I'll write simple functions having more appropriate comments and function
names.

+  int GetReverseCurrentSequenceNumber();
+
+  // Advances the sequence number to the next in the current interval. If number
+  // overflows the interval, then |within_bounds_| is set to false.
+  void Advance();
+
+ private:
+  using InflateFn = void (TriangularSequence::*)(int levels);
+  using IsWithinBoundsFn = bool (TriangularSequence::*)();
+
+  void Init(Type type);
+  void Reset();
+
+  // Interval inflating functions for different TriangularSequence types.
+  void InflateForward(int levels);
+  void InflateBackward(int levels);
+  void InflateDiagonalForward(int levels);
+  void InflateDiagonalBackward(int levels);
+
+  // Functions for checking the bounds for different TriangularSequence types.
+  bool IsWithinBoundsForward();
+  bool IsWithinBoundsBackward();
+  bool IsWithinBoundsDiagonal();
+
+  std::string name_;
+  Type type_;
+  Interval interval_;
+  Interval interval_inflate_limit_;
+  Interval initial_interval_;
+  int levels_;
+  int levels_traversed_;
+  int levels_limit_;
+  bool reverse_;
+  bool within_bounds_;
+  int current_sequence_number_;
+  int step_;
+
+  InflateFn inflate_;
+  IsWithinBoundsFn is_within_bounds_;
+};
+
+// This class implements the 2D sequence which uses two triangular sequences,
+// one for traversing the actual sequence and other for computing the number of
+// levels for the traversal sequence.
+//
+// LevelDistance means each level has some length value associated with it. The
+// distance is distance from the viewport or rect of 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 sequence is [3, 4], number of levels is 3 and distance is
+// 10, then layout of the level distance sequence would be as given below.
+//
+//   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| . . . . . . . .
+//
+// When the above sequence is iterated then the indices output 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)
+// At each level change, this sequence conveys that level has changed.
+class CC_EXPORT LevelDistanceSequence {
+ public:
+  typedef std::list<LevelDistanceSequence> List;
+  typedef List::iterator Iterator;
+  typedef List::reverse_iterator ReverseIterator;
+
+  LevelDistanceSequence();
+  // If |reverse| is true, then |traversal_sequence| is iterated from the
+  // interval at farthest level to the initial interval. If |swapped| is false
+  // then the sequence numbers in |traversal_sequence| represent the x index and
+  // sequence numbers in |level_sequence| represent the y index, otherwise vice
+  // versa.
+  LevelDistanceSequence(TriangularSequence&& traversal_sequence,
+                        TriangularSequence&& level_sequence,
+                        bool swapped,
+                        int levels_to_skip,
+                        int levels_delta,
+                        int distance,
+                        bool reverse);
+  LevelDistanceSequence(const LevelDistanceSequence& other);
+  LevelDistanceSequence(LevelDistanceSequence&& other);
+  ~LevelDistanceSequence();
+
+  LevelDistanceSequence& operator=(const LevelDistanceSequence& other);
+  LevelDistanceSequence& operator=(LevelDistanceSequence&& other);
+
+  // Return true if this sequence is valid or not.
+  bool IsValid() const { return !level_distances_.empty(); }
+
+  // Gets current indices.
+  int GetCurrentIndexX() const;
+  int GetCurrentIndexY() const;
+
+  // Get minimum/maximum distance.
+  int GetMinimumDistance() const;
+  int GetMaximumDistance() const;
+
+  // Advances or reverse-advances the |traversal_sequence|. When the interval is
+  // traversed fully, then this function return false for indicating the current
+  // level in |traversal_sequence| has been finished.
+  bool Advance();
+  bool ReverseAdvance();
+
+ private:
+  struct LevelDistance {
+    LevelDistance(int level, int distance) : level(level), distance(distance) {}
+
+    int level;
+    int distance;
+  };
+
+  void Reset();
+
+  TriangularSequence traversal_sequence_;
+  bool swapped_;
+  bool reverse_;
+  int current_sequence_index_;
+  int current_level_index_;
+  std::vector<LevelDistance> level_distances_;
+};
+
+// The pyramid sequence is list of 8 level distance sequences, one for each of
+// the directions considered counter-clockwise or clockwise. The actual order
+// of level distance sequences is computed by the direction in which coverage is
+// required. (See GetCoverageDirectionSequenceForDirections() for more details.)
+// 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 level distance sequences for the above pyramid sequence is
+// 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 level distance sequences level
+// by level in increasing or decreasing order of distances. The increasing order
+// of distance is called as TopDownPyramidSequence, while the other 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);
+  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);
+  bool IsTraversed();
+
+  virtual void Advance() = 0;
+
+  void UpdateCurrent();
+  int GetCurrentIndexX() const { return index_x_; }
+  int GetCurrentIndexY() const { return index_y_; }
+
+ protected:
+  virtual LevelDistanceSequence* GetNextLevelDistanceSequence() = 0;
+
+  void EmplaceAt(int position, LevelDistanceSequence&& level_distance_sequence);
+  bool InConsiderRect() const;
+  bool InIgnoreRect() const;
+  void RemoveEmptyLevelDistanceSequences();
+
+  bool reverse_;
+  LevelDistanceSequence* current_level_distance_sequence_;
+  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_;
+  LevelDistanceSequence::List level_distance_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);
+
+  void Advance() override;
+
+ private:
+  LevelDistanceSequence* GetNextLevelDistanceSequence() 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);
+
+  void Advance() override;
+
+ private:
+  LevelDistanceSequence* GetNextLevelDistanceSequence() override;
+};
+
+}  // namespace cc
+
+#endif  // CC_BASE_PYRAMID_SEQUENCE_H_