001/*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.CollectPreconditions.checkNonnegative;
021import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
022
023import com.google.common.annotations.GwtCompatible;
024import com.google.errorprone.annotations.CanIgnoreReturnValue;
025import java.io.Serializable;
026import java.util.AbstractCollection;
027import java.util.ArrayList;
028import java.util.Arrays;
029import java.util.Collection;
030import java.util.Collections;
031import java.util.Iterator;
032import java.util.List;
033import javax.annotation.Nullable;
034
035/**
036 * A {@link Collection} whose contents will never change, and which offers a few additional
037 * guarantees detailed below.
038 *
039 * <p><b>Warning:</b> avoid <i>direct</i> usage of {@link ImmutableCollection} as a type (just as
040 * with {@link Collection} itself). Prefer subtypes such as {@link ImmutableSet} or {@link
041 * ImmutableList}, which have well-defined {@link #equals} semantics, thus avoiding a common source
042 * of bugs and confusion.
043 *
044 * <h3>About <i>all</i> {@code Immutable-} collections</h3>
045 *
046 * <p>The remainder of this documentation applies to every public {@code Immutable-} type in this
047 * package, whether it is a subtype of {@code ImmutableCollection} or not.
048 *
049 * <h4>Guarantees</h4>
050 *
051 * <p>Each makes the following guarantees:
052 *
053 * <ul>
054 * <li><b>Shallow immutability.</b> Elements can never be added, removed or replaced in this
055 *     collection. This is a stronger guarantee than that of
056 *     {@link Collections#unmodifiableCollection}, whose contents change whenever the wrapped
057 *     collection is modified.
058 * <li><b>Null-hostility.</b> This collection will never contain a null element.
059 * <li><b>Deterministic iteration.</b> The iteration order is always well-defined, depending on how
060 *     the collection was created. Typically this is insertion order unless an explicit ordering is
061 *     otherwise specified (e.g. {@link ImmutableSortedSet#naturalOrder}).  See the appropriate
062 *     factory method for details. View collections such as {@link ImmutableMultiset#elementSet}
063 *     iterate in the same order as the parent, except as noted.
064 * <li><b>Thread safety.</b> It is safe to access this collection concurrently from multiple
065 *     threads.
066 * <li><b>Integrity.</b> This type cannot be subclassed outside this package (which would allow
067 *     these guarantees to be violated).
068 * </ul>
069 *
070 * <h4>"Interfaces", not implementations</h4>
071 *
072 * <p>Each public class, such as {@link ImmutableSet}, is a <i>type</i> offering meaningful
073 * behavioral guarantees -- not merely a specific <i>implementation</i> as in the case of, say,
074 * {@link ArrayList}. You should treat them as interfaces in every important sense of the word.
075 *
076 * <p>For field types and method return types, you should generally use the immutable type (such as
077 * {@link ImmutableList}) instead of the general collection interface type (such as {@link List}).
078 * This communicates to your callers all of the semantic guarantees listed above, which is almost
079 * always very useful information.
080 *
081 * <p>On the other hand, a <i>parameter</i> type of {@link ImmutableList} is generally a nuisance to
082 * callers. Instead, accept {@link Iterable} and have your method or constructor body pass it to the
083 * appropriate {@code copyOf} method itself.
084 *
085 * <h4>Creation</h4>
086 *
087 * <p>Except for logically "abstract" types like {@code ImmutableCollection} itself, each {@code
088 * Immutable} type provides the static operations you need to obtain instances of that type. These
089 * usually include:
090 *
091 * <ul>
092 * <li>Static methods named {@code of}, accepting an explicit list of elements or entries.
093 * <li>Static methods named {@code copyOf} (or {@code copyOfSorted}), accepting an existing
094 *     collection whose contents should be copied.
095 * <li>A static nested {@code Builder} class which can be used to populate a new immutable instance.
096 * </ul>
097 *
098 * <h4>Warnings</h4>
099 *
100 * <ul>
101 * <li><b>Warning:</b> as with any collection, it is almost always a bad idea to modify an element
102 *     (in a way that affects its {@link Object#equals} behavior) while it is contained in a
103 *     collection. Undefined behavior and bugs will result. It's generally best to avoid using
104 *     mutable objects as elements at all, as many users may expect your "immutable" object to be
105 *     <i>deeply</i> immutable.
106 * </ul>
107 *
108 * <h4>Performance notes</h4>
109 *
110 * <ul>
111 * <li>Implementations can be generally assumed to prioritize memory efficiency, then speed of
112 *     access, and lastly speed of creation.
113 * <li>The {@code copyOf} methods will sometimes recognize that the actual copy operation is
114 *     unnecessary; for example, {@code copyOf(copyOf(anArrayList))} should copy the data only once.
115 *     This reduces the expense of habitually making defensive copies at API boundaries. However,
116 *     the precise conditions for skipping the copy operation are undefined.
117 * <li><b>Warning:</b> a view collection such as {@link ImmutableMap#keySet} or {@link
118 *     ImmutableList#subList} may retain a reference to the entire data set, preventing it from
119 *     being garbage collected. If some of the data is no longer reachable through other means, this
120 *     constitutes a memory leak. Pass the view collection to the appropriate {@code copyOf} method
121 *     to obtain a correctly-sized copy.
122 * <li>The performance of using the associated {@code Builder} class can be assumed to be
123 *     no worse, and possibly better, than creating a mutable collection and copying it.
124 * <li>Implementations generally do not cache hash codes. If your element or key type has a slow
125 *     {@code hashCode} implementation, it should cache it itself.
126 * </ul>
127 *
128 * <h4>Example usage</h4>
129 *
130 * <pre>   {@code
131 *
132 *   class Foo {
133 *     private static final ImmutableSet<String> RESERVED_CODES =
134 *         ImmutableSet.of("AZ", "CQ", "ZX");
135 *
136 *     private final ImmutableSet<String> codes;
137 *
138 *     public Foo(Iterable<String> codes) {
139 *       this.codes = ImmutableSet.copyOf(codes);
140 *       checkArgument(Collections.disjoint(this.codes, RESERVED_CODES));
141 *     }
142 *   }}</pre>
143 *
144 * <h3>See also</h3>
145 *
146 * <p>See the Guava User Guide article on <a href=
147 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">
148 * immutable collections</a>.
149 *
150 * @since 2.0
151 */
152@GwtCompatible(emulated = true)
153@SuppressWarnings("serial") // we're overriding default serialization
154// TODO(kevinb): I think we should push everything down to "BaseImmutableCollection" or something,
155// just to do everything we can to emphasize the "practically an interface" nature of this class.
156public abstract class ImmutableCollection<E> extends AbstractCollection<E> implements Serializable {
157
158  ImmutableCollection() {}
159
160  /**
161   * Returns an unmodifiable iterator across the elements in this collection.
162   */
163  @Override
164  public abstract UnmodifiableIterator<E> iterator();
165
166  private static final Object[] EMPTY_ARRAY = {};
167
168  @Override
169  public final Object[] toArray() {
170    int size = size();
171    if (size == 0) {
172      return EMPTY_ARRAY;
173    }
174    Object[] result = new Object[size];
175    copyIntoArray(result, 0);
176    return result;
177  }
178
179  @CanIgnoreReturnValue
180  @Override
181  public final <T> T[] toArray(T[] other) {
182    checkNotNull(other);
183    int size = size();
184    if (other.length < size) {
185      other = ObjectArrays.newArray(other, size);
186    } else if (other.length > size) {
187      other[size] = null;
188    }
189    copyIntoArray(other, 0);
190    return other;
191  }
192
193  @Override
194  public abstract boolean contains(@Nullable Object object);
195
196  /**
197   * Guaranteed to throw an exception and leave the collection unmodified.
198   *
199   * @throws UnsupportedOperationException always
200   * @deprecated Unsupported operation.
201   */
202  @CanIgnoreReturnValue
203  @Deprecated
204  @Override
205  public final boolean add(E e) {
206    throw new UnsupportedOperationException();
207  }
208
209  /**
210   * Guaranteed to throw an exception and leave the collection unmodified.
211   *
212   * @throws UnsupportedOperationException always
213   * @deprecated Unsupported operation.
214   */
215  @CanIgnoreReturnValue
216  @Deprecated
217  @Override
218  public final boolean remove(Object object) {
219    throw new UnsupportedOperationException();
220  }
221
222  /**
223   * Guaranteed to throw an exception and leave the collection unmodified.
224   *
225   * @throws UnsupportedOperationException always
226   * @deprecated Unsupported operation.
227   */
228  @CanIgnoreReturnValue
229  @Deprecated
230  @Override
231  public final boolean addAll(Collection<? extends E> newElements) {
232    throw new UnsupportedOperationException();
233  }
234
235  /**
236   * Guaranteed to throw an exception and leave the collection unmodified.
237   *
238   * @throws UnsupportedOperationException always
239   * @deprecated Unsupported operation.
240   */
241  @CanIgnoreReturnValue
242  @Deprecated
243  @Override
244  public final boolean removeAll(Collection<?> oldElements) {
245    throw new UnsupportedOperationException();
246  }
247
248  /**
249   * Guaranteed to throw an exception and leave the collection unmodified.
250   *
251   * @throws UnsupportedOperationException always
252   * @deprecated Unsupported operation.
253   */
254  @CanIgnoreReturnValue
255  @Deprecated
256  @Override
257  public final boolean retainAll(Collection<?> elementsToKeep) {
258    throw new UnsupportedOperationException();
259  }
260
261  /**
262   * Guaranteed to throw an exception and leave the collection unmodified.
263   *
264   * @throws UnsupportedOperationException always
265   * @deprecated Unsupported operation.
266   */
267  @Deprecated
268  @Override
269  public final void clear() {
270    throw new UnsupportedOperationException();
271  }
272
273  /**
274   * Returns an {@code ImmutableList} containing the same elements, in the same order, as this
275   * collection.
276   *
277   * <p><b>Performance note:</b> in most cases this method can return quickly without actually
278   * copying anything. The exact circumstances under which the copy is performed are undefined and
279   * subject to change.
280   *
281   * @since 2.0
282   */
283  public ImmutableList<E> asList() {
284    return isEmpty() ? ImmutableList.<E>of() : ImmutableList.<E>asImmutableList(toArray());
285  }
286
287  /**
288   * Returns {@code true} if this immutable collection's implementation contains references to
289   * user-created objects that aren't accessible via this collection's methods. This is generally
290   * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid
291   * memory leaks.
292   */
293  abstract boolean isPartialView();
294
295  /**
296   * Copies the contents of this immutable collection into the specified array at the specified
297   * offset.  Returns {@code offset + size()}.
298   */
299  @CanIgnoreReturnValue
300  int copyIntoArray(Object[] dst, int offset) {
301    for (E e : this) {
302      dst[offset++] = e;
303    }
304    return offset;
305  }
306
307  Object writeReplace() {
308    // We serialize by default to ImmutableList, the simplest thing that works.
309    return new ImmutableList.SerializedForm(toArray());
310  }
311
312  /**
313   * Abstract base class for builders of {@link ImmutableCollection} types.
314   *
315   * @since 10.0
316   */
317  public abstract static class Builder<E> {
318    static final int DEFAULT_INITIAL_CAPACITY = 4;
319
320    static int expandedCapacity(int oldCapacity, int minCapacity) {
321      if (minCapacity < 0) {
322        throw new AssertionError("cannot store more than MAX_VALUE elements");
323      }
324      // careful of overflow!
325      int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
326      if (newCapacity < minCapacity) {
327        newCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
328      }
329      if (newCapacity < 0) {
330        newCapacity = Integer.MAX_VALUE;
331        // guaranteed to be >= newCapacity
332      }
333      return newCapacity;
334    }
335
336    Builder() {}
337
338    /**
339     * Adds {@code element} to the {@code ImmutableCollection} being built.
340     *
341     * <p>Note that each builder class covariantly returns its own type from
342     * this method.
343     *
344     * @param element the element to add
345     * @return this {@code Builder} instance
346     * @throws NullPointerException if {@code element} is null
347     */
348    @CanIgnoreReturnValue
349    public abstract Builder<E> add(E element);
350
351    /**
352     * Adds each element of {@code elements} to the {@code ImmutableCollection}
353     * being built.
354     *
355     * <p>Note that each builder class overrides this method in order to
356     * covariantly return its own type.
357     *
358     * @param elements the elements to add
359     * @return this {@code Builder} instance
360     * @throws NullPointerException if {@code elements} is null or contains a
361     *     null element
362     */
363    @CanIgnoreReturnValue
364    public Builder<E> add(E... elements) {
365      for (E element : elements) {
366        add(element);
367      }
368      return this;
369    }
370
371    /**
372     * Adds each element of {@code elements} to the {@code ImmutableCollection}
373     * being built.
374     *
375     * <p>Note that each builder class overrides this method in order to
376     * covariantly return its own type.
377     *
378     * @param elements the elements to add
379     * @return this {@code Builder} instance
380     * @throws NullPointerException if {@code elements} is null or contains a
381     *     null element
382     */
383    @CanIgnoreReturnValue
384    public Builder<E> addAll(Iterable<? extends E> elements) {
385      for (E element : elements) {
386        add(element);
387      }
388      return this;
389    }
390
391    /**
392     * Adds each element of {@code elements} to the {@code ImmutableCollection}
393     * being built.
394     *
395     * <p>Note that each builder class overrides this method in order to
396     * covariantly return its own type.
397     *
398     * @param elements the elements to add
399     * @return this {@code Builder} instance
400     * @throws NullPointerException if {@code elements} is null or contains a
401     *     null element
402     */
403    @CanIgnoreReturnValue
404    public Builder<E> addAll(Iterator<? extends E> elements) {
405      while (elements.hasNext()) {
406        add(elements.next());
407      }
408      return this;
409    }
410
411    /**
412     * Returns a newly-created {@code ImmutableCollection} of the appropriate
413     * type, containing the elements provided to this builder.
414     *
415     * <p>Note that each builder class covariantly returns the appropriate type
416     * of {@code ImmutableCollection} from this method.
417     */
418    public abstract ImmutableCollection<E> build();
419  }
420
421  abstract static class ArrayBasedBuilder<E> extends ImmutableCollection.Builder<E> {
422    Object[] contents;
423    int size;
424    boolean forceCopy;
425
426    ArrayBasedBuilder(int initialCapacity) {
427      checkNonnegative(initialCapacity, "initialCapacity");
428      this.contents = new Object[initialCapacity];
429      this.size = 0;
430    }
431
432    /*
433     * Expand the absolute capacity of the builder so it can accept at least the specified number of
434     * elements without being resized. Also, if we've already built a collection backed by the
435     * current array, create a new array.
436     */
437    private void getReadyToExpandTo(int minCapacity) {
438      if (contents.length < minCapacity) {
439        this.contents =
440            Arrays.copyOf(
441                this.contents, expandedCapacity(contents.length, minCapacity));
442        forceCopy = false;
443      } else if (forceCopy) {
444        this.contents = contents.clone();
445        forceCopy = false;
446      }
447    }
448
449    @CanIgnoreReturnValue
450    @Override
451    public ArrayBasedBuilder<E> add(E element) {
452      checkNotNull(element);
453      getReadyToExpandTo(size + 1);
454      contents[size++] = element;
455      return this;
456    }
457
458    @CanIgnoreReturnValue
459    @Override
460    public Builder<E> add(E... elements) {
461      checkElementsNotNull(elements);
462      getReadyToExpandTo(size + elements.length);
463      System.arraycopy(elements, 0, contents, size, elements.length);
464      size += elements.length;
465      return this;
466    }
467    
468    @CanIgnoreReturnValue
469    @Override
470    public Builder<E> addAll(Iterable<? extends E> elements) {
471      if (elements instanceof Collection) {
472        Collection<?> collection = (Collection<?>) elements;
473        getReadyToExpandTo(size + collection.size());
474      }
475      super.addAll(elements);
476      return this;
477    }
478  }
479}