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 |