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

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

Issue 14022007: Move Iterable implementation to collection. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Address comments. Merge to head. Created 7 years, 8 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/hash_set.dart ('k') | sdk/lib/collection/splay_tree.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 142 matching lines...) Expand 10 before | Expand all | Expand 10 after
153 } 153 }
154 } 154 }
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 Iterable<E> implements Queue<E> { 163 class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> {
164 _DoubleLinkedQueueEntrySentinel<E> _sentinel; 164 _DoubleLinkedQueueEntrySentinel<E> _sentinel;
165 int _elementCount = 0; 165 int _elementCount = 0;
166 166
167 DoubleLinkedQueue() { 167 DoubleLinkedQueue() {
168 _sentinel = new _DoubleLinkedQueueEntrySentinel<E>(); 168 _sentinel = new _DoubleLinkedQueueEntrySentinel<E>();
169 } 169 }
170 170
171 factory DoubleLinkedQueue.from(Iterable<E> other) { 171 factory DoubleLinkedQueue.from(Iterable<E> other) {
172 Queue<E> list = new DoubleLinkedQueue(); 172 Queue<E> list = new DoubleLinkedQueue();
173 for (final e in other) { 173 for (final e in other) {
(...skipping 173 matching lines...) Expand 10 before | Expand all | Expand 10 after
347 * 347 *
348 * Keeps a cyclic buffer of elements, and grows to a larger buffer when 348 * Keeps a cyclic buffer of elements, and grows to a larger buffer when
349 * it fills up. This guarantees constant time peek and remove operations, and 349 * it fills up. This guarantees constant time peek and remove operations, and
350 * amortized constant time add operations. 350 * amortized constant time add operations.
351 * 351 *
352 * The structure is efficient for any queue or stack usage. 352 * The structure is efficient for any queue or stack usage.
353 * 353 *
354 * Operations like [removeAll] and [removeWhere] are very 354 * Operations like [removeAll] and [removeWhere] are very
355 * inefficient. If those are needed, use a [DoubleLinkedQueue] instead. 355 * inefficient. If those are needed, use a [DoubleLinkedQueue] instead.
356 */ 356 */
357 class ListQueue<E> extends Iterable<E> implements Queue<E>{ 357 class ListQueue<E> extends IterableBase<E> implements Queue<E> {
358 static const int _INITIAL_CAPACITY = 8; 358 static const int _INITIAL_CAPACITY = 8;
359 List<E> _table; 359 List<E> _table;
360 int _head; 360 int _head;
361 int _tail; 361 int _tail;
362 int _modificationCount = 0; 362 int _modificationCount = 0;
363 363
364 /** 364 /**
365 * Create an empty queue. 365 * Create an empty queue.
366 * 366 *
367 * If [initialCapacity] is given, prepare the queue for at least that many 367 * If [initialCapacity] is given, prepare the queue for at least that many
(...skipping 340 matching lines...) Expand 10 before | Expand all | Expand 10 after
708 _queue._checkModification(_modificationCount); 708 _queue._checkModification(_modificationCount);
709 if (_position == _end) { 709 if (_position == _end) {
710 _current = null; 710 _current = null;
711 return false; 711 return false;
712 } 712 }
713 _current = _queue._table[_position]; 713 _current = _queue._table[_position];
714 _position = (_position + 1) & (_queue._table.length - 1); 714 _position = (_position + 1) & (_queue._table.length - 1);
715 return true; 715 return true;
716 } 716 }
717 } 717 }
OLDNEW
« no previous file with comments | « sdk/lib/collection/hash_set.dart ('k') | sdk/lib/collection/splay_tree.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698