OLD | NEW |
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 part of dart.collection; | 5 part of dart.collection; |
6 | 6 |
7 /** | 7 /** |
8 * A [Queue] is a collection that can be manipulated at both ends. One | 8 * A [Queue] is a collection that can be manipulated at both ends. One |
9 * can iterate over the elements of a queue through [forEach] or with | 9 * can iterate over the elements of a queue through [forEach] or with |
10 * an [Iterator]. | 10 * an [Iterator]. |
(...skipping 144 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
155 | 155 |
156 /** | 156 /** |
157 * A [Queue] implementation based on a double-linked list. | 157 * A [Queue] implementation based on a double-linked list. |
158 * | 158 * |
159 * Allows constant time add, remove-at-ends and peek operations. | 159 * Allows constant time add, remove-at-ends and peek operations. |
160 * | 160 * |
161 * Can do [removeAll] and [retainAll] in linear time. | 161 * Can do [removeAll] and [retainAll] in linear time. |
162 */ | 162 */ |
163 class DoubleLinkedQueue<E> extends Collection<E> implements Queue<E> { | 163 class DoubleLinkedQueue<E> extends Collection<E> implements Queue<E> { |
164 _DoubleLinkedQueueEntrySentinel<E> _sentinel; | 164 _DoubleLinkedQueueEntrySentinel<E> _sentinel; |
| 165 int _elementCount = 0; |
165 | 166 |
166 DoubleLinkedQueue() { | 167 DoubleLinkedQueue() { |
167 _sentinel = new _DoubleLinkedQueueEntrySentinel<E>(); | 168 _sentinel = new _DoubleLinkedQueueEntrySentinel<E>(); |
168 } | 169 } |
169 | 170 |
170 factory DoubleLinkedQueue.from(Iterable<E> other) { | 171 factory DoubleLinkedQueue.from(Iterable<E> other) { |
171 Queue<E> list = new DoubleLinkedQueue(); | 172 Queue<E> list = new DoubleLinkedQueue(); |
172 for (final e in other) { | 173 for (final e in other) { |
173 list.addLast(e); | 174 list.addLast(e); |
174 } | 175 } |
175 return list; | 176 return list; |
176 } | 177 } |
177 | 178 |
| 179 int get length => _elementCount; |
| 180 |
178 void addLast(E value) { | 181 void addLast(E value) { |
179 _sentinel.prepend(value); | 182 _sentinel.prepend(value); |
| 183 _elementCount++; |
180 } | 184 } |
181 | 185 |
182 void addFirst(E value) { | 186 void addFirst(E value) { |
183 _sentinel.append(value); | 187 _sentinel.append(value); |
| 188 _elementCount++; |
184 } | 189 } |
185 | 190 |
186 void add(E value) { | 191 void add(E value) { |
187 addLast(value); | 192 _sentinel.prepend(value); |
| 193 _elementCount++; |
188 } | 194 } |
189 | 195 |
190 void addAll(Iterable<E> iterable) { | 196 void addAll(Iterable<E> iterable) { |
191 for (final e in iterable) { | 197 for (final E value in iterable) { |
192 add(e); | 198 _sentinel.prepend(value); |
| 199 _elementCount++; |
193 } | 200 } |
194 } | 201 } |
195 | 202 |
196 E removeLast() { | 203 E removeLast() { |
197 return _sentinel._previous.remove(); | 204 E result = _sentinel._previous.remove(); |
| 205 _elementCount--; |
| 206 return result; |
198 } | 207 } |
199 | 208 |
200 E removeFirst() { | 209 E removeFirst() { |
201 return _sentinel._next.remove(); | 210 E result = _sentinel._next.remove(); |
| 211 _elementCount--; |
| 212 return result; |
202 } | 213 } |
203 | 214 |
204 void remove(Object o) { | 215 void remove(Object o) { |
205 DoubleLinkedQueueEntry<E> entry = firstEntry(); | 216 DoubleLinkedQueueEntry<E> entry = firstEntry(); |
206 while (!identical(entry, _sentinel)) { | 217 while (!identical(entry, _sentinel)) { |
207 if (entry.element == o) { | 218 if (entry.element == o) { |
208 entry.remove(); | 219 entry.remove(); |
| 220 _elementCount--; |
209 return; | 221 return; |
210 } | 222 } |
211 entry = entry._next; | 223 entry = entry._next; |
212 } | 224 } |
213 } | 225 } |
214 | 226 |
215 void removeAll(Iterable elements) { | 227 void removeAll(Iterable elements) { |
216 // Use this method when remove is slow and removeMatching more efficient. | 228 // Use this method when remove is slow and removeMatching more efficient. |
217 IterableMixinWorkaround.removeAllList(this, elements); | 229 IterableMixinWorkaround.removeAllList(this, elements); |
218 } | 230 } |
219 | 231 |
220 void removeMatching(bool test(E element)) { | 232 void removeMatching(bool test(E element)) { |
221 DoubleLinkedQueueEntry<E> entry = firstEntry(); | 233 DoubleLinkedQueueEntry<E> entry = firstEntry(); |
222 while (!identical(entry, _sentinel)) { | 234 while (!identical(entry, _sentinel)) { |
223 DoubleLinkedQueueEntry<E> next = entry._next; | 235 DoubleLinkedQueueEntry<E> next = entry._next; |
224 if (test(entry.element)) { | 236 if (test(entry.element)) { |
225 entry.remove(); | 237 entry.remove(); |
| 238 _elementCount--; |
226 } | 239 } |
227 entry = next; | 240 entry = next; |
228 } | 241 } |
229 } | 242 } |
230 | 243 |
231 void retainMatching(bool test(E element)) { | 244 void retainMatching(bool test(E element)) { |
232 DoubleLinkedQueueEntry<E> entry = firstEntry(); | 245 DoubleLinkedQueueEntry<E> entry = firstEntry(); |
233 while (!identical(entry, _sentinel)) { | 246 while (!identical(entry, _sentinel)) { |
234 DoubleLinkedQueueEntry<E> next = entry._next; | 247 DoubleLinkedQueueEntry<E> next = entry._next; |
235 if (!test(entry.element)) { | 248 if (!test(entry.element)) { |
236 entry.remove(); | 249 entry.remove(); |
| 250 _elementCount--; |
237 } | 251 } |
238 entry = next; | 252 entry = next; |
239 } | 253 } |
240 } | 254 } |
241 | 255 |
242 E get first { | 256 E get first { |
243 return _sentinel._next.element; | 257 return _sentinel._next.element; |
244 } | 258 } |
245 | 259 |
246 E get last { | 260 E get last { |
(...skipping 16 matching lines...) Expand all Loading... |
263 return _sentinel.nextEntry(); | 277 return _sentinel.nextEntry(); |
264 } | 278 } |
265 | 279 |
266 bool get isEmpty { | 280 bool get isEmpty { |
267 return (identical(_sentinel._next, _sentinel)); | 281 return (identical(_sentinel._next, _sentinel)); |
268 } | 282 } |
269 | 283 |
270 void clear() { | 284 void clear() { |
271 _sentinel._next = _sentinel; | 285 _sentinel._next = _sentinel; |
272 _sentinel._previous = _sentinel; | 286 _sentinel._previous = _sentinel; |
| 287 _elementCount = 0; |
273 } | 288 } |
274 | 289 |
275 void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) { | 290 void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) { |
276 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | 291 DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
277 while (!identical(entry, _sentinel)) { | 292 while (!identical(entry, _sentinel)) { |
278 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | 293 DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
279 f(entry); | 294 f(entry); |
280 entry = nextEntry; | 295 entry = nextEntry; |
281 } | 296 } |
282 } | 297 } |
(...skipping 409 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
692 _queue._checkModification(_modificationCount); | 707 _queue._checkModification(_modificationCount); |
693 if (_position == _end) { | 708 if (_position == _end) { |
694 _current = null; | 709 _current = null; |
695 return false; | 710 return false; |
696 } | 711 } |
697 _current = _queue._table[_position]; | 712 _current = _queue._table[_position]; |
698 _position = (_position + 1) & (_queue._table.length - 1); | 713 _position = (_position + 1) & (_queue._table.length - 1); |
699 return true; | 714 return true; |
700 } | 715 } |
701 } | 716 } |
OLD | NEW |