cc: Added a spiral difference iterator to tiling data.

cc/base/tiling_data_unittest.cc

Index: cc/base/tiling_data_unittest.cc
diff --git a/cc/base/tiling_data_unittest.cc b/cc/base/tiling_data_unittest.cc
index 55b3b6d77ecf7637fdc8012aa1e1c6fdc3d6b7c3..c81b5463fb69d8b6b42b4158e32f56b53417aa89 100644
--- a/cc/base/tiling_data_unittest.cc
+++ b/cc/base/tiling_data_unittest.cc
@@ -4,6 +4,7 @@
 
 #include "cc/base/tiling_data.h"
 
+#include <algorithm>
 #include <vector>
 
 #include "cc/test/geometry_test_utils.h"
@@ -1167,5 +1168,546 @@ TEST(TilingDataTest, DifferenceIteratorNoTiles) {
   TestDiff(data, gfx::Rect(0, 0, 100, 100), gfx::Rect(0, 0, 5, 5), 0);
 }
 
+void TestSpiralIterate(int source_line_number,
+                       const TilingData& tiling_data,
+                       const gfx::Rect& consider,
+                       const gfx::Rect& ignore,
+                       const gfx::Rect& center,
+                       const std::vector<std::pair<int, int> >& expected) {
+  std::vector<std::pair<int, int> > actual;
+  for (TilingData::SpiralDifferenceIterator it(
+           &tiling_data, consider, ignore, center);
+       it;
+       ++it) {
+    actual.push_back(it.index());
+  }
+
+  EXPECT_EQ(expected.size(), actual.size()) << "error from line "
+                                            << source_line_number;
+  for (size_t i = 0; i < std::min(expected.size(), actual.size()); ++i) {
+    EXPECT_EQ(expected[i].first, actual[i].first)
+        << "i: " << i << " error from line: " << source_line_number;
+    EXPECT_EQ(expected[i].second, actual[i].second)
+        << "i: " << i << " error from line: " << source_line_number;
+  }
+}
+
+TEST(TilingDataTest, SpiralDifferenceIteratorNoIgnoreFullConsider) {
+  TilingData tiling_data(gfx::Size(10, 10), gfx::Size(30, 30), false);
+  gfx::Rect consider(0, 0, 30, 30);
+  gfx::Rect ignore;
+  std::vector<std::pair<int, int> > expected;
+
+  // Center is in the center of the tiling.
+  gfx::Rect center(15, 15, 1, 1);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2
+  //  y.------
+  //  0| 4 3 2
+  //  1| 5 * 1
+  //  2| 6 7 8
+  expected.push_back(std::make_pair(2, 1));
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(1, 0));
+  expected.push_back(std::make_pair(0, 0));
+  expected.push_back(std::make_pair(0, 1));
+  expected.push_back(std::make_pair(0, 2));
+  expected.push_back(std::make_pair(1, 2));
+  expected.push_back(std::make_pair(2, 2));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Center is off to the right side of the tiling (and far away).
+  center = gfx::Rect(100, 15, 1, 1);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2
+  //  y.------
+  //  0| 7 4 1
+  //  1| 8 5 2 *
+  //  2| 9 6 3
+  expected.clear();
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(2, 1));
+  expected.push_back(std::make_pair(2, 2));
+  expected.push_back(std::make_pair(1, 0));
+  expected.push_back(std::make_pair(1, 1));
+  expected.push_back(std::make_pair(1, 2));
+  expected.push_back(std::make_pair(0, 0));
+  expected.push_back(std::make_pair(0, 1));
+  expected.push_back(std::make_pair(0, 2));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Center is the bottom right corner of the tiling.
+  center = gfx::Rect(25, 25, 1, 1);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2
+  //  y.------
+  //  0| 6 5 4
+  //  1| 7 2 1
+  //  2| 8 3 *
+  expected.clear();
+  expected.push_back(std::make_pair(2, 1));
+  expected.push_back(std::make_pair(1, 1));
+  expected.push_back(std::make_pair(1, 2));
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(1, 0));
+  expected.push_back(std::make_pair(0, 0));
+  expected.push_back(std::make_pair(0, 1));
+  expected.push_back(std::make_pair(0, 2));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Center is off the top left side of the tiling.
+  center = gfx::Rect(-60, -50, 1, 1);
+
+  // Layout of the tiling data, and expected return order:
+  // * x 0 1 2
+  //  y.------
+  //  0| 1 2 6
+  //  1| 3 4 5
+  //  2| 7 8 9
+  expected.clear();
+  expected.push_back(std::make_pair(0, 0));
+  expected.push_back(std::make_pair(1, 0));
+  expected.push_back(std::make_pair(0, 1));
+  expected.push_back(std::make_pair(1, 1));
+  expected.push_back(std::make_pair(2, 1));
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(0, 2));
+  expected.push_back(std::make_pair(1, 2));
+  expected.push_back(std::make_pair(2, 2));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Two tile center.
+  center = gfx::Rect(15, 15, 1, 10);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2
+  //  y.------
+  //  0| 5 4 3
+  //  1| 6 * 2
+  //  2| 7 * 1
+  expected.clear();
+  expected.push_back(std::make_pair(2, 2));
+  expected.push_back(std::make_pair(2, 1));
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(1, 0));
+  expected.push_back(std::make_pair(0, 0));
+  expected.push_back(std::make_pair(0, 1));
+  expected.push_back(std::make_pair(0, 2));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+}
+
+TEST(TilingDataTest, SpiralDifferenceIteratorSmallConsider) {
+  TilingData tiling_data(gfx::Size(10, 10), gfx::Size(50, 50), false);
+  gfx::Rect ignore;
+  std::vector<std::pair<int, int> > expected;
+  gfx::Rect center(15, 15, 1, 1);
+
+  // Consider is one cell.
+  gfx::Rect consider(0, 0, 1, 1);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2 3 4
+  //  y.----------
+  //  0| 1
+  //  1|   *
+  //  2|
+  //  3|
+  //  4|
+  expected.push_back(std::make_pair(0, 0));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Consider is bottom right corner.
+  consider = gfx::Rect(25, 25, 10, 10);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2 3 4
+  //  y.----------
+  //  0|
+  //  1|   *
+  //  2|     1 2
+  //  3|     3 4
+  //  4|
+  expected.clear();
+  expected.push_back(std::make_pair(2, 2));
+  expected.push_back(std::make_pair(3, 2));
+  expected.push_back(std::make_pair(2, 3));
+  expected.push_back(std::make_pair(3, 3));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Consider is one column.
+  consider = gfx::Rect(11, 0, 1, 100);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2 3 4
+  //  y.----------
+  //  0|   2
+  //  1|   *
+  //  2|   3
+  //  3|   4
+  //  4|   5
+  expected.clear();
+  expected.push_back(std::make_pair(1, 0));
+  expected.push_back(std::make_pair(1, 2));
+  expected.push_back(std::make_pair(1, 3));
+  expected.push_back(std::make_pair(1, 4));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+}
+
+TEST(TilingDataTest, SpiralDifferenceIteratorHasIgnore) {
+  TilingData tiling_data(gfx::Size(10, 10), gfx::Size(50, 50), false);
+  gfx::Rect consider(0, 0, 50, 50);
+  std::vector<std::pair<int, int> > expected;
+  gfx::Rect center(15, 15, 1, 1);
+
+  // Full ignore.
+  gfx::Rect ignore(0, 0, 50, 50);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2 3 4
+  //  y.----------
+  //  0| . . . . .
+  //  1| . * . . .
+  //  2| . . . . .
+  //  3| . . . . .
+  //  4| . . . . .
+  expected.clear();
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // 3 column ignore.
+  ignore = gfx::Rect(15, 0, 20, 100);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2 3 4
+  //  y.----------
+  //  0| 1 . . . 8
+  //  1| 2 * . . 7
+  //  2| 3 . . . 6
+  //  3| 4 . . . 5
+  //  4| 9 . . . 10
+  expected.clear();
+
+  expected.push_back(std::make_pair(0, 0));
+  expected.push_back(std::make_pair(0, 1));
+  expected.push_back(std::make_pair(0, 2));
+  expected.push_back(std::make_pair(0, 3));
+  expected.push_back(std::make_pair(4, 3));
+  expected.push_back(std::make_pair(4, 2));
+  expected.push_back(std::make_pair(4, 1));
+  expected.push_back(std::make_pair(4, 0));
+  expected.push_back(std::make_pair(0, 4));
+  expected.push_back(std::make_pair(4, 4));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Ignore covers the top half.
+  ignore = gfx::Rect(0, 0, 50, 25);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2 3 4
+  //  y.----------
+  //  0| . . . . .
+  //  1| . * . . .
+  //  2| . . . . .
+  //  3| 1 2 3 4 5
+  //  4| 6 7 8 9 10
+  expected.clear();
+
+  expected.push_back(std::make_pair(0, 3));
+  expected.push_back(std::make_pair(1, 3));
+  expected.push_back(std::make_pair(2, 3));
+  expected.push_back(std::make_pair(3, 3));
+  expected.push_back(std::make_pair(4, 3));
+  expected.push_back(std::make_pair(0, 4));
+  expected.push_back(std::make_pair(1, 4));
+  expected.push_back(std::make_pair(2, 4));
+  expected.push_back(std::make_pair(3, 4));
+  expected.push_back(std::make_pair(4, 4));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+}
+
+TEST(TilingDataTest, SpiralDifferenceIteratorRectangleCenter) {
+  TilingData tiling_data(gfx::Size(10, 10), gfx::Size(50, 50), false);
+  gfx::Rect consider(0, 0, 50, 50);
+  std::vector<std::pair<int, int> > expected;
+  gfx::Rect ignore;
+
+  // Two cell center
+  gfx::Rect center(25, 25, 1, 10);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2 3 4
+  //  y.----------
+  //  0| J I H G F
+  //  1| K 5 4 3 E
+  //  2| L 6 * 2 D
+  //  3| M 7 * 1 C
+  //  4| N 8 9 A B
+  expected.clear();
+
+  expected.push_back(std::make_pair(3, 3));
+  expected.push_back(std::make_pair(3, 2));
+  expected.push_back(std::make_pair(3, 1));
+  expected.push_back(std::make_pair(2, 1));
+  expected.push_back(std::make_pair(1, 1));
+  expected.push_back(std::make_pair(1, 2));
+  expected.push_back(std::make_pair(1, 3));
+  expected.push_back(std::make_pair(1, 4));
+  expected.push_back(std::make_pair(2, 4));
+  expected.push_back(std::make_pair(3, 4));
+  expected.push_back(std::make_pair(4, 4));
+  expected.push_back(std::make_pair(4, 3));
+  expected.push_back(std::make_pair(4, 2));
+  expected.push_back(std::make_pair(4, 1));
+  expected.push_back(std::make_pair(4, 0));
+  expected.push_back(std::make_pair(3, 0));
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(1, 0));
+  expected.push_back(std::make_pair(0, 0));
+  expected.push_back(std::make_pair(0, 1));
+  expected.push_back(std::make_pair(0, 2));
+  expected.push_back(std::make_pair(0, 3));
+  expected.push_back(std::make_pair(0, 4));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Three by two center.
+  center = gfx::Rect(15, 25, 20, 10);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2 3 4
+  //  y.----------
+  //  0| J I H G F
+  //  1| 7 6 5 4 3
+  //  2| 8 * * * 2
+  //  3| 9 * * * 1
+  //  4| A B C D E
+  expected.clear();
+
+  expected.push_back(std::make_pair(4, 3));
+  expected.push_back(std::make_pair(4, 2));
+  expected.push_back(std::make_pair(4, 1));
+  expected.push_back(std::make_pair(3, 1));
+  expected.push_back(std::make_pair(2, 1));
+  expected.push_back(std::make_pair(1, 1));
+  expected.push_back(std::make_pair(0, 1));
+  expected.push_back(std::make_pair(0, 2));
+  expected.push_back(std::make_pair(0, 3));
+  expected.push_back(std::make_pair(0, 4));
+  expected.push_back(std::make_pair(1, 4));
+  expected.push_back(std::make_pair(2, 4));
+  expected.push_back(std::make_pair(3, 4));
+  expected.push_back(std::make_pair(4, 4));
+  expected.push_back(std::make_pair(4, 0));
+  expected.push_back(std::make_pair(3, 0));
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(1, 0));
+  expected.push_back(std::make_pair(0, 0));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Column center off the left side.
+  center = gfx::Rect(-50, 0, 30, 50);
+
+  // Layout of the tiling data, and expected return order:
+  //    x 0 1 2 3 4
+  //   y.----------
+  // * 0| 5 A F K P
+  // * 1| 4 9 E J O
+  // * 2| 3 8 D I N
+  // * 3| 2 7 C H M
+  // * 4| 1 6 B G L
+  expected.clear();
+
+  expected.push_back(std::make_pair(0, 4));
+  expected.push_back(std::make_pair(0, 3));
+  expected.push_back(std::make_pair(0, 2));
+  expected.push_back(std::make_pair(0, 1));
+  expected.push_back(std::make_pair(0, 0));
+  expected.push_back(std::make_pair(1, 4));
+  expected.push_back(std::make_pair(1, 3));
+  expected.push_back(std::make_pair(1, 2));
+  expected.push_back(std::make_pair(1, 1));
+  expected.push_back(std::make_pair(1, 0));
+  expected.push_back(std::make_pair(2, 4));
+  expected.push_back(std::make_pair(2, 3));
+  expected.push_back(std::make_pair(2, 2));
+  expected.push_back(std::make_pair(2, 1));
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(3, 4));
+  expected.push_back(std::make_pair(3, 3));
+  expected.push_back(std::make_pair(3, 2));
+  expected.push_back(std::make_pair(3, 1));
+  expected.push_back(std::make_pair(3, 0));
+  expected.push_back(std::make_pair(4, 4));
+  expected.push_back(std::make_pair(4, 3));
+  expected.push_back(std::make_pair(4, 2));
+  expected.push_back(std::make_pair(4, 1));
+  expected.push_back(std::make_pair(4, 0));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+}
+
+TEST(TilingDataTest, SpiralDifferenceIteratorEdgeCases) {
+  TilingData tiling_data(gfx::Size(10, 10), gfx::Size(30, 30), false);
+  std::vector<std::pair<int, int> > expected;
+  gfx::Rect center;
+  gfx::Rect consider;
+  gfx::Rect ignore;
+
+  // Ignore contains, but is not equal to, consider and center.
+  ignore = gfx::Rect(15, 0, 20, 30);
+  consider = gfx::Rect(20, 10, 10, 20);
+  center = gfx::Rect(25, 0, 5, 5);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2
+  //  y.------
+  //  0|   . *
+  //  1|   . .
+  //  2|   . .
+  expected.clear();
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Center intersects with consider.
+  ignore = gfx::Rect();
+  center = gfx::Rect(0, 15, 30, 15);
+  consider = gfx::Rect(0, 0, 15, 30);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2
+  //  y.------
+  //  0| 2 1
+  //  1| * * *
+  //  2| * * *
+  expected.clear();
+
+  expected.push_back(std::make_pair(1, 0));
+  expected.push_back(std::make_pair(0, 0));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Consider and ignore are non-intersecting.
+  ignore = gfx::Rect(0, 0, 5, 30);
+  consider = gfx::Rect(25, 0, 5, 30);
+  center = gfx::Rect(15, 0, 1, 1);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2
+  //  y.------
+  //  0| . * 1
+  //  1| .   2
+  //  2| .   3
+  expected.clear();
+
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(2, 1));
+  expected.push_back(std::make_pair(2, 2));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Center intersects with ignore.
+  consider = gfx::Rect(0, 0, 30, 30);
+  center = gfx::Rect(15, 0, 1, 30);
+  ignore = gfx::Rect(0, 15, 30, 1);
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2
+  //  y.------
+  //  0| 3 * 2
+  //  1| . * .
+  //  2| 4 * 1
+  expected.clear();
+
+  expected.push_back(std::make_pair(2, 2));
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(0, 0));
+  expected.push_back(std::make_pair(0, 2));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Center and ignore are the same.
+  consider = gfx::Rect(0, 0, 30, 30);
+  center = gfx::Rect(15, 0, 1, 30);
+  ignore = center;
+
+  // Layout of the tiling data, and expected return order:
+  //   x 0 1 2
+  //  y.------
+  //  0| 4 * 3
+  //  1| 5 * 2
+  //  2| 6 * 1
+  expected.clear();
+
+  expected.push_back(std::make_pair(2, 2));
+  expected.push_back(std::make_pair(2, 1));
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(0, 0));
+  expected.push_back(std::make_pair(0, 1));
+  expected.push_back(std::make_pair(0, 2));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Empty tiling data.
+  TilingData empty_data(gfx::Size(0, 0), gfx::Size(0, 0), false);
+
+  expected.clear();
+  TestSpiralIterate(__LINE__, empty_data, consider, ignore, center, expected);
+
+  // Empty consider.
+  ignore = gfx::Rect();
+  center = gfx::Rect(1, 1, 1, 1);
+  consider = gfx::Rect();
+
+  expected.clear();
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Empty center. Note: This arbitrarily puts the center to be off the top-left

