sdk/lib/collection/queue.dart

// Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

part of dart.collection;

/// A [Queue] is a collection that can be manipulated at both ends. One
/// can iterate over the elements of a queue through [forEach] or with
/// an [Iterator].
///
/// It is generally not allowed to modify the queue (add or remove entries)
/// while an operation in the queue is being performed, for example during a
/// call to [forEach].
/// Modifying the queue while it is being iterated will most likely break the
/// iteration.
/// This goes both for using the [iterator] directly, or for iterating an
/// `Iterable` returned by a method like [map] or [where].
///
/// Example:
/// ```dart
/// final queue = Queue<int>(); // ListQueue() by default
/// print(queue.runtimeType); // ListQueue
///
/// // Adding items to queue
/// queue.addAll([1, 2, 3]);
/// queue.addFirst(0);
/// queue.addLast(10);
/// print(queue); // {0, 1, 2, 3, 10}
///
/// // Removing items from queue
/// queue.removeFirst();
/// queue.removeLast();
/// print(queue); // {1, 2, 3}
/// ```
abstract class Queue<E> implements EfficientLengthIterable<E> {
  /// Creates a queue.
  factory Queue() = ListQueue<E>;

  /// Creates a queue containing all [elements].
  ///
  /// The element order in the queue is as if the elements were added using
  /// [addLast] in the order provided by [elements].iterator.
  ///
  /// All the [elements] should be instances of [E].
  /// The `elements` iterable itself may have any element type, so this
  /// constructor can be used to down-cast a `Queue`, for example as:
  /// ```dart
  /// Queue<SuperType> superQueue = ...;
  /// Queue<SubType> subQueue =
  ///     Queue<SubType>.from(superQueue.whereType<SubType>());
  /// ```
  factory Queue.from(Iterable elements) = ListQueue<E>.from;

  /// Creates a queue from [elements].
  ///
  /// The element order in the queue is as if the elements were added using
  /// [addLast] in the order provided by [elements].iterator.
  factory Queue.of(Iterable<E> elements) = ListQueue<E>.of;

  /// Adapts [source] to be a `Queue<T>`.
  ///
  /// Any time the queue would produce an element that is not a [T],
  /// the element access will throw.
  ///
  /// When a [T] value is stored into the adapted queue,
  /// the operation will throw unless the value is also an instance of [S].
  ///
  /// If all accessed elements of [source] are actually instances of [T],
  /// and if all elements stored into the returned queue are actually instances
  /// of [S],
  /// then the returned queue can be used as a `Queue<T>`.
  ///
  /// Methods which accept `Object?` as argument, like [contains] and [remove],
  /// will pass the argument directly to this queue's method
  /// without any checks.
  static Queue<T> castFrom<S, T>(Queue<S> source) => CastQueue<S, T>(source);

  /// Provides a view of this queue as a queue of [R] instances, if necessary.
  ///
  /// If this queue contains only instances of [R], all read operations
  /// will work correctly. If any operation tries to access an element
  /// that is not an instance of [R], the access will throw instead.
  ///
  /// Elements added to the queue (e.g., by using [addFirst] or [addAll])
  /// must be instances of [R] to be valid arguments to the adding function,
  /// and they must also be instances of [E] to be accepted by
  /// this queue as well.
  ///
  /// Methods which accept `Object?` as argument, like [contains] and [remove],
  /// will pass the argument directly to the this queue's method
  /// without any checks.
  /// That means that you can do `queueOfStrings.cast<int>().remove("a")`
  /// successfully, even if it looks like it shouldn't have any effect.
  Queue<R> cast<R>();

  /// Removes and returns the first element of this queue.
  ///
  /// The queue must not be empty when this method is called.
  E removeFirst();

  /// Removes and returns the last element of the queue.
  ///
  /// The queue must not be empty when this method is called.
  E removeLast();

  /// Adds [value] at the beginning of the queue.
  void addFirst(E value);

