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 207 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
218 if (entry.element == o) { | 218 if (entry.element == o) { |
219 entry.remove(); | 219 entry.remove(); |
220 _elementCount--; | 220 _elementCount--; |
221 return; | 221 return; |
222 } | 222 } |
223 entry = entry._next; | 223 entry = entry._next; |
224 } | 224 } |
225 } | 225 } |
226 | 226 |
227 void removeAll(Iterable elements) { | 227 void removeAll(Iterable elements) { |
228 // Use this method when remove is slow and removeMatching more efficient. | 228 // Use this method when remove is slow and removeWhere more efficient. |
229 IterableMixinWorkaround.removeAllList(this, elements); | 229 IterableMixinWorkaround.removeAllList(this, elements); |
230 } | 230 } |
231 | 231 |
232 void removeMatching(bool test(E element)) { | 232 void removeWhere(bool test(E element)) { |
233 DoubleLinkedQueueEntry<E> entry = firstEntry(); | 233 DoubleLinkedQueueEntry<E> entry = firstEntry(); |
234 while (!identical(entry, _sentinel)) { | 234 while (!identical(entry, _sentinel)) { |
235 DoubleLinkedQueueEntry<E> next = entry._next; | 235 DoubleLinkedQueueEntry<E> next = entry._next; |
236 if (test(entry.element)) { | 236 if (test(entry.element)) { |
237 entry.remove(); | 237 entry.remove(); |
238 _elementCount--; | 238 _elementCount--; |
239 } | 239 } |
240 entry = next; | 240 entry = next; |
241 } | 241 } |
242 } | 242 } |
243 | 243 |
244 void retainMatching(bool test(E element)) { | 244 void retainWhere(bool test(E element)) { |
245 DoubleLinkedQueueEntry<E> entry = firstEntry(); | 245 DoubleLinkedQueueEntry<E> entry = firstEntry(); |
246 while (!identical(entry, _sentinel)) { | 246 while (!identical(entry, _sentinel)) { |
247 DoubleLinkedQueueEntry<E> next = entry._next; | 247 DoubleLinkedQueueEntry<E> next = entry._next; |
248 if (!test(entry.element)) { | 248 if (!test(entry.element)) { |
249 entry.remove(); | 249 entry.remove(); |
250 _elementCount--; | 250 _elementCount--; |
251 } | 251 } |
252 entry = next; | 252 entry = next; |
253 } | 253 } |
254 } | 254 } |
(...skipping 80 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
335 | 335 |
336 /** | 336 /** |
337 * List based [Queue]. | 337 * List based [Queue]. |
338 * | 338 * |
339 * Keeps a cyclic buffer of elements, and grows to a larger buffer when | 339 * Keeps a cyclic buffer of elements, and grows to a larger buffer when |
340 * it fills up. This guarantees constant time peek and remove operations, and | 340 * it fills up. This guarantees constant time peek and remove operations, and |
341 * amortized constant time add operations. | 341 * amortized constant time add operations. |
342 * | 342 * |
343 * The structure is efficient for any queue or stack usage. | 343 * The structure is efficient for any queue or stack usage. |
344 * | 344 * |
345 * Collection operations like [removeAll] and [removeMatching] are very | 345 * Collection operations like [removeAll] and [removeWhere] are very |
346 * inefficient. If those are needed, use a [DoubleLinkedQueue] instead. | 346 * inefficient. If those are needed, use a [DoubleLinkedQueue] instead. |
347 */ | 347 */ |
348 class ListQueue<E> extends Collection<E> implements Queue<E>{ | 348 class ListQueue<E> extends Collection<E> implements Queue<E>{ |
349 static const int _INITIAL_CAPACITY = 8; | 349 static const int _INITIAL_CAPACITY = 8; |
350 List<E> _table; | 350 List<E> _table; |
351 int _head; | 351 int _head; |
352 int _tail; | 352 int _tail; |
353 int _modificationCount = 0; | 353 int _modificationCount = 0; |
354 | 354 |
355 /** | 355 /** |
(...skipping 126 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
482 } | 482 } |
483 | 483 |
484 void removeAll(Iterable objectsToRemove) { | 484 void removeAll(Iterable objectsToRemove) { |
485 IterableMixinWorkaround.removeAllList(this, objectsToRemove); | 485 IterableMixinWorkaround.removeAllList(this, objectsToRemove); |
486 } | 486 } |
487 | 487 |
488 void retainAll(Iterable objectsToRetain) { | 488 void retainAll(Iterable objectsToRetain) { |
489 IterableMixinWorkaround.retainAll(this, objectsToRetain); | 489 IterableMixinWorkaround.retainAll(this, objectsToRetain); |
490 } | 490 } |
491 | 491 |
492 void _filterMatching(bool test(E element), bool removeMatching) { | 492 void _filterWhere(bool test(E element), bool removeMatching) { |
493 int index = _head; | 493 int index = _head; |
494 int modificationCount = _modificationCount; | 494 int modificationCount = _modificationCount; |
495 int i = _head; | 495 int i = _head; |
496 while (i != _tail) { | 496 while (i != _tail) { |
497 E element = _table[i]; | 497 E element = _table[i]; |
498 bool remove = (test(element) == removeMatching); | 498 bool remove = (test(element) == removeMatching); |
499 _checkModification(modificationCount); | 499 _checkModification(modificationCount); |
500 if (remove) { | 500 if (remove) { |
501 i = _remove(i); | 501 i = _remove(i); |
502 modificationCount = ++_modificationCount; | 502 modificationCount = ++_modificationCount; |
503 } else { | 503 } else { |
504 i = (i + 1) & (_table.length - 1); | 504 i = (i + 1) & (_table.length - 1); |
505 } | 505 } |
506 } | 506 } |
507 } | 507 } |
508 | 508 |
509 /** | 509 /** |
510 * Remove all elements matched by [test]. | 510 * Remove all elements matched by [test]. |
511 * | 511 * |
512 * This method is inefficient since it works by repeatedly removing single | 512 * This method is inefficient since it works by repeatedly removing single |
513 * elements, each of which can take linear time. | 513 * elements, each of which can take linear time. |
514 */ | 514 */ |
515 void removeMatching(bool test(E element)) { | 515 void removeWhere(bool test(E element)) { |
516 _filterMatching(test, true); | 516 _filterWhere(test, true); |
517 } | 517 } |
518 | 518 |
519 /** | 519 /** |
520 * Remove all elements not matched by [test]. | 520 * Remove all elements not matched by [test]. |
521 * | 521 * |
522 * This method is inefficient since it works by repeatedly removing single | 522 * This method is inefficient since it works by repeatedly removing single |
523 * elements, each of which can take linear time. | 523 * elements, each of which can take linear time. |
524 */ | 524 */ |
525 void retainMatching(bool test(E element)) { | 525 void retainWhere(bool test(E element)) { |
526 _filterMatching(test, false); | 526 _filterWhere(test, false); |
527 } | 527 } |
528 | 528 |
529 void clear() { | 529 void clear() { |
530 if (_head != _tail) { | 530 if (_head != _tail) { |
531 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { | 531 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { |
532 _table[i] = null; | 532 _table[i] = null; |
533 } | 533 } |
534 _head = _tail = 0; | 534 _head = _tail = 0; |
535 _modificationCount++; | 535 _modificationCount++; |
536 } | 536 } |
(...skipping 170 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
707 _queue._checkModification(_modificationCount); | 707 _queue._checkModification(_modificationCount); |
708 if (_position == _end) { | 708 if (_position == _end) { |
709 _current = null; | 709 _current = null; |
710 return false; | 710 return false; |
711 } | 711 } |
712 _current = _queue._table[_position]; | 712 _current = _queue._table[_position]; |
713 _position = (_position + 1) & (_queue._table.length - 1); | 713 _position = (_position + 1) & (_queue._table.length - 1); |
714 return true; | 714 return true; |
715 } | 715 } |
716 } | 716 } |
OLD | NEW |