| OLD | NEW |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, 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 import 'dart:collection'; | 5 import 'dart:collection'; |
| 6 | 6 |
| 7 /** | 7 /// A class that efficiently implements both [Queue] and [List]. |
| 8 * A class that efficiently implements both [Queue] and [List]. | |
| 9 */ | |
| 10 // TODO(nweiz): Currently this code is copied almost verbatim from | 8 // TODO(nweiz): Currently this code is copied almost verbatim from |
| 11 // dart:collection. The only changes are to implement List and to remove methods | 9 // dart:collection. The only changes are to implement List and to remove methods |
| 12 // that are redundant with ListMixin. Remove or simplify it when issue 21330 is | 10 // that are redundant with ListMixin. Remove or simplify it when issue 21330 is |
| 13 // fixed. | 11 // fixed. |
| 14 class QueueList<E> extends Object with ListMixin<E> implements Queue<E> { | 12 class QueueList<E> extends Object with ListMixin<E> implements Queue<E> { |
| 15 static const int _INITIAL_CAPACITY = 8; | 13 static const int _INITIAL_CAPACITY = 8; |
| 16 List<E> _table; | 14 List<E> _table; |
| 17 int _head; | 15 int _head; |
| 18 int _tail; | 16 int _tail; |
| 19 | 17 |
| 20 /** | 18 /// Create an empty queue. |
| 21 * Create an empty queue. | 19 /// |
| 22 * | 20 /// If [initialCapacity] is given, prepare the queue for at least that many |
| 23 * If [initialCapacity] is given, prepare the queue for at least that many | 21 /// elements. |
| 24 * elements. | |
| 25 */ | |
| 26 QueueList([int initialCapacity]) : _head = 0, _tail = 0 { | 22 QueueList([int initialCapacity]) : _head = 0, _tail = 0 { |
| 27 if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) { | 23 if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) { |
| 28 initialCapacity = _INITIAL_CAPACITY; | 24 initialCapacity = _INITIAL_CAPACITY; |
| 29 } else if (!_isPowerOf2(initialCapacity)) { | 25 } else if (!_isPowerOf2(initialCapacity)) { |
| 30 initialCapacity = _nextPowerOf2(initialCapacity); | 26 initialCapacity = _nextPowerOf2(initialCapacity); |
| 31 } | 27 } |
| 32 assert(_isPowerOf2(initialCapacity)); | 28 assert(_isPowerOf2(initialCapacity)); |
| 33 _table = new List<E>(initialCapacity); | 29 _table = new List<E>(initialCapacity); |
| 34 } | 30 } |
| 35 | 31 |
| 36 /** | 32 /// Create a queue initially containing the elements of [source]. |
| 37 * Create a queue initially containing the elements of [source]. | |
| 38 */ | |
| 39 factory QueueList.from(Iterable<E> source) { | 33 factory QueueList.from(Iterable<E> source) { |
| 40 if (source is List) { | 34 if (source is List) { |
| 41 int length = source.length; | 35 int length = source.length; |
| 42 QueueList<E> queue = new QueueList(length + 1); | 36 QueueList<E> queue = new QueueList(length + 1); |
| 43 assert(queue._table.length > length); | 37 assert(queue._table.length > length); |
| 44 List sourceList = source; | 38 List sourceList = source; |
| 45 queue._table.setRange(0, length, sourceList, 0); | 39 queue._table.setRange(0, length, sourceList, 0); |
| 46 queue._tail = length; | 40 queue._tail = length; |
| 47 return queue; | 41 return queue; |
| 48 } else { | 42 } else { |
| (...skipping 101 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 150 void operator[]=(int index, E value) { | 144 void operator[]=(int index, E value) { |
| 151 if (index < 0 || index >= length) { | 145 if (index < 0 || index >= length) { |
| 152 throw new RangeError("Index $index must be in the range [0..$length)."); | 146 throw new RangeError("Index $index must be in the range [0..$length)."); |
| 153 } | 147 } |
| 154 | 148 |
| 155 _table[(_head + index) & (_table.length - 1)] = value; | 149 _table[(_head + index) & (_table.length - 1)] = value; |
| 156 } | 150 } |
| 157 | 151 |
| 158 // Internal helper functions. | 152 // Internal helper functions. |
| 159 | 153 |
| 160 /** | 154 /// Whether [number] is a power of two. |
| 161 * Whether [number] is a power of two. | 155 /// |
| 162 * | 156 /// Only works for positive numbers. |
| 163 * Only works for positive numbers. | |
| 164 */ | |
| 165 static bool _isPowerOf2(int number) => (number & (number - 1)) == 0; | 157 static bool _isPowerOf2(int number) => (number & (number - 1)) == 0; |
| 166 | 158 |
| 167 /** | 159 /// Rounds [number] up to the nearest power of 2. |
| 168 * Rounds [number] up to the nearest power of 2. | 160 /// |
| 169 * | 161 /// If [number] is a power of 2 already, it is returned. |
| 170 * If [number] is a power of 2 already, it is returned. | 162 /// |
| 171 * | 163 /// Only works for positive numbers. |
| 172 * Only works for positive numbers. | |
| 173 */ | |
| 174 static int _nextPowerOf2(int number) { | 164 static int _nextPowerOf2(int number) { |
| 175 assert(number > 0); | 165 assert(number > 0); |
| 176 number = (number << 1) - 1; | 166 number = (number << 1) - 1; |
| 177 for(;;) { | 167 for(;;) { |
| 178 int nextNumber = number & (number - 1); | 168 int nextNumber = number & (number - 1); |
| 179 if (nextNumber == 0) return number; | 169 if (nextNumber == 0) return number; |
| 180 number = nextNumber; | 170 number = nextNumber; |
| 181 } | 171 } |
| 182 } | 172 } |
| 183 | 173 |
| 184 /** Adds element at end of queue. Used by both [add] and [addAll]. */ | 174 /// Adds element at end of queue. Used by both [add] and [addAll]. |
| 185 void _add(E element) { | 175 void _add(E element) { |
| 186 _table[_tail] = element; | 176 _table[_tail] = element; |
| 187 _tail = (_tail + 1) & (_table.length - 1); | 177 _tail = (_tail + 1) & (_table.length - 1); |
| 188 if (_head == _tail) _grow(); | 178 if (_head == _tail) _grow(); |
| 189 } | 179 } |
| 190 | 180 |
| 191 /** | 181 /// Grow the table when full. |
| 192 * Grow the table when full. | |
| 193 */ | |
| 194 void _grow() { | 182 void _grow() { |
| 195 List<E> newTable = new List<E>(_table.length * 2); | 183 List<E> newTable = new List<E>(_table.length * 2); |
| 196 int split = _table.length - _head; | 184 int split = _table.length - _head; |
| 197 newTable.setRange(0, split, _table, _head); | 185 newTable.setRange(0, split, _table, _head); |
| 198 newTable.setRange(split, split + _head, _table, 0); | 186 newTable.setRange(split, split + _head, _table, 0); |
| 199 _head = 0; | 187 _head = 0; |
| 200 _tail = _table.length; | 188 _tail = _table.length; |
| 201 _table = newTable; | 189 _table = newTable; |
| 202 } | 190 } |
| 203 | 191 |
| 204 int _writeToList(List<E> target) { | 192 int _writeToList(List<E> target) { |
| 205 assert(target.length >= length); | 193 assert(target.length >= length); |
| 206 if (_head <= _tail) { | 194 if (_head <= _tail) { |
| 207 int length = _tail - _head; | 195 int length = _tail - _head; |
| 208 target.setRange(0, length, _table, _head); | 196 target.setRange(0, length, _table, _head); |
| 209 return length; | 197 return length; |
| 210 } else { | 198 } else { |
| 211 int firstPartSize = _table.length - _head; | 199 int firstPartSize = _table.length - _head; |
| 212 target.setRange(0, firstPartSize, _table, _head); | 200 target.setRange(0, firstPartSize, _table, _head); |
| 213 target.setRange(firstPartSize, firstPartSize + _tail, _table, 0); | 201 target.setRange(firstPartSize, firstPartSize + _tail, _table, 0); |
| 214 return _tail + firstPartSize; | 202 return _tail + firstPartSize; |
| 215 } | 203 } |
| 216 } | 204 } |
| 217 | 205 |
| 218 /** Grows the table even if it is not full. */ | 206 /// Grows the table even if it is not full. |
| 219 void _preGrow(int newElementCount) { | 207 void _preGrow(int newElementCount) { |
| 220 assert(newElementCount >= length); | 208 assert(newElementCount >= length); |
| 221 | 209 |
| 222 // Add 1.5x extra room to ensure that there's room for more elements after | 210 // Add 1.5x extra room to ensure that there's room for more elements after |
| 223 // expansion. | 211 // expansion. |
| 224 newElementCount += newElementCount >> 1; | 212 newElementCount += newElementCount >> 1; |
| 225 int newCapacity = _nextPowerOf2(newElementCount); | 213 int newCapacity = _nextPowerOf2(newElementCount); |
| 226 List<E> newTable = new List<E>(newCapacity); | 214 List<E> newTable = new List<E>(newCapacity); |
| 227 _tail = _writeToList(newTable); | 215 _tail = _writeToList(newTable); |
| 228 _table = newTable; | 216 _table = newTable; |
| 229 _head = 0; | 217 _head = 0; |
| 230 } | 218 } |
| 231 } | 219 } |
| OLD | NEW |