| OLD | NEW |
| 1 part of dart.collection; | 1 part of dart.collection; |
| 2 abstract class Queue<E> implements Iterable<E>, EfficientLength {factory Queue(
) = ListQueue<E>; | 2 abstract class Queue<E> implements Iterable<E>, EfficientLength {factory Queue(
) = ListQueue<E>; |
| 3 factory Queue.from(Iterable elements) = ListQueue<E>.from; | 3 factory Queue.from(Iterable elements) = ListQueue<E>.from; |
| 4 E removeFirst(); | 4 E removeFirst(); |
| 5 E removeLast(); | 5 E removeLast(); |
| 6 void addFirst(E value); | 6 void addFirst(E value); |
| 7 void addLast(E value); | 7 void addLast(E value); |
| 8 void add(E value); | 8 void add(E value); |
| 9 bool remove(Object object); | 9 bool remove(Object object); |
| 10 void addAll(Iterable<E> iterable); | 10 void addAll(Iterable<E> iterable); |
| (...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 44 DoubleLinkedQueueEntry<E> nextEntry() { | 44 DoubleLinkedQueueEntry<E> nextEntry() { |
| 45 return _next._asNonSentinelEntry(); | 45 return _next._asNonSentinelEntry(); |
| 46 } | 46 } |
| 47 E get element { | 47 E get element { |
| 48 return _element; | 48 return _element; |
| 49 } | 49 } |
| 50 void set element(E e) { | 50 void set element(E e) { |
| 51 _element = e; | 51 _element = e; |
| 52 } | 52 } |
| 53 } | 53 } |
| 54 class _DoubleLinkedQueueEntrySentinel<E> extends DoubleLinkedQueueEntry<E> {_Do
ubleLinkedQueueEntrySentinel() : super(((__x32) => DDC$RT.cast(__x32, Null, E, "
CastLiteral", """line 164, column 45 of dart:collection/queue.dart: """, __x32 i
s E, false))(null)) { | 54 class _DoubleLinkedQueueEntrySentinel<E> extends DoubleLinkedQueueEntry<E> {_Do
ubleLinkedQueueEntrySentinel() : super(((__x38) => DDC$RT.cast(__x38, Null, E, "
CastLiteral", """line 164, column 45 of dart:collection/queue.dart: """, __x38 i
s E, false))(null)) { |
| 55 _link(this, this); | 55 _link(this, this); |
| 56 } | 56 } |
| 57 E remove() { | 57 E remove() { |
| 58 throw IterableElementError.noElement(); | 58 throw IterableElementError.noElement(); |
| 59 } | 59 } |
| 60 DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { | 60 DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { |
| 61 return null; | 61 return null; |
| 62 } | 62 } |
| 63 void set element(E e) { | 63 void set element(E e) { |
| 64 assert (false);} | 64 assert (false);} |
| 65 E get element { | 65 E get element { |
| 66 throw IterableElementError.noElement(); | 66 throw IterableElementError.noElement(); |
| 67 } | 67 } |
| 68 } | 68 } |
| 69 class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> {_Double
LinkedQueueEntrySentinel<E> _sentinel; | 69 class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> {_Double
LinkedQueueEntrySentinel<E> _sentinel; |
| 70 int _elementCount = 0; | 70 int _elementCount = 0; |
| 71 DoubleLinkedQueue() { | 71 DoubleLinkedQueue() { |
| 72 _sentinel = new _DoubleLinkedQueueEntrySentinel<E>(); | 72 _sentinel = new _DoubleLinkedQueueEntrySentinel<E>(); |
| 73 } | 73 } |
| 74 factory DoubleLinkedQueue.from(Iterable elements) { | 74 factory DoubleLinkedQueue.from(Iterable elements) { |
| 75 Queue<E> list = ((__x33) => DDC$RT.cast(__x33, DDC$RT.type((DoubleLinkedQueue<dy
namic> _) { | 75 Queue<E> list = ((__x39) => DDC$RT.cast(__x39, DDC$RT.type((DoubleLinkedQueue<dy
namic> _) { |
| 76 } | 76 } |
| 77 ), DDC$RT.type((Queue<E> _) { | 77 ), DDC$RT.type((Queue<E> _) { |
| 78 } | 78 } |
| 79 ), "CastExact", """line 207, column 21 of dart:collection/queue.dart: """, __x33
is Queue<E>, false))(new DoubleLinkedQueue()); | 79 ), "CastExact", """line 207, column 21 of dart:collection/queue.dart: """, __x39
is Queue<E>, false))(new DoubleLinkedQueue()); |
| 80 for (final E e in elements) { | 80 for (final E e in elements) { |
| 81 list.addLast(e); | 81 list.addLast(e); |
| 82 } | 82 } |
| 83 return DDC$RT.cast(list, DDC$RT.type((Queue<E> _) { | 83 return DDC$RT.cast(list, DDC$RT.type((Queue<E> _) { |
| 84 } | 84 } |
| 85 ), DDC$RT.type((DoubleLinkedQueue<E> _) { | 85 ), DDC$RT.type((DoubleLinkedQueue<E> _) { |
| 86 } | 86 } |
| 87 ), "CastGeneral", """line 211, column 12 of dart:collection/queue.dart: """, lis
t is DoubleLinkedQueue<E>, false); | 87 ), "CastGeneral", """line 211, column 12 of dart:collection/queue.dart: """, lis
t is DoubleLinkedQueue<E>, false); |
| 88 } | 88 } |
| 89 int get length => _elementCount; | 89 int get length => _elementCount; |
| (...skipping 96 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 186 class _DoubleLinkedQueueIterator<E> implements Iterator<E> {_DoubleLinkedQueueE
ntrySentinel<E> _sentinel; | 186 class _DoubleLinkedQueueIterator<E> implements Iterator<E> {_DoubleLinkedQueueE
ntrySentinel<E> _sentinel; |
| 187 DoubleLinkedQueueEntry<E> _nextEntry = null; | 187 DoubleLinkedQueueEntry<E> _nextEntry = null; |
| 188 E _current; | 188 E _current; |
| 189 _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel<E> sentinel) : _sent
inel = sentinel, _nextEntry = sentinel._next; | 189 _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel<E> sentinel) : _sent
inel = sentinel, _nextEntry = sentinel._next; |
| 190 bool moveNext() { | 190 bool moveNext() { |
| 191 if (!identical(_nextEntry, _sentinel)) { | 191 if (!identical(_nextEntry, _sentinel)) { |
| 192 _current = _nextEntry._element; | 192 _current = _nextEntry._element; |
| 193 _nextEntry = _nextEntry._next; | 193 _nextEntry = _nextEntry._next; |
| 194 return true; | 194 return true; |
| 195 } | 195 } |
| 196 _current = ((__x34) => DDC$RT.cast(__x34, Null, E, "CastLiteral", """line 348,
column 16 of dart:collection/queue.dart: """, __x34 is E, false))(null); | 196 _current = ((__x40) => DDC$RT.cast(__x40, Null, E, "CastLiteral", """line 348,
column 16 of dart:collection/queue.dart: """, __x40 is E, false))(null); |
| 197 _nextEntry = _sentinel = null; | 197 _nextEntry = _sentinel = null; |
| 198 return false; | 198 return false; |
| 199 } | 199 } |
| 200 E get current => _current; | 200 E get current => _current; |
| 201 } | 201 } |
| 202 class ListQueue<E> extends IterableBase<E> implements Queue<E> {static const in
t _INITIAL_CAPACITY = 8; | 202 class ListQueue<E> extends IterableBase<E> implements Queue<E> {static const in
t _INITIAL_CAPACITY = 8; |
| 203 List<E> _table; | 203 List<E> _table; |
| 204 int _head; | 204 int _head; |
| 205 int _tail; | 205 int _tail; |
| 206 int _modificationCount = 0; | 206 int _modificationCount = 0; |
| 207 ListQueue([int initialCapacity]) : _head = 0, _tail = 0 { | 207 ListQueue([int initialCapacity]) : _head = 0, _tail = 0 { |
| 208 if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) { | 208 if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) { |
| 209 initialCapacity = _INITIAL_CAPACITY; | 209 initialCapacity = _INITIAL_CAPACITY; |
| 210 } | 210 } |
| 211 else if (!_isPowerOf2(initialCapacity)) { | 211 else if (!_isPowerOf2(initialCapacity)) { |
| 212 initialCapacity = _nextPowerOf2(initialCapacity); | 212 initialCapacity = _nextPowerOf2(initialCapacity); |
| 213 } | 213 } |
| 214 assert (_isPowerOf2(initialCapacity)); _table = new List<E>(initialCapacity); | 214 assert (_isPowerOf2(initialCapacity)); _table = new List<E>(initialCapacity); |
| 215 } | 215 } |
| 216 factory ListQueue.from(Iterable elements) { | 216 factory ListQueue.from(Iterable elements) { |
| 217 if (elements is List) { | 217 if (elements is List) { |
| 218 int length = elements.length; | 218 int length = elements.length; |
| 219 ListQueue<E> queue = ((__x35) => DDC$RT.cast(__x35, DDC$RT.type((ListQueue<dyna
mic> _) { | 219 ListQueue<E> queue = ((__x41) => DDC$RT.cast(__x41, DDC$RT.type((ListQueue<dyna
mic> _) { |
| 220 } | 220 } |
| 221 ), DDC$RT.type((ListQueue<E> _) { | 221 ), DDC$RT.type((ListQueue<E> _) { |
| 222 } | 222 } |
| 223 ), "CastExact", """line 399, column 28 of dart:collection/queue.dart: """, __x35
is ListQueue<E>, false))(new ListQueue(length + 1)); | 223 ), "CastExact", """line 399, column 28 of dart:collection/queue.dart: """, __x41
is ListQueue<E>, false))(new ListQueue(length + 1)); |
| 224 assert (queue._table.length > length); List sourceList = elements; | 224 assert (queue._table.length > length); List sourceList = elements; |
| 225 queue._table.setRange(0, length, DDC$RT.cast(sourceList, DDC$RT.type((List<dyna
mic> _) { | 225 queue._table.setRange(0, length, DDC$RT.cast(sourceList, DDC$RT.type((List<dyna
mic> _) { |
| 226 } | 226 } |
| 227 ), DDC$RT.type((Iterable<E> _) { | 227 ), DDC$RT.type((Iterable<E> _) { |
| 228 } | 228 } |
| 229 ), "CastDynamic", """line 402, column 40 of dart:collection/queue.dart: """, sou
rceList is Iterable<E>, false), 0); | 229 ), "CastDynamic", """line 402, column 40 of dart:collection/queue.dart: """, sou
rceList is Iterable<E>, false), 0); |
| 230 queue._tail = length; | 230 queue._tail = length; |
| 231 return queue; | 231 return queue; |
| 232 } | 232 } |
| 233 else { | 233 else { |
| (...skipping 130 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 364 } | 364 } |
| 365 void removeWhere(bool test(E element)) { | 365 void removeWhere(bool test(E element)) { |
| 366 _filterWhere(test, true); | 366 _filterWhere(test, true); |
| 367 } | 367 } |
| 368 void retainWhere(bool test(E element)) { | 368 void retainWhere(bool test(E element)) { |
| 369 _filterWhere(test, false); | 369 _filterWhere(test, false); |
| 370 } | 370 } |
| 371 void clear() { | 371 void clear() { |
| 372 if (_head != _tail) { | 372 if (_head != _tail) { |
| 373 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { | 373 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { |
| 374 _table[i] = ((__x36) => DDC$RT.cast(__x36, Null, E, "CastLiteral", """line 553,
column 21 of dart:collection/queue.dart: """, __x36 is E, false))(null); | 374 _table[i] = ((__x42) => DDC$RT.cast(__x42, Null, E, "CastLiteral", """line 553,
column 21 of dart:collection/queue.dart: """, __x42 is E, false))(null); |
| 375 } | 375 } |
| 376 _head = _tail = 0; | 376 _head = _tail = 0; |
| 377 _modificationCount++; | 377 _modificationCount++; |
| 378 } | 378 } |
| 379 } | 379 } |
| 380 String toString() => IterableBase.iterableToFullString(this, "{", "}"); | 380 String toString() => IterableBase.iterableToFullString(this, "{", "}"); |
| 381 void addLast(E element) { | 381 void addLast(E element) { |
| 382 _add(element); | 382 _add(element); |
| 383 } | 383 } |
| 384 void addFirst(E element) { | 384 void addFirst(E element) { |
| 385 _head = (_head - 1) & (_table.length - 1); | 385 _head = (_head - 1) & (_table.length - 1); |
| 386 _table[_head] = element; | 386 _table[_head] = element; |
| 387 if (_head == _tail) _grow(); | 387 if (_head == _tail) _grow(); |
| 388 _modificationCount++; | 388 _modificationCount++; |
| 389 } | 389 } |
| 390 E removeFirst() { | 390 E removeFirst() { |
| 391 if (_head == _tail) throw IterableElementError.noElement(); | 391 if (_head == _tail) throw IterableElementError.noElement(); |
| 392 _modificationCount++; | 392 _modificationCount++; |
| 393 E result = _table[_head]; | 393 E result = _table[_head]; |
| 394 _table[_head] = ((__x37) => DDC$RT.cast(__x37, Null, E, "CastLiteral", """line
577, column 21 of dart:collection/queue.dart: """, __x37 is E, false))(null); | 394 _table[_head] = ((__x43) => DDC$RT.cast(__x43, Null, E, "CastLiteral", """line
577, column 21 of dart:collection/queue.dart: """, __x43 is E, false))(null); |
| 395 _head = (_head + 1) & (_table.length - 1); | 395 _head = (_head + 1) & (_table.length - 1); |
| 396 return result; | 396 return result; |
| 397 } | 397 } |
| 398 E removeLast() { | 398 E removeLast() { |
| 399 if (_head == _tail) throw IterableElementError.noElement(); | 399 if (_head == _tail) throw IterableElementError.noElement(); |
| 400 _modificationCount++; | 400 _modificationCount++; |
| 401 _tail = (_tail - 1) & (_table.length - 1); | 401 _tail = (_tail - 1) & (_table.length - 1); |
| 402 E result = _table[_tail]; | 402 E result = _table[_tail]; |
| 403 _table[_tail] = ((__x38) => DDC$RT.cast(__x38, Null, E, "CastLiteral", """line
587, column 21 of dart:collection/queue.dart: """, __x38 is E, false))(null); | 403 _table[_tail] = ((__x44) => DDC$RT.cast(__x44, Null, E, "CastLiteral", """line
587, column 21 of dart:collection/queue.dart: """, __x44 is E, false))(null); |
| 404 return result; | 404 return result; |
| 405 } | 405 } |
| 406 static bool _isPowerOf2(int number) => (number & (number - 1)) == 0; | 406 static bool _isPowerOf2(int number) => (number & (number - 1)) == 0; |
| 407 static int _nextPowerOf2(int number) { | 407 static int _nextPowerOf2(int number) { |
| 408 assert (number > 0); number = (number << 1) - 1; | 408 assert (number > 0); number = (number << 1) - 1; |
| 409 for (;;) { | 409 for (;;) { |
| 410 int nextNumber = number & (number - 1); | 410 int nextNumber = number & (number - 1); |
| 411 if (nextNumber == 0) return number; | 411 if (nextNumber == 0) return number; |
| 412 number = nextNumber; | 412 number = nextNumber; |
| 413 } | 413 } |
| (...skipping 13 matching lines...) Expand all Loading... |
| 427 int mask = _table.length - 1; | 427 int mask = _table.length - 1; |
| 428 int startDistance = (offset - _head) & mask; | 428 int startDistance = (offset - _head) & mask; |
| 429 int endDistance = (_tail - offset) & mask; | 429 int endDistance = (_tail - offset) & mask; |
| 430 if (startDistance < endDistance) { | 430 if (startDistance < endDistance) { |
| 431 int i = offset; | 431 int i = offset; |
| 432 while (i != _head) { | 432 while (i != _head) { |
| 433 int prevOffset = (i - 1) & mask; | 433 int prevOffset = (i - 1) & mask; |
| 434 _table[i] = _table[prevOffset]; | 434 _table[i] = _table[prevOffset]; |
| 435 i = prevOffset; | 435 i = prevOffset; |
| 436 } | 436 } |
| 437 _table[_head] = ((__x39) => DDC$RT.cast(__x39, Null, E, "CastLiteral", """line
654, column 23 of dart:collection/queue.dart: """, __x39 is E, false))(null); | 437 _table[_head] = ((__x45) => DDC$RT.cast(__x45, Null, E, "CastLiteral", """line
654, column 23 of dart:collection/queue.dart: """, __x45 is E, false))(null); |
| 438 _head = (_head + 1) & mask; | 438 _head = (_head + 1) & mask; |
| 439 return (offset + 1) & mask; | 439 return (offset + 1) & mask; |
| 440 } | 440 } |
| 441 else { | 441 else { |
| 442 _tail = (_tail - 1) & mask; | 442 _tail = (_tail - 1) & mask; |
| 443 int i = offset; | 443 int i = offset; |
| 444 while (i != _tail) { | 444 while (i != _tail) { |
| 445 int nextOffset = (i + 1) & mask; | 445 int nextOffset = (i + 1) & mask; |
| 446 _table[i] = _table[nextOffset]; | 446 _table[i] = _table[nextOffset]; |
| 447 i = nextOffset; | 447 i = nextOffset; |
| 448 } | 448 } |
| 449 _table[_tail] = ((__x40) => DDC$RT.cast(__x40, Null, E, "CastLiteral", """line
665, column 23 of dart:collection/queue.dart: """, __x40 is E, false))(null); | 449 _table[_tail] = ((__x46) => DDC$RT.cast(__x46, Null, E, "CastLiteral", """line
665, column 23 of dart:collection/queue.dart: """, __x46 is E, false))(null); |
| 450 return offset; | 450 return offset; |
| 451 } | 451 } |
| 452 } | 452 } |
| 453 void _grow() { | 453 void _grow() { |
| 454 List<E> newTable = new List<E>(_table.length * 2); | 454 List<E> newTable = new List<E>(_table.length * 2); |
| 455 int split = _table.length - _head; | 455 int split = _table.length - _head; |
| 456 newTable.setRange(0, split, _table, _head); | 456 newTable.setRange(0, split, _table, _head); |
| 457 newTable.setRange(split, split + _head, _table, 0); | 457 newTable.setRange(split, split + _head, _table, 0); |
| 458 _head = 0; | 458 _head = 0; |
| 459 _tail = _table.length; | 459 _tail = _table.length; |
| (...skipping 24 matching lines...) Expand all Loading... |
| 484 class _ListQueueIterator<E> implements Iterator<E> {final ListQueue _queue; | 484 class _ListQueueIterator<E> implements Iterator<E> {final ListQueue _queue; |
| 485 final int _end; | 485 final int _end; |
| 486 final int _modificationCount; | 486 final int _modificationCount; |
| 487 int _position; | 487 int _position; |
| 488 E _current; | 488 E _current; |
| 489 _ListQueueIterator(ListQueue queue) : _queue = queue, _end = queue._tail, _modi
ficationCount = queue._modificationCount, _position = queue._head; | 489 _ListQueueIterator(ListQueue queue) : _queue = queue, _end = queue._tail, _modi
ficationCount = queue._modificationCount, _position = queue._head; |
| 490 E get current => _current; | 490 E get current => _current; |
| 491 bool moveNext() { | 491 bool moveNext() { |
| 492 _queue._checkModification(_modificationCount); | 492 _queue._checkModification(_modificationCount); |
| 493 if (_position == _end) { | 493 if (_position == _end) { |
| 494 _current = ((__x41) => DDC$RT.cast(__x41, Null, E, "CastLiteral", """line 735, c
olumn 18 of dart:collection/queue.dart: """, __x41 is E, false))(null); | 494 _current = ((__x47) => DDC$RT.cast(__x47, Null, E, "CastLiteral", """line 735, c
olumn 18 of dart:collection/queue.dart: """, __x47 is E, false))(null); |
| 495 return false; | 495 return false; |
| 496 } | 496 } |
| 497 _current = ((__x42) => DDC$RT.cast(__x42, dynamic, E, "CastGeneral", """line 73
8, column 16 of dart:collection/queue.dart: """, __x42 is E, false))(_queue._tab
le[_position]); | 497 _current = ((__x48) => DDC$RT.cast(__x48, dynamic, E, "CastGeneral", """line 73
8, column 16 of dart:collection/queue.dart: """, __x48 is E, false))(_queue._tab
le[_position]); |
| 498 _position = (_position + 1) & (_queue._table.length - 1); | 498 _position = (_position + 1) & (_queue._table.length - 1); |
| 499 return true; | 499 return true; |
| 500 } | 500 } |
| 501 } | 501 } |
| OLD | NEW |