| 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 13 matching lines...) Expand all Loading... |
| 24 */ | 24 */ |
| 25 factory Queue() = ListQueue<E>; | 25 factory Queue() = ListQueue<E>; |
| 26 | 26 |
| 27 /** | 27 /** |
| 28 * Creates a queue with the elements of [other]. The order in | 28 * Creates a queue with the elements of [other]. The order in |
| 29 * the queue will be the order provided by the iterator of [other]. | 29 * the queue will be the order provided by the iterator of [other]. |
| 30 */ | 30 */ |
| 31 factory Queue.from(Iterable<E> other) = ListQueue<E>.from; | 31 factory Queue.from(Iterable<E> other) = ListQueue<E>.from; |
| 32 | 32 |
| 33 /** | 33 /** |
| 34 * Removes and returns the first element of this queue. Throws an | 34 * Removes and returns the first element of this queue. |
| 35 * [StateError] exception if this queue is empty. | 35 * |
| 36 * The queue must not be empty when this method is called. |
| 36 */ | 37 */ |
| 37 E removeFirst(); | 38 E removeFirst(); |
| 38 | 39 |
| 39 /** | 40 /** |
| 40 * Removes and returns the last element of the queue. Throws an | 41 * Removes and returns the last element of the queue. |
| 41 * [StateError] exception if this queue is empty. | 42 * |
| 43 * The queue must not be empty when this method is called. |
| 42 */ | 44 */ |
| 43 E removeLast(); | 45 E removeLast(); |
| 44 | 46 |
| 45 /** | 47 /** |
| 46 * Adds [value] at the beginning of the queue. | 48 * Adds [value] at the beginning of the queue. |
| 47 */ | 49 */ |
| 48 void addFirst(E value); | 50 void addFirst(E value); |
| 49 | 51 |
| 50 /** | 52 /** |
| 51 * Adds [value] at the end of the queue. | 53 * Adds [value] at the end of the queue. |
| (...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 155 * which is the only entry when the list is constructed. | 157 * which is the only entry when the list is constructed. |
| 156 * Initially, a sentinel has its next and previous entry point to itself. | 158 * Initially, a sentinel has its next and previous entry point to itself. |
| 157 * A sentinel does not box any user element. | 159 * A sentinel does not box any user element. |
| 158 */ | 160 */ |
| 159 class _DoubleLinkedQueueEntrySentinel<E> extends DoubleLinkedQueueEntry<E> { | 161 class _DoubleLinkedQueueEntrySentinel<E> extends DoubleLinkedQueueEntry<E> { |
| 160 _DoubleLinkedQueueEntrySentinel() : super(null) { | 162 _DoubleLinkedQueueEntrySentinel() : super(null) { |
| 161 _link(this, this); | 163 _link(this, this); |
| 162 } | 164 } |
| 163 | 165 |
| 164 E remove() { | 166 E remove() { |
| 165 throw new StateError("Empty queue"); | 167 throw IterableElementError.noElement(); |
| 166 } | 168 } |
| 167 | 169 |
| 168 DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { | 170 DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { |
| 169 return null; | 171 return null; |
| 170 } | 172 } |
| 171 | 173 |
| 172 void set element(E e) { | 174 void set element(E e) { |
| 173 // This setter is unreachable. | 175 // This setter is unreachable. |
| 174 // TODO(lrn): Don't inherit the field if we don't use it. | 176 // TODO(lrn): Don't inherit the field if we don't use it. |
| 175 assert(false); | 177 assert(false); |
| 176 } | 178 } |
| 177 | 179 |
| 178 E get element { | 180 E get element { |
| 179 throw new StateError("Empty queue"); | 181 throw IterableElementError.noElement(); |
| 180 } | 182 } |
| 181 } | 183 } |
| 182 | 184 |
| 183 /** | 185 /** |
| 184 * A [Queue] implementation based on a double-linked list. | 186 * A [Queue] implementation based on a double-linked list. |
| 185 * | 187 * |
| 186 * Allows constant time add, remove-at-ends and peek operations. | 188 * Allows constant time add, remove-at-ends and peek operations. |
| 187 */ | 189 */ |
| 188 class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> { | 190 class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> { |
| 189 _DoubleLinkedQueueEntrySentinel<E> _sentinel; | 191 _DoubleLinkedQueueEntrySentinel<E> _sentinel; |
| (...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 272 | 274 |
| 273 E get first { | 275 E get first { |
| 274 return _sentinel._next.element; | 276 return _sentinel._next.element; |
| 275 } | 277 } |
| 276 | 278 |
| 277 E get last { | 279 E get last { |
| 278 return _sentinel._previous.element; | 280 return _sentinel._previous.element; |
| 279 } | 281 } |
| 280 | 282 |
| 281 E get single { | 283 E get single { |
| 282 // Note that this also covers the case where the queue is empty. | 284 // Note that this throws correctly if the queue is empty. |
| 283 if (identical(_sentinel._next, _sentinel._previous)) { | 285 if (identical(_sentinel._next, _sentinel._previous)) { |
| 284 return _sentinel._next.element; | 286 return _sentinel._next.element; |
| 285 } | 287 } |
| 286 throw new StateError("More than one element"); | 288 throw IterableElementError.tooMany(); |
| 287 } | 289 } |
| 288 | 290 |
| 289 DoubleLinkedQueueEntry<E> lastEntry() { | 291 DoubleLinkedQueueEntry<E> lastEntry() { |
| 290 return _sentinel.previousEntry(); | 292 return _sentinel.previousEntry(); |
| 291 } | 293 } |
| 292 | 294 |
| 293 DoubleLinkedQueueEntry<E> firstEntry() { | 295 DoubleLinkedQueueEntry<E> firstEntry() { |
| 294 return _sentinel.nextEntry(); | 296 return _sentinel.nextEntry(); |
| 295 } | 297 } |
| 296 | 298 |
| (...skipping 13 matching lines...) Expand all Loading... |
| 310 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | 312 DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
| 311 f(entry); | 313 f(entry); |
| 312 entry = nextEntry; | 314 entry = nextEntry; |
| 313 } | 315 } |
| 314 } | 316 } |
| 315 | 317 |
| 316 _DoubleLinkedQueueIterator<E> get iterator { | 318 _DoubleLinkedQueueIterator<E> get iterator { |
| 317 return new _DoubleLinkedQueueIterator<E>(_sentinel); | 319 return new _DoubleLinkedQueueIterator<E>(_sentinel); |
| 318 } | 320 } |
| 319 | 321 |
| 320 String toString() => _collectionToString(this, '{', '}'); | 322 String toString() => IterableBase.iterableToFullString(this, '{', '}'); |
| 321 } | 323 } |
| 322 | 324 |
| 323 class _DoubleLinkedQueueIterator<E> implements Iterator<E> { | 325 class _DoubleLinkedQueueIterator<E> implements Iterator<E> { |
| 324 _DoubleLinkedQueueEntrySentinel<E> _sentinel; | 326 _DoubleLinkedQueueEntrySentinel<E> _sentinel; |
| 325 DoubleLinkedQueueEntry<E> _nextEntry = null; | 327 DoubleLinkedQueueEntry<E> _nextEntry = null; |
| 326 E _current; | 328 E _current; |
| 327 | 329 |
| 328 _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel<E> sentinel) | 330 _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel<E> sentinel) |
| 329 : _sentinel = sentinel, _nextEntry = sentinel._next; | 331 : _sentinel = sentinel, _nextEntry = sentinel._next; |
| 330 | 332 |
| (...skipping 71 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 402 action(_table[i]); | 404 action(_table[i]); |
| 403 _checkModification(modificationCount); | 405 _checkModification(modificationCount); |
| 404 } | 406 } |
| 405 } | 407 } |
| 406 | 408 |
| 407 bool get isEmpty => _head == _tail; | 409 bool get isEmpty => _head == _tail; |
| 408 | 410 |
| 409 int get length => (_tail - _head) & (_table.length - 1); | 411 int get length => (_tail - _head) & (_table.length - 1); |
| 410 | 412 |
| 411 E get first { | 413 E get first { |
| 412 if (_head == _tail) throw new StateError("No elements"); | 414 if (_head == _tail) throw IterableElementError.noElement(); |
| 413 return _table[_head]; | 415 return _table[_head]; |
| 414 } | 416 } |
| 415 | 417 |
| 416 E get last { | 418 E get last { |
| 417 if (_head == _tail) throw new StateError("No elements"); | 419 if (_head == _tail) throw IterableElementError.noElement(); |
| 418 return _table[(_tail - 1) & (_table.length - 1)]; | 420 return _table[(_tail - 1) & (_table.length - 1)]; |
| 419 } | 421 } |
| 420 | 422 |
| 421 E get single { | 423 E get single { |
| 422 if (_head == _tail) throw new StateError("No elements"); | 424 if (_head == _tail) throw IterableElementError.noElement(); |
| 423 if (length > 1) throw new StateError("Too many elements"); | 425 if (length > 1) throw IterableElementError.tooMany(); |
| 424 return _table[_head]; | 426 return _table[_head]; |
| 425 } | 427 } |
| 426 | 428 |
| 427 E elementAt(int index) { | 429 E elementAt(int index) { |
| 428 if (index < 0 || index > length) { | 430 if (index < 0 || index > length) { |
| 429 throw new RangeError.range(index, 0, length); | 431 throw new RangeError.range(index, 0, length); |
| 430 } | 432 } |
| 431 return _table[(_head + index) & (_table.length - 1)]; | 433 return _table[(_head + index) & (_table.length - 1)]; |
| 432 } | 434 } |
| 433 | 435 |
| (...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 529 void clear() { | 531 void clear() { |
| 530 if (_head != _tail) { | 532 if (_head != _tail) { |
| 531 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { | 533 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { |
| 532 _table[i] = null; | 534 _table[i] = null; |
| 533 } | 535 } |
| 534 _head = _tail = 0; | 536 _head = _tail = 0; |
| 535 _modificationCount++; | 537 _modificationCount++; |
| 536 } | 538 } |
| 537 } | 539 } |
| 538 | 540 |
| 539 String toString() => _collectionToString(this, '{', '}'); | 541 String toString() => IterableBase.iterableToFullString(this, "{", "}"); |
| 540 | 542 |
| 541 // Queue interface. | 543 // Queue interface. |
| 542 | 544 |
| 543 void addLast(E element) { _add(element); } | 545 void addLast(E element) { _add(element); } |
| 544 | 546 |
| 545 void addFirst(E element) { | 547 void addFirst(E element) { |
| 546 _head = (_head - 1) & (_table.length - 1); | 548 _head = (_head - 1) & (_table.length - 1); |
| 547 _table[_head] = element; | 549 _table[_head] = element; |
| 548 if (_head == _tail) _grow(); | 550 if (_head == _tail) _grow(); |
| 549 _modificationCount++; | 551 _modificationCount++; |
| 550 } | 552 } |
| 551 | 553 |
| 552 E removeFirst() { | 554 E removeFirst() { |
| 553 if (_head == _tail) throw new StateError("No elements"); | 555 if (_head == _tail) throw IterableElementError.noElement(); |
| 554 _modificationCount++; | 556 _modificationCount++; |
| 555 E result = _table[_head]; | 557 E result = _table[_head]; |
| 556 _table[_head] = null; | 558 _table[_head] = null; |
| 557 _head = (_head + 1) & (_table.length - 1); | 559 _head = (_head + 1) & (_table.length - 1); |
| 558 return result; | 560 return result; |
| 559 } | 561 } |
| 560 | 562 |
| 561 E removeLast() { | 563 E removeLast() { |
| 562 if (_head == _tail) throw new StateError("No elements"); | 564 if (_head == _tail) throw IterableElementError.noElement(); |
| 563 _modificationCount++; | 565 _modificationCount++; |
| 564 _tail = (_tail - 1) & (_table.length - 1); | 566 _tail = (_tail - 1) & (_table.length - 1); |
| 565 E result = _table[_tail]; | 567 E result = _table[_tail]; |
| 566 _table[_tail] = null; | 568 _table[_tail] = null; |
| 567 return result; | 569 return result; |
| 568 } | 570 } |
| 569 | 571 |
| 570 // Internal helper functions. | 572 // Internal helper functions. |
| 571 | 573 |
| 572 /** | 574 /** |
| (...skipping 135 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 708 _queue._checkModification(_modificationCount); | 710 _queue._checkModification(_modificationCount); |
| 709 if (_position == _end) { | 711 if (_position == _end) { |
| 710 _current = null; | 712 _current = null; |
| 711 return false; | 713 return false; |
| 712 } | 714 } |
| 713 _current = _queue._table[_position]; | 715 _current = _queue._table[_position]; |
| 714 _position = (_position + 1) & (_queue._table.length - 1); | 716 _position = (_position + 1) & (_queue._table.length - 1); |
| 715 return true; | 717 return true; |
| 716 } | 718 } |
| 717 } | 719 } |
| OLD | NEW |