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

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

Issue 12328104: Change new List(n) to return fixed length list. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Merge to head. Created 7 years, 9 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
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 332 matching lines...) Expand 10 before | Expand all | Expand 10 after
343 * If [initialCapacity] is given, prepare the queue for at least that many 343 * If [initialCapacity] is given, prepare the queue for at least that many
344 * elements. 344 * elements.
345 */ 345 */
346 ListQueue([int initialCapacity]) : _head = 0, _tail = 0 { 346 ListQueue([int initialCapacity]) : _head = 0, _tail = 0 {
347 if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) { 347 if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) {
348 initialCapacity = _INITIAL_CAPACITY; 348 initialCapacity = _INITIAL_CAPACITY;
349 } else if (!_isPowerOf2(initialCapacity)) { 349 } else if (!_isPowerOf2(initialCapacity)) {
350 initialCapacity = _nextPowerOf2(initialCapacity); 350 initialCapacity = _nextPowerOf2(initialCapacity);
351 } 351 }
352 assert(_isPowerOf2(initialCapacity)); 352 assert(_isPowerOf2(initialCapacity));
353 _table = new List<E>.fixedLength(initialCapacity); 353 _table = new List<E>(initialCapacity);
354 } 354 }
355 355
356 /** 356 /**
357 * Create a queue initially containing the elements of [source]. 357 * Create a queue initially containing the elements of [source].
358 */ 358 */
359 factory ListQueue.from(Iterable<E> source) { 359 factory ListQueue.from(Iterable<E> source) {
360 if (source is List) { 360 if (source is List) {
361 int length = source.length; 361 int length = source.length;
362 ListQueue<E> queue = new ListQueue(length + 1); 362 ListQueue<E> queue = new ListQueue(length + 1);
363 assert(queue._table.length > length); 363 assert(queue._table.length > length);
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after
402 return _table[_head]; 402 return _table[_head];
403 } 403 }
404 404
405 E elementAt(int index) { 405 E elementAt(int index) {
406 if (index < 0 || index > length) { 406 if (index < 0 || index > length) {
407 throw new RangeError.range(index, 0, length); 407 throw new RangeError.range(index, 0, length);
408 } 408 }
409 return _table[(_head + index) & (_table.length - 1)]; 409 return _table[(_head + index) & (_table.length - 1)];
410 } 410 }
411 411
412 List<E> toList() { 412 List<E> toList({ bool growable: false }) {
413 List<E> list = new List<E>(length); 413 List<E> list;
414 if (growable) {
415 list = new List<E>()..length = length;
416 } else {
417 list = new List<E>(length);
418 }
414 _writeToList(list); 419 _writeToList(list);
415 return list; 420 return list;
416 } 421 }
417 422
418 // Collection interface. 423 // Collection interface.
419 424
420 void add(E element) { 425 void add(E element) {
421 _add(element); 426 _add(element);
422 } 427 }
423 428
(...skipping 198 matching lines...) Expand 10 before | Expand all | Expand 10 after
622 } 627 }
623 _table[_tail] = null; 628 _table[_tail] = null;
624 return offset; 629 return offset;
625 } 630 }
626 } 631 }
627 632
628 /** 633 /**
629 * Grow the table when full. 634 * Grow the table when full.
630 */ 635 */
631 void _grow() { 636 void _grow() {
632 List<E> newTable = new List<E>.fixedLength(_table.length * 2); 637 List<E> newTable = new List<E>(_table.length * 2);
633 int split = _table.length - _head; 638 int split = _table.length - _head;
634 newTable.setRange(0, split, _table, _head); 639 newTable.setRange(0, split, _table, _head);
635 newTable.setRange(split, _head, _table, 0); 640 newTable.setRange(split, _head, _table, 0);
636 _head = 0; 641 _head = 0;
637 _tail = _table.length; 642 _tail = _table.length;
638 _table = newTable; 643 _table = newTable;
639 } 644 }
640 645
641 int _writeToList(List<E> target) { 646 int _writeToList(List<E> target) {
642 assert(target.length >= length); 647 assert(target.length >= length);
643 if (_head <= _tail) { 648 if (_head <= _tail) {
644 int length = _tail - _head; 649 int length = _tail - _head;
645 target.setRange(0, length, _table, _head); 650 target.setRange(0, length, _table, _head);
646 return length; 651 return length;
647 } else { 652 } else {
648 int firstPartSize = _table.length - _head; 653 int firstPartSize = _table.length - _head;
649 target.setRange(0, firstPartSize, _table, _head); 654 target.setRange(0, firstPartSize, _table, _head);
650 target.setRange(firstPartSize, _tail, _table, 0); 655 target.setRange(firstPartSize, _tail, _table, 0);
651 return _tail + firstPartSize; 656 return _tail + firstPartSize;
652 } 657 }
653 } 658 }
654 659
655 /** Grows the table even if it is not full. */ 660 /** Grows the table even if it is not full. */
656 void _preGrow(int newElementCount) { 661 void _preGrow(int newElementCount) {
657 assert(newElementCount >= length); 662 assert(newElementCount >= length);
658 int newCapacity = _nextPowerOf2(newElementCount); 663 int newCapacity = _nextPowerOf2(newElementCount);
659 List<E> newTable = new List<E>.fixedLength(newCapacity); 664 List<E> newTable = new List<E>(newCapacity);
660 _tail = _writeToList(newTable); 665 _tail = _writeToList(newTable);
661 _table = newTable; 666 _table = newTable;
662 _head = 0; 667 _head = 0;
663 } 668 }
664 } 669 }
665 670
666 /** 671 /**
667 * Iterator for a [ListQueue]. 672 * Iterator for a [ListQueue].
668 * 673 *
669 * Considers any add or remove operation a concurrent modification. 674 * Considers any add or remove operation a concurrent modification.
(...skipping 17 matching lines...) Expand all
687 _queue._checkModification(_modificationCount); 692 _queue._checkModification(_modificationCount);
688 if (_position == _end) { 693 if (_position == _end) {
689 _current = null; 694 _current = null;
690 return false; 695 return false;
691 } 696 }
692 _current = _queue._table[_position]; 697 _current = _queue._table[_position];
693 _position = (_position + 1) & (_queue._table.length - 1); 698 _position = (_position + 1) & (_queue._table.length - 1);
694 return true; 699 return true;
695 } 700 }
696 } 701 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698