/*

* Copyright (C) 2007 The Guava Authors

*

* Licensed under the Apache License, Version 2.0 (the "License");

* you may not use this file except in compliance with the License.

* You may obtain a copy of the License at

*

* http://www.apache.org/licenses/LICENSE-2.0

*

* Unless required by applicable law or agreed to in writing, software

* distributed under the License is distributed on an "AS IS" BASIS,

* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

* See the License for the specific language governing permissions and

* limitations under the License.

*/

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;

import static com.google.common.base.Preconditions.checkNotNull;

import static com.google.common.base.Predicates.and;

import static com.google.common.collect.CollectPreconditions.checkNonnegative;

import static com.google.common.collect.Iterables.find;

import static com.google.common.collect.Iterables.removeFirstMatching;

import static com.google.common.collect.Iterators.addAll;

import static com.google.common.collect.Iterators.find;

import static com.google.common.collect.Iterators.removeAll;

import static com.google.common.collect.Iterators.unmodifiableIterator;

import static com.google.common.collect.Lists.newArrayList;

import static com.google.common.collect.Maps.capacity;

import static com.google.common.collect.Maps.indexMap;

import static com.google.common.math.IntMath.saturatedAdd;

import static java.lang.Math.max;

import static java.lang.Math.min;

import static java.util.Arrays.asList;

import static java.util.Collections.unmodifiableSortedSet;

import com.google.common.annotations.GwtCompatible;

import com.google.common.annotations.GwtIncompatible;

import com.google.common.annotations.J2ktIncompatible;

import com.google.common.base.Predicate;

import com.google.common.collect.Collections2.FilteredCollection;

import com.google.common.math.IntMath;

import com.google.errorprone.annotations.CanIgnoreReturnValue;

import com.google.errorprone.annotations.DoNotCall;

import com.google.errorprone.annotations.InlineMe;

import com.google.errorprone.annotations.concurrent.LazyInit;

import java.io.Serializable;

import java.util.AbstractSet;

import java.util.Arrays;

import java.util.BitSet;

import java.util.Collection;

import java.util.Collections;

import java.util.Comparator;

import java.util.EnumSet;

import java.util.HashSet;

import java.util.IdentityHashMap;

import java.util.Iterator;

import java.util.LinkedHashSet;

import java.util.List;

import java.util.Map;

import java.util.NavigableSet;

import java.util.NoSuchElementException;

import java.util.Set;

import java.util.SortedSet;

import java.util.TreeSet;

import java.util.concurrent.ConcurrentHashMap;

import java.util.concurrent.CopyOnWriteArraySet;

import java.util.function.Consumer;

import java.util.stream.Collector;

import java.util.stream.Stream;

import org.jspecify.annotations.NonNull;

import org.jspecify.annotations.Nullable;

/**

* Static utility methods pertaining to {@link Set} instances. Also see this class's counterparts

* {@link Lists}, {@link Maps} and {@link Queues}.

*

* <p>See the Guava User Guide article on <a href=

* "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#sets">{@code Sets}</a>.

*

* @author Kevin Bourrillion

* @author Jared Levy

* @author Chris Povirk

* @since 2.0

*/

@GwtCompatible

