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 |