cc: Detach spiral iterator implementation to separate file.

cc/base/reverse_spiral_iterator.cc

+// 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.
+
+#include "cc/base/reverse_spiral_iterator.h"
+
+#include <algorithm>
+
+namespace cc {
+
+ReverseSpiralIterator::ReverseSpiralIterator()
+    : around_index_rect_(-1, -1, -1, -1),
+      consider_index_rect_(-1, -1, -1, -1),
+      ignore_index_rect_(-1, -1, -1, -1),
+      index_x_(-1),
+      index_y_(-1) {}
+
+ReverseSpiralIterator::ReverseSpiralIterator(
+    const IndexRect& around_index_rect,
+    const IndexRect& consider_index_rect,
+    const IndexRect& ignore_index_rect)
+    : around_index_rect_(around_index_rect),
+      consider_index_rect_(consider_index_rect),
+      ignore_index_rect_(ignore_index_rect),
+      index_x_(-1),
+      index_y_(-1),
+      direction_(LEFT),
+      delta_x_(-1),
+      delta_y_(0),
+      current_step_(0),
+      horizontal_step_count_(0),
+      vertical_step_count_(0) {
+  // Figure out the maximum distance from the around edge to consider edge.
+  int max_distance = 0;
+  max_distance = std::max(
+      max_distance, around_index_rect_.top() - consider_index_rect_.top());
+  max_distance = std::max(
+      max_distance, around_index_rect_.left() - consider_index_rect_.left());
+  max_distance = std::max(max_distance, consider_index_rect_.bottom() -
+                                            around_index_rect_.bottom());
+  max_distance = std::max(
+      max_distance, consider_index_rect_.right() - around_index_rect_.right());
+
+  // The step count is the length of the edge
+  // (around_index_rect_.num_indices_x()) plus twice the max distance to pad
+  // (to the right and to the left). This way the initial rect is the size
+  // proportional to the center, but big enough to cover the consider rect.
+  //
+  // C = consider rect
+  // A = around rect
+  // . = area of the padded around rect
+  // md = max distance (note in the picture below, there's md written vertically
+  //      as well).
+  // I = initial starting position
+  //
+  //       |md|  |md|
+  //
+  //     - ..........
+  //     m ..........
+  //     d ..........
+  //     - CCCCCCC...
+  //       CCCCAAC...
+  //       CCCCAAC...
+  //     - ..........
+  //     m ..........
+  //     d ..........
+  //     - ..........I
+  vertical_step_count_ = around_index_rect_.num_indices_y() + 2 * max_distance;
+  horizontal_step_count_ =
+      around_index_rect_.num_indices_x() + 2 * max_distance;
+
+  // Start with one to the right of the padded around rect.
+  index_x_ = around_index_rect_.right() + max_distance + 1;
+  index_y_ = around_index_rect_.bottom() + max_distance;
+
+  // The current index is outside a valid tile, so advance immediately.
+  ++(*this);
+}
+
+ReverseSpiralIterator::operator bool() const {
+  return index_x_ != -1 && index_y_ != -1;
+}
+
+ReverseSpiralIterator& ReverseSpiralIterator::operator++() {
+  while (!around_index_rect_.Contains(index_x_, index_y_)) {
+    if (needs_direction_switch())
+      switch_direction();
+
+    index_x_ += delta_x_;
+    index_y_ += delta_y_;
+    ++current_step_;
+
+    if (around_index_rect_.Contains(index_x_, index_y_)) {
+      break;
+    } else if (consider_index_rect_.Contains(index_x_, index_y_)) {
+      // If the tile is in the consider rect but not in ignore rect, then it's a
+      // valid tile to visit.
+      if (!ignore_index_rect_.Contains(index_x_, index_y_))
+        break;
+
+      // Steps needed to reach the very edge of the ignore rect, while remaining
+      // inside it (so that the continue would take us outside).
+      int steps_to_edge = 0;
+      switch (direction_) {
+        case UP:
+          steps_to_edge = index_y_ - ignore_index_rect_.top();
+          break;
+        case LEFT:
+          steps_to_edge = index_x_ - ignore_index_rect_.left();
+          break;
+        case DOWN:
+          steps_to_edge = ignore_index_rect_.bottom() - index_y_;
+          break;
+        case RIGHT:
+          steps_to_edge = ignore_index_rect_.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 {
+      // We're not in the consider rect.
+
+      int max_steps = current_step_count() - current_step_;
+      int steps_to_take = max_steps;
+
+      // We might hit the consider rect before needing to switch directions:
+      // update steps to take.
+      switch (direction_) {
+        case UP:
+          if (consider_index_rect_.valid_column(index_x_) &&
+              consider_index_rect_.bottom() < index_y_)
+            steps_to_take = index_y_ - consider_index_rect_.bottom() - 1;
+          break;
+        case LEFT:
+          if (consider_index_rect_.valid_row(index_y_) &&
+              consider_index_rect_.right() < index_x_)
+            steps_to_take = index_x_ - consider_index_rect_.right() - 1;
+          break;
+        case DOWN:
+          if (consider_index_rect_.valid_column(index_x_) &&
+              consider_index_rect_.top() > index_y_)
+            steps_to_take = consider_index_rect_.top() - index_y_ - 1;
+          break;
+        case RIGHT:
+          if (consider_index_rect_.valid_row(index_y_) &&
+              consider_index_rect_.left() > index_x_)
+            steps_to_take = consider_index_rect_.left() - index_x_ - 1;
+          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;
+    }
+  }
+
+  // Once we enter the around rect, we're done.
+  if (around_index_rect_.Contains(index_x_, index_y_)) {
+    index_x_ = -1;
+    index_y_ = -1;
+  }
+
+  return *this;
+}
+
+bool ReverseSpiralIterator::needs_direction_switch() const {
+  return current_step_ >= current_step_count();
+}
+
+void ReverseSpiralIterator::switch_direction() {
+  // Note that delta_x_ and delta_y_ always remain between -1 and 1.
+  int new_delta_y = delta_x_;
+  delta_x_ = -delta_y_;
+  delta_y_ = new_delta_y;
+
+  current_step_ = 0;
+  direction_ = static_cast<Direction>((direction_ + 1) % 4);
+
+  if (direction_ == UP || direction_ == DOWN) {
+    --vertical_step_count_;
+    --horizontal_step_count_;
+
+    // We should always end up in an around rect at some point.
+    // Since the direction is now vertical, we have to ensure that we will
+    // advance.
+    DCHECK_GE(horizontal_step_count_, 1);
+    DCHECK_GE(vertical_step_count_, 1);
+  }
+}
+
+}  // namespace cc