| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2015 Google Inc. | 2 * Copyright 2015 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 | 7 |
| 8 #ifndef SkTDPQueue_DEFINED | 8 #ifndef SkTDPQueue_DEFINED |
| 9 #define SkTDPQueue_DEFINED | 9 #define SkTDPQueue_DEFINED |
| 10 | 10 |
| (...skipping 16 matching lines...) Expand all Loading... |
| 27 class SkTDPQueue : public SkNoncopyable { | 27 class SkTDPQueue : public SkNoncopyable { |
| 28 public: | 28 public: |
| 29 SkTDPQueue() {} | 29 SkTDPQueue() {} |
| 30 | 30 |
| 31 /** Number of items in the queue. */ | 31 /** Number of items in the queue. */ |
| 32 int count() const { return fArray.count(); } | 32 int count() const { return fArray.count(); } |
| 33 | 33 |
| 34 /** Gets the next item in the queue without popping it. */ | 34 /** Gets the next item in the queue without popping it. */ |
| 35 const T& peek() const { return fArray[0]; } | 35 const T& peek() const { return fArray[0]; } |
| 36 T& peek() { return fArray[0]; } | 36 T& peek() { return fArray[0]; } |
| 37 | 37 |
| 38 /** Removes the next item. */ | 38 /** Removes the next item. */ |
| 39 void pop() { | 39 void pop() { |
| 40 this->validate(); | 40 this->validate(); |
| 41 SkDEBUGCODE(if (SkToBool(INDEX)) { *INDEX(fArray[0]) = -1; }) | 41 SkDEBUGCODE(if (SkToBool(INDEX)) { *INDEX(fArray[0]) = -1; }) |
| 42 if (1 == fArray.count()) { | 42 if (1 == fArray.count()) { |
| 43 fArray.pop(); | 43 fArray.pop(); |
| 44 return; | 44 return; |
| 45 } | 45 } |
| 46 | 46 |
| 47 fArray[0] = fArray[fArray.count() - 1]; | 47 fArray[0] = fArray[fArray.count() - 1]; |
| (...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 127 return percolated; | 127 return percolated; |
| 128 } | 128 } |
| 129 this->validate(index); | 129 this->validate(index); |
| 130 } while (true); | 130 } while (true); |
| 131 } | 131 } |
| 132 | 132 |
| 133 void percolateDownIfNecessary(int index) { | 133 void percolateDownIfNecessary(int index) { |
| 134 SkASSERT(index >= 0); | 134 SkASSERT(index >= 0); |
| 135 do { | 135 do { |
| 136 int child = LeftOf(index); | 136 int child = LeftOf(index); |
| 137 | 137 |
| 138 if (child >= fArray.count()) { | 138 if (child >= fArray.count()) { |
| 139 // We're a leaf. | 139 // We're a leaf. |
| 140 this->setIndex(index); | 140 this->setIndex(index); |
| 141 return; | 141 return; |
| 142 } | 142 } |
| 143 | 143 |
| 144 if (child + 1 >= fArray.count()) { | 144 if (child + 1 >= fArray.count()) { |
| 145 // We only have a left child. | 145 // We only have a left child. |
| 146 if (LESS(fArray[child], fArray[index])) { | 146 if (LESS(fArray[child], fArray[index])) { |
| 147 SkTSwap(fArray[child], fArray[index]); | 147 SkTSwap(fArray[child], fArray[index]); |
| (...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 181 int p = ParentOf(i); | 181 int p = ParentOf(i); |
| 182 if (excludedIndex != p && excludedIndex != i) { | 182 if (excludedIndex != p && excludedIndex != i) { |
| 183 SkASSERT(!(LESS(fArray[i], fArray[p]))); | 183 SkASSERT(!(LESS(fArray[i], fArray[p]))); |
| 184 SkASSERT(!SkToBool(INDEX) || *INDEX(fArray[i]) == i); | 184 SkASSERT(!SkToBool(INDEX) || *INDEX(fArray[i]) == i); |
| 185 } | 185 } |
| 186 } | 186 } |
| 187 #endif | 187 #endif |
| 188 } | 188 } |
| 189 | 189 |
| 190 SkTDArray<T> fArray; | 190 SkTDArray<T> fArray; |
| 191 | 191 |
| 192 typedef SkNoncopyable INHERITED; | 192 typedef SkNoncopyable INHERITED; |
| 193 }; | 193 }; |
| 194 | 194 |
| 195 #endif | 195 #endif |
| OLD | NEW |