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