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/pyramid_sequence.h" |
| 6 |
| 7 #include <algorithm> |
| 8 #include <string> |
| 9 |
| 10 #define ENUM_TO_INDEX(x) static_cast<unsigned int>(x) |
| 11 |
| 12 namespace cc { |
| 13 |
| 14 namespace { |
| 15 |
| 16 int LevelsToSkipAlongDirection(int levels) { |
| 17 return levels > 0 ? levels : 0; |
| 18 } |
| 19 |
| 20 int LevelsToSkipCrossDirection(int levels) { |
| 21 return levels >= 0 ? levels + 1 : 0; |
| 22 } |
| 23 |
| 24 // The following function returns default coverage as spiral order {R, T, L, B}. |
| 25 // TODO(prashant.n): Implement precedence in coverage directions instead of |
| 26 // default spiral coverage. http://crbug.com/629052. |
| 27 CoverageDirection* GetCoverageDirectionSequence() { |
| 28 static CoverageDirection |
| 29 spiral_coverage[ENUM_TO_INDEX(CoverageDirection::SIZE)] = { |
| 30 CoverageDirection::RIGHT, CoverageDirection::TOP, |
| 31 CoverageDirection::LEFT, CoverageDirection::BOTTOM}; |
| 32 return spiral_coverage; |
| 33 } |
| 34 |
| 35 int GetPositionForDirection(CoverageDirection* positions, |
| 36 CoverageDirection direction) { |
| 37 for (unsigned int i = 0; i < ENUM_TO_INDEX(CoverageDirection::SIZE); ++i) { |
| 38 if (positions[i] == direction) |
| 39 return i; |
| 40 } |
| 41 |
| 42 NOTREACHED(); |
| 43 return -1; |
| 44 } |
| 45 |
| 46 } // namespace |
| 47 |
| 48 // Interval implementation. |
| 49 Interval::Iterator Interval::Begin() { |
| 50 return Iterator(this); |
| 51 } |
| 52 |
| 53 Interval::ReverseIterator Interval::ReverseBegin() { |
| 54 return ReverseIterator(this); |
| 55 } |
| 56 |
| 57 int Interval::GetSpan() const { |
| 58 return empty_ ? 0 : std::abs(end_ - start_) + 1; |
| 59 } |
| 60 |
| 61 int Interval::GetForwardClampedIndex(int index) const { |
| 62 DCHECK_LE(start_, end_); |
| 63 return (index < start_) ? start_ : ((index > end_) ? end_ : index); |
| 64 } |
| 65 |
| 66 int Interval::GetBackwardClampedIndex(int index) const { |
| 67 DCHECK_GE(start_, end_); |
| 68 return (index > start_) ? start_ : ((index < end_) ? end_ : index); |
| 69 } |
| 70 |
| 71 void Interval::ForwardClampTo(const Interval& other) { |
| 72 DCHECK_LE(start_, end_); |
| 73 DCHECK_LE(other.start_, other.end_); |
| 74 start_ = other.GetForwardClampedIndex(start_); |
| 75 end_ = other.GetForwardClampedIndex(end_); |
| 76 } |
| 77 |
| 78 void Interval::BackwardClampTo(const Interval& other) { |
| 79 DCHECK_GE(start_, end_); |
| 80 DCHECK_GE(other.start_, other.end_); |
| 81 start_ = other.GetBackwardClampedIndex(start_); |
| 82 end_ = other.GetBackwardClampedIndex(end_); |
| 83 } |
| 84 |
| 85 Interval Interval::GetForwardInflatedInterval(int level) const { |
| 86 return Interval(start_ - level, end_ + level); |
| 87 } |
| 88 |
| 89 Interval Interval::GetBackwardInflatedInterval(int level) const { |
| 90 return Interval(start_ + level, end_ - level); |
| 91 } |
| 92 |
| 93 bool Interval::Contains(int index) const { |
| 94 return (start_ <= end_) ? (index >= start_ && index <= end_) |
| 95 : (index <= start_ && index >= end_); |
| 96 } |
| 97 |
| 98 bool Interval::Intersects(const Interval& interval) const { |
| 99 return interval.Contains(start_) || interval.Contains(end_); |
| 100 } |
| 101 |
| 102 void Interval::Intersect(const Interval& interval) { |
| 103 DCHECK(Intersects(interval)); |
| 104 DCHECK((start_ <= end_) && (interval.start_ <= interval.end_) || |
| 105 (start_ >= end_) && (interval.start_ >= interval.end_)); |
| 106 |
| 107 bool forward_direction = (GetSpan() > interval.GetSpan()) |
| 108 ? (start_ <= end_) |
| 109 : (interval.start_ <= interval.end_); |
| 110 |
| 111 if (forward_direction) { |
| 112 start_ = std::max(start_, interval.start_); |
| 113 end_ = std::min(end_, interval.end_); |
| 114 } else { |
| 115 start_ = std::min(start_, interval.start_); |
| 116 end_ = std::max(end_, interval.end_); |
| 117 } |
| 118 } |
| 119 |
| 120 // Interval::IteratorBase implementation. |
| 121 Interval::IteratorBase::IteratorBase() : within_bounds_(false), step_(0) {} |
| 122 |
| 123 Interval::IteratorBase::IteratorBase(Interval* interval) |
| 124 : interval_(interval), within_bounds_(!interval->empty_), step_(0) {} |
| 125 |
| 126 Interval::IteratorBase& Interval::IteratorBase::operator++() { |
| 127 current_index_ += step_; |
| 128 within_bounds_ = IsWithinBounds(); |
| 129 |
| 130 return *this; |
| 131 } |
| 132 |
| 133 // Interval::Iterator implementation. |
| 134 Interval::Iterator::Iterator() {} |
| 135 |
| 136 Interval::Iterator::Iterator(Interval* interval) |
| 137 : Interval::IteratorBase(interval) { |
| 138 step_ = (interval_->start_ <= interval_->end_) ? 1 : -1; |
| 139 current_index_ = interval_->start_; |
| 140 } |
| 141 |
| 142 bool Interval::Iterator::IsWithinBounds() { |
| 143 if (step_ == 1) { |
| 144 DCHECK(current_index_ >= interval_->start_); |
| 145 |
| 146 if (interval_->start_ == interval_->end_ || |
| 147 current_index_ > interval_->end_) |
| 148 return false; |
| 149 |
| 150 return true; |
| 151 } else { |
| 152 DCHECK(current_index_ <= interval_->start_); |
| 153 |
| 154 if (interval_->start_ == interval_->end_ || |
| 155 current_index_ < interval_->end_) |
| 156 return false; |
| 157 |
| 158 return true; |
| 159 } |
| 160 } |
| 161 |
| 162 // Interval::ReverseIterator implementation. |
| 163 Interval::ReverseIterator::ReverseIterator() {} |
| 164 |
| 165 Interval::ReverseIterator::ReverseIterator(Interval* interval) |
| 166 : Interval::IteratorBase(interval) { |
| 167 step_ = (interval_->start_ <= interval_->end_) ? -1 : 1; |
| 168 current_index_ = interval_->end_; |
| 169 } |
| 170 |
| 171 bool Interval::ReverseIterator::IsWithinBounds() { |
| 172 if (step_ == 1) { |
| 173 DCHECK(current_index_ >= interval_->end_); |
| 174 |
| 175 if (interval_->start_ == interval_->end_ || |
| 176 current_index_ > interval_->start_) |
| 177 return false; |
| 178 |
| 179 return true; |
| 180 } else { |
| 181 DCHECK(current_index_ <= interval_->end_); |
| 182 |
| 183 if (interval_->start_ == interval_->end_ || |
| 184 current_index_ < interval_->start_) |
| 185 return false; |
| 186 |
| 187 return true; |
| 188 } |
| 189 } |
| 190 |
| 191 // LinearSequence implementation. |
| 192 LinearSequence::LinearSequence() {} |
| 193 |
| 194 LinearSequence::LinearSequence(bool forward_direction, |
| 195 Interval interval, |
| 196 Interval affinity_interval, |
| 197 Interval inflate_limit) |
| 198 : forward_direction_(forward_direction), |
| 199 interval_(interval), |
| 200 inflate_limit_(inflate_limit), |
| 201 affinity_interval_(affinity_interval), |
| 202 initial_interval_(interval) { |
| 203 TrisectInterval(); |
| 204 } |
| 205 |
| 206 LinearSequence::LinearSequence(const LinearSequence& other) = default; |
| 207 |
| 208 LinearSequence::LinearSequence(LinearSequence&& other) = default; |
| 209 |
| 210 LinearSequence::~LinearSequence() = default; |
| 211 |
| 212 LinearSequence& LinearSequence::operator=(const LinearSequence& other) = |
| 213 default; |
| 214 |
| 215 LinearSequence& LinearSequence::operator=(LinearSequence&& other) = default; |
| 216 |
| 217 LinearSequence::Iterator LinearSequence::Begin() { |
| 218 return Iterator(this); |
| 219 } |
| 220 |
| 221 LinearSequence::ReverseIterator LinearSequence::ReverseBegin() { |
| 222 return ReverseIterator(this); |
| 223 } |
| 224 |
| 225 void LinearSequence::InflateToLevel(int level) { |
| 226 if (forward_direction_) { |
| 227 interval_ = initial_interval_.GetForwardInflatedInterval(level); |
| 228 interval_.ForwardClampTo(inflate_limit_); |
| 229 } else { |
| 230 interval_ = initial_interval_.GetBackwardInflatedInterval(level); |
| 231 interval_.BackwardClampTo(inflate_limit_); |
| 232 } |
| 233 |
| 234 TrisectInterval(); |
| 235 } |
| 236 |
| 237 void LinearSequence::TrisectInterval() { |
| 238 if (interval_.IsEmpty()) { |
| 239 affinity_sub_interval_ = Interval(); |
| 240 before_sub_interval_ = Interval(); |
| 241 after_sub_interval_ = Interval(); |
| 242 return; |
| 243 } |
| 244 |
| 245 if (forward_direction_) { |
| 246 affinity_sub_interval_ = affinity_interval_; |
| 247 if (affinity_sub_interval_.Intersects(interval_)) { |
| 248 affinity_sub_interval_.Intersect(interval_); |
| 249 |
| 250 // Compute before sub-interval. |
| 251 if (affinity_sub_interval_.start() > interval_.start()) |
| 252 before_sub_interval_ = |
| 253 Interval(affinity_sub_interval_.start() - 1, interval_.start()); |
| 254 else if (affinity_sub_interval_.start() == interval_.start()) |
| 255 before_sub_interval_ = Interval(); |
| 256 |
| 257 // Compute after sub-interval. |
| 258 if (affinity_sub_interval_.end() < interval_.end()) |
| 259 after_sub_interval_ = |
| 260 Interval(affinity_sub_interval_.end() + 1, interval_.end()); |
| 261 else if (affinity_sub_interval_.end() == interval_.end()) |
| 262 after_sub_interval_ = Interval(); |
| 263 } else { |
| 264 // The affinity interval is either before or after the |interval_|. |
| 265 if (affinity_sub_interval_.end() < interval_.start()) { |
| 266 before_sub_interval_ = Interval(); |
| 267 after_sub_interval_ = interval_; |
| 268 } else { |
| 269 after_sub_interval_ = Interval(); |
| 270 before_sub_interval_ = Interval(interval_.end(), interval_.start()); |
| 271 } |
| 272 |
| 273 affinity_sub_interval_ = Interval(); |
| 274 } |
| 275 } else { |
| 276 affinity_sub_interval_ = affinity_interval_; |
| 277 if (affinity_sub_interval_.Intersects(interval_)) { |
| 278 affinity_sub_interval_.Intersect(interval_); |
| 279 |
| 280 // Compute before sub-interval. |
| 281 if (affinity_sub_interval_.start() < interval_.start()) |
| 282 before_sub_interval_ = |
| 283 Interval(affinity_sub_interval_.start() + 1, interval_.start()); |
| 284 else if (affinity_sub_interval_.start() == interval_.start()) |
| 285 before_sub_interval_ = Interval(); |
| 286 |
| 287 // Compute after sub-interval. |
| 288 if (affinity_sub_interval_.end() > interval_.end()) |
| 289 after_sub_interval_ = |
| 290 Interval(affinity_sub_interval_.end() - 1, interval_.end()); |
| 291 else if (affinity_sub_interval_.end() == interval_.end()) |
| 292 after_sub_interval_ = Interval(); |
| 293 } else { |
| 294 // The affinity interval is either before or after the |interval_|. |
| 295 if (affinity_sub_interval_.end() > interval_.start()) { |
| 296 before_sub_interval_ = Interval(); |
| 297 after_sub_interval_ = interval_; |
| 298 } else { |
| 299 after_sub_interval_ = Interval(); |
| 300 before_sub_interval_ = Interval(interval_.end(), interval_.start()); |
| 301 } |
| 302 |
| 303 affinity_sub_interval_ = Interval(); |
| 304 } |
| 305 } |
| 306 } |
| 307 |
| 308 // LinearSequence::IteratorBase implementation. |
| 309 LinearSequence::IteratorBase::IteratorBase() : within_bounds_(false) {} |
| 310 |
| 311 LinearSequence::IteratorBase::IteratorBase(LinearSequence* level_sequence) |
| 312 : level_sequence_(level_sequence), within_bounds_(true) {} |
| 313 |
| 314 LinearSequence::IteratorBase::IteratorBase( |
| 315 const LinearSequence::IteratorBase& other) = default; |
| 316 LinearSequence::IteratorBase::IteratorBase( |
| 317 LinearSequence::IteratorBase&& other) = default; |
| 318 |
| 319 LinearSequence::IteratorBase::~IteratorBase() = default; |
| 320 |
| 321 LinearSequence::IteratorBase& LinearSequence::IteratorBase::operator=( |
| 322 const LinearSequence::IteratorBase& other) = default; |
| 323 LinearSequence::IteratorBase& LinearSequence::IteratorBase::operator=( |
| 324 LinearSequence::IteratorBase&& other) = default; |
| 325 |
| 326 LinearSequence::IteratorBase& LinearSequence::IteratorBase::operator++() { |
| 327 if (within_bounds_) { |
| 328 ++(*(sub_interval_iterators_[ENUM_TO_INDEX( |
| 329 current_sub_interval_iterator_)])); |
| 330 current_sub_interval_iterator_ = GetCurrentSubIntervalIteratorType(); |
| 331 current_index_ = |
| 332 sub_interval_iterators_[ENUM_TO_INDEX(current_sub_interval_iterator_)] |
| 333 ->index(); |
| 334 within_bounds_ = IsWithinBounds(); |
| 335 } |
| 336 return *this; |
| 337 } |
| 338 |
| 339 // LinearSequence::Iterator implementation. |
| 340 LinearSequence::Iterator::Iterator() {} |
| 341 |
| 342 LinearSequence::Iterator::Iterator(LinearSequence* level_sequence) |
| 343 : LinearSequence::IteratorBase(level_sequence), |
| 344 affinity_sub_interval_iterator_( |
| 345 level_sequence_->affinity_sub_interval_.Begin()), |
| 346 before_sub_interval_iterator_( |
| 347 level_sequence_->before_sub_interval_.Begin()), |
| 348 after_sub_interval_iterator_( |
| 349 level_sequence_->after_sub_interval_.Begin()), |
| 350 before_first_(true) { |
| 351 Setup(); |
| 352 |
| 353 current_sub_interval_iterator_ = GetCurrentSubIntervalIteratorType(); |
| 354 current_index_ = |
| 355 sub_interval_iterators_[ENUM_TO_INDEX(current_sub_interval_iterator_)] |
| 356 ->index(); |
| 357 } |
| 358 |
| 359 LinearSequence::Iterator::Iterator(const LinearSequence::Iterator& other) |
| 360 : IteratorBase(other), |
| 361 affinity_sub_interval_iterator_(other.affinity_sub_interval_iterator_), |
| 362 before_sub_interval_iterator_(other.before_sub_interval_iterator_), |
| 363 after_sub_interval_iterator_(other.after_sub_interval_iterator_), |
| 364 before_first_(other.before_first_) { |
| 365 Setup(); |
| 366 } |
| 367 |
| 368 LinearSequence::Iterator::Iterator(LinearSequence::Iterator&& other) |
| 369 : IteratorBase(std::move(other)), |
| 370 affinity_sub_interval_iterator_( |
| 371 std::move(other.affinity_sub_interval_iterator_)), |
| 372 before_sub_interval_iterator_( |
| 373 std::move(other.before_sub_interval_iterator_)), |
| 374 after_sub_interval_iterator_( |
| 375 std::move(other.after_sub_interval_iterator_)), |
| 376 before_first_(other.before_first_) { |
| 377 Setup(); |
| 378 } |
| 379 |
| 380 LinearSequence::Iterator::~Iterator() = default; |
| 381 |
| 382 LinearSequence::Iterator& LinearSequence::Iterator::operator=( |
| 383 const LinearSequence::Iterator& other) { |
| 384 IteratorBase::operator=(other); |
| 385 affinity_sub_interval_iterator_ = other.affinity_sub_interval_iterator_; |
| 386 before_sub_interval_iterator_ = other.before_sub_interval_iterator_; |
| 387 after_sub_interval_iterator_ = other.after_sub_interval_iterator_; |
| 388 before_first_ = other.before_first_; |
| 389 |
| 390 Setup(); |
| 391 |
| 392 return *this; |
| 393 } |
| 394 LinearSequence::Iterator& LinearSequence::Iterator::operator=( |
| 395 LinearSequence::Iterator&& other) { |
| 396 IteratorBase::operator=(std::move(other)); |
| 397 affinity_sub_interval_iterator_ = |
| 398 std::move(other.affinity_sub_interval_iterator_); |
| 399 before_sub_interval_iterator_ = |
| 400 std::move(other.before_sub_interval_iterator_); |
| 401 after_sub_interval_iterator_ = std::move(other.after_sub_interval_iterator_); |
| 402 before_first_ = other.before_first_; |
| 403 |
| 404 Setup(); |
| 405 |
| 406 return *this; |
| 407 } |
| 408 |
| 409 void LinearSequence::Iterator::Setup() { |
| 410 sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFFINITY)] = |
| 411 &affinity_sub_interval_iterator_; |
| 412 sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::BEFORE)] = |
| 413 &before_sub_interval_iterator_; |
| 414 sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFTER)] = |
| 415 &after_sub_interval_iterator_; |
| 416 } |
| 417 |
| 418 LinearSequence::IteratorBase::SubIntervalIteratorType |
| 419 LinearSequence::Iterator::GetCurrentSubIntervalIteratorType() { |
| 420 if (affinity_sub_interval_iterator_) |
| 421 return SubIntervalIteratorType::AFFINITY; |
| 422 |
| 423 if (before_first_) { |
| 424 before_first_ = false; |
| 425 if (before_sub_interval_iterator_) |
| 426 return SubIntervalIteratorType::BEFORE; |
| 427 |
| 428 return SubIntervalIteratorType::AFTER; |
| 429 } else { |
| 430 before_first_ = true; |
| 431 if (after_sub_interval_iterator_) |
| 432 return SubIntervalIteratorType::AFTER; |
| 433 |
| 434 return SubIntervalIteratorType::BEFORE; |
| 435 } |
| 436 } |
| 437 |
| 438 bool LinearSequence::Iterator::IsWithinBounds() { |
| 439 return affinity_sub_interval_iterator_ || before_sub_interval_iterator_ || |
| 440 after_sub_interval_iterator_; |
| 441 } |
| 442 |
| 443 // LinearSequence::ReverseIterator implementation. |
| 444 LinearSequence::ReverseIterator::ReverseIterator() {} |
| 445 |
| 446 LinearSequence::ReverseIterator::ReverseIterator(LinearSequence* level_sequence) |
| 447 : LinearSequence::IteratorBase(level_sequence), |
| 448 affinity_sub_interval_reverse_iterator_( |
| 449 level_sequence_->affinity_sub_interval_.ReverseBegin()), |
| 450 before_sub_interval_reverse_iterator_( |
| 451 level_sequence_->before_sub_interval_.ReverseBegin()), |
| 452 after_sub_interval_reverse_iterator_( |
| 453 level_sequence_->after_sub_interval_.ReverseBegin()), |
| 454 after_first_(true), |
| 455 before_sub_interval_span_( |
| 456 level_sequence_->before_sub_interval_.GetSpan()), |
| 457 after_sub_interval_span_(level_sequence_->after_sub_interval_.GetSpan()) { |
| 458 Setup(); |
| 459 |
| 460 current_sub_interval_iterator_ = GetCurrentSubIntervalIteratorType(); |
| 461 current_index_ = |
| 462 sub_interval_iterators_[ENUM_TO_INDEX(current_sub_interval_iterator_)] |
| 463 ->index(); |
| 464 } |
| 465 |
| 466 LinearSequence::ReverseIterator::ReverseIterator( |
| 467 const LinearSequence::ReverseIterator& other) |
| 468 : IteratorBase(other), |
| 469 affinity_sub_interval_reverse_iterator_( |
| 470 other.affinity_sub_interval_reverse_iterator_), |
| 471 before_sub_interval_reverse_iterator_( |
| 472 other.before_sub_interval_reverse_iterator_), |
| 473 after_sub_interval_reverse_iterator_( |
| 474 other.after_sub_interval_reverse_iterator_), |
| 475 after_first_(other.after_first_), |
| 476 before_sub_interval_span_(other.before_sub_interval_span_), |
| 477 after_sub_interval_span_(other.after_sub_interval_span_) { |
| 478 Setup(); |
| 479 } |
| 480 |
| 481 LinearSequence::ReverseIterator::ReverseIterator( |
| 482 LinearSequence::ReverseIterator&& other) |
| 483 : IteratorBase(std::move(other)), |
| 484 affinity_sub_interval_reverse_iterator_( |
| 485 std::move(other.affinity_sub_interval_reverse_iterator_)), |
| 486 before_sub_interval_reverse_iterator_( |
| 487 std::move(other.before_sub_interval_reverse_iterator_)), |
| 488 after_sub_interval_reverse_iterator_( |
| 489 std::move(other.after_sub_interval_reverse_iterator_)), |
| 490 after_first_(other.after_first_), |
| 491 before_sub_interval_span_(other.before_sub_interval_span_), |
| 492 after_sub_interval_span_(other.after_sub_interval_span_) { |
| 493 Setup(); |
| 494 } |
| 495 |
| 496 LinearSequence::ReverseIterator::~ReverseIterator() = default; |
| 497 |
| 498 LinearSequence::ReverseIterator& LinearSequence::ReverseIterator::operator=( |
| 499 const LinearSequence::ReverseIterator& other) { |
| 500 IteratorBase::operator=(other); |
| 501 affinity_sub_interval_reverse_iterator_ = |
| 502 other.affinity_sub_interval_reverse_iterator_; |
| 503 before_sub_interval_reverse_iterator_ = |
| 504 other.before_sub_interval_reverse_iterator_; |
| 505 after_sub_interval_reverse_iterator_ = |
| 506 other.after_sub_interval_reverse_iterator_; |
| 507 after_first_ = other.after_first_; |
| 508 before_sub_interval_span_ = other.before_sub_interval_span_; |
| 509 after_sub_interval_span_ = other.after_sub_interval_span_; |
| 510 |
| 511 Setup(); |
| 512 |
| 513 return *this; |
| 514 } |
| 515 LinearSequence::ReverseIterator& LinearSequence::ReverseIterator::operator=( |
| 516 LinearSequence::ReverseIterator&& other) { |
| 517 IteratorBase::operator=(std::move(other)); |
| 518 affinity_sub_interval_reverse_iterator_ = |
| 519 std::move(other.affinity_sub_interval_reverse_iterator_); |
| 520 before_sub_interval_reverse_iterator_ = |
| 521 std::move(other.before_sub_interval_reverse_iterator_); |
| 522 after_sub_interval_reverse_iterator_ = |
| 523 std::move(other.after_sub_interval_reverse_iterator_); |
| 524 after_first_ = other.after_first_; |
| 525 before_sub_interval_span_ = other.before_sub_interval_span_; |
| 526 after_sub_interval_span_ = other.after_sub_interval_span_; |
| 527 |
| 528 Setup(); |
| 529 |
| 530 return *this; |
| 531 } |
| 532 |
| 533 void LinearSequence::ReverseIterator::Setup() { |
| 534 sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFFINITY)] = |
| 535 &affinity_sub_interval_reverse_iterator_; |
| 536 sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::BEFORE)] = |
| 537 &before_sub_interval_reverse_iterator_; |
| 538 sub_interval_iterators_[ENUM_TO_INDEX(SubIntervalIteratorType::AFTER)] = |
| 539 &after_sub_interval_reverse_iterator_; |
| 540 } |
| 541 |
| 542 LinearSequence::IteratorBase::SubIntervalIteratorType |
| 543 LinearSequence::ReverseIterator::GetCurrentSubIntervalIteratorType() { |
| 544 if (before_sub_interval_span_ > after_sub_interval_span_) { |
| 545 --before_sub_interval_span_; |
| 546 return SubIntervalIteratorType::BEFORE; |
| 547 } else if (before_sub_interval_span_ < after_sub_interval_span_) { |
| 548 --after_sub_interval_span_; |
| 549 return SubIntervalIteratorType::AFTER; |
| 550 } else { |
| 551 if (after_first_) { |
| 552 after_first_ = false; |
| 553 if (after_sub_interval_reverse_iterator_) |
| 554 return SubIntervalIteratorType::AFTER; |
| 555 |
| 556 if (before_sub_interval_reverse_iterator_) |
| 557 return SubIntervalIteratorType::BEFORE; |
| 558 } else { |
| 559 after_first_ = true; |
| 560 if (before_sub_interval_reverse_iterator_) |
| 561 return SubIntervalIteratorType::BEFORE; |
| 562 |
| 563 if (after_sub_interval_reverse_iterator_) |
| 564 return SubIntervalIteratorType::AFTER; |
| 565 } |
| 566 } |
| 567 |
| 568 return SubIntervalIteratorType::AFFINITY; |
| 569 } |
| 570 |
| 571 bool LinearSequence::ReverseIterator::IsWithinBounds() { |
| 572 return affinity_sub_interval_reverse_iterator_ || |
| 573 before_sub_interval_reverse_iterator_ || |
| 574 after_sub_interval_reverse_iterator_; |
| 575 } |
| 576 |
| 577 // TriangularSequence implementation. |
| 578 TriangularSequence::TriangularSequence() |
| 579 : coverage_direction_(CoverageDirection::NONE), |
| 580 traversal_sequence_(true, Interval(), Interval(), Interval()), |
| 581 level_interval_(), |
| 582 should_swap_index_representation_(false), |
| 583 levels_to_skip_(0), |
| 584 distance_(0) {} |
| 585 |
| 586 TriangularSequence::TriangularSequence(CoverageDirection coverage_direction, |
| 587 LinearSequence&& traversal_sequence, |
| 588 Interval&& level_interval, |
| 589 bool should_swap_index_representation, |
| 590 int levels_to_skip, |
| 591 int distance) |
| 592 : coverage_direction_(coverage_direction), |
| 593 traversal_sequence_(std::move(traversal_sequence)), |
| 594 level_interval_(std::move(level_interval)), |
| 595 should_swap_index_representation_(should_swap_index_representation), |
| 596 levels_to_skip_(levels_to_skip), |
| 597 distance_(distance) {} |
| 598 |
| 599 TriangularSequence::TriangularSequence(const TriangularSequence& other) = |
| 600 default; |
| 601 |
| 602 TriangularSequence::TriangularSequence(TriangularSequence&& other) = default; |
| 603 |
| 604 TriangularSequence::~TriangularSequence() {} |
| 605 |
| 606 TriangularSequence& TriangularSequence::operator=( |
| 607 const TriangularSequence& other) = default; |
| 608 |
| 609 TriangularSequence& TriangularSequence::operator=(TriangularSequence&& other) = |
| 610 default; |
| 611 |
| 612 TriangularSequence::Iterator TriangularSequence::Begin() { |
| 613 return Iterator(this); |
| 614 } |
| 615 |
| 616 TriangularSequence::ReverseIterator TriangularSequence::ReverseBegin() { |
| 617 return ReverseIterator(this); |
| 618 } |
| 619 |
| 620 // TriangularSequence::IteratorBase implementation. |
| 621 TriangularSequence::IteratorBase::IteratorBase() {} |
| 622 |
| 623 TriangularSequence::IteratorBase::IteratorBase( |
| 624 TriangularSequence* triangular_sequence) |
| 625 : should_swap_index_representation_( |
| 626 triangular_sequence->should_swap_index_representation_) { |
| 627 DCHECK_NE(triangular_sequence->coverage_direction_, CoverageDirection::NONE); |
| 628 Interval::Iterator level_interval_it = |
| 629 triangular_sequence->level_interval_.Begin(); |
| 630 traversal_sequence_ = triangular_sequence->traversal_sequence_; |
| 631 int span = triangular_sequence->level_interval_.GetSpan(); |
| 632 DCHECK_GE(span, triangular_sequence->levels_to_skip_); |
| 633 |
| 634 // Skip |levels_to_skip| levels in level interval. |
| 635 for (int i = 0; i < triangular_sequence->levels_to_skip_; ++i) |
| 636 ++level_interval_it; |
| 637 |
| 638 for (int i = triangular_sequence->levels_to_skip_; i < span; ++i) { |
| 639 level_distances_.push_back(LevelDistance( |
| 640 i, level_interval_it.index(), triangular_sequence->distance_ * i)); |
| 641 ++level_interval_it; |
| 642 } |
| 643 } |
| 644 |
| 645 TriangularSequence::IteratorBase::IteratorBase( |
| 646 const TriangularSequence::IteratorBase& other) = default; |
| 647 TriangularSequence::IteratorBase::IteratorBase( |
| 648 TriangularSequence::IteratorBase&& other) = default; |
| 649 |
| 650 TriangularSequence::IteratorBase::~IteratorBase() = default; |
| 651 |
| 652 TriangularSequence::IteratorBase& TriangularSequence::IteratorBase::operator=( |
| 653 const TriangularSequence::IteratorBase& other) = default; |
| 654 TriangularSequence::IteratorBase& TriangularSequence::IteratorBase::operator=( |
| 655 TriangularSequence::IteratorBase&& other) = default; |
| 656 |
| 657 TriangularSequence::IteratorBase& TriangularSequence::IteratorBase:: |
| 658 operator++() { |
| 659 Advance(); |
| 660 UpdateCurrent(); |
| 661 |
| 662 return *this; |
| 663 } |
| 664 |
| 665 // TriangularSequence::Iterator implementation. |
| 666 TriangularSequence::Iterator::Iterator() {} |
| 667 |
| 668 TriangularSequence::Iterator::Iterator(TriangularSequence* triangular_sequence) |
| 669 : TriangularSequence::IteratorBase(triangular_sequence) { |
| 670 UpdateCurrent(); |
| 671 } |
| 672 |
| 673 int TriangularSequence::Iterator::GetNextDistance() const { |
| 674 DCHECK(*this); |
| 675 return level_distances_.front().distance; |
| 676 } |
| 677 |
| 678 void TriangularSequence::Iterator::Advance() { |
| 679 if (!*this) |
| 680 return; |
| 681 |
| 682 level_distances_.erase(level_distances_.begin()); |
| 683 } |
| 684 |
| 685 void TriangularSequence::Iterator::UpdateCurrent() { |
| 686 if (!*this) |
| 687 return; |
| 688 |
| 689 current_level_index_ = level_distances_.front().level_index; |
| 690 traversal_sequence_.InflateToLevel(level_distances_.front().interval_level); |
| 691 } |
| 692 |
| 693 // TriangularSequence::ReverseIterator implementation. |
| 694 TriangularSequence::ReverseIterator::ReverseIterator() {} |
| 695 |
| 696 TriangularSequence::ReverseIterator::ReverseIterator( |
| 697 TriangularSequence* triangular_sequence) |
| 698 : TriangularSequence::IteratorBase(triangular_sequence) { |
| 699 UpdateCurrent(); |
| 700 } |
| 701 |
| 702 int TriangularSequence::ReverseIterator::GetNextDistance() const { |
| 703 DCHECK(!level_distances_.empty()); |
| 704 return level_distances_.back().distance; |
| 705 } |
| 706 |
| 707 void TriangularSequence::ReverseIterator::Advance() { |
| 708 if (!*this) |
| 709 return; |
| 710 |
| 711 level_distances_.erase(level_distances_.end() - 1); |
| 712 } |
| 713 |
| 714 void TriangularSequence::ReverseIterator::UpdateCurrent() { |
| 715 if (!*this) |
| 716 return; |
| 717 |
| 718 current_level_index_ = level_distances_.back().level_index; |
| 719 traversal_sequence_.InflateToLevel(level_distances_.back().interval_level); |
| 720 } |
| 721 |
| 722 // PyramidSequence implementation. |
| 723 PyramidSequence::PyramidSequence() |
| 724 : consider_index_rect_(-1, -1, -1, -1), |
| 725 ignore_index_rect_(-1, -1, -1, -1) {} |
| 726 |
| 727 PyramidSequence::PyramidSequence(const IndexRect& around_index_rect, |
| 728 const IndexRect& consider_index_rect, |
| 729 const IndexRect& ignore_index_rect, |
| 730 int width, |
| 731 int height) |
| 732 : consider_index_rect_(consider_index_rect), |
| 733 ignore_index_rect_(ignore_index_rect) { |
| 734 // Compute center_index_rect and if it is valid (i.e. |around_index_rect| is |
| 735 // really around some index_rect) and both |consider_index_rect| and |
| 736 // |ignore_index_rect| are valid, then proceed, otherwise keep the pyramid |
| 737 // sequence empty. |
| 738 IndexRect center_index_rect(around_index_rect); |
| 739 center_index_rect.Inset(1, 1, 1, 1); |
| 740 if (!center_index_rect.is_valid() || !consider_index_rect.is_valid() || |
| 741 !ignore_index_rect.is_valid()) |
| 742 return; |
| 743 |
| 744 // Compute the max possible levels along all directions. |
| 745 int left_levels = around_index_rect.left() - consider_index_rect_.left() + 1; |
| 746 int right_levels = |
| 747 consider_index_rect_.right() - around_index_rect.right() + 1; |
| 748 int top_levels = around_index_rect.top() - consider_index_rect_.top() + 1; |
| 749 int bottom_levels = |
| 750 consider_index_rect_.bottom() - around_index_rect.bottom() + 1; |
| 751 |
| 752 // When center_index_rect and consider_index_rect are non-intersecting, then |
| 753 // we need to compute the levels to skip for avoiding traversal of levels |
| 754 // which do not fall in consider_index_rect. The pyramid sequence adds |
| 755 // diagonal indices to left and right directions and no diagonal indices for |
| 756 // top and bottom directions, so while considering skip levels for top/bottom, |
| 757 // we need to consider maximum of levels to skip "along" the top/bottom |
| 758 // directions and levels to skip "cross" left/right directions and for |
| 759 // considering skip levels for left/right, we need to consider maximum of |
| 760 // levels to skip "along" the left/right directions and levels to skip "along" |
| 761 // top/bottom directions. |
| 762 // Compute the levels to skip along and cross all directions. |
| 763 int skip_levels_along_left = |
| 764 around_index_rect.left() - consider_index_rect_.right(); |
| 765 int skip_levels_along_right = |
| 766 consider_index_rect_.left() - around_index_rect.right(); |
| 767 int skip_levels_along_top = |
| 768 around_index_rect.top() - consider_index_rect_.bottom(); |
| 769 int skip_levels_along_bottom = |
| 770 consider_index_rect_.top() - around_index_rect.bottom(); |
| 771 int skip_levels_cross_left = |
| 772 LevelsToSkipCrossDirection(skip_levels_along_left); |
| 773 int skip_levels_cross_right = |
| 774 LevelsToSkipCrossDirection(skip_levels_along_right); |
| 775 skip_levels_along_left = LevelsToSkipAlongDirection(skip_levels_along_left); |
| 776 skip_levels_along_right = LevelsToSkipAlongDirection(skip_levels_along_right); |
| 777 skip_levels_along_top = LevelsToSkipAlongDirection(skip_levels_along_top); |
| 778 skip_levels_along_bottom = |
| 779 LevelsToSkipAlongDirection(skip_levels_along_bottom); |
| 780 |
| 781 DCHECK(triangular_sequences_.empty()); |
| 782 triangular_sequences_.resize(ENUM_TO_INDEX(CoverageDirection::SIZE)); |
| 783 CoverageDirection* positions = GetCoverageDirectionSequence(); |
| 784 DCHECK(positions); |
| 785 |
| 786 // Add triangular sequences for all directions. |
| 787 // RIGHT sequence. |
| 788 if (right_levels > 0) { |
| 789 int start = around_index_rect.bottom(); |
| 790 int end = around_index_rect.top(); |
| 791 int skip_levels = |
| 792 std::max(skip_levels_along_right, |
| 793 std::max(skip_levels_along_bottom, skip_levels_along_top)); |
| 794 if (right_levels > skip_levels) { |
| 795 EmplaceAt( |
| 796 GetPositionForDirection(positions, CoverageDirection::RIGHT), |
| 797 TriangularSequence( |
| 798 CoverageDirection::RIGHT, |
| 799 LinearSequence( |
| 800 false, Interval(start, end), |
| 801 Interval(center_index_rect.bottom(), center_index_rect.top()), |
| 802 Interval(consider_index_rect_.bottom(), |
| 803 consider_index_rect_.top())), |
| 804 Interval(around_index_rect.right(), consider_index_rect_.right()), |
| 805 true, skip_levels, width)); |
| 806 } |
| 807 } |
| 808 |
| 809 // TOP sequence. |
| 810 if (top_levels > 0) { |
| 811 int start = around_index_rect.right() - 1; |
| 812 int end = around_index_rect.left() + 1; |
| 813 int skip_levels = |
| 814 std::max(skip_levels_along_top, |
| 815 std::max(skip_levels_cross_right, skip_levels_cross_left)); |
| 816 if (top_levels > skip_levels) { |
| 817 EmplaceAt( |
| 818 GetPositionForDirection(positions, CoverageDirection::TOP), |
| 819 TriangularSequence( |
| 820 CoverageDirection::TOP, |
| 821 LinearSequence( |
| 822 false, Interval(start, end), |
| 823 Interval(center_index_rect.right(), center_index_rect.left()), |
| 824 Interval(consider_index_rect_.right(), |
| 825 consider_index_rect_.left())), |
| 826 Interval(around_index_rect.top(), consider_index_rect_.top()), |
| 827 false, skip_levels, height)); |
| 828 } |
| 829 } |
| 830 |
| 831 // LEFT sequence. |
| 832 if (left_levels > 0) { |
| 833 int start = around_index_rect.top(); |
| 834 int end = around_index_rect.bottom(); |
| 835 int skip_levels = |
| 836 std::max(skip_levels_along_left, |
| 837 std::max(skip_levels_along_top, skip_levels_along_bottom)); |
| 838 if (left_levels > skip_levels) { |
| 839 EmplaceAt( |
| 840 GetPositionForDirection(positions, CoverageDirection::LEFT), |
| 841 TriangularSequence( |
| 842 CoverageDirection::LEFT, |
| 843 LinearSequence( |
| 844 true, Interval(start, end), |
| 845 Interval(center_index_rect.top(), center_index_rect.bottom()), |
| 846 Interval(consider_index_rect_.top(), |
| 847 consider_index_rect_.bottom())), |
| 848 Interval(around_index_rect.left(), consider_index_rect_.left()), |
| 849 true, skip_levels, width)); |
| 850 } |
| 851 } |
| 852 |
| 853 // BOTTOM sequence. |
| 854 if (bottom_levels > 0) { |
| 855 int start = around_index_rect.left() + 1; |
| 856 int end = around_index_rect.right() - 1; |
| 857 int skip_levels = |
| 858 std::max(skip_levels_along_bottom, |
| 859 std::max(skip_levels_cross_left, skip_levels_cross_right)); |
| 860 if (bottom_levels > skip_levels) { |
| 861 EmplaceAt(GetPositionForDirection(positions, CoverageDirection::BOTTOM), |
| 862 TriangularSequence( |
| 863 CoverageDirection::BOTTOM, |
| 864 LinearSequence(true, Interval(start, end), |
| 865 Interval(center_index_rect.left(), |
| 866 center_index_rect.right()), |
| 867 Interval(consider_index_rect_.left(), |
| 868 consider_index_rect_.right())), |
| 869 Interval(around_index_rect.bottom(), |
| 870 consider_index_rect_.bottom()), |
| 871 false, skip_levels, height)); |
| 872 } |
| 873 } |
| 874 |
| 875 // Remove dummy triangular sequences. |
| 876 triangular_sequences_.erase( |
| 877 std::remove_if(triangular_sequences_.begin(), triangular_sequences_.end(), |
| 878 [](const TriangularSequence& triangular_sequence) { |
| 879 return triangular_sequence.coverage_direction() == |
| 880 CoverageDirection::NONE; |
| 881 }), |
| 882 triangular_sequences_.end()); |
| 883 } |
| 884 |
| 885 PyramidSequence::PyramidSequence(const PyramidSequence& other) = default; |
| 886 |
| 887 PyramidSequence::PyramidSequence(PyramidSequence&& other) = default; |
| 888 |
| 889 PyramidSequence::~PyramidSequence() = default; |
| 890 |
| 891 PyramidSequence& PyramidSequence::operator=(const PyramidSequence& other) = |
| 892 default; |
| 893 |
| 894 PyramidSequence& PyramidSequence::operator=(PyramidSequence&& other) = default; |
| 895 |
| 896 PyramidSequence::Iterator PyramidSequence::Begin() { |
| 897 return Iterator(this); |
| 898 } |
| 899 |
| 900 PyramidSequence::ReverseIterator PyramidSequence::ReverseBegin() { |
| 901 return ReverseIterator(this); |
| 902 } |
| 903 |
| 904 void PyramidSequence::EmplaceAt(int position, |
| 905 TriangularSequence&& triangular_sequence) { |
| 906 TriangularSequence::Vector::iterator it = triangular_sequences_.begin(); |
| 907 std::advance(it, position); |
| 908 triangular_sequences_.emplace(it, std::move(triangular_sequence)); |
| 909 TriangularSequence::Vector::iterator erase_it = triangular_sequences_.begin(); |
| 910 std::advance(erase_it, position + 1); |
| 911 triangular_sequences_.erase(erase_it); |
| 912 } |
| 913 |
| 914 // PyramidSequence::IteratorBase implementation. |
| 915 PyramidSequence::IteratorBase::IteratorBase() |
| 916 : consider_index_rect_(-1, -1, -1, -1), |
| 917 ignore_index_rect_(-1, -1, -1, -1), |
| 918 current_triangular_sequence_it_(nullptr) {} |
| 919 |
| 920 PyramidSequence::IteratorBase::IteratorBase( |
| 921 const IndexRect& consider_index_rect, |
| 922 const IndexRect& ignore_index_rect) |
| 923 : consider_index_rect_(consider_index_rect), |
| 924 ignore_index_rect_(ignore_index_rect), |
| 925 current_triangular_sequence_it_(nullptr) {} |
| 926 |
| 927 PyramidSequence::IteratorBase::IteratorBase( |
| 928 const PyramidSequence::IteratorBase& other) = default; |
| 929 |
| 930 PyramidSequence::IteratorBase::IteratorBase( |
| 931 PyramidSequence::IteratorBase&& other) = default; |
| 932 |
| 933 PyramidSequence::IteratorBase::~IteratorBase() = default; |
| 934 |
| 935 PyramidSequence::IteratorBase& PyramidSequence::IteratorBase::operator=( |
| 936 const PyramidSequence::IteratorBase& other) = default; |
| 937 |
| 938 PyramidSequence::IteratorBase& PyramidSequence::IteratorBase::operator=( |
| 939 PyramidSequence::IteratorBase&& other) = default; |
| 940 |
| 941 PyramidSequence::IteratorBase::operator bool() const { |
| 942 return current_triangular_sequence_it_ && !IsEmpty(); |
| 943 } |
| 944 |
| 945 PyramidSequence::IteratorBase& PyramidSequence::IteratorBase::operator++() { |
| 946 Advance(); |
| 947 UpdateCurrent(); |
| 948 |
| 949 return *this; |
| 950 } |
| 951 |
| 952 // PyramidSequence::Iterator implementation. |
| 953 PyramidSequence::Iterator::Iterator() {} |
| 954 |
| 955 PyramidSequence::Iterator::Iterator(PyramidSequence* pyramid_sequence) |
| 956 : PyramidSequence::IteratorBase(pyramid_sequence->consider_index_rect_, |
| 957 pyramid_sequence->ignore_index_rect_) { |
| 958 for (TriangularSequence::Vector::iterator it = |
| 959 pyramid_sequence->triangular_sequences_.begin(); |
| 960 it != pyramid_sequence->triangular_sequences_.end(); ++it) { |
| 961 DCHECK(it->coverage_direction() != CoverageDirection::NONE); |
| 962 triangular_sequence_iterators_.emplace_back(it->Begin()); |
| 963 } |
| 964 |
| 965 Setup(); |
| 966 } |
| 967 |
| 968 PyramidSequence::Iterator::Iterator(const PyramidSequence::Iterator& other) |
| 969 : IteratorBase(other), |
| 970 triangular_sequence_iterators_(other.triangular_sequence_iterators_) { |
| 971 Setup(); |
| 972 } |
| 973 |
| 974 PyramidSequence::Iterator::Iterator(PyramidSequence::Iterator&& other) |
| 975 : IteratorBase(std::move(other)), |
| 976 triangular_sequence_iterators_( |
| 977 std::move(other.triangular_sequence_iterators_)) { |
| 978 Setup(); |
| 979 } |
| 980 |
| 981 PyramidSequence::Iterator::~Iterator() = default; |
| 982 |
| 983 PyramidSequence::Iterator& PyramidSequence::Iterator::operator=( |
| 984 const PyramidSequence::Iterator& other) { |
| 985 IteratorBase::operator=(other); |
| 986 triangular_sequence_iterators_ = other.triangular_sequence_iterators_; |
| 987 |
| 988 Setup(); |
| 989 |
| 990 return *this; |
| 991 } |
| 992 |
| 993 PyramidSequence::Iterator& PyramidSequence::Iterator::operator=( |
| 994 PyramidSequence::Iterator&& other) { |
| 995 IteratorBase::operator=(std::move(other)); |
| 996 triangular_sequence_iterators_ = |
| 997 std::move(other.triangular_sequence_iterators_); |
| 998 |
| 999 Setup(); |
| 1000 |
| 1001 return *this; |
| 1002 } |
| 1003 |
| 1004 void PyramidSequence::Iterator::Setup() { |
| 1005 current_triangular_sequence_it_ = GetNextTriangularSequenceIterator(); |
| 1006 if (current_triangular_sequence_it_) { |
| 1007 if (*current_triangular_sequence_it_) { |
| 1008 current_traversal_sequence_iterator_ = |
| 1009 current_triangular_sequence_it_->traversal_sequence()->Begin(); |
| 1010 } |
| 1011 |
| 1012 UpdateCurrent(); |
| 1013 } |
| 1014 } |
| 1015 |
| 1016 bool PyramidSequence::Iterator::IsEmpty() const { |
| 1017 return triangular_sequence_iterators_.empty(); |
| 1018 } |
| 1019 |
| 1020 void PyramidSequence::Iterator::Advance() { |
| 1021 if (!*this) |
| 1022 return; |
| 1023 |
| 1024 ++current_traversal_sequence_iterator_; |
| 1025 if (!current_traversal_sequence_iterator_) { |
| 1026 ++(*current_triangular_sequence_it_); |
| 1027 current_triangular_sequence_it_ = GetNextTriangularSequenceIterator(); |
| 1028 if (current_triangular_sequence_it_) { |
| 1029 current_traversal_sequence_iterator_ = |
| 1030 current_triangular_sequence_it_->traversal_sequence()->Begin(); |
| 1031 } |
| 1032 } |
| 1033 } |
| 1034 |
| 1035 void PyramidSequence::Iterator::UpdateCurrent() { |
| 1036 while (*this) { |
| 1037 if (current_traversal_sequence_iterator_) { |
| 1038 if (current_triangular_sequence_it_->is_index_representation_swapped()) { |
| 1039 index_x_ = current_triangular_sequence_it_->level_index(); |
| 1040 index_y_ = current_traversal_sequence_iterator_.index(); |
| 1041 } else { |
| 1042 index_x_ = current_traversal_sequence_iterator_.index(); |
| 1043 index_y_ = current_triangular_sequence_it_->level_index(); |
| 1044 } |
| 1045 |
| 1046 if (consider_index_rect_.Contains(index_x_, index_y_) && |
| 1047 !ignore_index_rect_.Contains(index_x_, index_y_)) |
| 1048 break; |
| 1049 } |
| 1050 |
| 1051 Advance(); |
| 1052 } |
| 1053 } |
| 1054 |
| 1055 TriangularSequence::IteratorBase* |
| 1056 PyramidSequence::Iterator::GetNextTriangularSequenceIterator() { |
| 1057 // Remove traversed TriangularSequence::Iterator(s). |
| 1058 triangular_sequence_iterators_.erase( |
| 1059 std::remove_if( |
| 1060 triangular_sequence_iterators_.begin(), |
| 1061 triangular_sequence_iterators_.end(), |
| 1062 [](const TriangularSequence::Iterator& it) { return !it; }), |
| 1063 triangular_sequence_iterators_.end()); |
| 1064 |
| 1065 if (triangular_sequence_iterators_.empty()) |
| 1066 return nullptr; |
| 1067 |
| 1068 std::vector<TriangularSequence::Iterator>::iterator min_distance_it = |
| 1069 triangular_sequence_iterators_.begin(); |
| 1070 |
| 1071 for (std::vector<TriangularSequence::Iterator>::iterator it = |
| 1072 triangular_sequence_iterators_.begin(); |
| 1073 it != triangular_sequence_iterators_.end(); ++it) { |
| 1074 int distance = it->GetNextDistance(); |
| 1075 if (distance == 0) { |
| 1076 min_distance_it = it; |
| 1077 break; |
| 1078 } |
| 1079 |
| 1080 if (min_distance_it->GetNextDistance() > distance) |
| 1081 min_distance_it = it; |
| 1082 } |
| 1083 |
| 1084 return &(*min_distance_it); |
| 1085 } |
| 1086 |
| 1087 // PyramidSequence::ReverseIterator implementation. |
| 1088 PyramidSequence::ReverseIterator::ReverseIterator() {} |
| 1089 |
| 1090 PyramidSequence::ReverseIterator::ReverseIterator( |
| 1091 PyramidSequence* pyramid_sequence) |
| 1092 : PyramidSequence::IteratorBase(pyramid_sequence->consider_index_rect_, |
| 1093 pyramid_sequence->ignore_index_rect_) { |
| 1094 for (TriangularSequence::Vector::iterator it = |
| 1095 pyramid_sequence->triangular_sequences_.begin(); |
| 1096 it != pyramid_sequence->triangular_sequences_.end(); ++it) { |
| 1097 triangular_sequence_reverse_iterators_.emplace_back(it->ReverseBegin()); |
| 1098 } |
| 1099 |
| 1100 Setup(); |
| 1101 } |
| 1102 |
| 1103 PyramidSequence::ReverseIterator::ReverseIterator( |
| 1104 const PyramidSequence::ReverseIterator& other) |
| 1105 : IteratorBase(other), |
| 1106 triangular_sequence_reverse_iterators_( |
| 1107 other.triangular_sequence_reverse_iterators_) { |
| 1108 Setup(); |
| 1109 } |
| 1110 |
| 1111 PyramidSequence::ReverseIterator::ReverseIterator( |
| 1112 PyramidSequence::ReverseIterator&& other) |
| 1113 : IteratorBase(std::move(other)), |
| 1114 triangular_sequence_reverse_iterators_( |
| 1115 std::move(other.triangular_sequence_reverse_iterators_)) { |
| 1116 Setup(); |
| 1117 } |
| 1118 |
| 1119 PyramidSequence::ReverseIterator::~ReverseIterator() = default; |
| 1120 |
| 1121 PyramidSequence::ReverseIterator& PyramidSequence::ReverseIterator::operator=( |
| 1122 const PyramidSequence::ReverseIterator& other) { |
| 1123 IteratorBase::operator=(other); |
| 1124 triangular_sequence_reverse_iterators_ = |
| 1125 other.triangular_sequence_reverse_iterators_; |
| 1126 Setup(); |
| 1127 return *this; |
| 1128 } |
| 1129 |
| 1130 PyramidSequence::ReverseIterator& PyramidSequence::ReverseIterator::operator=( |
| 1131 PyramidSequence::ReverseIterator&& other) { |
| 1132 IteratorBase::operator=(std::move(other)); |
| 1133 triangular_sequence_reverse_iterators_ = |
| 1134 std::move(other.triangular_sequence_reverse_iterators_); |
| 1135 Setup(); |
| 1136 return *this; |
| 1137 } |
| 1138 |
| 1139 void PyramidSequence::ReverseIterator::Setup() { |
| 1140 current_triangular_sequence_it_ = GetNextTriangularSequenceReverseIterator(); |
| 1141 if (current_triangular_sequence_it_) { |
| 1142 if (*current_triangular_sequence_it_) { |
| 1143 current_traversal_sequence_reverse_iterator_ = |
| 1144 current_triangular_sequence_it_->traversal_sequence()->ReverseBegin(); |
| 1145 } |
| 1146 UpdateCurrent(); |
| 1147 } |
| 1148 } |
| 1149 |
| 1150 bool PyramidSequence::ReverseIterator::IsEmpty() const { |
| 1151 return triangular_sequence_reverse_iterators_.empty(); |
| 1152 } |
| 1153 |
| 1154 void PyramidSequence::ReverseIterator::Advance() { |
| 1155 if (!*this) |
| 1156 return; |
| 1157 |
| 1158 ++current_traversal_sequence_reverse_iterator_; |
| 1159 if (!current_traversal_sequence_reverse_iterator_) { |
| 1160 ++(*current_triangular_sequence_it_); |
| 1161 current_triangular_sequence_it_ = |
| 1162 GetNextTriangularSequenceReverseIterator(); |
| 1163 if (current_triangular_sequence_it_) { |
| 1164 current_traversal_sequence_reverse_iterator_ = |
| 1165 current_triangular_sequence_it_->traversal_sequence()->ReverseBegin(); |
| 1166 } |
| 1167 } |
| 1168 } |
| 1169 |
| 1170 void PyramidSequence::ReverseIterator::UpdateCurrent() { |
| 1171 while (*this) { |
| 1172 if (current_traversal_sequence_reverse_iterator_) { |
| 1173 if (current_triangular_sequence_it_->is_index_representation_swapped()) { |
| 1174 index_x_ = current_triangular_sequence_it_->level_index(); |
| 1175 index_y_ = current_traversal_sequence_reverse_iterator_.index(); |
| 1176 } else { |
| 1177 index_x_ = current_traversal_sequence_reverse_iterator_.index(); |
| 1178 index_y_ = current_triangular_sequence_it_->level_index(); |
| 1179 } |
| 1180 |
| 1181 if (consider_index_rect_.Contains(index_x_, index_y_) && |
| 1182 !ignore_index_rect_.Contains(index_x_, index_y_)) |
| 1183 break; |
| 1184 } |
| 1185 |
| 1186 Advance(); |
| 1187 } |
| 1188 } |
| 1189 |
| 1190 TriangularSequence::IteratorBase* |
| 1191 PyramidSequence::ReverseIterator::GetNextTriangularSequenceReverseIterator() { |
| 1192 // Remove traversed TriangularSequence::ReverseIterator(s). |
| 1193 triangular_sequence_reverse_iterators_.erase( |
| 1194 std::remove_if( |
| 1195 triangular_sequence_reverse_iterators_.begin(), |
| 1196 triangular_sequence_reverse_iterators_.end(), |
| 1197 [](const TriangularSequence::ReverseIterator& it) { return !it; }), |
| 1198 triangular_sequence_reverse_iterators_.end()); |
| 1199 |
| 1200 if (triangular_sequence_reverse_iterators_.empty()) |
| 1201 return nullptr; |
| 1202 |
| 1203 std::vector<TriangularSequence::ReverseIterator>::reverse_iterator |
| 1204 max_distance_it = triangular_sequence_reverse_iterators_.rbegin(); |
| 1205 |
| 1206 for (std::vector<TriangularSequence::ReverseIterator>::reverse_iterator it = |
| 1207 triangular_sequence_reverse_iterators_.rbegin(); |
| 1208 it != triangular_sequence_reverse_iterators_.rend(); ++it) { |
| 1209 int distance = it->GetNextDistance(); |
| 1210 |
| 1211 if (max_distance_it->GetNextDistance() < distance) |
| 1212 max_distance_it = it; |
| 1213 } |
| 1214 |
| 1215 return &(*max_distance_it); |
| 1216 } |
| 1217 |
| 1218 } // namespace cc |
OLD | NEW |