  /// Adds [value] at the end of the queue.
  void addLast(E value);

  /// Adds [value] at the end of the queue.
  void add(E value);

  /// Removes a single instance of [value] from the queue.
  ///
  /// Returns `true` if a value was removed, or `false` if the queue
  /// contained no element equal to [value].
  bool remove(Object? value);

  /// Adds all elements of [iterable] at the end of the queue. The
  /// length of the queue is extended by the length of [iterable].
  void addAll(Iterable<E> iterable);

  /// Removes all elements matched by [test] from the queue.
  ///
  /// The `test` function must not throw or modify the queue.
  void removeWhere(bool test(E element));

  /// Removes all elements not matched by [test] from the queue.
  ///
  /// The `test` function must not throw or modify the queue.
  void retainWhere(bool test(E element));

  /// Removes all elements in the queue. The size of the queue becomes zero.
  void clear();
}

/// Interface and base class for the link classes used by [DoubleLinkedQueue].
///
/// Both the [_DoubleLinkedQueueElement] and [_DoubleLinkedQueueSentinel]
/// implement this interface.
abstract class _DoubleLinkedQueueEntry<E> {
  _DoubleLinkedQueueEntry<E>? _previousLink;
  _DoubleLinkedQueueEntry<E>? _nextLink;

  void _link(
      _DoubleLinkedQueueEntry<E>? previous, _DoubleLinkedQueueEntry<E>? next) {
    _nextLink = next;
    _previousLink = previous;
    previous?._nextLink = this;
    next?._previousLink = this;
  }

  void _unlink() {
    _previousLink?._nextLink = _nextLink;
    _nextLink?._previousLink = _previousLink;
    _previousLink = _nextLink = null;
  }

  _DoubleLinkedQueueElement<E>? _asNonSentinelEntry();

  void _append(E element, DoubleLinkedQueue<E>? queue) {
    _DoubleLinkedQueueElement<E>(element, queue)._link(this, _nextLink);
  }

  void _prepend(E element, DoubleLinkedQueue<E>? queue) {
    _DoubleLinkedQueueElement<E>(element, queue)._link(_previousLink, this);
  }

  E _remove();

  E get element;
}

/// Linked list entry used by the [DoubleLinkedQueue] to hold an element.
///
/// These entry objects are also exposed by [DoubleLinkedQueue.firstEntry],
/// [DoubleLinkedQueue.lastEntry] and [DoubleLinkedQueue.forEachEntry].
///
/// The entry contains both the [element] (which is mutable to anyone with
/// access to the entry object) and a reference to the queue, allowing
/// [append]/[prepend] to update the list length.
///
/// When an entry is removed from its queue, the [_queue] is set to `null`
/// and will never change again. You can still use the unlinked entry
/// to create a new list, by calling [append] and [prepend], but it won't
/// be part of any [DoubleLinkedQueue].
class _DoubleLinkedQueueElement<E> extends _DoubleLinkedQueueEntry<E>
    implements DoubleLinkedQueueEntry<E> {
  DoubleLinkedQueue<E>? _queue;
  E element;

  _DoubleLinkedQueueElement(this.element, this._queue);

  void append(E e) {
    _append(e, _queue);
    _queue?._elementCount++;
  }

  void prepend(E e) {
    _prepend(e, _queue);
    _queue?._elementCount++;
  }

  E _remove() {
    _queue = null;
    _unlink();
    return element;
  }

  E remove() {
    _queue?._elementCount--;
    return _remove();
  }

  _DoubleLinkedQueueElement<E> _asNonSentinelEntry() => this;

  DoubleLinkedQueueEntry<E>? previousEntry() =>
      _previousLink?._asNonSentinelEntry();

  DoubleLinkedQueueEntry<E>? nextEntry() => _nextLink?._asNonSentinelEntry();
}

