    "A collection in which each distinct element occurs at most
     once. Two non-[[identical|Identifiable]] values are
     considered distinct only if they are unequal, according to
     their own definition of [[value equality|Object.equals]].

     A `Set` is a [[Collection]] of its elements. Sets may not
     have [[null|Null]] elements.

     A new `Set` may be obtained by calling the function [[set]].

         value words = set { \"hello\", \"world\" };
         value greetings = set { \"hello\", \"goodbye\", \"hola\", \"adios\" };

     The [[emptySet]] is a `Set` with no elements.

     Sets may be the subject of the binary union, intersection,
     and complement operators `|`, `&`, and `~`.

         value greetingsInWords = words & greetings;
         value allWords = words | greetings;

     An implementation of `Set` may compare elements for
     equality using [[Object.equals]] or [[Comparable.compare]]."
    tagged("Collections")
    see (`function package.set`, `value emptySet`)
    shared interface Set<out Element=Object>
            satisfies Collection<Element>
            given Element satisfies Object {

        "The fundamental operation for `Set`s. Determines if the
         given value belongs to this set."
        shared actual default Boolean contains(Object element)
                => super.contains(element);

        "A shallow copy of this set, that is, a set with the
         same elements as this set, which do not change if the
         elements of this set change."
        shared actual formal Set<Element> clone();

        "Determines if this set is a superset of the given
         `Set`, that is, if this set contains all of the
         elements in the given set."
        shared default Boolean superset(Set<> set) {
            for (element in set) {
                if (!contains(element)) {
                    return false;
                }
            }
            else {
                return true;
            }
        }

        "Determines if this set is a subset of the given `Set`,
         that is, if the given set contains all of the elements
         in this set."
        shared default Boolean subset(Set<> set) {
            for (element in this) {
                if (!element in set) {
                    return false;
                }
            }
            else {
                return true;
            }
        }

        distinct => this;

        shared actual {Element*}
        defaultNullElements<Default>(Default defaultValue)
                given Default satisfies Object => this;

        "Returns a new `Set` containing all the elements of this
         set and all the elements of the given `Set`.

         For example:

             set { \"hello\", \"world\" } | set { 1, 2, \"hello\" }

         Produces the set `{ \"hello\", \"world\", 1, 2 }` of
         type `Set<String|Integer>`.

         Note that it is possible for two sets of disjoint
         element type to be considered to have elements in
         common. For example, since \`1==1.0\`
         [[evaluates to true|Integer.equals]],
         the expression

             set { 1 } | set { 1.0 }

         produces the set `{ 1 }`."
        shared default
        Set<Element|Other> union<Other>(Set<Other> set)
                given Other satisfies Object
                => package.set(chain(set));

        "Returns a new `Set` containing only the elements that
         are present in both this set and the given `Set` and
         that are instances of the intersection `Element&Other`
         of the element types of the two sets.

         For example:

             set { \"hello\", \"world\" } & set { 1, 2, \"hello\" }

         Produces the set `{ \"hello\" }` of type `Set<String>`.

         Note that, according to this definition, and even
         though `1==1.0` [[evaluates to true|Integer.equals]],
         the expression

             set { 1 } & set { 1.0 }

         produces the empty set `{}`."
        shared default
        Set<Element&Other> intersection<Other>(Set<Other> set)
                given Other satisfies Object
                => package.set(filter((e) => e in set)
                        .narrow<Other>());

        "Returns a new `Set` containing all the elements in this
         set that are not contained in the given `Set`.

         For example:

             set { \"hello\", \"world\" } ~ set { 1, 2, \"hello\" }

         Produces the set `{ \"world\" }` of type `Set<String>`."
        shared default
        Set<Element> complement<Other>(Set<Other> set)
                given Other satisfies Object
                => package.set(filter((e) => !e in set));

        "Returns a new `Set` containing only the elements
         contained in either this set or the given `Set`, but no
         element contained in both sets."
        shared default
        Set<Element|Other> exclusiveUnion<Other>(Set<Other> set)
                given Other satisfies Object
                => package.set(filter((e) => !e in set)
                        .chain(set.filter((e) => !e in this)));

        "Two `Set`s are considered equal if they have the same
         size and if every element of the first set is also an
         element of the second set, as determined by
         [[contains]]. Equivalently, a set is equal to a second
         set if it is both a subset and a superset of the second
         set."
        shared actual default Boolean equals(Object that) {
            if (is Set<> that,
                    that.size==size) {
                for (element in this) {
                    if (!element in that) {
                        return false;
                    }
                }
                else {
                    return true;
                }
            }
            return false;
        }

        shared actual default Integer hash {
            variable Integer hashCode = 0;
            for (elem in this) {
                hashCode += elem.hash;
            }
            return hashCode;
        }

    }

    "Create a new immutable [[Set]] containing every element
     produced by the given [[stream]], resolving items with
     duplicate keys according to the given [[function|choosing]].

     For example:

         set { 0, 1, 1, 2, 3, 3, 3 }

     produces the set `{ 0, 1, 2, 3 }`.

     This is an eager operation and the resulting set does not
     reflect changes to the given [[stream]]."
    see(`value Iterable.distinct`)
    shared Set<Element> set<Element>(
        "The stream of elements."
        {Element*} stream,
        "A function that chooses between duplicate elements. By
         default, the element that occurs _earlier_ in the
         stream is chosen."
        Element choosing(Element earlier, Element later)
                => earlier)
            given Element satisfies Object
            => object extends Object()
            satisfies Set<Element&Object> {

        value elements =
                stream.summarize(identity,
                    (Element? current, element)
                            => if (exists current)
                            then choosing(current, element)
                            else element);

        contains(Object element) => elements.defines(element);

        iterator() => elements.keys.iterator();

        size => elements.size;

        empty => elements.empty;

        clone() => this;

    };

    "An immutable [[Set]] with no elements."
    tagged("Collections")
    shared object emptySet
            extends Object()
            satisfies Set<Nothing> {

        shared actual
        Set<Other> union<Other>(Set<Other> set)
                given Other satisfies Object
                => set;

        shared actual
        Set<Nothing> intersection<Other>(Set<Other> set)
                given Other satisfies Object
                => this;

        shared actual
        Set<Other> exclusiveUnion<Other>(Set<Other> set)
                given Other satisfies Object
                => set;

        shared actual
        Set<Nothing> complement<Other>(Set<Other> set)
                given Other satisfies Object
                => this;

        subset(Set<> set) => true;
        superset(Set<> set) => set.empty;

        clone() => this;
        iterator() => emptyIterator;
        size => 0;
        empty => true;

        contains(Object element) => false;
        containsAny({Object*} elements) => false;
        containsEvery({Object*} elements) => false;

        count(Boolean selecting(Nothing element)) => 0;
        any(Boolean selecting(Nothing element)) => false;
        every(Boolean selecting(Nothing element)) => true;

        shared actual
        Null find(Boolean selecting(Nothing element))
                => null;

        shared actual
        Null findLast(Boolean selecting(Nothing element))
                => null;

        skip(Integer skipping) => this;
        take(Integer taking) => this;
        by(Integer step) => this;

        shared actual
        void each(void step(Nothing element)) {}

    }