/*
 * Copyright (C) 2007 Google Inc.
 *
 * 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 com.google.common.annotations.GwtCompatible;
import static com.google.common.base.Preconditions.checkNotNull;
 
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
 
import javax.annotation.Nullable;
 
/**
 * A high-performance, immutable {@code Set} with reliable, user-specified
 * iteration order. Does not permit null elements.
 *
 * <p>Unlike {@link Collections#unmodifiableSet}, which is a <i>view</i> of a
 * separate collection that can still change, an instance of this class contains
 * its own private data and will <i>never</i> change. This class is convenient
 * for {@code public static final} sets ("constant sets" ) and also lets you
 * easily make a "defensive copy" of a set provided to your class by a caller.
 *
 * <p><b>Warning:</b> Like most sets, an {@code ImmutableSet} will not function
 * correctly if an element is modified after being placed in the set. For this
 * reason, and to avoid general confusion, it is strongly recommended to place
 * only immutable objects into this collection.
 *
 * <p>This class has been observed to perform significantly better than {@link
 * HashSet} for objects with very fast {@link Object#hashCode} implementations
 * (as a well-behaved immutable object should). While this class's factory
 * methods create hash-based instances, the {@link ImmutableSortedSet} subclass
 * performs binary searches instead.
 *
 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed
 * outside its package as it has no public or protected constructors. Thus,
 * instances of this type are guaranteed to be immutable.
 *
 * @see ImmutableList
 * @see ImmutableMap
 * @author Kevin Bourrillion
 * @author Nick Kralevich
 */
