| // Copyright (c) 2013, 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; |
| |
| /// An unordered hash-table based [Set] implementation. |
| /// |
| /// The elements of a `HashSet` must have consistent equality |
| /// and hashCode implementations. This means that the equals operation |
| /// must define a stable equivalence relation on the elements (reflexive, |
| /// symmetric, transitive, and consistent over time), and that the hashCode |
| /// must consistent with equality, so that the same for objects that are |
| /// considered equal. |
| /// |
| /// Most simple operations on `HashSet` are done in (potentially amortized) |
| /// constant time: [add], [contains], [remove], and [length], provided the hash |
| /// codes of objects are well distributed. |
| /// |
| /// The iteration order of the set is not specified and depends on |
| /// the hashcodes of the provided elements. However, the order is stable: |
| /// multiple iterations over the same set produce the same order, as long as |
| /// the set is not modified. |
| abstract class HashSet<E> implements Set<E> { |
| /// Create a hash set using the provided [equals] as equality. |
| /// |
| /// The provided [equals] must define a stable equivalence relation, and |
| /// [hashCode] must be consistent with [equals]. |
| /// |
| /// If [equals] or [hashCode] are omitted, the set uses |
| /// the elements' intrinsic [Object.==] and [Object.hashCode]. |
| /// |
| /// If you supply one of [equals] and [hashCode], |
| /// you should generally also to supply the other. |
| /// |
| /// Some [equals] or [hashCode] functions might not work for all objects. |
| /// If [isValidKey] is supplied, it's used to check a potential element |
| /// which is not necessarily an instance of [E], like the argument to |
| /// [contains] which is typed as `Object?`. |
| /// If [isValidKey] returns `false`, for an object, the [equals] and |
| /// [hashCode] functions are not called, and no key equal to that object |
| /// is assumed to be in the map. |
| /// The [isValidKey] function defaults to just testing if the object is an |
| /// instance of [E], which means that: |
| /// ```dart template:expression |
| /// HashSet<int>(equals: (int e1, int e2) => (e1 - e2) % 5 == 0, |
| /// hashCode: (int e) => e % 5) |
| /// ``` |
| /// does not need an `isValidKey` argument because it defaults to only |
| /// accepting `int` values which are accepted by both `equals` and `hashCode`. |
| /// |
| /// If neither `equals`, `hashCode`, nor `isValidKey` is provided, |
| /// the default `isValidKey` instead accepts all values. |
| /// The default equality and hashcode operations are assumed to work on all |
| /// objects. |
| /// |
| /// Likewise, if `equals` is [identical], `hashCode` is [identityHashCode] |
| /// and `isValidKey` is omitted, the resulting set is identity based, |
| /// and the `isValidKey` defaults to accepting all keys. |
| /// Such a map can be created directly using [HashSet.identity]. |
| external factory HashSet( |
| {bool Function(E, E)? equals, |
| int Function(E)? hashCode, |
| bool Function(dynamic)? isValidKey}); |
| |
| /// Creates an unordered identity-based set. |
| /// |
| /// Effectively a shorthand for: |
| /// ```dart |
| /// HashSet<E>(equals: identical, hashCode: identityHashCode) |
| /// ``` |
| external factory HashSet.identity(); |
| |
| /// Create a hash set containing all [elements]. |
| /// |
| /// Creates a hash set as by `HashSet<E>()` and adds all given [elements] |
| /// to the set. The elements are added in order. If [elements] contains |
| /// two entries that are equal, but not identical, then the first one is |
| /// the one in the resulting set. |
| /// |
| /// 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 `Set`, for example as: |
| /// ```dart |
| /// Set<SuperType> superSet = ...; |
| /// Set<SubType> subSet = |
| /// HashSet<SubType>.from(superSet.whereType<SubType>()); |
| /// ``` |
| factory HashSet.from(Iterable<dynamic> elements) { |
| HashSet<E> result = HashSet<E>(); |
| for (final e in elements) { |
| result.add(e as E); |
| } |
| return result; |
| } |
| |
| /// Create a hash set containing all [elements]. |
| /// |
| /// Creates a hash set as by `new HashSet<E>()` and adds all given [elements] |
| /// to the set. The elements are added in order. If [elements] contains |
| /// two entries that are equal, but not identical, then the first one is |
| /// the one in the resulting set. |
| factory HashSet.of(Iterable<E> elements) => HashSet<E>()..addAll(elements); |
| |
| /// Provides an iterator that iterates over the elements of this set. |
| /// |
| /// The order of iteration is unspecified, |
| /// but consistent between changes to the set. |
| Iterator<E> get iterator; |
| } |