Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(52)

Side by Side Diff: sdk/lib/collection/queue.dart

Issue 297053002: Reinstall previous behavior for Set and Queue toString. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Address comments. Created 6 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « sdk/lib/collection/list.dart ('k') | sdk/lib/collection/set.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « sdk/lib/collection/list.dart ('k') | sdk/lib/collection/set.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698