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 #ifndef CC_BASE_PYRAMID_SEQUENCE_H_ |
| 6 #define CC_BASE_PYRAMID_SEQUENCE_H_ |
| 7 |
| 8 #include <vector> |
| 9 |
| 10 #include "base/logging.h" |
| 11 #include "cc/base/cc_export.h" |
| 12 #include "cc/base/index_rect.h" |
| 13 |
| 14 namespace cc { |
| 15 |
| 16 // The pyramid sequence covers following 4 directions while iterating, where R |
| 17 // is right, T is top, L is left and B is bottom. |
| 18 // T |
| 19 // L * R |
| 20 // B |
| 21 enum class CoverageDirection : int { |
| 22 NONE = -1, |
| 23 RIGHT = 0, |
| 24 TOP, |
| 25 LEFT, |
| 26 BOTTOM, |
| 27 SIZE |
| 28 }; |
| 29 |
| 30 // This class provides iterating mechanism for numbers between defined bounds. |
| 31 // e.g. For interval having bounds 3 as start and 6 as end, represented as |
| 32 // [3, 6], the interval returns 3, 4, 5, 6 sequence for Iterator traversal and |
| 33 // returns 6, 5, 4, 3 for ReverseIterator traversal. |
| 34 // |
| 35 // start end |
| 36 // | | |
| 37 // V V |
| 38 // ┌───┬───┬───┬───┐ |
| 39 // │ 3 │ 4 │ 5 │ 6 │ |
| 40 // └───┴───┴───┴───┘ |
| 41 class CC_EXPORT Interval { |
| 42 public: |
| 43 class Iterator; |
| 44 class ReverseIterator; |
| 45 |
| 46 Interval() : empty_(true) {} |
| 47 Interval(int start, int end) : empty_(false), start_(start), end_(end) {} |
| 48 |
| 49 Iterator Begin(); |
| 50 ReverseIterator ReverseBegin(); |
| 51 |
| 52 // Return the bounds of the interval. |
| 53 int start() const { return start_; } |
| 54 int end() const { return end_; } |
| 55 |
| 56 // Returns true if interval is empty. Empty interval does not return any |
| 57 // index on traversing. |
| 58 bool IsEmpty() const { return empty_; } |
| 59 |
| 60 // Returns the distance between |start_| and |end_| which includes both |
| 61 // |start_| and |end_|. |
| 62 int GetSpan() const; |
| 63 |
| 64 // Return clamped indices for the given indices. |
| 65 int GetForwardClampedIndex(int index) const; |
| 66 int GetBackwardClampedIndex(int index) const; |
| 67 |
| 68 // Clamp this interval to the given interval. For these functions, interval |
| 69 // and other interval to which this interval is to be clammped should be in |
| 70 // the same direction, i.e. both intervals should have either |
| 71 // |start_| <= |end_| or |start_| >= |end_|. |
| 72 void ForwardClampTo(const Interval& other); |
| 73 void BackwardClampTo(const Interval& other); |
| 74 |
| 75 // Return the inflated intervals for the given |level|. |
| 76 Interval GetForwardInflatedInterval(int level) const; |
| 77 Interval GetBackwardInflatedInterval(int level) const; |
| 78 |
| 79 // Returns true if interval contains the given index. |
| 80 bool Contains(int index) const; |
| 81 |
| 82 // For these functions, interval and other interval to which first one is to |
| 83 // be intersected should be in the same direction, i.e. both intervals should |
| 84 // have |start_| <= |end_| or |start_| >= |end_|. |
| 85 bool Intersects(const Interval& interval) const; |
| 86 void Intersect(const Interval& interval); |
| 87 |
| 88 // Iterators. |
| 89 class IteratorBase { |
| 90 public: |
| 91 IteratorBase(); |
| 92 |
| 93 operator bool() const { return within_bounds_; } |
| 94 IteratorBase& operator++(); |
| 95 int index() { return current_index_; } |
| 96 |
| 97 protected: |
| 98 explicit IteratorBase(Interval* interval); |
| 99 |
| 100 virtual bool IsWithinBounds() = 0; |
| 101 |
| 102 Interval* interval_; |
| 103 bool within_bounds_; |
| 104 int step_; |
| 105 int current_index_; |
| 106 }; |
| 107 |
| 108 class Iterator : public IteratorBase { |
| 109 public: |
| 110 Iterator(); |
| 111 |
| 112 private: |
| 113 explicit Iterator(Interval* interval); |
| 114 |
| 115 bool IsWithinBounds() override; |
| 116 |
| 117 friend class Interval; |
| 118 }; |
| 119 |
| 120 class ReverseIterator : public IteratorBase { |
| 121 public: |
| 122 ReverseIterator(); |
| 123 |
| 124 private: |
| 125 explicit ReverseIterator(Interval* interval); |
| 126 |
| 127 bool IsWithinBounds() override; |
| 128 |
| 129 friend class Interval; |
| 130 }; |
| 131 |
| 132 private: |
| 133 bool empty_; |
| 134 int start_; |
| 135 int end_; |
| 136 }; |
| 137 |
| 138 // This class provides affinity based interating mechanism for the given |
| 139 // |interval| [start, end] with functionality of inflating the |interval|. |
| 140 // The interval inflation means expanding the start and end by n steps forward |
| 141 // or backward, based on |forward_direction| argument provided. Suppose the |
| 142 // LinearSequence has interval [3, 3] i.e. start = 3 and end = 3, the interval |
| 143 // inflated by 1 step in forward direction would be [2, 4] and that of in |
| 144 // backward direction would be [4, 2]. |
| 145 // The affinity based traversing means portion of |interval| that intersects |
| 146 // with |affinity_interval| is traversed before remaining two portions of |
| 147 // |interval|. Internally the |interval| is split up into three sub-intervals |
| 148 // before traversing as |affinity_sub_interval_|, |before_sub_interval_| and |
| 149 // |after_sub_interval_|. These sub-intervals are traversed instead of directly |
| 150 // traversing |interval|. First |affinity_sub_interval_| is traversed fully, |
| 151 // then remaining two sub-intervals are traversed in alternative fashion. |
| 152 // |
| 153 // e.g. Suppose LinearSequence has interval [0, 9] and affinity interval |
| 154 // [4, 6], then the interval is splitted into three sub-intervals viz. [4, 6], |
| 155 // [3, 0], [7, 9]. |
| 156 // |
| 157 // affinity_sub_interval |
| 158 // ┌─────^─────┐ |
| 159 // ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ |
| 160 // │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ |
| 161 // └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘ |
| 162 // └───────v───────┘ └─────v─────┘ |
| 163 // before_sub_interval after_sub_interval |
| 164 // |
| 165 // On traversal, Iterator returns the sequence as 4, 5, 6, 3, 7, 2, 8, 1, 9, 0 |
| 166 // and RerverseIterator returns the sequence as 0, 9, 1, 8, 2, 7, 3, 6, 5, 4. |
| 167 class CC_EXPORT LinearSequence { |
| 168 public: |
| 169 class Iterator; |
| 170 class ReverseIterator; |
| 171 |
| 172 LinearSequence(); |
| 173 // The |interval| is used for actual traversal. The |affinity_interval| is |
| 174 // used for defining affinity in the |interval|. While traversing portion of |
| 175 // |interval| which intersects |affinity_interval| is traversed before |
| 176 // remaining portions of the interval. The |inflate_limit| is used to clamp |
| 177 // the |interval|, when it is inflated to any given |level|. |
| 178 LinearSequence(bool forward_direction, |
| 179 Interval interval, |
| 180 Interval affinity_interval, |
| 181 Interval inflate_limit); |
| 182 LinearSequence(const LinearSequence& other); |
| 183 LinearSequence(LinearSequence&& other); |
| 184 ~LinearSequence(); |
| 185 |
| 186 LinearSequence& operator=(const LinearSequence& other); |
| 187 LinearSequence& operator=(LinearSequence&& other); |
| 188 |
| 189 Iterator Begin(); |
| 190 ReverseIterator ReverseBegin(); |
| 191 |
| 192 // This function inflates the original |interval| to the given |level|, |
| 193 // where level >= 0. |
| 194 void InflateToLevel(int level); |
| 195 |
| 196 // Iterators. |
| 197 class IteratorBase { |
| 198 public: |
| 199 IteratorBase(); |
| 200 IteratorBase(const IteratorBase& other); |
| 201 IteratorBase(IteratorBase&& other); |
| 202 ~IteratorBase(); |
| 203 |
| 204 IteratorBase& operator=(const IteratorBase& other); |
| 205 IteratorBase& operator=(IteratorBase&& other); |
| 206 |
| 207 operator bool() const { return within_bounds_; } |
| 208 IteratorBase& operator++(); |
| 209 int index() { return current_index_; } |
| 210 |
| 211 protected: |
| 212 enum class SubIntervalIteratorType : unsigned int { |
| 213 AFFINITY, |
| 214 BEFORE, |
| 215 AFTER |
| 216 }; |
| 217 |
| 218 explicit IteratorBase(LinearSequence* level_sequence); |
| 219 |
| 220 virtual void Setup() = 0; |
| 221 virtual SubIntervalIteratorType GetCurrentSubIntervalIteratorType() = 0; |
| 222 virtual bool IsWithinBounds() = 0; |
| 223 |
| 224 LinearSequence* level_sequence_; |
| 225 bool within_bounds_; |
| 226 int current_index_; |
| 227 Interval::IteratorBase* sub_interval_iterators_[3]; |
| 228 SubIntervalIteratorType current_sub_interval_iterator_; |
| 229 }; |
| 230 |
| 231 class Iterator : public IteratorBase { |
| 232 public: |
| 233 Iterator(); |
| 234 Iterator(const Iterator& other); |
| 235 Iterator(Iterator&& other); |
| 236 ~Iterator(); |
| 237 |
| 238 Iterator& operator=(const Iterator& other); |
| 239 Iterator& operator=(Iterator&& other); |
| 240 |
| 241 private: |
| 242 explicit Iterator(LinearSequence* level_sequence); |
| 243 |
| 244 void Setup() override; |
| 245 SubIntervalIteratorType GetCurrentSubIntervalIteratorType() override; |
| 246 bool IsWithinBounds() override; |
| 247 |
| 248 Interval::Iterator affinity_sub_interval_iterator_; |
| 249 Interval::Iterator before_sub_interval_iterator_; |
| 250 Interval::Iterator after_sub_interval_iterator_; |
| 251 bool before_first_; |
| 252 |
| 253 friend class LinearSequence; |
| 254 }; |
| 255 |
| 256 class ReverseIterator : public IteratorBase { |
| 257 public: |
| 258 ReverseIterator(); |
| 259 ReverseIterator(const ReverseIterator& other); |
| 260 ReverseIterator(ReverseIterator&& other); |
| 261 ~ReverseIterator(); |
| 262 |
| 263 ReverseIterator& operator=(const ReverseIterator& other); |
| 264 ReverseIterator& operator=(ReverseIterator&& other); |
| 265 |
| 266 private: |
| 267 explicit ReverseIterator(LinearSequence* level_sequence); |
| 268 |
| 269 void Setup() override; |
| 270 SubIntervalIteratorType GetCurrentSubIntervalIteratorType() override; |
| 271 bool IsWithinBounds() override; |
| 272 |
| 273 Interval::ReverseIterator affinity_sub_interval_reverse_iterator_; |
| 274 Interval::ReverseIterator before_sub_interval_reverse_iterator_; |
| 275 Interval::ReverseIterator after_sub_interval_reverse_iterator_; |
| 276 bool after_first_; |
| 277 int before_sub_interval_span_; |
| 278 int after_sub_interval_span_; |
| 279 |
| 280 friend class LinearSequence; |
| 281 }; |
| 282 |
| 283 private: |
| 284 void TrisectInterval(); |
| 285 |
| 286 bool forward_direction_; |
| 287 Interval interval_; |
| 288 Interval inflate_limit_; |
| 289 Interval affinity_interval_; |
| 290 |
| 291 Interval initial_interval_; |
| 292 |
| 293 // The |interval_| is split up into following sub-intervals such a way that |
| 294 // they are non-intersecting, adjacent and union of these three sub-intervals |
| 295 // is |interval_|. |
| 296 Interval affinity_sub_interval_; |
| 297 Interval before_sub_interval_; |
| 298 Interval after_sub_interval_; |
| 299 }; |
| 300 |
| 301 // This class implements the 2D sequence (x, y) which uses LinearSequence and |
| 302 // Interval to represent the co-ordinates. The linear sequence |
| 303 // |traversal_sequence| is used for traversing the actual sequence cross the |
| 304 // direction and |level_interval| is used for computing the number of levels in |
| 305 // the |traversal_sequence|. The interval in |traversal_sequence| can be |
| 306 // inflated max to the levels given by |level_interval|. |
| 307 // This class uses LevelDistance structure to represent the distance associated |
| 308 // with the level. The first level has distance 0, to represent the minimum |
| 309 // distance for the origin level, and increments by the step of |distance| |
| 310 // given in LevelDistance for every level. Suppose there are 5 levels and |
| 311 // distance is 10, then the levels would have distances as 0, 10, 20, 30, 40. |
| 312 // The distances are stored in the sorted order in vector, so that the distance |
| 313 // at front is minimum, while the distance at back is maximum. The layout of |
| 314 // the level distance vector for the example would be (0, 0), (1, 10), (2, 20), |
| 315 // (3, 30), (4, 40). |
| 316 // |
| 317 // e.g. If traversal sequence has interval [3, 4], number of levels is 3 and |
| 318 // distance is 10, then the Iterator would give following data on traversal. |
| 319 // |
| 320 // traversal_sequence level_index |
| 321 // [3, 4] 0 |
| 322 // [2, 5] 1 |
| 323 // [1, 6] 2 |
| 324 // |
| 325 // The order of iteration for ReverseIterator would be as given below. |
| 326 // |
| 327 // traversal_sequence level index |
| 328 // [1, 6] 2 |
| 329 // [2, 5] 1 |
| 330 // [3, 4] 0 |
| 331 // |
| 332 // The indices (x, y) for the iterator are as given below. |
| 333 // |
| 334 // (3, 0), (4, 0) (level 1) |
| 335 // (2, 1), (3, 1), (4, 1), (5, 1), (level 2) |
| 336 // (1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 2) (level 3) |
| 337 // |
| 338 // In a way the original interval in |traversal_sequence| and inflated |
| 339 // intervals form triangular geometry in co-ordinate space as given below, |
| 340 // hence the name TriangularSequence. |
| 341 // |
| 342 // x 0 1 2 3 4 5 6 |
| 343 // y ┌───┬───┬───┬───┬───┬───┬───┐ |
| 344 // 0 │ │ │ │ 3 │ 4 │ │ │ (level 1, distance 0) |
| 345 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 346 // 1 │ │ │ 2 │ 3 │ 4 │ 5 │ │ (level 2, distance 10) |
| 347 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 348 // 2 │ │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ (level 3, distance 20) |
| 349 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 350 // 3 │ │ │ │ │ │ │ │ |
| 351 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 352 // 4 │ │ │ │ │ │ │ │ |
| 353 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 354 // 5 │ │ │ │ │ │ │ │ |
| 355 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 356 // 6 │ │ │ │ │ │ │ │ |
| 357 // └───┴───┴───┴───┴───┴───┴───┘ |
| 358 class CC_EXPORT TriangularSequence { |
| 359 public: |
| 360 class Iterator; |
| 361 class ReverseIterator; |
| 362 |
| 363 TriangularSequence(); |
| 364 // The |traversal_sequence| defines the sequence for traversal and |
| 365 // |level_interval| defines the number of levels for |traversal_sequence|. |
| 366 // If |should_swap_index_representation| is false, then the indices in |
| 367 // |traversal_sequence| represent the x indices and level indices in |
| 368 // |level_interval| represent the y indices, otherwise vice-versa. The |
| 369 // |levels_to_skip| defines the number of levels which should be skipped to |
| 370 // avoid unnecessary traversing. Check PyramidSequence::PyramidSequence() for |
| 371 // more details on level skipping. The |distance| defines the length for the |
| 372 // index. |
| 373 TriangularSequence(CoverageDirection coverage_direction, |
| 374 LinearSequence&& traversal_sequence, |
| 375 Interval&& level_interval, |
| 376 bool should_swap_index_representation, |
| 377 int levels_to_skip, |
| 378 int distance); |
| 379 TriangularSequence(const TriangularSequence& other); |
| 380 TriangularSequence(TriangularSequence&& other); |
| 381 ~TriangularSequence(); |
| 382 |
| 383 TriangularSequence& operator=(const TriangularSequence& other); |
| 384 TriangularSequence& operator=(TriangularSequence&& other); |
| 385 |
| 386 Iterator Begin(); |
| 387 ReverseIterator ReverseBegin(); |
| 388 |
| 389 CoverageDirection coverage_direction() const { return coverage_direction_; } |
| 390 |
| 391 struct LevelDistance { |
| 392 LevelDistance(int interval_level, int level_index, int distance) |
| 393 : interval_level(interval_level), |
| 394 level_index(level_index), |
| 395 distance(distance) {} |
| 396 |
| 397 int interval_level; |
| 398 int level_index; |
| 399 int distance; |
| 400 }; |
| 401 |
| 402 class IteratorBase { |
| 403 public: |
| 404 IteratorBase(); |
| 405 IteratorBase(const IteratorBase& other); |
| 406 IteratorBase(IteratorBase&& other); |
| 407 ~IteratorBase(); |
| 408 |
| 409 IteratorBase& operator=(const IteratorBase& other); |
| 410 IteratorBase& operator=(IteratorBase&& other); |
| 411 |
| 412 operator bool() const { return !level_distances_.empty(); } |
| 413 IteratorBase& operator++(); |
| 414 LinearSequence* traversal_sequence() { |
| 415 DCHECK(*this); |
| 416 return &traversal_sequence_; |
| 417 } |
| 418 int level_index() { |
| 419 DCHECK(*this); |
| 420 return current_level_index_; |
| 421 } |
| 422 |
| 423 bool is_index_representation_swapped() const { |
| 424 return should_swap_index_representation_; |
| 425 } |
| 426 |
| 427 virtual int GetNextDistance() const = 0; |
| 428 |
| 429 protected: |
| 430 explicit IteratorBase(TriangularSequence* triangular_sequence); |
| 431 |
| 432 virtual void Advance() = 0; |
| 433 virtual void UpdateCurrent() = 0; |
| 434 |
| 435 LinearSequence traversal_sequence_; |
| 436 bool should_swap_index_representation_; |
| 437 std::vector<LevelDistance> level_distances_; |
| 438 int current_level_index_; |
| 439 }; |
| 440 |
| 441 class Iterator : public IteratorBase { |
| 442 public: |
| 443 Iterator(); |
| 444 |
| 445 // Returns next minimum distance. |
| 446 int GetNextDistance() const override; |
| 447 |
| 448 private: |
| 449 explicit Iterator(TriangularSequence* triangular_sequence); |
| 450 |
| 451 void Advance() override; |
| 452 void UpdateCurrent() override; |
| 453 |
| 454 friend class TriangularSequence; |
| 455 }; |
| 456 |
| 457 class ReverseIterator : public IteratorBase { |
| 458 public: |
| 459 ReverseIterator(); |
| 460 |
| 461 // Returns next maximum distance. |
| 462 int GetNextDistance() const override; |
| 463 |
| 464 private: |
| 465 explicit ReverseIterator(TriangularSequence* triangular_sequence); |
| 466 |
| 467 void Advance() override; |
| 468 void UpdateCurrent() override; |
| 469 |
| 470 friend class TriangularSequence; |
| 471 }; |
| 472 |
| 473 typedef std::vector<TriangularSequence> Vector; |
| 474 typedef std::vector<TriangularSequence::IteratorBase> IteratorVector; |
| 475 |
| 476 private: |
| 477 CoverageDirection coverage_direction_; |
| 478 LinearSequence traversal_sequence_; |
| 479 Interval level_interval_; |
| 480 bool should_swap_index_representation_; |
| 481 int levels_to_skip_; |
| 482 int distance_; |
| 483 }; |
| 484 |
| 485 // The pyramid sequence consists of 4 triangular sequences, one for each of |
| 486 // the directions considered counter-clockwise or clockwise. The ideal pyramid |
| 487 // sequence is as given below where it has all triangular sequences in 4 |
| 488 // directions. |
| 489 // |
| 490 // ┌───┬───┬───┬───┬───┬───┬───┐ |
| 491 // │ L │ T │ T │ T │ T │ T │ R │ |
| 492 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 493 // │ L │ L │ T │ T │ T │ R │ R │ |
| 494 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 495 // │ L │ L │ L │ T │ R │ R │ R │ |
| 496 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 497 // │ L │ L │ L │ * │ R │ R │ R │ |
| 498 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 499 // │ L │ L │ L │ B │ R │ R │ R │ |
| 500 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 501 // │ L │ L │ B │ B │ B │ R │ R │ |
| 502 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 503 // │ L │ B │ B │ B │ B │ B │ R │ |
| 504 // └───┴───┴───┴───┴───┴───┴───┘ |
| 505 // |
| 506 // The triangular sequences for the above pyramid sequence are shown below. |
| 507 // * represents the center. |
| 508 // |
| 509 // (T = top) |
| 510 // ┌───┬───┬───┬───┬───┐ |
| 511 // │ T │ T │ T │ T │ T │ |
| 512 // ┌───┐ └───┼───┼───┼───┼───┘ ┌───┐ |
| 513 // │ L │ │ T │ T │ T │ │ R │ |
| 514 // ├───┼───┐ └───┼───┼───┘ ┌───┼───┤ |
| 515 // │ L │ L │ │ T │ │ R │ R │ |
| 516 // ├───┼───┼───┐ └───┘ ┌───┼───┼───┤ |
| 517 // │ L │ L │ L │ │ R │ R │ R │ |
| 518 // ├───┼───┼───┤ ┌───┐ ├───┼───┼───┤ |
| 519 // (L = left) │ L │ L │ L │ │ * │ │ R │ R │ R │ (R = right) |
| 520 // ├───┼───┼───┤ └───┘ ├───┼───┼───┤ |
| 521 // │ L │ L │ L │ │ R │ R │ R │ |
| 522 // ├───┼───┼───┘ ┌───┐ └───┼───┼───┤ |
| 523 // │ L │ L │ │ B │ │ R │ R │ |
| 524 // ├───┼───┘ ┌───┼───┼───┐ └───┼───┤ |
| 525 // │ L │ │ B │ B │ B │ │ R │ |
| 526 // └───┘ ┌───┼───┼───┼───┼───┐ └───┘ |
| 527 // │ B │ B │ B │ B │ B │ |
| 528 // └───┴───┴───┴───┴───┘ |
| 529 // (B = bottom) |
| 530 // |
| 531 // This sequence iterates over all the underlined triangular sequences level by |
| 532 // level in increasing or decreasing order of distances. The increasing order of |
| 533 // distances can be iterated using Iterator, while the decreasing order of |
| 534 // distances can be iterated using ReverseIterator. The default coverage for |
| 535 // internal triangular sequences is R, T, L, B forming spiral order. |
| 536 // The iteration sequence generated by Iterator is as given below. |
| 537 // (Iteration is considered counter-clockwise.) |
| 538 // |
| 539 // x 0 1 2 3 4 5 6 |
| 540 // y ┌───┬───┬───┬───┬───┬───┬───┐ |
| 541 // 0 │ 42│ 36│ 34│ 32│ 33│ 35│ 31│ |
| 542 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 543 // 1 │ 40│ 20│ 16│ 14│ 15│ 13│ 29│ |
| 544 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 545 // 2 │ 38│ 18│ 6│ 4│ 3│ 11│ 27│ |
| 546 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 547 // 3 │ 37│ 17│ 5│ *│ 1│ 9│ 25│ |
| 548 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 549 // 4 │ 39│ 19│ 7│ 8│ 2│ 10│ 26│ |
| 550 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 551 // 5 │ 41│ 21│ 23│ 22│ 24│ 12│ 28│ |
| 552 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 553 // 6 │ 43│ 47│ 45│ 44│ 46│ 48│ 30│ |
| 554 // └───┴───┴───┴───┴───┴───┴───┘ |
| 555 // |
| 556 // The iteration sequence generated by ReverseIterator is as given below. |
| 557 // (Iteration is considered clockwise.) |
| 558 // |
| 559 // x 0 1 2 3 4 5 6 |
| 560 // y ┌───┬───┬───┬───┬───┬───┬───┐ |
| 561 // 0 │ 7│ 13│ 15│ 17│ 16│ 14│ 18│ |
| 562 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 563 // 1 │ 9│ 29│ 33│ 35│ 34│ 36│ 20│ |
| 564 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 565 // 2 │ 11│ 31│ 43│ 45│ 46│ 38│ 22│ |
| 566 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 567 // 3 │ 12│ 32│ 44│ *│ 48│ 40│ 24│ |
| 568 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 569 // 4 │ 10│ 30│ 42│ 41│ 47│ 39│ 23│ |
| 570 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 571 // 5 │ 8│ 28│ 26│ 27│ 25│ 37│ 21│ |
| 572 // ├───┼───┼───┼───┼───┼───┼───┤ |
| 573 // 6 │ 6│ 2│ 4│ 5│ 3│ 1│ 19│ |
| 574 // └───┴───┴───┴───┴───┴───┴───┘ |
| 575 class CC_EXPORT PyramidSequence { |
| 576 public: |
| 577 class Iterator; |
| 578 class ReverseIterator; |
| 579 |
| 580 PyramidSequence(); |
| 581 // The |around_index_rect| is the index rect computed around some index rect, |
| 582 // called as center index rect. In the above example, center index rect is |
| 583 // (3, 3, 3, 3), so around index rect for it is (2, 4, 2, 4). |
| 584 // The |consider_index_rect| is used to limit the coverage and the |
| 585 // |ignore_index_rect| is used to ignore the indices from coverage. For above |
| 586 // example consider index rect is (0, 6, 0, 6) and ignore index rect is |
| 587 // (-1, -1, -1, -1). |
| 588 // The width and height specify the width and height of the single index. This |
| 589 // is used for traversing indices based on their distances from center index |
| 590 // rect. |
| 591 PyramidSequence(const IndexRect& around_index_rect, |
| 592 const IndexRect& consider_index_rect, |
| 593 const IndexRect& ignore_index_rect, |
| 594 int width, |
| 595 int height); |
| 596 PyramidSequence(const PyramidSequence& other); |
| 597 PyramidSequence(PyramidSequence&& other); |
| 598 virtual ~PyramidSequence(); |
| 599 |
| 600 PyramidSequence& operator=(const PyramidSequence& other); |
| 601 PyramidSequence& operator=(PyramidSequence&& other); |
| 602 |
| 603 Iterator Begin(); |
| 604 ReverseIterator ReverseBegin(); |
| 605 |
| 606 class IteratorBase { |
| 607 public: |
| 608 IteratorBase(); |
| 609 IteratorBase(const IteratorBase& other); |
| 610 IteratorBase(IteratorBase&& other); |
| 611 ~IteratorBase(); |
| 612 |
| 613 IteratorBase& operator=(const IteratorBase& other); |
| 614 IteratorBase& operator=(IteratorBase&& other); |
| 615 |
| 616 operator bool() const; |
| 617 IteratorBase& operator++(); |
| 618 int index_x() const { return index_x_; } |
| 619 int index_y() const { return index_y_; } |
| 620 |
| 621 protected: |
| 622 explicit IteratorBase(const IndexRect& consider_index_rect, |
| 623 const IndexRect& ignore_index_rect); |
| 624 |
| 625 virtual void Setup() = 0; |
| 626 virtual bool IsEmpty() const = 0; |
| 627 virtual void Advance() = 0; |
| 628 virtual void UpdateCurrent() = 0; |
| 629 |
| 630 IndexRect consider_index_rect_; |
| 631 IndexRect ignore_index_rect_; |
| 632 int index_x_; |
| 633 int index_y_; |
| 634 |
| 635 TriangularSequence::IteratorBase* current_triangular_sequence_it_; |
| 636 }; |
| 637 |
| 638 class Iterator : public IteratorBase { |
| 639 public: |
| 640 Iterator(); |
| 641 Iterator(const Iterator& other); |
| 642 Iterator(Iterator&& other); |
| 643 ~Iterator(); |
| 644 |
| 645 Iterator& operator=(const Iterator& other); |
| 646 Iterator& operator=(Iterator&& other); |
| 647 |
| 648 private: |
| 649 explicit Iterator(PyramidSequence* pyramid_sequence); |
| 650 |
| 651 void Setup() override; |
| 652 bool IsEmpty() const override; |
| 653 void Advance() override; |
| 654 void UpdateCurrent() override; |
| 655 |
| 656 TriangularSequence::IteratorBase* GetNextTriangularSequenceIterator(); |
| 657 |
| 658 LinearSequence::Iterator current_traversal_sequence_iterator_; |
| 659 std::vector<TriangularSequence::Iterator> triangular_sequence_iterators_; |
| 660 |
| 661 friend class PyramidSequence; |
| 662 }; |
| 663 |
| 664 class ReverseIterator : public IteratorBase { |
| 665 public: |
| 666 ReverseIterator(); |
| 667 ReverseIterator(const ReverseIterator& other); |
| 668 ReverseIterator(ReverseIterator&& other); |
| 669 ~ReverseIterator(); |
| 670 |
| 671 ReverseIterator& operator=(const ReverseIterator& other); |
| 672 ReverseIterator& operator=(ReverseIterator&& other); |
| 673 |
| 674 private: |
| 675 explicit ReverseIterator(PyramidSequence* pyramid_sequence); |
| 676 |
| 677 void Setup() override; |
| 678 bool IsEmpty() const override; |
| 679 void Advance() override; |
| 680 void UpdateCurrent() override; |
| 681 |
| 682 TriangularSequence::IteratorBase* |
| 683 GetNextTriangularSequenceReverseIterator(); |
| 684 |
| 685 LinearSequence::ReverseIterator |
| 686 current_traversal_sequence_reverse_iterator_; |
| 687 std::vector<TriangularSequence::ReverseIterator> |
| 688 triangular_sequence_reverse_iterators_; |
| 689 |
| 690 friend class PyramidSequence; |
| 691 }; |
| 692 |
| 693 private: |
| 694 void EmplaceAt(int position, TriangularSequence&& triangular_sequence); |
| 695 |
| 696 IndexRect consider_index_rect_; |
| 697 IndexRect ignore_index_rect_; |
| 698 TriangularSequence::Vector triangular_sequences_; |
| 699 }; |
| 700 |
| 701 } // namespace cc |
| 702 |
| 703 #endif // CC_BASE_PYRAMID_SEQUENCE_H_ |
OLD | NEW |