| 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 238 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 249 E get element { | 249 E get element { |
| 250 throw IterableElementError.noElement(); | 250 throw IterableElementError.noElement(); |
| 251 } | 251 } |
| 252 } | 252 } |
| 253 | 253 |
| 254 /** | 254 /** |
| 255 * A [Queue] implementation based on a double-linked list. | 255 * A [Queue] implementation based on a double-linked list. |
| 256 * | 256 * |
| 257 * Allows constant time add, remove-at-ends and peek operations. | 257 * Allows constant time add, remove-at-ends and peek operations. |
| 258 */ | 258 */ |
| 259 class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> { | 259 class DoubleLinkedQueue<E> extends Iterable<E> implements Queue<E> { |
| 260 _DoubleLinkedQueueSentinel<E> _sentinel; | 260 _DoubleLinkedQueueSentinel<E> _sentinel; |
| 261 int _elementCount = 0; | 261 int _elementCount = 0; |
| 262 | 262 |
| 263 DoubleLinkedQueue() { | 263 DoubleLinkedQueue() { |
| 264 _sentinel = new _DoubleLinkedQueueSentinel<E>(this); | 264 _sentinel = new _DoubleLinkedQueueSentinel<E>(this); |
| 265 } | 265 } |
| 266 | 266 |
| 267 /** | 267 /** |
| 268 * Creates a double-linked queue containing all [elements]. | 268 * Creates a double-linked queue containing all [elements]. |
| 269 * | 269 * |
| (...skipping 163 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 433 | 433 |
| 434 /** | 434 /** |
| 435 * List based [Queue]. | 435 * List based [Queue]. |
| 436 * | 436 * |
| 437 * Keeps a cyclic buffer of elements, and grows to a larger buffer when | 437 * Keeps a cyclic buffer of elements, and grows to a larger buffer when |
| 438 * it fills up. This guarantees constant time peek and remove operations, and | 438 * it fills up. This guarantees constant time peek and remove operations, and |
| 439 * amortized constant time add operations. | 439 * amortized constant time add operations. |
| 440 * | 440 * |
| 441 * The structure is efficient for any queue or stack usage. | 441 * The structure is efficient for any queue or stack usage. |
| 442 */ | 442 */ |
| 443 class ListQueue<E> extends IterableBase<E> implements Queue<E> { | 443 class ListQueue<E> extends Iterable<E> implements Queue<E> { |
| 444 static const int _INITIAL_CAPACITY = 8; | 444 static const int _INITIAL_CAPACITY = 8; |
| 445 List<E> _table; | 445 List<E> _table; |
| 446 int _head; | 446 int _head; |
| 447 int _tail; | 447 int _tail; |
| 448 int _modificationCount = 0; | 448 int _modificationCount = 0; |
| 449 | 449 |
| 450 /** | 450 /** |
| 451 * Create an empty queue. | 451 * Create an empty queue. |
| 452 * | 452 * |
| 453 * If [initialCapacity] is given, prepare the queue for at least that many | 453 * If [initialCapacity] is given, prepare the queue for at least that many |
| (...skipping 357 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 811 _queue._checkModification(_modificationCount); | 811 _queue._checkModification(_modificationCount); |
| 812 if (_position == _end) { | 812 if (_position == _end) { |
| 813 _current = null; | 813 _current = null; |
| 814 return false; | 814 return false; |
| 815 } | 815 } |
| 816 _current = _queue._table[_position]; | 816 _current = _queue._table[_position]; |
| 817 _position = (_position + 1) & (_queue._table.length - 1); | 817 _position = (_position + 1) & (_queue._table.length - 1); |
| 818 return true; | 818 return true; |
| 819 } | 819 } |
| 820 } | 820 } |
| OLD | NEW |