Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(11)

Side by Side Diff: sdk/lib/collection/queue.dart

Issue 12537009: Rename XMatching to XWhere. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Merge and rebuild dom libraries. Created 7 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « sdk/lib/collection/linked_hash_set.dart ('k') | sdk/lib/core/collection.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « sdk/lib/collection/linked_hash_set.dart ('k') | sdk/lib/core/collection.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698