class HashSetIterator<E> implements Iterator<E> {

  // TODO(4504458): Replace set_ with set.
  HashSetIterator(HashSetImplementation<E> set_)
    : _nextValidIndex = -1,
      _entries = set_._backingMap._keys {
    _advance();
  }

  bool hasNext() {
    if (_nextValidIndex >= _entries.length) return false;
    if (_entries[_nextValidIndex] === HashMapImplementation._DELETED_KEY) {
      // This happens in case the set was modified in the meantime.
      // A modification on the set may make this iterator misbehave,
      // but we should never return the sentinel.
      _advance();
    }
    return _nextValidIndex < _entries.length;
  }

  E next() {
    if (!hasNext()) {
      throw const NoMoreElementsException();
    }
    E res = _entries[_nextValidIndex];
    _advance();
    return res;
  }

  void _advance() {
    int length = _entries.length;
    var entry;
    final deletedKey = HashMapImplementation._DELETED_KEY;
    do {
      if (++_nextValidIndex >= length) break;
      entry = _entries[_nextValidIndex];
    } while ((entry === null) || (entry === deletedKey));
  }

  // The entries in the set. May contain null or the sentinel value.
  List<E> _entries;

  // The next valid index in [_entries] or the length of [entries_].
  // If it is the length of [_entries], calling [hasNext] on the
  // iterator will return false.
  int _nextValidIndex;
}