| OLD | NEW |
|---|
| (Empty) |
| 1 part of dart.collection; | |
| 2 abstract class Queue<E> implements Iterable<E>, EfficientLength {factory Queue(
) = ListQueue<E>; | |
| 3 factory Queue.from(Iterable elements) = ListQueue<E>.from; | |
| 4 E removeFirst(); | |
| 5 E removeLast(); | |
| 6 void addFirst(E value); | |
| 7 void addLast(E value); | |
| 8 void add(E value); | |
| 9 bool remove(Object object); | |
| 10 void addAll(Iterable<E> iterable); | |
| 11 void removeWhere(bool test(E element)); | |
| 12 void retainWhere(bool test(E element)); | |
| 13 void clear(); | |
| 14 } | |
| 15 class DoubleLinkedQueueEntry<E> {DoubleLinkedQueueEntry<E> _previous; | |
| 16 DoubleLinkedQueueEntry<E> _next; | |
| 17 E _element; | |
| 18 DoubleLinkedQueueEntry(E e) : _element = e; | |
| 19 void _link(DoubleLinkedQueueEntry<E> previous, DoubleLinkedQueueEntry<E> next)
{ | |
| 20 _next = next; | |
| 21 _previous = previous; | |
| 22 previous._next = this; | |
| 23 next._previous = this; | |
| 24 } | |
| 25 void append(E e) { | |
| 26 new DoubleLinkedQueueEntry<E>(e)._link(this, _next); | |
| 27 } | |
| 28 void prepend(E e) { | |
| 29 new DoubleLinkedQueueEntry<E>(e)._link(_previous, this); | |
| 30 } | |
| 31 E remove() { | |
| 32 _previous._next = _next; | |
| 33 _next._previous = _previous; | |
| 34 _next = null; | |
| 35 _previous = null; | |
| 36 return _element; | |
| 37 } | |
| 38 DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { | |
| 39 return this; | |
| 40 } | |
| 41 DoubleLinkedQueueEntry<E> previousEntry() { | |
| 42 return _previous._asNonSentinelEntry(); | |
| 43 } | |
| 44 DoubleLinkedQueueEntry<E> nextEntry() { | |
| 45 return _next._asNonSentinelEntry(); | |
| 46 } | |
| 47 E get element { | |
| 48 return _element; | |
| 49 } | |
| 50 void set element(E e) { | |
| 51 _element = e; | |
| 52 } | |
| 53 } | |
| 54 class _DoubleLinkedQueueEntrySentinel<E> extends DoubleLinkedQueueEntry<E> {_Do
ubleLinkedQueueEntrySentinel() : super(null) { | |
| 55 _link(this, this); | |
| 56 } | |
| 57 E remove() { | |
| 58 throw IterableElementError.noElement(); | |
| 59 } | |
| 60 DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { | |
| 61 return null; | |
| 62 } | |
| 63 void set element(E e) { | |
| 64 assert (false);} | |
| 65 E get element { | |
| 66 throw IterableElementError.noElement(); | |
| 67 } | |
| 68 } | |
| 69 class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> {_Double
LinkedQueueEntrySentinel<E> _sentinel; | |
| 70 int _elementCount = 0; | |
| 71 DoubleLinkedQueue() { | |
| 72 _sentinel = new _DoubleLinkedQueueEntrySentinel<E>(); | |
| 73 } | |
| 74 factory DoubleLinkedQueue.from(Iterable elements) { | |
| 75 Queue<E> list = new DoubleLinkedQueue<E>(); | |
| 76 for (final E e in DEVC$RT.cast(elements, DEVC$RT.type((Iterable<dynamic> _) { | |
| 77 } | |
| 78 ), DEVC$RT.type((Iterable<E> _) { | |
| 79 } | |
| 80 ), "CompositeCast", """line 208, column 23 of dart:collection/queue.dart: """, e
lements is Iterable<E>, false)) { | |
| 81 list.addLast(e); | |
| 82 } | |
| 83 return DEVC$RT.cast(list, DEVC$RT.type((Queue<E> _) { | |
| 84 } | |
| 85 ), DEVC$RT.type((DoubleLinkedQueue<E> _) { | |
| 86 } | |
| 87 ), "CompositeCast", """line 211, column 12 of dart:collection/queue.dart: """, l
ist is DoubleLinkedQueue<E>, false); | |
| 88 } | |
| 89 int get length => _elementCount; | |
| 90 void addLast(E value) { | |
| 91 _sentinel.prepend(value); | |
| 92 _elementCount++; | |
| 93 } | |
| 94 void addFirst(E value) { | |
| 95 _sentinel.append(value); | |
| 96 _elementCount++; | |
| 97 } | |
| 98 void add(E value) { | |
| 99 _sentinel.prepend(value); | |
| 100 _elementCount++; | |
| 101 } | |
| 102 void addAll(Iterable<E> iterable) { | |
| 103 for (final E value in iterable) { | |
| 104 _sentinel.prepend(value); | |
| 105 _elementCount++; | |
| 106 } | |
| 107 } | |
| 108 E removeLast() { | |
| 109 E result = _sentinel._previous.remove(); | |
| 110 _elementCount--; | |
| 111 return result; | |
| 112 } | |
| 113 E removeFirst() { | |
| 114 E result = _sentinel._next.remove(); | |
| 115 _elementCount--; | |
| 116 return result; | |
| 117 } | |
| 118 bool remove(Object o) { | |
| 119 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | |
| 120 while (!identical(entry, _sentinel)) { | |
| 121 if (entry.element == o) { | |
| 122 entry.remove(); | |
| 123 _elementCount--; | |
| 124 return true; | |
| 125 } | |
| 126 entry = entry._next; | |
| 127 } | |
| 128 return false; | |
| 129 } | |
| 130 void _filter(bool test(E element), bool removeMatching) { | |
| 131 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | |
| 132 while (!identical(entry, _sentinel)) { | |
| 133 DoubleLinkedQueueEntry<E> next = entry._next; | |
| 134 if (identical(removeMatching, test(entry.element))) { | |
| 135 entry.remove(); | |
| 136 _elementCount--; | |
| 137 } | |
| 138 entry = next; | |
| 139 } | |
| 140 } | |
| 141 void removeWhere(bool test(E element)) { | |
| 142 _filter(test, true); | |
| 143 } | |
| 144 void retainWhere(bool test(E element)) { | |
| 145 _filter(test, false); | |
| 146 } | |
| 147 E get first { | |
| 148 return _sentinel._next.element; | |
| 149 } | |
| 150 E get last { | |
| 151 return _sentinel._previous.element; | |
| 152 } | |
| 153 E get single { | |
| 154 if (identical(_sentinel._next, _sentinel._previous)) { | |
| 155 return _sentinel._next.element; | |
| 156 } | |
| 157 throw IterableElementError.tooMany(); | |
| 158 } | |
| 159 DoubleLinkedQueueEntry<E> lastEntry() { | |
| 160 return _sentinel.previousEntry(); | |
| 161 } | |
| 162 DoubleLinkedQueueEntry<E> firstEntry() { | |
| 163 return _sentinel.nextEntry(); | |
| 164 } | |
| 165 bool get isEmpty { | |
| 166 return (identical(_sentinel._next, _sentinel)); | |
| 167 } | |
| 168 void clear() { | |
| 169 _sentinel._next = _sentinel; | |
| 170 _sentinel._previous = _sentinel; | |
| 171 _elementCount = 0; | |
| 172 } | |
| 173 void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) { | |
| 174 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | |
| 175 while (!identical(entry, _sentinel)) { | |
| 176 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | |
| 177 f(entry); | |
| 178 entry = nextEntry; | |
| 179 } | |
| 180 } | |
| 181 _DoubleLinkedQueueIterator<E> get iterator { | |
| 182 return new _DoubleLinkedQueueIterator<E>(_sentinel); | |
| 183 } | |
| 184 String toString() => IterableBase.iterableToFullString(this, '{', '}'); | |
| 185 } | |
| 186 class _DoubleLinkedQueueIterator<E> implements Iterator<E> {_DoubleLinkedQueueE
ntrySentinel<E> _sentinel; | |
| 187 DoubleLinkedQueueEntry<E> _nextEntry = null; | |
| 188 E _current; | |
| 189 _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel<E> sentinel) : _sent
inel = sentinel, _nextEntry = sentinel._next; | |
| 190 bool moveNext() { | |
| 191 if (!identical(_nextEntry, _sentinel)) { | |
| 192 _current = _nextEntry._element; | |
| 193 _nextEntry = _nextEntry._next; | |
| 194 return true; | |
| 195 } | |
| 196 _current = null; | |
| 197 _nextEntry = _sentinel = null; | |
| 198 return false; | |
| 199 } | |
| 200 E get current => _current; | |
| 201 } | |
| 202 class ListQueue<E> extends IterableBase<E> implements Queue<E> {static const in
t _INITIAL_CAPACITY = 8; | |
| 203 List<E> _table; | |
| 204 int _head; | |
| 205 int _tail; | |
| 206 int _modificationCount = 0; | |
| 207 ListQueue([int initialCapacity]) : _head = 0, _tail = 0 { | |
| 208 if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) { | |
| 209 initialCapacity = _INITIAL_CAPACITY; | |
| 210 } | |
| 211 else if (!_isPowerOf2(initialCapacity)) { | |
| 212 initialCapacity = _nextPowerOf2(initialCapacity); | |
| 213 } | |
| 214 assert (_isPowerOf2(initialCapacity)); _table = new List<E>(initialCapacity); | |
| 215 } | |
| 216 factory ListQueue.from(Iterable elements) { | |
| 217 if (elements is List) { | |
| 218 int length = elements.length; | |
| 219 ListQueue<E> queue = new ListQueue<E>(length + 1); | |
| 220 assert (queue._table.length > length); List sourceList = elements; | |
| 221 queue._table.setRange(0, length, DEVC$RT.cast(sourceList, DEVC$RT.type((List<dy
namic> _) { | |
| 222 } | |
| 223 ), DEVC$RT.type((Iterable<E> _) { | |
| 224 } | |
| 225 ), "CompositeCast", """line 402, column 40 of dart:collection/queue.dart: """, s
ourceList is Iterable<E>, false), 0); | |
| 226 queue._tail = length; | |
| 227 return queue; | |
| 228 } | |
| 229 else { | |
| 230 int capacity = _INITIAL_CAPACITY; | |
| 231 if (elements is EfficientLength) { | |
| 232 capacity = elements.length; | |
| 233 } | |
| 234 ListQueue<E> result = new ListQueue<E>(capacity); | |
| 235 for (final E element in DEVC$RT.cast(elements, DEVC$RT.type((Iterable<dynamic>
_) { | |
| 236 } | |
| 237 ), DEVC$RT.type((Iterable<E> _) { | |
| 238 } | |
| 239 ), "CompositeCast", """line 411, column 31 of dart:collection/queue.dart: """, e
lements is Iterable<E>, false)) { | |
| 240 result.addLast(element); | |
| 241 } | |
| 242 return result; | |
| 243 } | |
| 244 } | |
| 245 Iterator<E> get iterator => new _ListQueueIterator<E>(this); | |
| 246 void forEach(void action(E element)) { | |
| 247 int modificationCount = _modificationCount; | |
| 248 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { | |
| 249 action(_table[i]); | |
| 250 _checkModification(modificationCount); | |
| 251 } | |
| 252 } | |
| 253 bool get isEmpty => _head == _tail; | |
| 254 int get length => (_tail - _head) & (_table.length - 1); | |
| 255 E get first { | |
| 256 if (_head == _tail) throw IterableElementError.noElement(); | |
| 257 return _table[_head]; | |
| 258 } | |
| 259 E get last { | |
| 260 if (_head == _tail) throw IterableElementError.noElement(); | |
| 261 return _table[(_tail - 1) & (_table.length - 1)]; | |
| 262 } | |
| 263 E get single { | |
| 264 if (_head == _tail) throw IterableElementError.noElement(); | |
| 265 if (length > 1) throw IterableElementError.tooMany(); | |
| 266 return _table[_head]; | |
| 267 } | |
| 268 E elementAt(int index) { | |
| 269 RangeError.checkValidIndex(index, this); | |
| 270 return _table[(_head + index) & (_table.length - 1)]; | |
| 271 } | |
| 272 List<E> toList({ | |
| 273 bool growable : true} | |
| 274 ) { | |
| 275 List<E> list; | |
| 276 if (growable) { | |
| 277 list = new List<E>()..length = length; | |
| 278 } | |
| 279 else { | |
| 280 list = new List<E>(length); | |
| 281 } | |
| 282 _writeToList(list); | |
| 283 return list; | |
| 284 } | |
| 285 void add(E element) { | |
| 286 _add(element); | |
| 287 } | |
| 288 void addAll(Iterable<E> elements) { | |
| 289 if (elements is List) { | |
| 290 List list = DEVC$RT.cast(elements, DEVC$RT.type((Iterable<E> _) { | |
| 291 } | |
| 292 ), DEVC$RT.type((List<dynamic> _) { | |
| 293 } | |
| 294 ), "AssignmentCast", """line 474, column 19 of dart:collection/queue.dart: """,
elements is List<dynamic>, true); | |
| 295 int addCount = list.length; | |
| 296 int length = this.length; | |
| 297 if (length + addCount >= _table.length) { | |
| 298 _preGrow(length + addCount); | |
| 299 _table.setRange(length, length + addCount, DEVC$RT.cast(list, DEVC$RT.type((Lis
t<dynamic> _) { | |
| 300 } | |
| 301 ), DEVC$RT.type((Iterable<E> _) { | |
| 302 } | |
| 303 ), "CompositeCast", """line 480, column 52 of dart:collection/queue.dart: """, l
ist is Iterable<E>, false), 0); | |
| 304 _tail += addCount; | |
| 305 } | |
| 306 else { | |
| 307 int endSpace = _table.length - _tail; | |
| 308 if (addCount < endSpace) { | |
| 309 _table.setRange(_tail, _tail + addCount, DEVC$RT.cast(list, DEVC$RT.type((List<d
ynamic> _) { | |
| 310 } | |
| 311 ), DEVC$RT.type((Iterable<E> _) { | |
| 312 } | |
| 313 ), "CompositeCast", """line 486, column 52 of dart:collection/queue.dart: """, l
ist is Iterable<E>, false), 0); | |
| 314 _tail += addCount; | |
| 315 } | |
| 316 else { | |
| 317 int preSpace = addCount - endSpace; | |
| 318 _table.setRange(_tail, _tail + endSpace, DEVC$RT.cast(list, DEVC$RT.type((List<
dynamic> _) { | |
| 319 } | |
| 320 ), DEVC$RT.type((Iterable<E> _) { | |
| 321 } | |
| 322 ), "CompositeCast", """line 490, column 52 of dart:collection/queue.dart: """, l
ist is Iterable<E>, false), 0); | |
| 323 _table.setRange(0, preSpace, DEVC$RT.cast(list, DEVC$RT.type((List<dynamic> _)
{ | |
| 324 } | |
| 325 ), DEVC$RT.type((Iterable<E> _) { | |
| 326 } | |
| 327 ), "CompositeCast", """line 491, column 40 of dart:collection/queue.dart: """, l
ist is Iterable<E>, false), endSpace); | |
| 328 _tail = preSpace; | |
| 329 } | |
| 330 } | |
| 331 _modificationCount++; | |
| 332 } | |
| 333 else { | |
| 334 for (E element in elements) _add(element); | |
| 335 } | |
| 336 } | |
| 337 bool remove(Object object) { | |
| 338 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { | |
| 339 E element = _table[i]; | |
| 340 if (element == object) { | |
| 341 _remove(i); | |
| 342 _modificationCount++; | |
| 343 return true; | |
| 344 } | |
| 345 } | |
| 346 return false; | |
| 347 } | |
| 348 void _filterWhere(bool test(E element), bool removeMatching) { | |
| 349 int index = _head; | |
| 350 int modificationCount = _modificationCount; | |
| 351 int i = _head; | |
| 352 while (i != _tail) { | |
| 353 E element = _table[i]; | |
| 354 bool remove = identical(removeMatching, test(element)); | |
| 355 _checkModification(modificationCount); | |
| 356 if (remove) { | |
| 357 i = _remove(i); | |
| 358 modificationCount = ++_modificationCount; | |
| 359 } | |
| 360 else { | |
| 361 i = (i + 1) & (_table.length - 1); | |
| 362 } | |
| 363 } | |
| 364 } | |
| 365 void removeWhere(bool test(E element)) { | |
| 366 _filterWhere(test, true); | |
| 367 } | |
| 368 void retainWhere(bool test(E element)) { | |
| 369 _filterWhere(test, false); | |
| 370 } | |
| 371 void clear() { | |
| 372 if (_head != _tail) { | |
| 373 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { | |
| 374 _table[i] = null; | |
| 375 } | |
| 376 _head = _tail = 0; | |
| 377 _modificationCount++; | |
| 378 } | |
| 379 } | |
| 380 String toString() => IterableBase.iterableToFullString(this, "{", "}"); | |
| 381 void addLast(E element) { | |
| 382 _add(element); | |
| 383 } | |
| 384 void addFirst(E element) { | |
| 385 _head = (_head - 1) & (_table.length - 1); | |
| 386 _table[_head] = element; | |
| 387 if (_head == _tail) _grow(); | |
| 388 _modificationCount++; | |
| 389 } | |
| 390 E removeFirst() { | |
| 391 if (_head == _tail) throw IterableElementError.noElement(); | |
| 392 _modificationCount++; | |
| 393 E result = _table[_head]; | |
| 394 _table[_head] = null; | |
| 395 _head = (_head + 1) & (_table.length - 1); | |
| 396 return result; | |
| 397 } | |
| 398 E removeLast() { | |
| 399 if (_head == _tail) throw IterableElementError.noElement(); | |
| 400 _modificationCount++; | |
| 401 _tail = (_tail - 1) & (_table.length - 1); | |
| 402 E result = _table[_tail]; | |
| 403 _table[_tail] = null; | |
| 404 return result; | |
| 405 } | |
| 406 static bool _isPowerOf2(int number) => (number & (number - 1)) == 0; | |
| 407 static int _nextPowerOf2(int number) { | |
| 408 assert (number > 0); number = (number << 1) - 1; | |
| 409 for (;;) { | |
| 410 int nextNumber = number & (number - 1); | |
| 411 if (nextNumber == 0) return number; | |
| 412 number = nextNumber; | |
| 413 } | |
| 414 } | |
| 415 void _checkModification(int expectedModificationCount) { | |
| 416 if (expectedModificationCount != _modificationCount) { | |
| 417 throw new ConcurrentModificationError(this); | |
| 418 } | |
| 419 } | |
| 420 void _add(E element) { | |
| 421 _table[_tail] = element; | |
| 422 _tail = (_tail + 1) & (_table.length - 1); | |
| 423 if (_head == _tail) _grow(); | |
| 424 _modificationCount++; | |
| 425 } | |
| 426 int _remove(int offset) { | |
| 427 int mask = _table.length - 1; | |
| 428 int startDistance = (offset - _head) & mask; | |
| 429 int endDistance = (_tail - offset) & mask; | |
| 430 if (startDistance < endDistance) { | |
| 431 int i = offset; | |
| 432 while (i != _head) { | |
| 433 int prevOffset = (i - 1) & mask; | |
| 434 _table[i] = _table[prevOffset]; | |
| 435 i = prevOffset; | |
| 436 } | |
| 437 _table[_head] = null; | |
| 438 _head = (_head + 1) & mask; | |
| 439 return (offset + 1) & mask; | |
| 440 } | |
| 441 else { | |
| 442 _tail = (_tail - 1) & mask; | |
| 443 int i = offset; | |
| 444 while (i != _tail) { | |
| 445 int nextOffset = (i + 1) & mask; | |
| 446 _table[i] = _table[nextOffset]; | |
| 447 i = nextOffset; | |
| 448 } | |
| 449 _table[_tail] = null; | |
| 450 return offset; | |
| 451 } | |
| 452 } | |
| 453 void _grow() { | |
| 454 List<E> newTable = new List<E>(_table.length * 2); | |
| 455 int split = _table.length - _head; | |
| 456 newTable.setRange(0, split, _table, _head); | |
| 457 newTable.setRange(split, split + _head, _table, 0); | |
| 458 _head = 0; | |
| 459 _tail = _table.length; | |
| 460 _table = newTable; | |
| 461 } | |
| 462 int _writeToList(List<E> target) { | |
| 463 assert (target.length >= length); if (_head <= _tail) { | |
| 464 int length = _tail - _head; | |
| 465 target.setRange(0, length, _table, _head); | |
| 466 return length; | |
| 467 } | |
| 468 else { | |
| 469 int firstPartSize = _table.length - _head; | |
| 470 target.setRange(0, firstPartSize, _table, _head); | |
| 471 target.setRange(firstPartSize, firstPartSize + _tail, _table, 0); | |
| 472 return _tail + firstPartSize; | |
| 473 } | |
| 474 } | |
| 475 void _preGrow(int newElementCount) { | |
| 476 assert (newElementCount >= length); newElementCount += newElementCount >> 1; | |
| 477 int newCapacity = _nextPowerOf2(newElementCount); | |
| 478 List<E> newTable = new List<E>(newCapacity); | |
| 479 _tail = _writeToList(newTable); | |
| 480 _table = newTable; | |
| 481 _head = 0; | |
| 482 } | |
| 483 } | |
| 484 class _ListQueueIterator<E> implements Iterator<E> {final ListQueue _queue; | |
| 485 final int _end; | |
| 486 final int _modificationCount; | |
| 487 int _position; | |
| 488 E _current; | |
| 489 _ListQueueIterator(ListQueue queue) : _queue = queue, _end = queue._tail, _modi
ficationCount = queue._modificationCount, _position = queue._head; | |
| 490 E get current => _current; | |
| 491 bool moveNext() { | |
| 492 _queue._checkModification(_modificationCount); | |
| 493 if (_position == _end) { | |
| 494 _current = null; | |
| 495 return false; | |
| 496 } | |
| 497 _current = ((__x11) => DEVC$RT.cast(__x11, dynamic, E, "CompositeCast", """line
738, column 16 of dart:collection/queue.dart: """, __x11 is E, false))(_queue._
table[_position]); | |
| 498 _position = (_position + 1) & (_queue._table.length - 1); | |
| 499 return true; | |
| 500 } | |
| 501 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1148283010:
Remove dart backend (Closed)
Base URL: https://github.com/dart-lang/dev_compiler.git@master