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 |