cc: Added a spiral difference iterator to tiling data.

This patch adds another iterator to tiling data. This iterator acts
similar to the difference iterator, but it also takes an extra center
rect parameter. The indices are returned in a counter-clockwise spiral
around the center rect. Note that the center rect itself is also
considered to be ignored.

Added tests to verify the behavior. Currently, the iterator is not used
anywhere outside of the unit tests.

R=enne@chromium.org

Review URL: https://codereview.chromium.org/183123004

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@254622 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 830 insertions, 0 deletions

diff --git a/cc/base/tiling_data.cc b/cc/base/tiling_data.cc
index 8b3ba62..4852110 100644
--- a/cc/base/tiling_data.cc
+++ b/cc/base/tiling_data.cc
@@ -68,6 +68,30 @@ void TilingData::SetBorderTexels(int border_texels) {
   RecomputeNumTiles();
 }
 
+std::pair<int, int> TilingData::UnclampedFirstBorderTileIndexFromSrcCoord(
+    int x,
+    int y) const {
+  int inner_tile_width = max_texture_size_.width() - 2 * border_texels_;
+  int result_x = (x - 2 * border_texels_) / inner_tile_width;
+
+  int inner_tile_height = max_texture_size_.height() - 2 * border_texels_;
+  int result_y = (y - 2 * border_texels_) / inner_tile_height;
+
+  return std::make_pair(result_x, result_y);
+}
+
+std::pair<int, int> TilingData::UnclampedLastBorderTileIndexFromSrcCoord(
+    int x,
+    int y) const {
+  int inner_tile_width = max_texture_size_.width() - 2 * border_texels_;
+  int result_x = x / inner_tile_width;
+
+  int inner_tile_height = max_texture_size_.height() - 2 * border_texels_;
+  int result_y = y / inner_tile_height;
+
+  return std::make_pair(result_x, result_y);
+}
+
 int TilingData::TileXIndexFromSrcCoord(int src_position) const {
   if (num_tiles_x_ <= 1)
     return 0;
@@ -409,4 +433,209 @@ TilingData::DifferenceIterator& TilingData::DifferenceIterator::operator++() {
   return *this;
 }
 
+TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator(
+    const TilingData* tiling_data,
+    const gfx::Rect& consider_rect,
+    const gfx::Rect& ignore_rect,
+    const gfx::Rect& center_rect)
+    : BaseIterator(tiling_data),
+      consider_left_(-1),
+      consider_top_(-1),
+      consider_right_(-1),
+      consider_bottom_(-1),
+      ignore_left_(-1),
+      ignore_top_(-1),
+      ignore_right_(-1),
+      ignore_bottom_(-1),
+      direction_(RIGHT),
+      delta_x_(1),
+      delta_y_(0),
+      current_step_(0),
+      horizontal_step_count_(0),
+      vertical_step_count_(0) {
+  if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) {
+    done();
+    return;
+  }
+
+  gfx::Rect bounds(tiling_data_->total_size());
+  gfx::Rect consider(consider_rect);
+  gfx::Rect ignore(ignore_rect);
+  gfx::Rect center(center_rect);
+  consider.Intersect(bounds);
+  ignore.Intersect(bounds);
+  if (consider.IsEmpty()) {
+    done();
+    return;
+  }
+
+  consider_left_ =
+      tiling_data_->FirstBorderTileXIndexFromSrcCoord(consider.x());
+  consider_top_ = tiling_data_->FirstBorderTileYIndexFromSrcCoord(consider.y());
+  consider_right_ =
+      tiling_data_->LastBorderTileXIndexFromSrcCoord(consider.right() - 1);
+  consider_bottom_ =
+      tiling_data_->LastBorderTileYIndexFromSrcCoord(consider.bottom() - 1);
+
+  if (!ignore.IsEmpty()) {
+    ignore_left_ = tiling_data_->FirstBorderTileXIndexFromSrcCoord(ignore.x());
+    ignore_top_ = tiling_data_->FirstBorderTileYIndexFromSrcCoord(ignore.y());
+    ignore_right_ =
+        tiling_data_->LastBorderTileXIndexFromSrcCoord(ignore.right() - 1);
+    ignore_bottom_ =
+        tiling_data_->LastBorderTileYIndexFromSrcCoord(ignore.bottom() - 1);
+
+    // Clamp ignore indices to consider indices.
+    ignore_left_ = std::max(ignore_left_, consider_left_);
+    ignore_top_ = std::max(ignore_top_, consider_top_);
+    ignore_right_ = std::min(ignore_right_, consider_right_);
+    ignore_bottom_ = std::min(ignore_bottom_, consider_bottom_);
+  }
+
+  if (ignore_left_ == consider_left_ && ignore_right_ == consider_right_ &&
+      ignore_top_ == consider_top_ && ignore_bottom_ == consider_bottom_) {
+    done();
+    return;
+  }
+
+  std::pair<int, int> around_left_top =
+      tiling_data->UnclampedFirstBorderTileIndexFromSrcCoord(center.x(),
+                                                             center.y());
+  std::pair<int, int> around_right_bottom =
+      tiling_data->UnclampedLastBorderTileIndexFromSrcCoord(
+          center.right() - 1, center.bottom() - 1);
+
+  if (center.IsEmpty()) {
+    around_left_top = std::make_pair(-1, -1);
+    around_right_bottom = std::make_pair(-1, -1);
+  }
+
+  int around_left = std::max(
+      -1, std::min(tiling_data_->num_tiles_x(), around_left_top.first));
+  int around_top = std::max(
+      -1, std::min(tiling_data_->num_tiles_y(), around_left_top.second));
+  int around_right = std::max(
+      -1, std::min(tiling_data_->num_tiles_x(), around_right_bottom.first));
+  int around_bottom = std::max(
+      -1, std::min(tiling_data_->num_tiles_y(), around_right_bottom.second));
+
+  vertical_step_count_ = around_bottom - around_top + 1;
+  horizontal_step_count_ = around_right - around_left + 1;
+  current_step_ = horizontal_step_count_ - 1;
+
+  index_x_ = around_right;
+  index_y_ = around_bottom;
+
+  // The current index is the bottom right of the around rect, which is also
+  // ignored. So we have to advance.
+  ++(*this);
+}
+
+TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator::
+operator++() {
+  int cannot_hit_consider_count = 0;
+  while (cannot_hit_consider_count < 4) {
+    if (needs_direction_switch())
+      switch_direction();
+
+    index_x_ += delta_x_;
+    index_y_ += delta_y_;
+    ++current_step_;
+
+    if (in_consider_rect()) {
+      cannot_hit_consider_count = 0;
+
+      if (!in_ignore_rect())
+        break;
+
+      // Steps needed to reach the very edge of the ignore rect, while remaining
+      // inside (so that the continue would take us outside).
+      int steps_to_edge = 0;
+      switch (direction_) {
+        case UP:
+          steps_to_edge = index_y_ - ignore_top_;
+          break;
+        case LEFT:
+          steps_to_edge = index_x_ - ignore_left_;
+          break;
+        case DOWN:
+          steps_to_edge = ignore_bottom_ - index_y_;
+          break;
+        case RIGHT:
+          steps_to_edge = ignore_right_ - index_x_;
+          break;
+      }
+
+      // We need to switch directions in |max_steps|.
+      int max_steps = current_step_count() - current_step_;
+
+      int steps_to_take = std::min(steps_to_edge, max_steps);
+      DCHECK_GE(steps_to_take, 0);
+
+      index_x_ += steps_to_take * delta_x_;
+      index_y_ += steps_to_take * delta_y_;
+      current_step_ += steps_to_take;
+    } else {
+      int max_steps = current_step_count() - current_step_;
+      int steps_to_take = max_steps;
+      bool can_hit_consider_rect = false;
+      switch (direction_) {
+        case UP:
+          if (valid_column() && consider_bottom_ < index_y_)
+            steps_to_take = index_y_ - consider_bottom_ - 1;
+          can_hit_consider_rect |= consider_right_ >= index_x_;
+          break;
+        case LEFT:
+          if (valid_row() && consider_right_ < index_x_)
+            steps_to_take = index_x_ - consider_right_ - 1;
+          can_hit_consider_rect |= consider_top_ <= index_y_;
+          break;
+        case DOWN:
+          if (valid_column() && consider_top_ > index_y_)
+            steps_to_take = consider_top_ - index_y_ - 1;
+          can_hit_consider_rect |= consider_left_ <= index_x_;
+          break;
+        case RIGHT:
+          if (valid_row() && consider_left_ > index_x_)
+            steps_to_take = consider_left_ - index_x_ - 1;
+          can_hit_consider_rect |= consider_bottom_ >= index_y_;
+          break;
+      }
+      steps_to_take = std::min(steps_to_take, max_steps);
+      DCHECK_GE(steps_to_take, 0);
+
+      index_x_ += steps_to_take * delta_x_;
+      index_y_ += steps_to_take * delta_y_;
+      current_step_ += steps_to_take;
+
+      if (can_hit_consider_rect)
+        cannot_hit_consider_count = 0;
+      else
+        ++cannot_hit_consider_count;
+    }
+  }
+
+  if (cannot_hit_consider_count >= 4)
+    done();
+  return *this;
+}
+
+bool TilingData::SpiralDifferenceIterator::needs_direction_switch() const {
+  return current_step_ >= current_step_count();
+}
+
+void TilingData::SpiralDifferenceIterator::switch_direction() {
+  int new_delta_x_ = delta_y_;
+  delta_y_ = -delta_x_;
+  delta_x_ = new_delta_x_;
+
+  current_step_ = 0;
+  direction_ = static_cast<Direction>((direction_ + 1) % 4);
+
+  if (direction_ == RIGHT || direction_ == LEFT) {
+    ++vertical_step_count_;
+    ++horizontal_step_count_;
+  }
+}
+
 }  // namespace cc