/// A header object used to hold the two ends of a double linked queue.
///
/// A [DoubleLinkedQueue] has exactly one sentinel,
/// which is the only entry when the list is constructed.
///
/// Initially, a sentinel has its next and previous entries point to itself.
/// Its next and previous links are never `null` after creation, and
/// the entries linked always form a circular structure with the next link
/// pointing to the first element of the queue, and the previous link
/// pointing to the last element of the queue, or both pointing to itself
/// again if the queue becomes empty.
///
/// Implements [_DoubleLinkedQueueEntry._remove] and
/// [_DoubleLinkedQueueEntry.element] as throwing because
/// it makes it simple to implement members like [Queue.removeFirst]
/// or [Queue.first] as throwing on an empty queue.
///
/// A sentinel does not contain any user element.
class _DoubleLinkedQueueSentinel<E> extends _DoubleLinkedQueueEntry<E> {
  _DoubleLinkedQueueSentinel() {
    _previousLink = this;
    _nextLink = this;
  }

  Null _asNonSentinelEntry() => null;

  /// Hit by, e.g., [DoubleLinkedQueue.removeFirst] if the queue is empty.
  E _remove() {
    throw IterableElementError.noElement();
  }

  /// Hit by, e.g., [DoubleLinkedQueue.first] if the queue is empty.
  E get element {
    throw IterableElementError.noElement();
  }
}

/// A [Queue] implementation based on a double-linked list.
///
/// Allows constant time add, remove-at-ends and peek operations.
class DoubleLinkedQueue<E> extends Iterable<E> implements Queue<E> {
  final _DoubleLinkedQueueSentinel<E> _sentinel =
      _DoubleLinkedQueueSentinel<E>();

  int _elementCount = 0;

  DoubleLinkedQueue();

  /// Creates a double-linked queue containing all [elements].
  ///
  /// The element order in the queue is as if the elements were added using
  /// [addLast] in the order provided by [elements].iterator.
  ///
  /// All the [elements] should be instances of [E].
  /// The [elements] iterable itself may have any element type, so this
  /// constructor can be used to down-cast a [Queue], for example as:
  /// ```dart
  /// Queue<SuperType> superQueue = ...;
  /// Queue<SubType> subQueue =
  ///     DoubleLinkedQueue<SubType>.from(superQueue.whereType<SubType>());
  /// ```
  factory DoubleLinkedQueue.from(Iterable<dynamic> elements) {
    DoubleLinkedQueue<E> list = DoubleLinkedQueue<E>();
    for (final e in elements) {
      list.addLast(e as E);
    }
    return list;
  }

  /// Creates a double-linked queue from [elements].
  ///
  /// The element order in the queue is as if the elements were added using
  /// [addLast] in the order provided by [elements].iterator.
  factory DoubleLinkedQueue.of(Iterable<E> elements) =>
      DoubleLinkedQueue<E>()..addAll(elements);

  Queue<R> cast<R>() => Queue.castFrom<E, R>(this);

  int get length => _elementCount;

  void addLast(E value) {
    _sentinel._prepend(value, this);
    _elementCount++;
  }

  void addFirst(E value) {
    _sentinel._append(value, this);
    _elementCount++;
  }

  void add(E value) {
    _sentinel._prepend(value, this);
    _elementCount++;
  }

  void addAll(Iterable<E> iterable) {
    for (final E value in iterable) {
      _sentinel._prepend(value, this);
      _elementCount++;
    }
  }

  E removeLast() {
    // Hits sentinel's `_remove` if queue is empty.
    E result = _sentinel._previousLink!._remove();
    _elementCount--;
    return result;
  }

  E removeFirst() {
    // Hits sentinel's `_remove` if queue is empty.
    E result = _sentinel._nextLink!._remove();
    _elementCount--;
    return result;
  }

  bool remove(Object? o) {
    _DoubleLinkedQueueEntry<E> entry = _sentinel._nextLink!;
    while (true) {
      var elementEntry = entry._asNonSentinelEntry();
      if (elementEntry == null) return false;
      bool equals = (elementEntry.element == o);
      if (!identical(this, elementEntry._queue)) {
        // Entry must still be in the queue.
        throw ConcurrentModificationError(this);
      }
      if (equals) {
        entry._remove();
        _elementCount--;
        return true;
      }
      entry = entry._nextLink!;
    }
  }

