blob: 0aca645c2477fbe561d974a7a42cb53e244f82ea [file] [log] [blame]
// 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>
#include "base/check_op.h"
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