@GwtCompatible(serializable = true)
@SuppressWarnings("serial" ) // we're overriding default serialization
public abstract class ImmutableSet<E> extends ImmutableCollection<E>
    implements Set<E> {
  private static final ImmutableSet<?> EMPTY_IMMUTABLE_SET
      = new EmptyImmutableSet();
 
  /**
   * Returns the empty immutable set. This set behaves and performs comparably
   * to {@link Collections#emptySet}, and is preferable mainly for consistency
   * and maintainability of your code.
   */
  // Casting to any type is safe because the set will never hold any elements.
  @SuppressWarnings({"unchecked"})
  public static <E> ImmutableSet<E> of() {
    return (ImmutableSet<E> ) EMPTY_IMMUTABLE_SET;
  }
 
  /**
   * Returns an immutable set containing a single element. This set behaves and
   * performs comparably to {@link Collections#singleton}, but will not accept
   * a null element. It is preferable mainly for consistency and
   * maintainability of your code.
   */
  public static <E> ImmutableSet<E> of(E element) {
    return new SingletonImmutableSet<E>(element, element.hashCode());
  }
 
  /**
   * Returns an immutable set containing the given elements, in order. Repeated
   * occurrences of an element (according to {@link Object#equals}) after the
   * first are ignored (but too many of these may result in the set being
   * sized inappropriately).
   *
   * @throws NullPointerException if any of {@code elements} is null
   */
  public static <E> ImmutableSet<E> of(E... elements) {
    switch (elements.length) {
      case 0:
        return of();
      case 1:
        return of(elements[0]);
      default:
        return create(Arrays.asList(elements), elements.length);
    }
  }
 
  /**
   * Returns an immutable set containing the given elements, in order. Repeated
   * occurrences of an element (according to {@link Object#equals}) after the
   * first are ignored (but too many of these may result in the set being
   * sized inappropriately). This method iterates over {@code elements} at most
   * once.
   *
   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
   * ImmutableSet.copyOf(s)} returns an {@code ImmutableSet<String>} containing
   * each of the strings in {@code s}, while {@code ImmutableSet.of(s)} returns
   * a {@code ImmutableSet<Set<String>>} containing one element (the given set
   * itself).
   *
   * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
   * is an {@code ImmutableSet} (but not an {@code ImmutableSortedSet}), no copy
   * will actually be performed, and the given set itself will be returned.
   *
   * @throws NullPointerException if any of {@code elements} is null
   */
  public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) {
    if (elements instanceof ImmutableSet
        && !(elements instanceof ImmutableSortedSet)) {
      @SuppressWarnings("unchecked" ) // all supported methods are covariant
      ImmutableSet<E> set = (ImmutableSet<E> ) elements;
      return set;
    }
    return copyOfInternal(Collections2.toCollection(elements));
  }
 
  /**
   * Returns an immutable set containing the given elements, in order. Repeated
   * occurrences of an element (according to {@link Object#equals}) after the
   * first are ignored.
   *
   * @throws NullPointerException if any of {@code elements} is null
   */
  public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) {
    Collection<E> list = Lists.newArrayList(elements);
    return copyOfInternal(list);
  }
 
  private static <E> ImmutableSet<E> copyOfInternal(
      Collection<? extends E> collection) {
    // TODO: Support concurrent collections that change while this method is
    // running.
    switch (collection.size()) {
      case 0:
        return of();
      case 1:
        // TODO: Remove "ImmutableSet.<E>" when eclipse bug is fixed.
        return ImmutableSet.<E>of(collection.iterator().next());
      default:
        return create(collection, collection.size());
    }
  }
 
  ImmutableSet() {}
 
  /** Returns {@code true} if the {@code hashCode()} method runs quickly. */
  boolean isHashCodeFast() {
    return false;
  }
 
  @Override public boolean equals(@Nullable Object object) {
    if (object == this) {
      return true;
    }
    if (object instanceof ImmutableSet
        && isHashCodeFast()
        && ((ImmutableSet<?> ) object).isHashCodeFast()
        && hashCode() != object.hashCode()) {
      return false;
    }
    return Collections2.setEquals(this, object);
  }
 
  @Override public int hashCode() {
    int hashCode = 0;
    for (Object o : this) {
      hashCode += o.hashCode();
    }
    return hashCode;
  }
 
  // This declaration is needed to make Set.iterator() and
  // ImmutableCollection.iterator() consistent.
  @Override public abstract UnmodifiableIterator<E> iterator();
 
  // Package-private for GWT serialization.
  static final class EmptyImmutableSet extends ImmutableSet<Object> {
    public int size() {
      return 0;
    }
 
    @Override public boolean isEmpty() {
      return true;
    }
 
    @Override public boolean contains(Object target) {
      return false;
    }
 
    @Override public UnmodifiableIterator<Object> iterator() {
      return Iterators.emptyIterator();
    }
 
    private static final Object[] EMPTY_ARRAY = new Object[0];
 
    @Override public Object[] toArray() {
      return EMPTY_ARRAY;
    }
 
    @Override public <T> T[] toArray(T[] a) {
      if (a.length > 0) {
        a[0] = null;
      }
      return a;
    }
 
    @Override public boolean containsAll(Collection<?> targets) {
      return targets.isEmpty();
    }
 
    @Override public boolean equals(@Nullable Object object) {
      if (object instanceof Set) {
        Set<?> that = (Set<?> ) object;
        return that.isEmpty();
      }
      return false;
    }
 
    @Override public final int hashCode() {
      return 0;
    }
 
    @Override boolean isHashCodeFast() {
      return true;
    }
 
    @Override public String toString() {
      return "[]";
    }
  }
 
  private static <E> ImmutableSet<E> create(
      Iterable<? extends E> iterable, int count) {
    // count is always the (nonzero) number of elements in the iterable
    int tableSize = Hashing.chooseTableSize(count);
    Object[] table = new Object[tableSize];
    int mask = tableSize - 1;
 
    List<E> elements = new ArrayList<E>(count);
    int hashCode = 0;
 
    for (E element : iterable) {
      int hash = element.hashCode();
      for (int i = Hashing.smear(hash); true; i++) {
        int index = i & mask;
        Object value = table[index];
        if (value == null) {
          // Came to an empty bucket. Put the element here.
          table[index] = element;
          elements.add(element);
          hashCode += hash;
          break;
        } else if (value.equals(element)) {
          break; // Found a duplicate. Nothing to do.
        }
      }
    }
 
    // The iterable might have contained only duplicates of the same element.
    return (elements.size() == 1)
        ? new SingletonImmutableSet<E>(elements.get(0), hashCode)
        : new RegularImmutableSet<E>(elements.toArray(), hashCode, table, mask);
  }
 
  abstract static class ArrayImmutableSet<E> extends ImmutableSet<E> {
    final Object[] elements; // the elements (two or more) in the desired order
 
    ArrayImmutableSet(Object[] elements) {
      this.elements = elements;
    }
 
    public int size() {
      return elements.length;
    }
 
    @Override public boolean isEmpty() {
      return false;
    }
 
    /*
     * The cast is safe because the only way to create an instance is via the
     * create() method above, which only permits elements of type E.
     */
    @SuppressWarnings("unchecked" )
    @Override public UnmodifiableIterator<E> iterator() {
      return (UnmodifiableIterator<E> ) Iterators.forArray(elements);
    }
 
    @Override public Object[] toArray() {
      Object[] array = new Object[size()];
      System.arraycopy(elements, 0, array, 0, size());
      return array;
    }
 
    @Override public <T> T[] toArray(T[] array) {
      int size = size();
      if (array.length < size) {
        array = ObjectArrays.newArray(array, size);
      } else if (array.length > size) {
        array[size] = null;
      }
      System.arraycopy(elements, 0, array, 0, size);
      return array;
    }
 
    @Override public boolean containsAll(Collection<?> targets) {
      if (targets == this) {
        return true;
      }
      if (!(targets instanceof ArrayImmutableSet)) {
        return super.containsAll(targets);
      }
      if (targets.size() > size()) {
        return false;
      }
      for (Object target : ((ArrayImmutableSet<?> ) targets).elements) {
        if (!contains(target)) {
          return false;
        }
      }
      return true;
    }
  }
 
  /** such as ImmutableMap.keySet() */
  abstract static class TransformedImmutableSet<D, E> extends ImmutableSet<E> {
    final D[] source;
    final int hashCode;
 
    TransformedImmutableSet(D[] source, int hashCode) {
      this.source = source;
      this.hashCode = hashCode;
    }
 
    abstract E transform(D element);
 
    public int size() {
      return source.length;
    }
 
    @Override public boolean isEmpty() {
      return false;
    }
 
    @Override public UnmodifiableIterator<E> iterator() {
      Iterator<E> iterator = new AbstractIterator<E>() {
        int index = 0;
        @Override protected E computeNext() {
          return index < source.length
              ? transform(source[index++])
              : endOfData();
        }
      };
      // Though the AbstractIterator is unmodifiable, it isn't an
      // UnmodifiableIterator.
      return Iterators.unmodifiableIterator(iterator);
    }
 
    @Override public Object[] toArray() {
      return toArray(new Object[size()]);
    }
 
    @Override public <T> T[] toArray(T[] array) {
      int size = size();
      if (array.length < size) {
        array = ObjectArrays.newArray(array, size);
      } else if (array.length > size) {
        array[size] = null;
      }
 
      for (int i = 0; i < source.length; i++) {
        // Technically unsafe. But if T is generic, the caller already got a
        // warning when they created their array, and if it isn't, we can count
        // on an ArrayStoreException in the following statement to catch any
        // problem.
        @SuppressWarnings("unchecked" )
        T t = (T) transform(source[i]);
        array[i] = t;
      }
      return array;
    }
 
    @Override public final int hashCode() {
      return hashCode;
    }
 
    @Override boolean isHashCodeFast() {
      return true;
    }
  }
 
  /*
   * This class is used to serialize all ImmutableSet instances, regardless of
   * implementation type. It captures their "logical contents" and they are
   * reconstructed using public static factories. This is necessary to ensure
   * that the existence of a particular implementation type is an implementation
   * detail.
   */
  private static class SerializedForm implements Serializable {
    final Object[] elements;
    SerializedForm(Object[] elements) {
      this.elements = elements;
    }
    Object readResolve() {
      return of(elements);
    }
    private static final long serialVersionUID = 0;
  }
 
  @Override Object writeReplace() {
    return new SerializedForm(toArray());
  }
 
  /**
   * Returns a new builder. The generated builder is equivalent to the builder
   * created by the {@link Builder} constructor.
   */
  public static <E> Builder<E> builder() {
    return new Builder<E>();
  }
 
  /**
   * A builder for creating immutable set instances, especially
   * {@code public static final} sets ("constant sets" ).
   *
   * <p>Example:
   * <pre>{@code
   *   public static final ImmutableSet<Color> GOOGLE_COLORS
   *       = new ImmutableSet.Builder<Color>()
   *           .addAll(WEBSAFE_COLORS)
   *           .add(new Color(0, 191, 255))
   *           .build();}</pre>
   *
   * <p>Builder instances can be reused - it is safe to call {@link #build}
   * multiple times to build multiple sets in series. Each set
   * is a superset of the set created before it.
   */
  public static class Builder<E> {
    final ArrayList<E> contents = Lists.newArrayList();
 
    /**
     * Creates a new builder. The returned builder is equivalent to the builder
     * generated by {@link ImmutableSet#builder}.
     */
    public Builder() {}
 
    /**
     * Adds {@code element} to the {@code ImmutableSet}.  If the
     * {@code ImmutableSet} already contains {@code element}, then
     * {@code add} has no effect. (only the previously added element
     * is retained).
     *
     * @param element the element to add
     * @return this {@code Builder} object
     * @throws NullPointerException if {@code element} is null
     */
    public Builder<E> add(E element) {
      checkNotNull(element, "element cannot be null" );
      contents.add(element);
      return this;
    }
 
    /**
     * Adds each element of {@code elements} to the {@code ImmutableSet},
     * ignoring duplicate elements (only the first duplicate element is added).
     *
     * @param elements the elements to add
     * @return this {@code Builder} object
     * @throws NullPointerException if {@code elements} is or contains null
     */
    public Builder<E> add(E... elements) {
      checkNotNull(elements, "elements cannot be null" );
      for (E element : elements) {
        if (element == null) {
          throw new NullPointerException(
              "null element in: " + Arrays.toString(elements));
        }
        contents.add(element);
      }
      return this;
    }
 
    /**
     * Adds each element of {@code elements} to the {@code ImmutableSet},
     * ignoring duplicate elements (only the first duplicate element is added).
     *
     * @param elements the {@code Iterable} to add to the {@code ImmutableSet}
     * @return this {@code Builder} object
     * @throws NullPointerException if {@code elements} is or contains null
     */
    public Builder<E> addAll(Iterable<? extends E> elements) {
      if (elements instanceof Collection) {
        @SuppressWarnings("unchecked" )
        Collection<? extends E> collection = (Collection<? extends E> ) elements;
        contents.ensureCapacity(contents.size() + collection.size());
      }
      for (E elem : elements) {
        checkNotNull(elem, "elements contains a null" );
        contents.add(elem);
      }
      return this;
    }
 
    /**
     * Adds each element of {@code elements} to the {@code ImmutableSet},
     * ignoring duplicate elements (only the first duplicate element is added).
     *
     * @param elements the elements to add to the {@code ImmutableSet}
     * @return this {@code Builder} object
     * @throws NullPointerException if {@code elements} is or contains null
     */
    public Builder<E> addAll(Iterator<? extends E> elements) {
      while (elements.hasNext()) {
        E element = elements.next();
        checkNotNull(element, "element cannot be null" );
        contents.add(element);
      }
      return this;
    }
 
    /**
     * Returns a newly-created {@code ImmutableSet} based on the contents of
     * the {@code Builder}.
     */
    public ImmutableSet<E> build() {
      return copyOf(contents);
    }
  }
}