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

Side by Side Diff: lib/src/queue_list.dart

Issue 1638163002: Modernize the package's style. (Closed) Base URL: git@github.com:dart-lang/collection@master
Patch Set: Code review changes Created 4 years, 10 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
« no previous file with comments | « lib/src/priority_queue.dart ('k') | lib/src/unmodifiable_wrappers.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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 }
OLDNEW
« no previous file with comments | « lib/src/priority_queue.dart ('k') | lib/src/unmodifiable_wrappers.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698