  void _filter(bool test(E element), bool removeMatching) {
    _DoubleLinkedQueueEntry<E> entry = _sentinel._nextLink!;
    while (true) {
      var elementEntry = entry._asNonSentinelEntry();
      if (elementEntry == null) return;
      bool matches = test(elementEntry.element);
      if (!identical(this, elementEntry._queue)) {
        // Entry must still be in the queue.
        throw ConcurrentModificationError(this);
      }
      var next = entry._nextLink!; // Cannot be null while entry is in queue.
      if (identical(removeMatching, matches)) {
        elementEntry._remove();
        _elementCount--;
      }
      entry = next;
    }
  }

  void removeWhere(bool test(E element)) {
    _filter(test, true);
  }

  void retainWhere(bool test(E element)) {
    _filter(test, false);
  }

  // Hits sentinel's `get element` if no element in queue.
  E get first => _sentinel._nextLink!.element;

  // Hits sentinel's `get element` if no element in queue.
  E get last => _sentinel._previousLink!.element;

  E get single {
    // Note that this throws correctly if the queue is empty
    // because reading the element of the sentinel throws.
    if (identical(_sentinel._nextLink, _sentinel._previousLink)) {
      return _sentinel._nextLink!.element;
    }
    throw IterableElementError.tooMany();
  }

  /// The entry object of the first element in the queue.
  ///
  /// Each element of the queue has an associated [DoubleLinkedQueueEntry].
  ///
  /// Returns the entry object corresponding to the first element of the queue,
  /// or `null` if the queue is empty.
  ///
  /// The entry objects can also be accessed using [lastEntry],
  /// and they can be iterated using [DoubleLinkedQueueEntry.nextEntry] and
  /// [DoubleLinkedQueueEntry.previousEntry].
  DoubleLinkedQueueEntry<E>? firstEntry() =>
      _sentinel._nextLink!._asNonSentinelEntry();

  /// The entry object of the last element in the queue.
  ///
  /// Each element of the queue has an associated [DoubleLinkedQueueEntry].
  ///
  /// Returns the entry object corresponding to the last element of the queue,
  /// or `null` if the queue is empty.
  ///
  /// The entry objects can also be accessed using [firstEntry],
  /// and they can be iterated using [DoubleLinkedQueueEntry.nextEntry] and
  /// [DoubleLinkedQueueEntry.previousEntry].
  DoubleLinkedQueueEntry<E>? lastEntry() =>
      _sentinel._previousLink!._asNonSentinelEntry();

  bool get isEmpty => identical(_sentinel._nextLink, _sentinel);

  void clear() {
    var cursor = _sentinel._nextLink!;
    while (true) {
      var entry = cursor._asNonSentinelEntry();
      if (entry == null) break;
      cursor = cursor._nextLink!;
      entry
        .._nextLink = null
        .._previousLink = null
        .._queue = null;
    }
    _sentinel._nextLink = _sentinel;
    _sentinel._previousLink = _sentinel;
    _elementCount = 0;
  }

