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 142 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
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 Loading... |
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 Loading... |
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 } |
OLD | NEW |