| 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 |