// 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;

/**
 * A [LinkedHashSet] is a hash-table based [Set] implementation.
 *
 * The `LinkedHashSet` also keep track of the order that elements were inserted
 * in, and iteration happens in first-to-last insertion order.
 *
 * The elements of a `LinkedHashSet` must have consistent [Object.operator==]
 * and [Object.hashCode] implementations. This means that the `==` operator
 * must define a stable equivalence relation on the elements (reflexive,
 * symmetric, transitive, and consistent over time), and that `hashCode`
 * must be the same for objects that are considered equal by `==`.
 *
 * The set allows `null` as an element.
 *
 * Iteration of elements is done in element insertion order.
 * An element that was added after another will occur later in the iteration.
 * Adding an element that is already in the set
 * does not change its position in the iteration order,
 * but removing an element and adding it again,
 * will make it the last element of an iteration.
 *
 * 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..
 */
abstract class LinkedHashSet<E> implements HashSet<E> {
  /**
   * Create an insertion-ordered hash set using the provided
   * [equals] and [hashCode].
   *
   * The provided [equals] must define a stable equivalence relation, and
   * [hashCode] must be consistent with [equals]. If the [equals] or [hashCode]
   * methods won't work on all objects, but only to instances of E, the
   * [isValidKey] predicate can be used to restrict the keys that they are
   * applied to. Any key for which [isValidKey] returns false is automatically
   * assumed to not be in the set.
   *
   * If [equals] or [hashCode] are omitted, the set uses
   * the objects' intrinsic [Object.operator==] and [Object.hashCode],
   *
   * If [isValidKey] is omitted, it defaults to testing if the object is an
   * [E] instance.
   *
   * If you supply one of [equals] and [hashCode],
   * you should generally also to supply the other.
   * An example would be using [identical] and [identityHashCode],
   * which is equivalent to using the shorthand [LinkedSet.identity]).
   */
  external factory LinkedHashSet({ bool equals(E e1, E e2),
                                   int hashCode(E e),
                                   bool isValidKey(potentialKey) });

  /**
   * Creates an insertion-ordered identity-based set.
   *
   * Effectively a shorthand for:
   *
   *     new LinkedHashSet(equals: identical, hashCode: identityHashCodeOf)
   */
  external factory LinkedHashSet.identity();

  /**
   * Create a linked hash set containing all [elements].
   *
   * Creates a linked hash set as by `new LinkedHashSet<E>()` and adds each
   * element of`elements` to this set in the order they are iterated.
   *
   * All the [elements] should be assignable to [E].
   * The `elements` iterable itself may have any element type,
   * so this constructor can be used to down-cast a `Set`, for example as:
   *
   *     Set<SuperType> superSet = ...;
   *     Iterable<SuperType> tmp = superSet.where((e) => e is SubType);
   *     Set<SubType> subSet = new LinkedHashSet<SubType>.from(tmp);
   */
  factory LinkedHashSet.from(Iterable<E> elements) {
    LinkedHashSet<E> result = new LinkedHashSet<E>();
    for (final E element in elements) {
      result.add(element);
    }
    return result;
  }

  /**
   * Executes a function on each element of the set.
   *
   * The elements are iterated in insertion order.
   */
  void forEach(void action(E element));

  /**
   * Provides an iterator that iterates over the elements in insertion order.
   */
  Iterator<E> get iterator;
}