cc: Added a spiral difference iterator to tiling data.

cc/base/tiling_data_unittest.cc

 // Copyright 2013 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/tiling_data.h"
 
+#include <algorithm>
 #include <vector>
 
 #include "cc/test/geometry_test_utils.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace cc {
 namespace {
 
 int NumTiles(
     const gfx::Size& max_texture_size,
@@ skipping 1143 matching lines @@
   TilingData big_border(gfx::Size(1000, 1000), gfx::Size(30, 40), 50);
   TestDiff(big_border, gfx::Rect(0, 0, 30, 40), gfx::Rect(), 1);
   TestDiff(big_border, gfx::Rect(5, 5, 100, 100), gfx::Rect(5, 5, 1, 1), 0);
 }
 
 TEST(TilingDataTest, DifferenceIteratorNoTiles) {
   TilingData data(gfx::Size(100, 100), gfx::Size(), false);
   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