| 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 |