  /// Calls [action] for each entry object of this double-linked queue.
  ///
  /// Each element of the queue has an associated [DoubleLinkedQueueEntry].
  /// This method iterates the entry objects from first to last and calls
  /// [action] with each object in turn.
  ///
  /// The entry objects can also be accessed using [firstEntry] and [lastEntry],
  /// and iterated using [DoubleLinkedQueueEntry.nextEntry()] and
  /// [DoubleLinkedQueueEntry.previousEntry()].
  ///
  /// The [action] function can use methods on [DoubleLinkedQueueEntry] to
  /// remove the entry or it can insert elements before or after the entry.
  /// If the current entry is removed, iteration continues with the entry that
  /// was following the current entry when [action] was called. Any elements
  /// inserted after the current element before it is removed will not be
  /// visited by the iteration.
  void forEachEntry(void action(DoubleLinkedQueueEntry<E> element)) {
    var cursor = _sentinel._nextLink!;
    while (true) {
      var element = cursor._asNonSentinelEntry();
      if (element == null) break;
      if (!identical(element._queue, this)) {
        throw ConcurrentModificationError(this);
      }
      cursor = cursor._nextLink!;
      // Remember both element and element._nextLink (as cursor).
      // If someone calls `element.remove()` we continue from `next`.
      // Otherwise we use the value of element._nextLink which may have been
      // updated.
      action(element);
      if (identical(this, element._queue)) {
        cursor = element._nextLink!;
      }
    }
  }

  _DoubleLinkedQueueIterator<E> get iterator {
    return _DoubleLinkedQueueIterator<E>(this);
  }

  String toString() => IterableBase.iterableToFullString(this, '{', '}');
}

class _DoubleLinkedQueueIterator<E> implements Iterator<E> {
  /// Queue being iterated. Used for concurrent modification checks.
  DoubleLinkedQueue<E>? _queue;

  /// Next entry to visit. Set to null when hitting the sentinel.
  _DoubleLinkedQueueEntry<E>? _nextEntry;

  /// Current element value, when valid.
  E? _current;

  _DoubleLinkedQueueIterator(DoubleLinkedQueue<E> this._queue)
      : _nextEntry = _queue._sentinel._nextLink;

  bool moveNext() {
    var nextElement = _nextEntry?._asNonSentinelEntry();
    if (nextElement == null) {
      // Clear everything to not unnecessarily keep values alive.
      _current = null;
      _nextEntry = null;
      _queue = null;
      return false;
    }
    if (!identical(_queue, nextElement._queue)) {
      throw ConcurrentModificationError(_queue);
    }
    _current = nextElement.element;
    _nextEntry = nextElement._nextLink;
    return true;
  }

  E get current => _current as E;
}

/// List based [Queue].
///
/// Keeps a cyclic buffer of elements, and grows to a larger buffer when
/// it fills up. This guarantees constant time peek and remove operations, and
/// amortized constant time add operations.
///
/// The structure is efficient for any queue or stack usage.
///
/// Example:
/// ```dart
/// final queue = ListQueue<int>();
/// ```
/// To add objects to a queue, use [add], [addAll], [addFirst] or[addLast].
/// ```dart continued
/// queue.add(5);
/// queue.addFirst(0);
/// queue.addLast(10);
/// queue.addAll([1, 2, 3]);
/// print(queue); // {0, 5, 10, 1, 2, 3}
/// ```
/// To check if the queue is empty, use [isEmpty] or [isNotEmpty].
/// To find the number of queue entries, use [length].
/// ```dart continued
/// final isEmpty = queue.isEmpty; // false
/// final queueSize = queue.length; // 6
/// ```
/// To get first or last item from queue, use [first] or [last].
/// ```dart continued
/// final first = queue.first; // 0
/// final last = queue.last; // 3
/// ```
/// To get item value using index, use [elementAt].
/// ```dart continued
/// final itemAt = queue.elementAt(2); // 10
/// ```
/// To convert queue to list, call [toList].
/// ```dart continued
/// final numbers = queue.toList();
/// print(numbers); // [0, 5, 10, 1, 2, 3]
/// ```
/// To remove item from queue, call [remove], [removeFirst] or [removeLast].
/// ```dart continued
/// queue.remove(10);
/// queue.removeFirst();
/// queue.removeLast();
/// print(queue); // {5, 1, 2}
/// ```
/// To remove multiple elements at the same time, use [removeWhere].
/// ```dart continued
/// queue.removeWhere((element) => element == 1);
/// print(queue); // {5, 2}
/// ```
/// To remove all elements in this queue that do not meet a condition,
/// use [retainWhere].
/// ```dart continued
/// queue.retainWhere((element) => element < 4);
/// print(queue); // {2}
/// ```
/// To remove all items and empty the set, use [clear].
/// ```dart continued
/// queue.clear();
/// print(queue.isEmpty); // true
/// print(queue); // {}
/// ```
class ListQueue<E> extends ListIterable<E> implements Queue<E> {
  static const int _INITIAL_CAPACITY = 8;
  List<E?> _table;
  int _head;
  int _tail;
  int _modificationCount = 0;