[enne (OOO), 2014/03/01 00:43:45]

I think I'd weakly prefer an empty center to just not return anything at all. 
Empty rects don't really have a position.

[vmpstr, 2014/03/03 18:32:23]

I kept it as is, since I believe that an empty center should still enumerate all
indecies, it's just the order of those is not defined (arbitrary). I fear that
making empty center not return anything can result is subtle bugs where the
center becomes empty through some calculation and then nothing is iterated. I'm
going to CQ as is, but if you feel strongly please un-cq.

+  // corner.
+  consider = gfx::Rect(0, 0, 30, 30);
+  ignore = gfx::Rect();
+  center = gfx::Rect();
+
+  // Layout of the tiling data, and expected return order:
+  // * x 0 1 2
+  //  y.------
+  //  0| 1 2 6
+  //  1| 3 4 5
+  //  2| 7 8 9
+  expected.clear();
+
+  expected.push_back(std::make_pair(0, 0));
+  expected.push_back(std::make_pair(1, 0));
+  expected.push_back(std::make_pair(0, 1));
+  expected.push_back(std::make_pair(1, 1));
+  expected.push_back(std::make_pair(2, 1));
+  expected.push_back(std::make_pair(2, 0));
+  expected.push_back(std::make_pair(0, 2));
+  expected.push_back(std::make_pair(1, 2));
+  expected.push_back(std::make_pair(2, 2));
+
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+
+  // Every rect is empty.
+  ignore = gfx::Rect();
+  center = gfx::Rect();
+  consider = gfx::Rect();
+
+  expected.clear();
+  TestSpiralIterate(__LINE__, tiling_data, consider, ignore, center, expected);
+}
 }  // namespace
 }  // namespace cc