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 |