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