diff --git a/cc/base/tiling_data.h b/cc/base/tiling_data.h
index 9540c38..17274af 100644
--- a/cc/base/tiling_data.h
+++ b/cc/base/tiling_data.h
@@ -124,7 +124,66 @@ class CC_EXPORT TilingData {
     int ignore_bottom_;
   };
 
+  // Iterate through all indices whose bounds + border intersect with
+  // |consider| but which also do not intersect with |ignore|. The iterator
+  // order is a counterclockwise spiral around the given center.
+  class CC_EXPORT SpiralDifferenceIterator : public BaseIterator {
+   public:
+    SpiralDifferenceIterator(const TilingData* tiling_data,
+                             const gfx::Rect& consider_rect,
+                             const gfx::Rect& ignore_rect,
+                             const gfx::Rect& center_rect);
+    SpiralDifferenceIterator& operator++();
+
+   private:
+    bool in_consider_rect() const {
+      return index_x_ >= consider_left_ && index_x_ <= consider_right_ &&
+             index_y_ >= consider_top_ && index_y_ <= consider_bottom_;
+    }
+    bool in_ignore_rect() const {
+      return index_x_ >= ignore_left_ && index_x_ <= ignore_right_ &&
+             index_y_ >= ignore_top_ && index_y_ <= ignore_bottom_;
+    }
+    bool valid_column() const {
+      return index_x_ >= consider_left_ && index_x_ <= consider_right_;
+    }
+    bool valid_row() const {
+      return index_y_ >= consider_top_ && index_y_ <= consider_bottom_;
+    }
+
+    int current_step_count() const {
+      return (direction_ == UP || direction_ == DOWN) ? vertical_step_count_
+                                                      : horizontal_step_count_;
+    }
+
+    bool needs_direction_switch() const;
+    void switch_direction();
+
+    int consider_left_;
+    int consider_top_;
+    int consider_right_;
+    int consider_bottom_;
+    int ignore_left_;
+    int ignore_top_;
+    int ignore_right_;
+    int ignore_bottom_;
+
+    enum Direction { UP, LEFT, DOWN, RIGHT };
+
+    Direction direction_;
+    int delta_x_;
+    int delta_y_;
+    int current_step_;
+    int horizontal_step_count_;
+    int vertical_step_count_;
+  };
+
  private:
+  std::pair<int, int> UnclampedFirstBorderTileIndexFromSrcCoord(int x,
+                                                                int y) const;
+  std::pair<int, int> UnclampedLastBorderTileIndexFromSrcCoord(int x,
+                                                               int y) const;
+
   void AssertTile(int i, int j) const {
     DCHECK_GE(i,  0);
     DCHECK_LT(i, num_tiles_x_);
diff --git a/cc/base/tiling_data_unittest.cc b/cc/base/tiling_data_unittest.cc
index 55b3b6d..c81b546 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
+  // 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