OLD | NEW |
(Empty) | |
| 1 // Copyright 2016 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. |
| 4 |
| 5 #include "cc/base/spiral_iterator.h" |
| 6 |
| 7 #include <algorithm> |
| 8 |
| 9 namespace cc { |
| 10 |
| 11 SpiralIterator::SpiralIterator() |
| 12 : around_index_rect_(-1, -1, -1, -1), |
| 13 consider_index_rect_(-1, -1, -1, -1), |
| 14 ignore_index_rect_(-1, -1, -1, -1), |
| 15 index_x_(-1), |
| 16 index_y_(-1) {} |
| 17 |
| 18 SpiralIterator::SpiralIterator(const IndexRect& around_index_rect, |
| 19 const IndexRect& consider_index_rect, |
| 20 const IndexRect& ignore_index_rect) |
| 21 : around_index_rect_(around_index_rect), |
| 22 consider_index_rect_(consider_index_rect), |
| 23 ignore_index_rect_(ignore_index_rect), |
| 24 index_x_(-1), |
| 25 index_y_(-1), |
| 26 direction_(RIGHT), |
| 27 delta_x_(1), |
| 28 delta_y_(0), |
| 29 current_step_(0), |
| 30 horizontal_step_count_(0), |
| 31 vertical_step_count_(0) { |
| 32 vertical_step_count_ = around_index_rect_.num_indices_y(); |
| 33 horizontal_step_count_ = around_index_rect_.num_indices_x(); |
| 34 current_step_ = horizontal_step_count_ - 1; |
| 35 |
| 36 index_x_ = around_index_rect_.right(); |
| 37 index_y_ = around_index_rect_.bottom(); |
| 38 |
| 39 // The current index is the bottom right of the around rect, which is also |
| 40 // ignored. So we have to advance. |
| 41 ++(*this); |
| 42 } |
| 43 |
| 44 SpiralIterator::operator bool() const { |
| 45 return index_x_ != -1 && index_y_ != -1; |
| 46 } |
| 47 |
| 48 SpiralIterator& SpiralIterator::operator++() { |
| 49 int cannot_hit_consider_count = 0; |
| 50 while (cannot_hit_consider_count < 4) { |
| 51 if (needs_direction_switch()) |
| 52 switch_direction(); |
| 53 |
| 54 index_x_ += delta_x_; |
| 55 index_y_ += delta_y_; |
| 56 ++current_step_; |
| 57 |
| 58 if (consider_index_rect_.Contains(index_x_, index_y_)) { |
| 59 cannot_hit_consider_count = 0; |
| 60 |
| 61 if (!ignore_index_rect_.Contains(index_x_, index_y_)) |
| 62 break; |
| 63 |
| 64 // Steps needed to reach the very edge of the ignore rect, while remaining |
| 65 // inside (so that the continue would take us outside). |
| 66 int steps_to_edge = 0; |
| 67 switch (direction_) { |
| 68 case UP: |
| 69 steps_to_edge = index_y_ - ignore_index_rect_.top(); |
| 70 break; |
| 71 case LEFT: |
| 72 steps_to_edge = index_x_ - ignore_index_rect_.left(); |
| 73 break; |
| 74 case DOWN: |
| 75 steps_to_edge = ignore_index_rect_.bottom() - index_y_; |
| 76 break; |
| 77 case RIGHT: |
| 78 steps_to_edge = ignore_index_rect_.right() - index_x_; |
| 79 break; |
| 80 } |
| 81 |
| 82 // We need to switch directions in |max_steps|. |
| 83 int max_steps = current_step_count() - current_step_; |
| 84 |
| 85 int steps_to_take = std::min(steps_to_edge, max_steps); |
| 86 DCHECK_GE(steps_to_take, 0); |
| 87 |
| 88 index_x_ += steps_to_take * delta_x_; |
| 89 index_y_ += steps_to_take * delta_y_; |
| 90 current_step_ += steps_to_take; |
| 91 } else { |
| 92 int max_steps = current_step_count() - current_step_; |
| 93 int steps_to_take = max_steps; |
| 94 bool can_hit_consider_rect = false; |
| 95 switch (direction_) { |
| 96 case UP: |
| 97 if (consider_index_rect_.valid_column(index_x_) && |
| 98 consider_index_rect_.bottom() < index_y_) |
| 99 steps_to_take = index_y_ - consider_index_rect_.bottom() - 1; |
| 100 can_hit_consider_rect |= consider_index_rect_.right() >= index_x_; |
| 101 break; |
| 102 case LEFT: |
| 103 if (consider_index_rect_.valid_row(index_y_) && |
| 104 consider_index_rect_.right() < index_x_) |
| 105 steps_to_take = index_x_ - consider_index_rect_.right() - 1; |
| 106 can_hit_consider_rect |= consider_index_rect_.top() <= index_y_; |
| 107 break; |
| 108 case DOWN: |
| 109 if (consider_index_rect_.valid_column(index_x_) && |
| 110 consider_index_rect_.top() > index_y_) |
| 111 steps_to_take = consider_index_rect_.top() - index_y_ - 1; |
| 112 can_hit_consider_rect |= consider_index_rect_.left() <= index_x_; |
| 113 break; |
| 114 case RIGHT: |
| 115 if (consider_index_rect_.valid_row(index_y_) && |
| 116 consider_index_rect_.left() > index_x_) |
| 117 steps_to_take = consider_index_rect_.left() - index_x_ - 1; |
| 118 can_hit_consider_rect |= consider_index_rect_.bottom() >= index_y_; |
| 119 break; |
| 120 } |
| 121 steps_to_take = std::min(steps_to_take, max_steps); |
| 122 DCHECK_GE(steps_to_take, 0); |
| 123 |
| 124 index_x_ += steps_to_take * delta_x_; |
| 125 index_y_ += steps_to_take * delta_y_; |
| 126 current_step_ += steps_to_take; |
| 127 |
| 128 if (can_hit_consider_rect) |
| 129 cannot_hit_consider_count = 0; |
| 130 else |
| 131 ++cannot_hit_consider_count; |
| 132 } |
| 133 } |
| 134 |
| 135 if (cannot_hit_consider_count >= 4) { |
| 136 index_x_ = -1; |
| 137 index_y_ = -1; |
| 138 } |
| 139 |
| 140 return *this; |
| 141 } |
| 142 |
| 143 bool SpiralIterator::needs_direction_switch() const { |
| 144 return current_step_ >= current_step_count(); |
| 145 } |
| 146 |
| 147 void SpiralIterator::switch_direction() { |
| 148 // Note that delta_x_ and delta_y_ always remain between -1 and 1. |
| 149 int new_delta_x = delta_y_; |
| 150 delta_y_ = -delta_x_; |
| 151 delta_x_ = new_delta_x; |
| 152 |
| 153 current_step_ = 0; |
| 154 direction_ = static_cast<Direction>((direction_ + 1) % 4); |
| 155 |
| 156 if (direction_ == RIGHT || direction_ == LEFT) { |
| 157 ++vertical_step_count_; |
| 158 ++horizontal_step_count_; |
| 159 } |
| 160 } |
| 161 |
| 162 } // namespace cc |
OLD | NEW |