sdk/lib/core/set.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.

/**
 * This class is the public interface of a set. A set is a collection
 * without duplicates.
 */
abstract class Set<E> extends Collection<E> {
  factory Set() => new _HashSetImpl<E>();

  /**
   * Creates a [Set] that contains all elements of [other].
   */
  factory Set.from(Iterable<E> other) => new _HashSetImpl<E>.from(other);

  /**
   * Returns true if [value] is in the set.
   */
  bool contains(E value);

  /**
   * Adds [value] into the set. The method has no effect if
   * [value] was already in the set.
   */
  void add(E value);

  /**
   * Removes [value] from the set. Returns true if [value] was
   * in the set. Returns false otherwise. The method has no effect
   * if [value] value was not in the set.
   */
  bool remove(E value);

  /**
   * Adds all the elements of the given collection to the set.
   */
  void addAll(Collection<E> collection);

  /**
   * Removes all the elements of the given collection from the set.
   */
  void removeAll(Collection<E> collection);

  /**
   * Returns true if [collection] contains all the elements of this
   * collection.
   */
  bool isSubsetOf(Collection<E> collection);

  /**
   * Returns true if this collection contains all the elements of
   * [collection].
   */
  bool containsAll(Collection<E> collection);

  /**
   * Returns a new set which is the intersection between this set and
   * the given collection.
   */
  Set<E> intersection(Collection<E> other);

  /**
   * Removes all elements in the set.
   */
  void clear();

}

abstract class HashSet<E> extends Set<E> {
  factory HashSet() => new _HashSetImpl<E>();

  /**
   * Creates a [Set] that contains all elements of [other].
   */
  factory HashSet.from(Iterable<E> other) => new _HashSetImpl<E>.from(other);
}


class _HashSetImpl<E> implements HashSet<E> {

  _HashSetImpl() {
    _backingMap = new _HashMapImpl<E, E>();
  }

  factory _HashSetImpl.from(Iterable<E> other) {
    Set<E> set = new _HashSetImpl<E>();
    for (final e in other) {
      set.add(e);
    }
    return set;
  }

  void clear() {
    _backingMap.clear();
  }

  void add(E value) {
    _backingMap[value] = value;
  }

  bool contains(E value) {
    return _backingMap.containsKey(value);
  }

  bool remove(E value) {
    if (!_backingMap.containsKey(value)) return false;
    _backingMap.remove(value);
    return true;
  }

  void addAll(Collection<E> collection) {
    collection.forEach(void _(E value) {
      add(value);
    });
  }

  Set<E> intersection(Collection<E> collection) {
    Set<E> result = new Set<E>();
    collection.forEach(void _(E value) {
      if (contains(value)) result.add(value);
    });
    return result;
  }

  bool isSubsetOf(Collection<E> other) {
    return new Set<E>.from(other).containsAll(this);
  }

  void removeAll(Collection<E> collection) {
    collection.forEach(void _(E value) {
      remove(value);
    });
  }

  bool containsAll(Collection<E> collection) {
    return collection.every(bool _(E value) {
      return contains(value);
    });
  }

  void forEach(void f(E element)) {
    _backingMap.forEach(void _(E key, E value) {
      f(key);
    });
  }

  Set map(f(E element)) {
    Set result = new Set();
    _backingMap.forEach(void _(E key, E value) {
      result.add(f(key));
    });
    return result;
  }

  Dynamic reduce(Dynamic initialValue,
                 Dynamic combine(Dynamic previousValue, E element)) {
    return Collections.reduce(this, initialValue, combine);
  }

  Set<E> filter(bool f(E element)) {
    Set<E> result = new Set<E>();
    _backingMap.forEach(void _(E key, E value) {
      if (f(key)) result.add(key);
    });
    return result;
  }

  bool every(bool f(E element)) {
    Collection<E> keys = _backingMap.keys;
    return keys.every(f);
  }

  bool some(bool f(E element)) {
    Collection<E> keys = _backingMap.keys;
    return keys.some(f);
  }

  bool get isEmpty {
    return _backingMap.isEmpty;
  }

  int get length {
    return _backingMap.length;
  }

  Iterator<E> iterator() {
    return new _HashSetIterator<E>(this);
  }

  String toString() {
    return Collections.collectionToString(this);
  }

  // The map backing this set. The associations in this map are all
  // of the form element -> element. If a value is not in the map,
  // then it is not in the set.
  _HashMapImpl<E, E> _backingMap;
}

class _HashSetIterator<E> implements Iterator<E> {

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

  bool get hasNext {
    if (_nextValidIndex >= _entries.length) return false;
    if (identical(_entries[_nextValidIndex], _HashMapImpl._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 new StateError("No more elements");
    }
    E res = _entries[_nextValidIndex];
    _advance();
    return res;
  }

  void _advance() {
    int length = _entries.length;
    var entry;
    final deletedKey = _HashMapImpl._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;
}