| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | |
| 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. | |
| 4 | |
| 5 part of dart.collection; | |
| 6 | |
| 7 /** | |
| 8 * A [Queue] is a collection that can be manipulated at both ends. One | |
| 9 * can iterate over the elements of a queue through [forEach] or with | |
| 10 * an [Iterator]. | |
| 11 * | |
| 12 * It is generally not allowed to modify the queue (add or remove entries) while | |
| 13 * an operation on the queue is being performed, for example during a call to | |
| 14 * [forEach]. | |
| 15 * Modifying the queue while it is being iterated will most likely break the | |
| 16 * iteration. | |
| 17 * This goes both for using the [iterator] directly, or for iterating an | |
| 18 * `Iterable` returned by a method like [map] or [where]. | |
| 19 */ | |
| 20 abstract class Queue<E> implements Iterable<E>, EfficientLength { | |
| 21 | |
| 22 /** | |
| 23 * Creates a queue. | |
| 24 */ | |
| 25 factory Queue() = ListQueue<E>; | |
| 26 | |
| 27 /** | |
| 28 * Creates a queue containing all [elements]. | |
| 29 * | |
| 30 * The element order in the queue is as if the elements were added using | |
| 31 * [addLast] in the order provided by [elements.iterator]. | |
| 32 */ | |
| 33 factory Queue.from(Iterable elements) = ListQueue<E>.from; | |
| 34 | |
| 35 /** | |
| 36 * Removes and returns the first element of this queue. | |
| 37 * | |
| 38 * The queue must not be empty when this method is called. | |
| 39 */ | |
| 40 E removeFirst(); | |
| 41 | |
| 42 /** | |
| 43 * Removes and returns the last element of the queue. | |
| 44 * | |
| 45 * The queue must not be empty when this method is called. | |
| 46 */ | |
| 47 E removeLast(); | |
| 48 | |
| 49 /** | |
| 50 * Adds [value] at the beginning of the queue. | |
| 51 */ | |
| 52 void addFirst(E value); | |
| 53 | |
| 54 /** | |
| 55 * Adds [value] at the end of the queue. | |
| 56 */ | |
| 57 void addLast(E value); | |
| 58 | |
| 59 /** | |
| 60 * Adds [value] at the end of the queue. | |
| 61 */ | |
| 62 void add(E value); | |
| 63 | |
| 64 /** | |
| 65 * Remove a single instance of [value] from the queue. | |
| 66 * | |
| 67 * Returns `true` if a value was removed, or `false` if the queue | |
| 68 * contained no element equal to [value]. | |
| 69 */ | |
| 70 bool remove(Object value); | |
| 71 | |
| 72 /** | |
| 73 * Adds all elements of [iterable] at the end of the queue. The | |
| 74 * length of the queue is extended by the length of [iterable]. | |
| 75 */ | |
| 76 void addAll(Iterable<E> iterable); | |
| 77 | |
| 78 /** | |
| 79 * Removes all elements matched by [test] from the queue. | |
| 80 * | |
| 81 * The `test` function must not throw or modify the queue. | |
| 82 */ | |
| 83 void removeWhere(bool test(E element)); | |
| 84 | |
| 85 /** | |
| 86 * Removes all elements not matched by [test] from the queue. | |
| 87 * | |
| 88 * The `test` function must not throw or modify the queue. | |
| 89 */ | |
| 90 void retainWhere(bool test(E element)); | |
| 91 | |
| 92 /** | |
| 93 * Removes all elements in the queue. The size of the queue becomes zero. | |
| 94 */ | |
| 95 void clear(); | |
| 96 } | |
| 97 | |
| 98 | |
| 99 class _DoubleLink<E extends _DoubleLink> { | |
| 100 E _previousLink; | |
| 101 E _nextLink; | |
| 102 | |
| 103 void _link(E previous, E next) { | |
| 104 _nextLink = next; | |
| 105 _previousLink = previous; | |
| 106 if (previous != null) previous._nextLink = this; | |
| 107 if (next != null) next._previousLink = this; | |
| 108 } | |
| 109 | |
| 110 void _unlink() { | |
| 111 if (_previousLink != null) _previousLink._nextLink = _nextLink; | |
| 112 if (_nextLink != null) _nextLink._previousLink = _previousLink; | |
| 113 _nextLink = null; | |
| 114 _previousLink = null; | |
| 115 } | |
| 116 } | |
| 117 | |
| 118 /** | |
| 119 * An entry in a doubly linked list. It contains a pointer to the next | |
| 120 * entry, the previous entry, and the boxed element. | |
| 121 */ | |
| 122 abstract class DoubleLinkedQueueEntry<E> { | |
| 123 factory DoubleLinkedQueueEntry(E element) = _UserDoubleLinkedQueueEntry<E>; | |
| 124 | |
| 125 /// The element in the queue. | |
| 126 E get element; | |
| 127 | |
| 128 /// Appends the given [e] as entry just after this entry. | |
| 129 void append(E e); | |
| 130 | |
| 131 /// Prepends the given [e] as entry just before this entry. | |
| 132 void prepend(E e); | |
| 133 | |
| 134 /// Returns the previous entry or `null` if there is none. | |
| 135 DoubleLinkedQueueEntry<E> previousEntry(); | |
| 136 | |
| 137 /// Returns the next entry or `null` if there is none. | |
| 138 DoubleLinkedQueueEntry<E> nextEntry(); | |
| 139 } | |
| 140 | |
| 141 /// Default implementation of a doubly linked queue entry. | |
| 142 /// | |
| 143 /// This implementation is only used if a user instantiates a | |
| 144 /// [DoubleLinkedQueueEntry] directly. The internal implementations don't use | |
| 145 /// this class. | |
| 146 class _UserDoubleLinkedQueueEntry<E> | |
| 147 extends _DoubleLink<_UserDoubleLinkedQueueEntry<E>> | |
| 148 implements DoubleLinkedQueueEntry<E> { | |
| 149 E element; | |
| 150 | |
| 151 _UserDoubleLinkedQueueEntry(this.element); | |
| 152 | |
| 153 void append(E e) { | |
| 154 new _UserDoubleLinkedQueueEntry<E>(e)._link(this, _nextLink); | |
| 155 } | |
| 156 | |
| 157 void prepend(E e) { | |
| 158 new _UserDoubleLinkedQueueEntry<E>(e)._link(_previousLink, this); | |
| 159 } | |
| 160 | |
| 161 E remove() { | |
| 162 _unlink(); | |
| 163 return element; | |
| 164 } | |
| 165 | |
| 166 DoubleLinkedQueueEntry<E> previousEntry() => _previousLink; | |
| 167 | |
| 168 DoubleLinkedQueueEntry<E> nextEntry() => _nextLink; | |
| 169 } | |
| 170 | |
| 171 /** | |
| 172 * Interface for the link classes used by [DoubleLinkedQueue]. | |
| 173 * | |
| 174 * Both the [_DoubleLinkedQueueElement] and [_DoubleLinkedQueueSentinel] | |
| 175 * implement this interface. | |
| 176 * The entry contains a link back to the queue, so calling `append` | |
| 177 * or `prepend` can correctly update the element count. | |
| 178 */ | |
| 179 abstract class _DoubleLinkedQueueEntry<E> | |
| 180 extends _DoubleLink<_DoubleLinkedQueueEntry<E>> { | |
| 181 DoubleLinkedQueue<E> _queue; | |
| 182 _DoubleLinkedQueueEntry(this._queue); | |
| 183 | |
| 184 DoubleLinkedQueueEntry<E> _asNonSentinelEntry(); | |
| 185 | |
| 186 void _append(E e) { | |
| 187 new _DoubleLinkedQueueElement<E>(e, _queue)._link(this, _nextLink); | |
| 188 } | |
| 189 | |
| 190 void _prepend(E e) { | |
| 191 new _DoubleLinkedQueueElement<E>(e, _queue)._link(_previousLink, this); | |
| 192 } | |
| 193 | |
| 194 E _remove(); | |
| 195 | |
| 196 E get element; | |
| 197 | |
| 198 DoubleLinkedQueueEntry<E> nextEntry() { | |
| 199 return _nextLink._asNonSentinelEntry(); | |
| 200 } | |
| 201 | |
| 202 DoubleLinkedQueueEntry<E> previousEntry() { | |
| 203 return _previousLink._asNonSentinelEntry(); | |
| 204 } | |
| 205 } | |
| 206 | |
| 207 /** | |
| 208 * The actual entry type used by the [DoubleLinkedQueue]. | |
| 209 * | |
| 210 * The entry contains a reference to the queue, allowing | |
| 211 * [append]/[prepend] to update the list length. | |
| 212 */ | |
| 213 class _DoubleLinkedQueueElement<E> extends _DoubleLinkedQueueEntry<E> | |
| 214 implements DoubleLinkedQueueEntry<E> { | |
| 215 E element; | |
| 216 _DoubleLinkedQueueElement(this.element, DoubleLinkedQueue<E> queue) | |
| 217 : super(queue); | |
| 218 | |
| 219 void append(E e) { | |
| 220 _append(e); | |
| 221 if (_queue != null) _queue._elementCount++; | |
| 222 } | |
| 223 | |
| 224 void prepend(E e) { | |
| 225 _prepend(e); | |
| 226 if (_queue != null) _queue._elementCount++; | |
| 227 } | |
| 228 | |
| 229 E _remove() { | |
| 230 _queue = null; | |
| 231 _unlink(); | |
| 232 return element; | |
| 233 } | |
| 234 | |
| 235 E remove() { | |
| 236 if (_queue != null) _queue._elementCount--; | |
| 237 return _remove(); | |
| 238 } | |
| 239 | |
| 240 _DoubleLinkedQueueElement<E> _asNonSentinelEntry() { | |
| 241 return this; | |
| 242 } | |
| 243 } | |
| 244 | |
| 245 /** | |
| 246 * A sentinel in a double linked list is used to manipulate the list | |
| 247 * at both ends. | |
| 248 * A double linked list has exactly one sentinel, | |
| 249 * which is the only entry when the list is constructed. | |
| 250 * Initially, a sentinel has its next and previous entry point to itself. | |
| 251 * A sentinel does not box any user element. | |
| 252 */ | |
| 253 class _DoubleLinkedQueueSentinel<E> extends _DoubleLinkedQueueEntry<E> { | |
| 254 _DoubleLinkedQueueSentinel(DoubleLinkedQueue<E> queue) : super(queue) { | |
| 255 _previousLink = this; | |
| 256 _nextLink = this; | |
| 257 } | |
| 258 | |
| 259 DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { | |
| 260 return null; | |
| 261 } | |
| 262 | |
| 263 /** Hit by, e.g., [DoubleLinkedQueue.removeFirst] if the queue is empty. */ | |
| 264 E _remove() { | |
| 265 throw IterableElementError.noElement(); | |
| 266 } | |
| 267 | |
| 268 /** Hit by, e.g., [DoubleLinkedQueue.first] if the queue is empty. */ | |
| 269 E get element { | |
| 270 throw IterableElementError.noElement(); | |
| 271 } | |
| 272 } | |
| 273 | |
| 274 /** | |
| 275 * A [Queue] implementation based on a double-linked list. | |
| 276 * | |
| 277 * Allows constant time add, remove-at-ends and peek operations. | |
| 278 */ | |
| 279 class DoubleLinkedQueue<E> extends Iterable<E> implements Queue<E> { | |
| 280 _DoubleLinkedQueueSentinel<E> _sentinel; | |
| 281 int _elementCount = 0; | |
| 282 | |
| 283 DoubleLinkedQueue() { | |
| 284 _sentinel = new _DoubleLinkedQueueSentinel<E>(this); | |
| 285 } | |
| 286 | |
| 287 /** | |
| 288 * Creates a double-linked queue containing all [elements]. | |
| 289 * | |
| 290 * The element order in the queue is as if the elements were added using | |
| 291 * [addLast] in the order provided by [elements.iterator]. | |
| 292 */ | |
| 293 factory DoubleLinkedQueue.from(Iterable elements) { | |
| 294 Queue<E> list = new DoubleLinkedQueue<E>(); | |
| 295 for (final e in elements) { | |
| 296 E element = e as Object/*=E*/; | |
| 297 list.addLast(element); | |
| 298 } | |
| 299 return list; | |
| 300 } | |
| 301 | |
| 302 int get length => _elementCount; | |
| 303 | |
| 304 void addLast(E value) { | |
| 305 _sentinel._prepend(value); | |
| 306 _elementCount++; | |
| 307 } | |
| 308 | |
| 309 void addFirst(E value) { | |
| 310 _sentinel._append(value); | |
| 311 _elementCount++; | |
| 312 } | |
| 313 | |
| 314 void add(E value) { | |
| 315 _sentinel._prepend(value); | |
| 316 _elementCount++; | |
| 317 } | |
| 318 | |
| 319 void addAll(Iterable<E> iterable) { | |
| 320 for (final E value in iterable) { | |
| 321 _sentinel._prepend(value); | |
| 322 _elementCount++; | |
| 323 } | |
| 324 } | |
| 325 | |
| 326 E removeLast() { | |
| 327 _DoubleLinkedQueueEntry<E> lastEntry = _sentinel._previousLink; | |
| 328 E result = lastEntry._remove(); | |
| 329 _elementCount--; | |
| 330 return result; | |
| 331 } | |
| 332 | |
| 333 E removeFirst() { | |
| 334 _DoubleLinkedQueueEntry<E> firstEntry = _sentinel._nextLink; | |
| 335 E result = firstEntry._remove(); | |
| 336 _elementCount--; | |
| 337 return result; | |
| 338 } | |
| 339 | |
| 340 bool remove(Object o) { | |
| 341 _DoubleLinkedQueueEntry<E> entry = _sentinel._nextLink; | |
| 342 while (!identical(entry, _sentinel)) { | |
| 343 if (entry.element == o) { | |
| 344 entry._remove(); | |
| 345 _elementCount--; | |
| 346 return true; | |
| 347 } | |
| 348 entry = entry._nextLink; | |
| 349 } | |
| 350 return false; | |
| 351 } | |
| 352 | |
| 353 void _filter(bool test(E element), bool removeMatching) { | |
| 354 _DoubleLinkedQueueEntry<E> entry = _sentinel._nextLink; | |
| 355 while (!identical(entry, _sentinel)) { | |
| 356 _DoubleLinkedQueueEntry<E> next = entry._nextLink; | |
| 357 if (identical(removeMatching, test(entry.element))) { | |
| 358 entry._remove(); | |
| 359 _elementCount--; | |
| 360 } | |
| 361 entry = next; | |
| 362 } | |
| 363 } | |
| 364 | |
| 365 void removeWhere(bool test(E element)) { | |
| 366 _filter(test, true); | |
| 367 } | |
| 368 | |
| 369 void retainWhere(bool test(E element)) { | |
| 370 _filter(test, false); | |
| 371 } | |
| 372 | |
| 373 E get first { | |
| 374 _DoubleLinkedQueueEntry<E> firstEntry = _sentinel._nextLink; | |
| 375 return firstEntry.element; | |
| 376 } | |
| 377 | |
| 378 E get last { | |
| 379 _DoubleLinkedQueueEntry<E> lastEntry = _sentinel._previousLink; | |
| 380 return lastEntry.element; | |
| 381 } | |
| 382 | |
| 383 E get single { | |
| 384 // Note that this throws correctly if the queue is empty | |
| 385 // because reading element on the sentinel throws. | |
| 386 if (identical(_sentinel._nextLink, _sentinel._previousLink)) { | |
| 387 _DoubleLinkedQueueEntry<E> entry = _sentinel._nextLink; | |
| 388 return entry.element; | |
| 389 } | |
| 390 throw IterableElementError.tooMany(); | |
| 391 } | |
| 392 | |
| 393 DoubleLinkedQueueEntry<E> lastEntry() { | |
| 394 return _sentinel.previousEntry(); | |
| 395 } | |
| 396 | |
| 397 DoubleLinkedQueueEntry<E> firstEntry() { | |
| 398 return _sentinel.nextEntry(); | |
| 399 } | |
| 400 | |
| 401 bool get isEmpty { | |
| 402 return (identical(_sentinel._nextLink, _sentinel)); | |
| 403 } | |
| 404 | |
| 405 void clear() { | |
| 406 _sentinel._nextLink = _sentinel; | |
| 407 _sentinel._previousLink = _sentinel; | |
| 408 _elementCount = 0; | |
| 409 } | |
| 410 | |
| 411 void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) { | |
| 412 _DoubleLinkedQueueEntry<E> entry = _sentinel._nextLink; | |
| 413 while (!identical(entry, _sentinel)) { | |
| 414 _DoubleLinkedQueueEntry<E> nextEntry = entry._nextLink; | |
| 415 _DoubleLinkedQueueElement<E> element = entry; | |
| 416 f(element); | |
| 417 entry = nextEntry; | |
| 418 } | |
| 419 } | |
| 420 | |
| 421 _DoubleLinkedQueueIterator<E> get iterator { | |
| 422 return new _DoubleLinkedQueueIterator<E>(_sentinel); | |
| 423 } | |
| 424 | |
| 425 String toString() => IterableBase.iterableToFullString(this, '{', '}'); | |
| 426 } | |
| 427 | |
| 428 class _DoubleLinkedQueueIterator<E> implements Iterator<E> { | |
| 429 _DoubleLinkedQueueSentinel<E> _sentinel; | |
| 430 _DoubleLinkedQueueEntry<E> _nextEntry = null; | |
| 431 E _current; | |
| 432 | |
| 433 _DoubleLinkedQueueIterator(_DoubleLinkedQueueSentinel<E> sentinel) | |
| 434 : _sentinel = sentinel, | |
| 435 _nextEntry = sentinel._nextLink; | |
| 436 | |
| 437 bool moveNext() { | |
| 438 if (identical(_nextEntry, _sentinel)) { | |
| 439 _current = null; | |
| 440 _nextEntry = null; | |
| 441 _sentinel = null; | |
| 442 return false; | |
| 443 } | |
| 444 _DoubleLinkedQueueElement<E> elementEntry = _nextEntry; | |
| 445 if (elementEntry._queue == null) { | |
| 446 throw new ConcurrentModificationError(_sentinel._queue); | |
| 447 } | |
| 448 _current = elementEntry.element; | |
| 449 _nextEntry = elementEntry._nextLink; | |
| 450 return true; | |
| 451 } | |
| 452 | |
| 453 E get current => _current; | |
| 454 } | |
| 455 | |
| 456 /** | |
| 457 * List based [Queue]. | |
| 458 * | |
| 459 * Keeps a cyclic buffer of elements, and grows to a larger buffer when | |
| 460 * it fills up. This guarantees constant time peek and remove operations, and | |
| 461 * amortized constant time add operations. | |
| 462 * | |
| 463 * The structure is efficient for any queue or stack usage. | |
| 464 */ | |
| 465 class ListQueue<E> extends Iterable<E> implements Queue<E> { | |
| 466 static const int _INITIAL_CAPACITY = 8; | |
| 467 List<E> _table; | |
| 468 int _head; | |
| 469 int _tail; | |
| 470 int _modificationCount = 0; | |
| 471 | |
| 472 /** | |
| 473 * Create an empty queue. | |
| 474 * | |
| 475 * If [initialCapacity] is given, prepare the queue for at least that many | |
| 476 * elements. | |
| 477 */ | |
| 478 ListQueue([int initialCapacity]) : _head = 0, _tail = 0 { | |
| 479 if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) { | |
| 480 initialCapacity = _INITIAL_CAPACITY; | |
| 481 } else if (!_isPowerOf2(initialCapacity)) { | |
| 482 initialCapacity = _nextPowerOf2(initialCapacity); | |
| 483 } | |
| 484 assert(_isPowerOf2(initialCapacity)); | |
| 485 _table = new List<E>(initialCapacity); | |
| 486 } | |
| 487 | |
| 488 /** | |
| 489 * Create a `ListQueue` containing all [elements]. | |
| 490 * | |
| 491 * The elements are added to the queue, as by [addLast], in the order given by | |
| 492 * `elements.iterator`. | |
| 493 * | |
| 494 * All `elements` should be assignable to [E]. | |
| 495 */ | |
| 496 factory ListQueue.from(Iterable elements) { | |
| 497 if (elements is List) { | |
| 498 int length = elements.length; | |
| 499 ListQueue<E> queue = new ListQueue(length + 1); | |
| 500 assert(queue._table.length > length); | |
| 501 for (int i = 0; i < length; i++) { | |
| 502 queue._table[i] = elements[i] as Object/*=E*/; | |
| 503 } | |
| 504 queue._tail = length; | |
| 505 return queue; | |
| 506 } else { | |
| 507 int capacity = _INITIAL_CAPACITY; | |
| 508 if (elements is EfficientLength) { | |
| 509 capacity = elements.length; | |
| 510 } | |
| 511 ListQueue<E> result = new ListQueue<E>(capacity); | |
| 512 for (final element in elements) { | |
| 513 result.addLast(element as Object/*=E*/); | |
| 514 } | |
| 515 return result; | |
| 516 } | |
| 517 } | |
| 518 | |
| 519 // Iterable interface. | |
| 520 | |
| 521 Iterator<E> get iterator => new _ListQueueIterator<E>(this); | |
| 522 | |
| 523 void forEach(void action (E element)) { | |
| 524 int modificationCount = _modificationCount; | |
| 525 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { | |
| 526 action(_table[i]); | |
| 527 _checkModification(modificationCount); | |
| 528 } | |
| 529 } | |
| 530 | |
| 531 bool get isEmpty => _head == _tail; | |
| 532 | |
| 533 int get length => (_tail - _head) & (_table.length - 1); | |
| 534 | |
| 535 E get first { | |
| 536 if (_head == _tail) throw IterableElementError.noElement(); | |
| 537 return _table[_head]; | |
| 538 } | |
| 539 | |
| 540 E get last { | |
| 541 if (_head == _tail) throw IterableElementError.noElement(); | |
| 542 return _table[(_tail - 1) & (_table.length - 1)]; | |
| 543 } | |
| 544 | |
| 545 E get single { | |
| 546 if (_head == _tail) throw IterableElementError.noElement(); | |
| 547 if (length > 1) throw IterableElementError.tooMany(); | |
| 548 return _table[_head]; | |
| 549 } | |
| 550 | |
| 551 E elementAt(int index) { | |
| 552 RangeError.checkValidIndex(index, this); | |
| 553 return _table[(_head + index) & (_table.length - 1)]; | |
| 554 } | |
| 555 | |
| 556 List<E> toList({ bool growable: true }) { | |
| 557 List<E> list; | |
| 558 if (growable) { | |
| 559 list = new List<E>()..length = length; | |
| 560 } else { | |
| 561 list = new List<E>(length); | |
| 562 } | |
| 563 _writeToList(list); | |
| 564 return list; | |
| 565 } | |
| 566 | |
| 567 // Collection interface. | |
| 568 | |
| 569 void add(E value) { | |
| 570 _add(value); | |
| 571 } | |
| 572 | |
| 573 void addAll(Iterable<E> elements) { | |
| 574 if (elements is List/*<E>*/) { | |
| 575 List<E> list = elements; | |
| 576 int addCount = list.length; | |
| 577 int length = this.length; | |
| 578 if (length + addCount >= _table.length) { | |
| 579 _preGrow(length + addCount); | |
| 580 // After preGrow, all elements are at the start of the list. | |
| 581 _table.setRange(length, length + addCount, list, 0); | |
| 582 _tail += addCount; | |
| 583 } else { | |
| 584 // Adding addCount elements won't reach _head. | |
| 585 int endSpace = _table.length - _tail; | |
| 586 if (addCount < endSpace) { | |
| 587 _table.setRange(_tail, _tail + addCount, list, 0); | |
| 588 _tail += addCount; | |
| 589 } else { | |
| 590 int preSpace = addCount - endSpace; | |
| 591 _table.setRange(_tail, _tail + endSpace, list, 0); | |
| 592 _table.setRange(0, preSpace, list, endSpace); | |
| 593 _tail = preSpace; | |
| 594 } | |
| 595 } | |
| 596 _modificationCount++; | |
| 597 } else { | |
| 598 for (E element in elements) _add(element); | |
| 599 } | |
| 600 } | |
| 601 | |
| 602 bool remove(Object value) { | |
| 603 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { | |
| 604 E element = _table[i]; | |
| 605 if (element == value) { | |
| 606 _remove(i); | |
| 607 _modificationCount++; | |
| 608 return true; | |
| 609 } | |
| 610 } | |
| 611 return false; | |
| 612 } | |
| 613 | |
| 614 void _filterWhere(bool test(E element), bool removeMatching) { | |
| 615 int modificationCount = _modificationCount; | |
| 616 int i = _head; | |
| 617 while (i != _tail) { | |
| 618 E element = _table[i]; | |
| 619 bool remove = identical(removeMatching, test(element)); | |
| 620 _checkModification(modificationCount); | |
| 621 if (remove) { | |
| 622 i = _remove(i); | |
| 623 modificationCount = ++_modificationCount; | |
| 624 } else { | |
| 625 i = (i + 1) & (_table.length - 1); | |
| 626 } | |
| 627 } | |
| 628 } | |
| 629 | |
| 630 /** | |
| 631 * Remove all elements matched by [test]. | |
| 632 * | |
| 633 * This method is inefficient since it works by repeatedly removing single | |
| 634 * elements, each of which can take linear time. | |
| 635 */ | |
| 636 void removeWhere(bool test(E element)) { | |
| 637 _filterWhere(test, true); | |
| 638 } | |
| 639 | |
| 640 /** | |
| 641 * Remove all elements not matched by [test]. | |
| 642 * | |
| 643 * This method is inefficient since it works by repeatedly removing single | |
| 644 * elements, each of which can take linear time. | |
| 645 */ | |
| 646 void retainWhere(bool test(E element)) { | |
| 647 _filterWhere(test, false); | |
| 648 } | |
| 649 | |
| 650 void clear() { | |
| 651 if (_head != _tail) { | |
| 652 for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) { | |
| 653 _table[i] = null; | |
| 654 } | |
| 655 _head = _tail = 0; | |
| 656 _modificationCount++; | |
| 657 } | |
| 658 } | |
| 659 | |
| 660 String toString() => IterableBase.iterableToFullString(this, "{", "}"); | |
| 661 | |
| 662 // Queue interface. | |
| 663 | |
| 664 void addLast(E value) { _add(value); } | |
| 665 | |
| 666 void addFirst(E value) { | |
| 667 _head = (_head - 1) & (_table.length - 1); | |
| 668 _table[_head] = value; | |
| 669 if (_head == _tail) _grow(); | |
| 670 _modificationCount++; | |
| 671 } | |
| 672 | |
| 673 E removeFirst() { | |
| 674 if (_head == _tail) throw IterableElementError.noElement(); | |
| 675 _modificationCount++; | |
| 676 E result = _table[_head]; | |
| 677 _table[_head] = null; | |
| 678 _head = (_head + 1) & (_table.length - 1); | |
| 679 return result; | |
| 680 } | |
| 681 | |
| 682 E removeLast() { | |
| 683 if (_head == _tail) throw IterableElementError.noElement(); | |
| 684 _modificationCount++; | |
| 685 _tail = (_tail - 1) & (_table.length - 1); | |
| 686 E result = _table[_tail]; | |
| 687 _table[_tail] = null; | |
| 688 return result; | |
| 689 } | |
| 690 | |
| 691 // Internal helper functions. | |
| 692 | |
| 693 /** | |
| 694 * Whether [number] is a power of two. | |
| 695 * | |
| 696 * Only works for positive numbers. | |
| 697 */ | |
| 698 static bool _isPowerOf2(int number) => (number & (number - 1)) == 0; | |
| 699 | |
| 700 /** | |
| 701 * Rounds [number] up to the nearest power of 2. | |
| 702 * | |
| 703 * If [number] is a power of 2 already, it is returned. | |
| 704 * | |
| 705 * Only works for positive numbers. | |
| 706 */ | |
| 707 static int _nextPowerOf2(int number) { | |
| 708 assert(number > 0); | |
| 709 number = (number << 1) - 1; | |
| 710 for(;;) { | |
| 711 int nextNumber = number & (number - 1); | |
| 712 if (nextNumber == 0) return number; | |
| 713 number = nextNumber; | |
| 714 } | |
| 715 } | |
| 716 | |
| 717 /** Check if the queue has been modified during iteration. */ | |
| 718 void _checkModification(int expectedModificationCount) { | |
| 719 if (expectedModificationCount != _modificationCount) { | |
| 720 throw new ConcurrentModificationError(this); | |
| 721 } | |
| 722 } | |
| 723 | |
| 724 /** Adds element at end of queue. Used by both [add] and [addAll]. */ | |
| 725 void _add(E element) { | |
| 726 _table[_tail] = element; | |
| 727 _tail = (_tail + 1) & (_table.length - 1); | |
| 728 if (_head == _tail) _grow(); | |
| 729 _modificationCount++; | |
| 730 } | |
| 731 | |
| 732 /** | |
| 733 * Removes the element at [offset] into [_table]. | |
| 734 * | |
| 735 * Removal is performed by linerarly moving elements either before or after | |
| 736 * [offset] by one position. | |
| 737 * | |
| 738 * Returns the new offset of the following element. This may be the same | |
| 739 * offset or the following offset depending on how elements are moved | |
| 740 * to fill the hole. | |
| 741 */ | |
| 742 int _remove(int offset) { | |
| 743 int mask = _table.length - 1; | |
| 744 int startDistance = (offset - _head) & mask; | |
| 745 int endDistance = (_tail - offset) & mask; | |
| 746 if (startDistance < endDistance) { | |
| 747 // Closest to start. | |
| 748 int i = offset; | |
| 749 while (i != _head) { | |
| 750 int prevOffset = (i - 1) & mask; | |
| 751 _table[i] = _table[prevOffset]; | |
| 752 i = prevOffset; | |
| 753 } | |
| 754 _table[_head] = null; | |
| 755 _head = (_head + 1) & mask; | |
| 756 return (offset + 1) & mask; | |
| 757 } else { | |
| 758 _tail = (_tail - 1) & mask; | |
| 759 int i = offset; | |
| 760 while (i != _tail) { | |
| 761 int nextOffset = (i + 1) & mask; | |
| 762 _table[i] = _table[nextOffset]; | |
| 763 i = nextOffset; | |
| 764 } | |
| 765 _table[_tail] = null; | |
| 766 return offset; | |
| 767 } | |
| 768 } | |
| 769 | |
| 770 /** | |
| 771 * Grow the table when full. | |
| 772 */ | |
| 773 void _grow() { | |
| 774 List<E> newTable = new List<E>(_table.length * 2); | |
| 775 int split = _table.length - _head; | |
| 776 newTable.setRange(0, split, _table, _head); | |
| 777 newTable.setRange(split, split + _head, _table, 0); | |
| 778 _head = 0; | |
| 779 _tail = _table.length; | |
| 780 _table = newTable; | |
| 781 } | |
| 782 | |
| 783 int _writeToList(List<E> target) { | |
| 784 assert(target.length >= length); | |
| 785 if (_head <= _tail) { | |
| 786 int length = _tail - _head; | |
| 787 target.setRange(0, length, _table, _head); | |
| 788 return length; | |
| 789 } else { | |
| 790 int firstPartSize = _table.length - _head; | |
| 791 target.setRange(0, firstPartSize, _table, _head); | |
| 792 target.setRange(firstPartSize, firstPartSize + _tail, _table, 0); | |
| 793 return _tail + firstPartSize; | |
| 794 } | |
| 795 } | |
| 796 | |
| 797 /** Grows the table even if it is not full. */ | |
| 798 void _preGrow(int newElementCount) { | |
| 799 assert(newElementCount >= length); | |
| 800 | |
| 801 // Add some extra room to ensure that there's room for more elements after | |
| 802 // expansion. | |
| 803 newElementCount += newElementCount >> 1; | |
| 804 int newCapacity = _nextPowerOf2(newElementCount); | |
| 805 List<E> newTable = new List<E>(newCapacity); | |
| 806 _tail = _writeToList(newTable); | |
| 807 _table = newTable; | |
| 808 _head = 0; | |
| 809 } | |
| 810 } | |
| 811 | |
| 812 /** | |
| 813 * Iterator for a [ListQueue]. | |
| 814 * | |
| 815 * Considers any add or remove operation a concurrent modification. | |
| 816 */ | |
| 817 class _ListQueueIterator<E> implements Iterator<E> { | |
| 818 final ListQueue<E> _queue; | |
| 819 final int _end; | |
| 820 final int _modificationCount; | |
| 821 int _position; | |
| 822 E _current; | |
| 823 | |
| 824 _ListQueueIterator(ListQueue<E> queue) | |
| 825 : _queue = queue, | |
| 826 _end = queue._tail, | |
| 827 _modificationCount = queue._modificationCount, | |
| 828 _position = queue._head; | |
| 829 | |
| 830 E get current => _current; | |
| 831 | |
| 832 bool moveNext() { | |
| 833 _queue._checkModification(_modificationCount); | |
| 834 if (_position == _end) { | |
| 835 _current = null; | |
| 836 return false; | |
| 837 } | |
| 838 _current = _queue._table[_position]; | |
| 839 _position = (_position + 1) & (_queue._table.length - 1); | |
| 840 return true; | |
| 841 } | |
| 842 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2698353003:
unfork DDC's copy of most SDK libraries (Closed)