  /// Create an empty queue.
  ///
  /// If [initialCapacity] is given, prepare the queue for at least that many
  /// elements.
  ListQueue([int? initialCapacity])
      : _head = 0,
        _tail = 0,
        _table = List<E?>.filled(_calculateCapacity(initialCapacity), null);

  static int _calculateCapacity(int? initialCapacity) {
    if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) {
      return _INITIAL_CAPACITY;
    } else if (!_isPowerOf2(initialCapacity)) {
      return _nextPowerOf2(initialCapacity);
    }
    assert(_isPowerOf2(initialCapacity));
    return initialCapacity;
  }

  /// Create a `ListQueue` containing all [elements].
  ///
  /// The elements are added to the queue, as by [addLast], in the order given
  /// by `elements.iterator`.
  ///
  /// All the [elements] should be instances of [E].
  /// The `elements` iterable itself may have any element type, so this
  /// constructor can be used to down-cast a `Queue`, for example as:
  /// ```dart
  /// Queue<SuperType> superQueue = ...;
  /// Queue<SubType> subQueue =
  ///     ListQueue<SubType>.from(superQueue.whereType<SubType>());
  /// ```
  /// Example:
  /// ```dart
  /// final numbers = <num>[10, 20, 30];
  /// final queue = ListQueue<int>.from(numbers);
  /// print(queue); // {10, 20, 30}
  /// ```
  factory ListQueue.from(Iterable<dynamic> elements) {
    if (elements is List<dynamic>) {
      int length = elements.length;
      ListQueue<E> queue = ListQueue<E>(length + 1);
      assert(queue._table.length > length);
      for (int i = 0; i < length; i++) {
        queue._table[i] = elements[i] as E;
      }
      queue._tail = length;
      return queue;
    } else {
      int capacity = _INITIAL_CAPACITY;
      if (elements is EfficientLengthIterable) {
        capacity = elements.length;
      }
      ListQueue<E> result = ListQueue<E>(capacity);
      for (final element in elements) {
        result.addLast(element as E);
      }
      return result;
    }
  }

  /// Create a `ListQueue` from [elements].
  ///
  /// The elements are added to the queue, as by [addLast], in the order given
  /// by `elements.iterator`.
  /// Example:
  /// ```dart
  /// final baseQueue = ListQueue.of([1.0, 2.0, 3.0]); // A ListQueue<double>
  /// final numQueue = ListQueue<num>.of(baseQueue);
  /// print(numQueue); // {1.0, 2.0, 3.0}
  /// ```
  factory ListQueue.of(Iterable<E> elements) =>
      ListQueue<E>()..addAll(elements);

  // Iterable interface.

  Queue<R> cast<R>() => Queue.castFrom<E, R>(this);
  Iterator<E> get iterator => _ListQueueIterator<E>(this);

  void forEach(void f(E element)) {
    int modificationCount = _modificationCount;
    for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) {
      f(_table[i] as E);
      _checkModification(modificationCount);
    }
  }

  bool get isEmpty => _head == _tail;

  int get length => (_tail - _head) & (_table.length - 1);

  E get first {
    if (_head == _tail) throw IterableElementError.noElement();
    return _table[_head] as E;
  }

  E get last {
    if (_head == _tail) throw IterableElementError.noElement();
    return _table[(_tail - 1) & (_table.length - 1)] as E;
  }

  E get single {
    if (_head == _tail) throw IterableElementError.noElement();
    if (length > 1) throw IterableElementError.tooMany();
    return _table[_head] as E;
  }

  E elementAt(int index) {
    RangeError.checkValidIndex(index, this);
    return _table[(_head + index) & (_table.length - 1)] as E;
  }

  List<E> toList({bool growable = true}) {
    int mask = _table.length - 1;
    int length = (_tail - _head) & mask;
    if (length == 0) return List<E>.empty(growable: growable);

    var list = List<E>.filled(length, first, growable: growable);
    for (int i = 0; i < length; i++) {
      list[i] = _table[(_head + i) & mask] as E;
    }
    return list;
  }

  // Collection interface.

  void add(E value) {
    _add(value);
  }

  void addAll(Iterable<E> elements) {
    if (elements is List<E>) {
      List<E> list = elements;
      int addCount = list.length;
      int length = this.length;
      if (length + addCount >= _table.length) {
        _preGrow(length + addCount);
        // After preGrow, all elements are at the start of the list.
        _table.setRange(length, length + addCount, list, 0);
        _tail += addCount;
      } else {
        // Adding addCount elements won't reach _head.
        int endSpace = _table.length - _tail;
        if (addCount < endSpace) {
          _table.setRange(_tail, _tail + addCount, list, 0);
          _tail += addCount;
        } else {
          int preSpace = addCount - endSpace;
          _table.setRange(_tail, _tail + endSpace, list, 0);
          _table.setRange(0, preSpace, list, endSpace);
          _tail = preSpace;
        }
      }
      _modificationCount++;
    } else {
      for (E element in elements) _add(element);
    }
  }

  bool remove(Object? value) {
    for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) {
      E? element = _table[i];
      if (element == value) {
        _remove(i);
        _modificationCount++;
        return true;
      }
    }
    return false;
  }

  void _filterWhere(bool test(E element), bool removeMatching) {
    int modificationCount = _modificationCount;
    int i = _head;
    while (i != _tail) {
      E element = _table[i] as E;
      bool remove = identical(removeMatching, test(element));
      _checkModification(modificationCount);
      if (remove) {
        i = _remove(i);
        modificationCount = ++_modificationCount;
      } else {
        i = (i + 1) & (_table.length - 1);
      }
    }
  }

  /// Remove all elements matched by [test].
  ///
  /// This method is inefficient since it works by repeatedly removing single
  /// elements, each of which can take linear time.
  void removeWhere(bool test(E element)) {
    _filterWhere(test, true);
  }

  /// Remove all elements not matched by [test].
  ///
  /// This method is inefficient since it works by repeatedly removing single
  /// elements, each of which can take linear time.
  void retainWhere(bool test(E element)) {
    _filterWhere(test, false);
  }

  void clear() {
    if (_head != _tail) {
      for (int i = _head; i != _tail; i = (i + 1) & (_table.length - 1)) {
        _table[i] = null;
      }
      _head = _tail = 0;
      _modificationCount++;
    }
  }

  String toString() => IterableBase.iterableToFullString(this, "{", "}");

  // Queue interface.

  void addLast(E value) {
    _add(value);
  }

  void addFirst(E value) {
    _head = (_head - 1) & (_table.length - 1);
    _table[_head] = value;
    if (_head == _tail) _grow();
    _modificationCount++;
  }

  E removeFirst() {
    if (_head == _tail) throw IterableElementError.noElement();
    _modificationCount++;
    E result = _table[_head] as E;
    _table[_head] = null;
    _head = (_head + 1) & (_table.length - 1);
    return result;
  }

  E removeLast() {
    if (_head == _tail) throw IterableElementError.noElement();
    _modificationCount++;
    _tail = (_tail - 1) & (_table.length - 1);
    E result = _table[_tail] as E;
    _table[_tail] = null;
    return result;
  }

  // Internal helper functions.

  /// Whether [number] is a power of two.
  ///
  /// Only works for positive numbers.
  static bool _isPowerOf2(int number) => (number & (number - 1)) == 0;

  /// Rounds [number] up to the nearest power of 2.
  ///
  /// If [number] is a power of 2 already, it is returned.
  ///
  /// Only works for positive numbers.
  static int _nextPowerOf2(int number) {
    assert(number > 0);
    number = (number << 1) - 1;
    for (;;) {
      int nextNumber = number & (number - 1);
      if (nextNumber == 0) return number;
      number = nextNumber;
    }
  }

  /// Check if the queue has been modified during iteration.
  void _checkModification(int expectedModificationCount) {
    if (expectedModificationCount != _modificationCount) {
      throw ConcurrentModificationError(this);
    }
  }

  /// Adds element at end of queue. Used by both [add] and [addAll].
  void _add(E element) {
    _table[_tail] = element;
    _tail = (_tail + 1) & (_table.length - 1);
    if (_head == _tail) _grow();
    _modificationCount++;
  }

  /// Removes the element at [offset] into [_table].
  ///
  /// Removal is performed by linearly moving elements either before or after
  /// [offset] by one position.
  ///
  /// Returns the new offset of the following element. This may be the same
  /// offset or the following offset depending on how elements are moved
  /// to fill the hole.
  int _remove(int offset) {
    int mask = _table.length - 1;
    int startDistance = (offset - _head) & mask;
    int endDistance = (_tail - offset) & mask;
    if (startDistance < endDistance) {
      // Closest to start.
      int i = offset;
      while (i != _head) {
        int prevOffset = (i - 1) & mask;
        _table[i] = _table[prevOffset];
        i = prevOffset;
      }
      _table[_head] = null;
      _head = (_head + 1) & mask;
      return (offset + 1) & mask;
    } else {
      _tail = (_tail - 1) & mask;
      int i = offset;
      while (i != _tail) {
        int nextOffset = (i + 1) & mask;
        _table[i] = _table[nextOffset];
        i = nextOffset;
      }
      _table[_tail] = null;
      return offset;
    }
  }

  /// Grow the table when full.
  void _grow() {
    List<E?> newTable = List<E?>.filled(_table.length * 2, null);
    int split = _table.length - _head;
    newTable.setRange(0, split, _table, _head);
    newTable.setRange(split, split + _head, _table, 0);
    _head = 0;
    _tail = _table.length;
    _table = newTable;
  }

  int _writeToList(List<E?> target) {
    assert(target.length >= length);
    if (_head <= _tail) {
      int length = _tail - _head;
      target.setRange(0, length, _table, _head);
      return length;
    } else {
      int firstPartSize = _table.length - _head;
      target.setRange(0, firstPartSize, _table, _head);
      target.setRange(firstPartSize, firstPartSize + _tail, _table, 0);
      return _tail + firstPartSize;
    }
  }

  /// Grows the table even if it is not full.
  void _preGrow(int newElementCount) {
    assert(newElementCount >= length);

    // Add some extra room to ensure that there's room for more elements after
    // expansion.
    newElementCount += newElementCount >> 1;
    int newCapacity = _nextPowerOf2(newElementCount);
    List<E?> newTable = List<E?>.filled(newCapacity, null);
    _tail = _writeToList(newTable);
    _table = newTable;
    _head = 0;
  }
}

/// Iterator for a [ListQueue].
///
/// Considers any add or remove operation a concurrent modification.
class _ListQueueIterator<E> implements Iterator<E> {
  final ListQueue<E> _queue;
  final int _end;
  final int _modificationCount;
  int _position;
  E? _current;

  _ListQueueIterator(ListQueue<E> queue)
      : _queue = queue,
        _end = queue._tail,
        _modificationCount = queue._modificationCount,
        _position = queue._head;

  E get current => _current as E;

  bool moveNext() {
    _queue._checkModification(_modificationCount);
    if (_position == _end) {
      _current = null;
      return false;
    }
    _current = _queue._table[_position];
    _position = (_position + 1) & (_queue._table.length - 1);
    return true;
  }
}