public final class Sets {

private Sets() {}

/**

* {@link AbstractSet} substitute without the potentially-quadratic {@code removeAll}

* implementation.

*/

abstract static class ImprovedAbstractSet<E extends @Nullable Object> extends AbstractSet<E> {

@Override

public boolean removeAll(Collection<?> c) {

return removeAllImpl(this, c);

}

@Override

public boolean retainAll(Collection<?> c) {

return super.retainAll(checkNotNull(c)); // GWT compatibility

}

}

/**

* Returns an immutable set instance containing the given enum elements. Internally, the returned

* set will be backed by an {@link EnumSet}.

*

* <p>The iteration order of the returned set follows the enum's iteration order, not the order in

* which the elements are provided to the method.

*

* @param anElement one of the elements the set should contain

* @param otherElements the rest of the elements the set should contain

* @return an immutable set containing those elements, minus duplicates

*/

public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(

E anElement, E... otherElements) {

return ImmutableEnumSet.asImmutable(EnumSet.of(anElement, otherElements));

}

/**

* Returns an immutable set instance containing the given enum elements. Internally, the returned

* set will be backed by an {@link EnumSet}.

*

* <p>The iteration order of the returned set follows the enum's iteration order, not the order in

* which the elements appear in the given collection.

*

* @param elements the elements, all of the same {@code enum} type, that the set should contain

* @return an immutable set containing those elements, minus duplicates

*/

public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(Iterable<E> elements) {

if (elements instanceof ImmutableEnumSet) {

return (ImmutableEnumSet<E>) elements;

} else if (elements instanceof Collection) {

Collection<E> collection = (Collection<E>) elements;

if (collection.isEmpty()) {

return ImmutableSet.of();

} else {

return ImmutableEnumSet.asImmutable(EnumSet.copyOf(collection));

}

} else {

Iterator<E> itr = elements.iterator();

if (itr.hasNext()) {

EnumSet<E> enumSet = EnumSet.of(itr.next());

addAll(enumSet, itr);

return ImmutableEnumSet.asImmutable(enumSet);

} else {

return ImmutableSet.of();

}

}

}

/**

* Returns a {@code Collector} that accumulates the input elements into a new {@code ImmutableSet}

* with an implementation specialized for enums. Unlike {@link ImmutableSet#toImmutableSet}, the

* resulting set will iterate over elements in their enum definition order, not encounter order.

*

* @since 21.0

*/

public static <E extends Enum<E>> Collector<E, ?, ImmutableSet<E>> toImmutableEnumSet() {

return CollectCollectors.toImmutableEnumSet();

}

/**

* Returns a new, <i>mutable</i> {@code EnumSet} instance containing the given elements in their

* natural order. This method behaves identically to {@link EnumSet#copyOf(Collection)}, but also

* accepts non-{@code Collection} iterables and empty iterables.

*/

public static <E extends Enum<E>> EnumSet<E> newEnumSet(

Iterable<E> iterable, Class<E> elementType) {

EnumSet<E> set = EnumSet.noneOf(elementType);

Iterables.addAll(set, iterable);

return set;

}

// HashSet

/**

* Creates a <i>mutable</i>, initially empty {@code HashSet} instance.

*

* <p><b>Note:</b> if mutability is not required, use {@link ImmutableSet#of()} instead. If {@code

* E} is an {@link Enum} type, use {@link EnumSet#noneOf} instead. Otherwise, strongly consider

* using a {@code LinkedHashSet} instead, at the cost of increased memory footprint, to get

* deterministic iteration behavior.

*

* <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,

* use the {@code HashSet} constructor directly, taking advantage of <a

* href="https://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html#type-inference-instantiation">"diamond"

* syntax</a>.

*/

@SuppressWarnings("NonApiType") // acts as a direct substitute for a constructor call

public static <E extends @Nullable Object> HashSet<E> newHashSet() {

return new HashSet<>();

}

/**

* Creates a <i>mutable</i> {@code HashSet} instance initially containing the given elements.

*

* <p><b>Note:</b> if elements are non-null and won't be added or removed after this point, use

* {@link ImmutableSet#of()} or {@link ImmutableSet#copyOf(Object[])} instead. If {@code E} is an

* {@link Enum} type, use {@link EnumSet#of(Enum, Enum[])} instead. Otherwise, strongly consider

* using a {@code LinkedHashSet} instead, at the cost of increased memory footprint, to get

* deterministic iteration behavior.

*

* <p>This method is just a small convenience, either for {@code newHashSet(}{@link Arrays#asList

* asList}{@code (...))}, or for creating an empty set then calling {@link Collections#addAll}.

* This method is not actually very useful and will likely be deprecated in the future.

*/

@SuppressWarnings("NonApiType") // acts as a direct substitute for a constructor call

public static <E extends @Nullable Object> HashSet<E> newHashSet(E... elements) {

HashSet<E> set = newHashSetWithExpectedSize(elements.length);

Collections.addAll(set, elements);

return set;

}

/**

* Creates a <i>mutable</i> {@code HashSet} instance containing the given elements. A very thin

* convenience for creating an empty set then calling {@link Collection#addAll} or {@link

* Iterables#addAll}.

*

* <p><b>Note:</b> if mutability is not required and the elements are non-null, use {@link

* ImmutableSet#copyOf(Iterable)} instead.

*

* <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link #newEnumSet(Iterable, Class)}

* instead.

*

* <p><b>Note:</b> if {@code elements} is a {@link Collection}, you don't need this method.

* Instead, use the {@code HashSet} constructor directly, taking advantage of <a

* href="https://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html#type-inference-instantiation">"diamond"

* syntax</a>.

*

* <p>Overall, this method is not very useful and will likely be deprecated in the future.

*/

@SuppressWarnings("NonApiType") // acts as a direct substitute for a constructor call

public static <E extends @Nullable Object> HashSet<E> newHashSet(Iterable<? extends E> elements) {

return (elements instanceof Collection)

? new HashSet<>((Collection<? extends E>) elements)

: newHashSet(elements.iterator());

}

/**

* Creates a <i>mutable</i> {@code HashSet} instance containing the given elements. A very thin

* convenience for creating an empty set and then calling {@link Iterators#addAll}.

*

* <p><b>Note:</b> if mutability is not required and the elements are non-null, use {@link

* ImmutableSet#copyOf(Iterator)} instead.

*

* <p><b>Note:</b> if {@code E} is an {@link Enum} type, you should create an {@link EnumSet}

* instead.

*

* <p>Overall, this method is not very useful and will likely be deprecated in the future.

*/

@SuppressWarnings("NonApiType") // acts as a direct substitute for a constructor call

public static <E extends @Nullable Object> HashSet<E> newHashSet(Iterator<? extends E> elements) {

HashSet<E> set = new HashSet<>();

addAll(set, elements);

return set;

}

/**

* Returns a new hash set using the smallest initial table size that can hold {@code expectedSize}

* elements without resizing. Note that this is not what {@link HashSet#HashSet(int)} does, but it

* is what most users want and expect it to do.

*

* <p>This behavior can't be broadly guaranteed, but has been tested with OpenJDK 1.7 and 1.8.

*

* @param expectedSize the number of elements you expect to add to the returned set

* @return a new, empty hash set with enough capacity to hold {@code expectedSize} elements

* without resizing

* @throws IllegalArgumentException if {@code expectedSize} is negative

*/

@SuppressWarnings("NonApiType") // acts as a direct substitute for a constructor call

public static <E extends @Nullable Object> HashSet<E> newHashSetWithExpectedSize(

int expectedSize) {

return new HashSet<>(capacity(expectedSize));

}

/**

* Creates a thread-safe set backed by a hash map. The set is backed by a {@link

* ConcurrentHashMap} instance, and thus carries the same concurrency guarantees.

*

* <p>Unlike {@code HashSet}, this class does NOT allow {@code null} to be used as an element. The

* set is serializable.

*

* @return a new, empty thread-safe {@code Set}

* @since 15.0

*/

public static <E> Set<E> newConcurrentHashSet() {

return Platform.newConcurrentHashSet();

}

/**

* Creates a thread-safe set backed by a hash map and containing the given elements. The set is

* backed by a {@link ConcurrentHashMap} instance, and thus carries the same concurrency

* guarantees.

*

* <p>Unlike {@code HashSet}, this class does NOT allow {@code null} to be used as an element. The

* set is serializable.

*

* @param elements the elements that the set should contain

* @return a new thread-safe set containing those elements (minus duplicates)

* @throws NullPointerException if {@code elements} or any of its contents is null

* @since 15.0

*/

public static <E> Set<E> newConcurrentHashSet(Iterable<? extends E> elements) {

Set<E> set = newConcurrentHashSet();

Iterables.addAll(set, elements);

return set;

}

// LinkedHashSet

/**

* Creates a <i>mutable</i>, empty {@code LinkedHashSet} instance.

*

* <p><b>Note:</b> if mutability is not required, use {@link ImmutableSet#of()} instead.

*

* <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,

* use the {@code LinkedHashSet} constructor directly, taking advantage of <a

* href="https://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html#type-inference-instantiation">"diamond"

* syntax</a>.

*

* @return a new, empty {@code LinkedHashSet}

*/

@SuppressWarnings("NonApiType") // acts as a direct substitute for a constructor call

public static <E extends @Nullable Object> LinkedHashSet<E> newLinkedHashSet() {

return new LinkedHashSet<>();

}

/**

* Creates a <i>mutable</i> {@code LinkedHashSet} instance containing the given elements in order.

*

* <p><b>Note:</b> if mutability is not required and the elements are non-null, use {@link

* ImmutableSet#copyOf(Iterable)} instead.

*

* <p><b>Note:</b> if {@code elements} is a {@link Collection}, you don't need this method.

* Instead, use the {@code LinkedHashSet} constructor directly, taking advantage of <a

* href="https://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html#type-inference-instantiation">"diamond"

* syntax</a>.

*

* <p>Overall, this method is not very useful and will likely be deprecated in the future.

*

* @param elements the elements that the set should contain, in order

* @return a new {@code LinkedHashSet} containing those elements (minus duplicates)

*/

@SuppressWarnings("NonApiType") // acts as a direct substitute for a constructor call

public static <E extends @Nullable Object> LinkedHashSet<E> newLinkedHashSet(

Iterable<? extends E> elements) {

if (elements instanceof Collection) {

return new LinkedHashSet<>((Collection<? extends E>) elements);

}

LinkedHashSet<E> set = new LinkedHashSet<>();

Iterables.addAll(set, elements);

return set;

}

/**

* Creates a {@code LinkedHashSet} instance, with a high enough "initial capacity" that it

* <i>should</i> hold {@code expectedSize} elements without growth. This behavior cannot be

* broadly guaranteed, but it is observed to be true for OpenJDK 1.7. It also can't be guaranteed

* that the method isn't inadvertently <i>oversizing</i> the returned set.

*

* @param expectedSize the number of elements you expect to add to the returned set

* @return a new, empty {@code LinkedHashSet} with enough capacity to hold {@code expectedSize}

* elements without resizing

* @throws IllegalArgumentException if {@code expectedSize} is negative

* @since 11.0

*/

@SuppressWarnings("NonApiType") // acts as a direct substitute for a constructor call

public static <E extends @Nullable Object> LinkedHashSet<E> newLinkedHashSetWithExpectedSize(

int expectedSize) {

return new LinkedHashSet<>(capacity(expectedSize));

}

// TreeSet

/**

* Creates a <i>mutable</i>, empty {@code TreeSet} instance sorted by the natural sort ordering of

* its elements.

*

* <p><b>Note:</b> if mutability is not required, use {@link ImmutableSortedSet#of()} instead.

*

* <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,

* use the {@code TreeSet} constructor directly, taking advantage of <a

* href="https://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html#type-inference-instantiation">"diamond"

* syntax</a>.

*

* @return a new, empty {@code TreeSet}

*/

@SuppressWarnings({

"rawtypes", // https://github.com/google/guava/issues/989

"NonApiType", // acts as a direct substitute for a constructor call

})

public static <E extends Comparable> TreeSet<E> newTreeSet() {

return new TreeSet<>();

}

/**

* Creates a <i>mutable</i> {@code TreeSet} instance containing the given elements sorted by their

* natural ordering.

*

* <p><b>Note:</b> if mutability is not required, use {@link ImmutableSortedSet#copyOf(Iterable)}

* instead.

*

* <p><b>Note:</b> If {@code elements} is a {@code SortedSet} with an explicit comparator, this

* method has different behavior than {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code

* TreeSet} with that comparator.

*

* <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,

* use the {@code TreeSet} constructor directly, taking advantage of <a

* href="https://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html#type-inference-instantiation">"diamond"

* syntax</a>.

*

* <p>This method is just a small convenience for creating an empty set and then calling {@link

* Iterables#addAll}. This method is not very useful and will likely be deprecated in the future.

*

* @param elements the elements that the set should contain

* @return a new {@code TreeSet} containing those elements (minus duplicates)

*/

@SuppressWarnings({

"rawtypes", // https://github.com/google/guava/issues/989

"NonApiType", // acts as a direct substitute for a constructor call

})

public static <E extends Comparable> TreeSet<E> newTreeSet(Iterable<? extends E> elements) {

TreeSet<E> set = newTreeSet();

Iterables.addAll(set, elements);

return set;

}

/**

* Creates a <i>mutable</i>, empty {@code TreeSet} instance with the given comparator.

*

* <p><b>Note:</b> if mutability is not required, use {@code

* ImmutableSortedSet.orderedBy(comparator).build()} instead.

*

* <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,

* use the {@code TreeSet} constructor directly, taking advantage of <a

* href="https://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html#type-inference-instantiation">"diamond"

* syntax</a>. One caveat to this is that the {@code TreeSet} constructor uses a null {@code

* Comparator} to mean "natural ordering," whereas this factory rejects null. Clean your code

* accordingly.

*

* @param comparator the comparator to use to sort the set

* @return a new, empty {@code TreeSet}

* @throws NullPointerException if {@code comparator} is null

*/

@SuppressWarnings("NonApiType") // acts as a direct substitute for a constructor call

public static <E extends @Nullable Object> TreeSet<E> newTreeSet(

Comparator<? super E> comparator) {

return new TreeSet<>(checkNotNull(comparator));

}

/**

* Creates an empty {@code Set} that uses identity to determine equality. It compares object

* references, instead of calling {@code equals}, to determine whether a provided object matches

* an element in the set. For example, {@code contains} returns {@code false} when passed an

* object that equals a set member, but isn't the same instance. This behavior is similar to the

* way {@code IdentityHashMap} handles key lookups.

*

* @since 8.0

*/

public static <E extends @Nullable Object> Set<E> newIdentityHashSet() {

return Collections.newSetFromMap(new IdentityHashMap<>());

}

/**

* Creates an empty {@code CopyOnWriteArraySet} instance.

*

* <p><b>Note:</b> if you need an immutable empty {@link Set}, use {@link Collections#emptySet}

* instead.

*

* @return a new, empty {@code CopyOnWriteArraySet}

* @since 12.0

*/

@J2ktIncompatible

@GwtIncompatible // CopyOnWriteArraySet

public static <E extends @Nullable Object> CopyOnWriteArraySet<E> newCopyOnWriteArraySet() {

return new CopyOnWriteArraySet<>();

}

/**

* Creates a {@code CopyOnWriteArraySet} instance containing the given elements.

*

* @param elements the elements that the set should contain, in order

* @return a new {@code CopyOnWriteArraySet} containing those elements

* @since 12.0

*/

@J2ktIncompatible

@GwtIncompatible // CopyOnWriteArraySet

public static <E extends @Nullable Object> CopyOnWriteArraySet<E> newCopyOnWriteArraySet(

Iterable<? extends E> elements) {

// We copy elements to an ArrayList first, rather than incurring the

// quadratic cost of adding them to the COWAS directly.

Collection<? extends E> elementsCollection =

(elements instanceof Collection)

? (Collection<? extends E>) elements

: newArrayList(elements);

return new CopyOnWriteArraySet<>(elementsCollection);

}

/**

* Creates an {@code EnumSet} consisting of all enum values that are not in the specified

* collection. If the collection is an {@link EnumSet}, this method has the same behavior as

* {@link EnumSet#complementOf}. Otherwise, the specified collection must contain at least one

* element, in order to determine the element type. If the collection could be empty, use {@link

* #complementOf(Collection, Class)} instead of this method.

*

* @param collection the collection whose complement should be stored in the enum set

* @return a new, modifiable {@code EnumSet} containing all values of the enum that aren't present

* in the given collection

* @throws IllegalArgumentException if {@code collection} is not an {@code EnumSet} instance and

* contains no elements

*/

@J2ktIncompatible

@GwtIncompatible // EnumSet.complementOf

public static <E extends Enum<E>> EnumSet<E> complementOf(Collection<E> collection) {

if (collection instanceof EnumSet) {

return EnumSet.complementOf((EnumSet<E>) collection);

}

checkArgument(

!collection.isEmpty(), "collection is empty; use the other version of this method");

Class<E> type = collection.iterator().next().getDeclaringClass();

return makeComplementByHand(collection, type);

}

/**

* Creates an {@code EnumSet} consisting of all enum values that are not in the specified

* collection. This is equivalent to {@link EnumSet#complementOf}, but can act on any input

* collection, as long as the elements are of enum type.

*

* @param collection the collection whose complement should be stored in the {@code EnumSet}

* @param type the type of the elements in the set

* @return a new, modifiable {@code EnumSet} initially containing all the values of the enum not

* present in the given collection

*/

@J2ktIncompatible

@GwtIncompatible // EnumSet.complementOf

public static <E extends Enum<E>> EnumSet<E> complementOf(

Collection<E> collection, Class<E> type) {

checkNotNull(collection);

return (collection instanceof EnumSet)

? EnumSet.complementOf((EnumSet<E>) collection)

: makeComplementByHand(collection, type);

}

@J2ktIncompatible

@GwtIncompatible

private static <E extends Enum<E>> EnumSet<E> makeComplementByHand(

Collection<E> collection, Class<E> type) {

EnumSet<E> result = EnumSet.allOf(type);

result.removeAll(collection);

return result;

}

/**

* Returns a set backed by the specified map. The resulting set displays the same ordering,

* concurrency, and performance characteristics as the backing map. In essence, this factory

* method provides a {@link Set} implementation corresponding to any {@link Map} implementation.

* There is no need to use this method on a {@link Map} implementation that already has a

* corresponding {@link Set} implementation (such as {@link java.util.HashMap} or {@link

* java.util.TreeMap}).

*

* <p>Each method invocation on the set returned by this method results in exactly one method

* invocation on the backing map or its {@code keySet} view, with one exception. The {@code

* addAll} method is implemented as a sequence of {@code put} invocations on the backing map.

*

* <p>The specified map must be empty at the time this method is invoked, and should not be

* accessed directly after this method returns. These conditions are ensured if the map is created

* empty, passed directly to this method, and no reference to the map is retained, as illustrated

* in the following code fragment:

*

* {@snippet :

* Set<Object> identityHashSet = Sets.newSetFromMap(new IdentityHashMap<>());

* }

*

* <p>The returned set is serializable if the backing map is.

*

* @param map the backing map

* @return the set backed by the map

* @throws IllegalArgumentException if {@code map} is not empty

* @deprecated Use {@link Collections#newSetFromMap} instead.

*/

@InlineMe(replacement = "Collections.newSetFromMap(map)", imports = "java.util.Collections")

@Deprecated

public static <E extends @Nullable Object> Set<E> newSetFromMap(

Map<E, Boolean> map) {

return Collections.newSetFromMap(map);

}

/**

* An unmodifiable view of a set which may be backed by other sets; this view will change as the

* backing sets do. Contains methods to copy the data into a new set which will then remain

* stable. There is usually no reason to retain a reference of type {@code SetView}; typically,

* you either use it as a plain {@link Set}, or immediately invoke {@link #immutableCopy} or

* {@link #copyInto} and forget the {@code SetView} itself.

*

* @since 2.0

*/

public abstract static class SetView<E extends @Nullable Object> extends AbstractSet<E> {

private SetView() {} // no subclasses but our own

/**

* Returns an immutable copy of the current contents of this set view. Does not support null

* elements.

*

* <p><b>Warning:</b> this may have unexpected results if a backing set of this view uses a

* nonstandard notion of equivalence, for example if it is a {@link TreeSet} using a comparator

* that is inconsistent with {@link Object#equals(Object)}.

*/

public ImmutableSet<@NonNull E> immutableCopy() {

// Not using ImmutableSet.copyOf() to avoid iterating thrice (isEmpty, size, iterator).

int maxSize = maxSize();

if (maxSize == 0) {

return ImmutableSet.of();

}

ImmutableSet.Builder<@NonNull E> builder = ImmutableSet.builderWithExpectedSize(maxSize);

for (E element : this) {

builder.add(checkNotNull(element));

}

return builder.build();

}

/**

* Copies the current contents of this set view into an existing set. This method has equivalent

* behavior to {@code set.addAll(this)}, assuming that all the sets involved are based on the

* same notion of equivalence.

*

* @return a reference to {@code set}, for convenience

*/

// Note: S should logically extend Set<? super E> but can't due to either

// some javac bug or some weirdness in the spec, not sure which.

@CanIgnoreReturnValue

public <S extends Set<E>> S copyInto(S set) {

set.addAll(this);

return set;

}

/**

* Guaranteed to throw an exception and leave the collection unmodified.

*

* @throws UnsupportedOperationException always

* @deprecated Unsupported operation.

*/

@CanIgnoreReturnValue

@Deprecated

@Override

@DoNotCall("Always throws UnsupportedOperationException")

public final boolean add(@ParametricNullness E e) {

throw new UnsupportedOperationException();

}

/**

* Guaranteed to throw an exception and leave the collection unmodified.

*

* @throws UnsupportedOperationException always

* @deprecated Unsupported operation.

*/

@CanIgnoreReturnValue

@Deprecated

@Override

@DoNotCall("Always throws UnsupportedOperationException")

public final boolean remove(@Nullable Object object) {

throw new UnsupportedOperationException();

}

/**

* Guaranteed to throw an exception and leave the collection unmodified.

*

* @throws UnsupportedOperationException always

* @deprecated Unsupported operation.

*/

@CanIgnoreReturnValue

@Deprecated

@Override

@DoNotCall("Always throws UnsupportedOperationException")

public final boolean addAll(Collection<? extends E> newElements) {

throw new UnsupportedOperationException();

}

/**

* Guaranteed to throw an exception and leave the collection unmodified.

*

* @throws UnsupportedOperationException always

* @deprecated Unsupported operation.

*/

@CanIgnoreReturnValue

@Deprecated

@Override

@DoNotCall("Always throws UnsupportedOperationException")

public final boolean removeAll(Collection<?> oldElements) {

throw new UnsupportedOperationException();

}

/**

* Guaranteed to throw an exception and leave the collection unmodified.

*

* @throws UnsupportedOperationException always

* @deprecated Unsupported operation.

*/

@CanIgnoreReturnValue

@Deprecated

@Override

@DoNotCall("Always throws UnsupportedOperationException")

public final boolean removeIf(java.util.function.Predicate<? super E> filter) {

throw new UnsupportedOperationException();

}

/**

* Guaranteed to throw an exception and leave the collection unmodified.

*

* @throws UnsupportedOperationException always

* @deprecated Unsupported operation.

*/

@CanIgnoreReturnValue

@Deprecated

@Override

@DoNotCall("Always throws UnsupportedOperationException")

public final boolean retainAll(Collection<?> elementsToKeep) {

throw new UnsupportedOperationException();

}

/**

* Guaranteed to throw an exception and leave the collection unmodified.

*

* @throws UnsupportedOperationException always

* @deprecated Unsupported operation.

*/

@Deprecated

@Override

@DoNotCall("Always throws UnsupportedOperationException")

public final void clear() {

throw new UnsupportedOperationException();

}

/**

* Scope the return type to {@link UnmodifiableIterator} to ensure this is an unmodifiable view.

*

* @since 20.0 (present with return type {@link Iterator} since 2.0)

*/

@Override

public abstract UnmodifiableIterator<E> iterator();

@Override

@SuppressWarnings("EqualsHashCode") // same semantics

public boolean equals(@Nullable Object object) {

if (object == this) {

return true;

}

if (!(object instanceof Set)) {

return false;

}

Set<?> that = (Set<?>) object;

int thatMaxSize = maxSize(that);

if (minSize() > thatMaxSize) {

return false; // this.size() > that.size()

}

int thatMinSize = minSize(that);

if (maxSize() < thatMinSize) {

return false; // this.size() < that.size()

}

// the base implementation from AbstractSet uses size() and containsAll()

// both require iterating over the entire SetView

// we avoid iterating twice by doing the equivalent of both in one iteration

int thisSize = 0;

for (E e : this) {

try {

if (!that.contains(e)) {

return false;

}

} catch (NullPointerException | ClassCastException ignored) {

return false;

}

thisSize++;

} // that.containsAll(this) so that.size() >= this.size()

if (thisSize == thatMaxSize) {

// this.size() == maxSize(that) >= that.size() >= this.size()

return true; // this.size() == that.size()

} else if (thisSize < thatMinSize) {

// this.size() < minSize(that) <= that.size()

return false; // this.size() < that.size()

} else { // that can only be a SetView at this point

int thatSize = 0;

for (Object unused : that) {

if (++thatSize > thisSize) {

return false;

}

}

return true; // that.size() == this.size()

}

}

/**

* Returns a lower bound for {@link #size()} based on the sizes of the backing sets.

*

* <p>This is more efficient than {@link #size()}, which iterates over the entire {@link

* SetView}.

*/

abstract int minSize();

/**

* Returns the {@link #minSize()} of {@code set} if it is a {@link SetView}, or the exact {@link

* #size()} of {@code set} otherwise.

*/

static int minSize(Set<?> set) {

return set instanceof SetView ? ((SetView<?>) set).minSize() : set.size();

}

/**

* Returns an upper bound for {@link #size()} based on the sizes of the backing sets.

*

* <p>This is more efficient than {@link #size()}, which iterates over the entire {@link

* SetView}.

*/

abstract int maxSize();

/**

* Returns the {@link #maxSize()} of {@code set} if it is a {@link SetView}, or the exact {@link

* #size()} of {@code set} otherwise.

*/

static int maxSize(Set<?> set) {

return set instanceof SetView ? ((SetView<?>) set).maxSize() : set.size();

}

}

/**

* Returns an unmodifiable <b>view</b> of the union of two sets. The returned set contains all

* elements that are contained in either backing set. Iterating over the returned set iterates

* first over all the elements of {@code set1}, then over each element of {@code set2}, in order,

* that is not contained in {@code set1}.

*

* <p>Results are undefined if {@code set1} and {@code set2} are sets based on different

* equivalence relations, for example if {@code set1} is a {@link HashSet} and {@code set2} is a

* {@link TreeSet} or the {@link Map#keySet} of an {@code IdentityHashMap}.

*/

public static <E extends @Nullable Object> SetView<E> union(

Set<? extends E> set1, Set<? extends E> set2) {

checkNotNull(set1, "set1");

checkNotNull(set2, "set2");

return new SetView<E>() {

@Override

public int size() {

int size = set1.size();

for (E e : set2) {

if (!set1.contains(e)) {

size++;

}

}

return size;

}

@Override

public boolean isEmpty() {

return set1.isEmpty() && set2.isEmpty();

}

@Override

public UnmodifiableIterator<E> iterator() {

return new AbstractIterator<E>() {

final Iterator<? extends E> itr1 = set1.iterator();

final Iterator<? extends E> itr2 = set2.iterator();

@Override

protected @Nullable E computeNext() {

if (itr1.hasNext()) {

return itr1.next();

}

while (itr2.hasNext()) {

E e = itr2.next();

if (!set1.contains(e)) {

return e;

}

}

return endOfData();

}

};

}

@Override

public Stream<E> stream() {

return Stream.concat(set1.stream(), set2.stream().filter((E e) -> !set1.contains(e)));

}

@Override

public Stream<E> parallelStream() {

return stream().parallel();

}

@Override

public boolean contains(@Nullable Object object) {

return set1.contains(object) || set2.contains(object);

}

@Override

public <S extends Set<E>> S copyInto(S set) {

set.addAll(set1);

set.addAll(set2);

return set;

}

@Override

int minSize() {

return max(minSize(set1), minSize(set2));

}

@Override

int maxSize() {

return saturatedAdd(maxSize(set1), maxSize(set2));

}

};

}

/**

* Returns an unmodifiable <b>view</b> of the intersection of two sets. The returned set contains

* all elements that are contained by both backing sets. The iteration order of the returned set

* matches that of {@code set1}.

*

* <p>Results are undefined if {@code set1} and {@code set2} are sets based on different

* equivalence relations, for example if {@code set1} is a {@link HashSet} and {@code set2} is a

* {@link TreeSet} or the {@link Map#keySet} of an {@code IdentityHashMap}.

*

* <p><b>Note:</b> The returned view performs slightly better when {@code set1} is the smaller of

* the two sets. If you have reason to believe one of your sets will generally be smaller than the

* other, pass it first. Unfortunately, since this method sets the generic type of the returned

* set based on the type of the first set passed, this could in rare cases force you to make a

* cast, for example:

*

* {@snippet :

* Set<Object> aFewBadObjects = ...

* Set<String> manyBadStrings = ...

*

* // impossible for a non-String to be in the intersection

* SuppressWarnings("unchecked")

* Set<String> badStrings = (Set) Sets.intersection(aFewBadObjects, manyBadStrings);

* }

*

* <p>This is unfortunate, but should come up only very rarely.

*/

public static <E extends @Nullable Object> SetView<E> intersection(Set<E> set1, Set<?> set2) {

checkNotNull(set1, "set1");

checkNotNull(set2, "set2");

return new SetView<E>() {

@Override

public UnmodifiableIterator<E> iterator() {

return new AbstractIterator<E>() {

final Iterator<E> itr = set1.iterator();

@Override

protected @Nullable E computeNext() {

while (itr.hasNext()) {

E e = itr.next();

if (set2.contains(e)) {

return e;

}

}

return endOfData();

}

};

}

@Override

public Stream<E> stream() {

return set1.stream().filter(set2::contains);

}

@Override

public Stream<E> parallelStream() {

return set1.parallelStream().filter(set2::contains);

}

@Override

public int size() {

int size = 0;

for (E e : set1) {

if (set2.contains(e)) {

size++;

}

}

return size;

}

@Override

public boolean isEmpty() {

return Collections.disjoint(set2, set1);

}

@Override

public boolean contains(@Nullable Object object) {

return set1.contains(object) && set2.contains(object);

}

@Override

public boolean containsAll(Collection<?> collection) {

return set1.containsAll(collection) && set2.containsAll(collection);