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 332 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 } |
OLD | NEW |