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 com.google.common.annotations.GwtCompatible;
020import com.google.common.annotations.VisibleForTesting;
021
022import java.io.Serializable;
023import java.util.Collection;
024import java.util.Iterator;
025
026import javax.annotation.Nullable;
027
028/**
029 * An immutable collection. Does not permit null elements.
030 *
031 * <p>In addition to the {@link Collection} methods, this class has an {@link
032 * #asList()} method, which returns a list view of the collection's elements.
033 *
034 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed
035 * outside of this package as it has no public or protected constructors. Thus,
036 * instances of this type are guaranteed to be immutable.
037 *
038 * @author Jesse Wilson
039 * @since 2.0 (imported from Google Collections Library)
040 */
041@GwtCompatible(emulated = true)
042@SuppressWarnings("serial") // we're overriding default serialization
043public abstract class ImmutableCollection<E>
044    implements Collection<E>, Serializable {
045  static final ImmutableCollection<Object> EMPTY_IMMUTABLE_COLLECTION
046      = new EmptyImmutableCollection();
047
048  ImmutableCollection() {}
049
050  /**
051   * Returns an unmodifiable iterator across the elements in this collection.
052   */
053  @Override
054  public abstract UnmodifiableIterator<E> iterator();
055
056  @Override
057  public Object[] toArray() {
058    return ObjectArrays.toArrayImpl(this);
059  }
060
061  @Override
062  public <T> T[] toArray(T[] other) {
063    return ObjectArrays.toArrayImpl(this, other);
064  }
065
066  @Override
067  public boolean contains(@Nullable Object object) {
068    return object != null && Iterators.contains(iterator(), object);
069  }
070
071  @Override
072  public boolean containsAll(Collection<?> targets) {
073    return Collections2.containsAllImpl(this, targets);
074  }
075
076  @Override
077  public boolean isEmpty() {
078    return size() == 0;
079  }
080
081  @Override public String toString() {
082    return Collections2.toStringImpl(this);
083  }
084
085  /**
086   * Guaranteed to throw an exception and leave the collection unmodified.
087   *
088   * @throws UnsupportedOperationException always
089   */
090  @Override
091  public final boolean add(E e) {
092    throw new UnsupportedOperationException();
093  }
094
095  /**
096   * Guaranteed to throw an exception and leave the collection unmodified.
097   *
098   * @throws UnsupportedOperationException always
099   */
100  @Override
101  public final boolean remove(Object object) {
102    throw new UnsupportedOperationException();
103  }
104
105  /**
106   * Guaranteed to throw an exception and leave the collection unmodified.
107   *
108   * @throws UnsupportedOperationException always
109   */
110  @Override
111  public final boolean addAll(Collection<? extends E> newElements) {
112    throw new UnsupportedOperationException();
113  }
114
115  /**
116   * Guaranteed to throw an exception and leave the collection unmodified.
117   *
118   * @throws UnsupportedOperationException always
119   */
120  @Override
121  public final boolean removeAll(Collection<?> oldElements) {
122    throw new UnsupportedOperationException();
123  }
124
125  /**
126   * Guaranteed to throw an exception and leave the collection unmodified.
127   *
128   * @throws UnsupportedOperationException always
129   */
130  @Override
131  public final boolean retainAll(Collection<?> elementsToKeep) {
132    throw new UnsupportedOperationException();
133  }
134
135  /**
136   * Guaranteed to throw an exception and leave the collection unmodified.
137   *
138   * @throws UnsupportedOperationException always
139   */
140  @Override
141  public final void clear() {
142    throw new UnsupportedOperationException();
143  }
144
145  /*
146   * TODO(kevinb): Restructure code so ImmutableList doesn't contain this
147   * variable, which it doesn't use.
148   */
149  private transient ImmutableList<E> asList;
150
151  /**
152   * Returns a list view of the collection.
153   *
154   * @since 2.0
155   */
156  public ImmutableList<E> asList() {
157    ImmutableList<E> list = asList;
158    return (list == null) ? (asList = createAsList()) : list;
159  }
160
161  ImmutableList<E> createAsList() {
162    switch (size()) {
163      case 0:
164        return ImmutableList.of();
165      case 1:
166        return ImmutableList.of(iterator().next());
167      default:
168        return new RegularImmutableAsList<E>(this, toArray());
169    }
170  }
171
172  abstract boolean isPartialView();
173
174  private static class EmptyImmutableCollection
175      extends ImmutableCollection<Object> {
176    @Override
177    public int size() {
178      return 0;
179    }
180
181    @Override public boolean isEmpty() {
182      return true;
183    }
184
185    @Override public boolean contains(@Nullable Object object) {
186      return false;
187    }
188
189    @Override public UnmodifiableIterator<Object> iterator() {
190      return Iterators.EMPTY_LIST_ITERATOR;
191    }
192
193    private static final Object[] EMPTY_ARRAY = new Object[0];
194
195    @Override public Object[] toArray() {
196      return EMPTY_ARRAY;
197    }
198
199    @Override public <T> T[] toArray(T[] array) {
200      if (array.length > 0) {
201        array[0] = null;
202      }
203      return array;
204    }
205
206    @Override ImmutableList<Object> createAsList() {
207      return ImmutableList.of();
208    }
209
210    @Override boolean isPartialView() {
211      return false;
212    }
213  }
214
215  /**
216   * Nonempty collection stored in an array.
217   */
218  private static class ArrayImmutableCollection<E>
219      extends ImmutableCollection<E> {
220    private final E[] elements;
221
222    ArrayImmutableCollection(E[] elements) {
223      this.elements = elements;
224    }
225
226    @Override
227    public int size() {
228      return elements.length;
229    }
230
231    @Override public boolean isEmpty() {
232      return false;
233    }
234
235    @Override public UnmodifiableIterator<E> iterator() {
236      return Iterators.forArray(elements);
237    }
238
239    @Override ImmutableList<E> createAsList() {
240      return elements.length == 1 ? new SingletonImmutableList<E>(elements[0])
241          : new RegularImmutableList<E>(elements);
242    }
243
244    @Override boolean isPartialView() {
245      return false;
246    }
247  }
248
249  /*
250   * Serializes ImmutableCollections as their logical contents. This ensures
251   * that implementation types do not leak into the serialized representation.
252   */
253  private static class SerializedForm implements Serializable {
254    final Object[] elements;
255    SerializedForm(Object[] elements) {
256      this.elements = elements;
257    }
258    Object readResolve() {
259      return elements.length == 0
260          ? EMPTY_IMMUTABLE_COLLECTION
261          : new ArrayImmutableCollection<Object>(Platform.clone(elements));
262    }
263    private static final long serialVersionUID = 0;
264  }
265
266  Object writeReplace() {
267    return new SerializedForm(toArray());
268  }
269
270  /**
271   * Abstract base class for builders of {@link ImmutableCollection} types.
272   *
273   * @since 10.0
274   */
275  public abstract static class Builder<E> {
276    static final int DEFAULT_INITIAL_CAPACITY = 4;
277
278    @VisibleForTesting
279    static int expandedCapacity(int oldCapacity, int minCapacity) {
280      if (minCapacity < 0) {
281        throw new AssertionError("cannot store more than MAX_VALUE elements");
282      }
283      // careful of overflow!
284      int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
285      if (newCapacity < minCapacity) {
286        newCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
287      }
288      if (newCapacity < 0) {
289        newCapacity = Integer.MAX_VALUE;
290        // guaranteed to be >= newCapacity
291      }
292      return newCapacity;
293    }
294
295    Builder() {
296    }
297
298    /**
299     * Adds {@code element} to the {@code ImmutableCollection} being built.
300     *
301     * <p>Note that each builder class covariantly returns its own type from
302     * this method.
303     *
304     * @param element the element to add
305     * @return this {@code Builder} instance
306     * @throws NullPointerException if {@code element} is null
307     */
308    public abstract Builder<E> add(E element);
309
310    /**
311     * Adds each element of {@code elements} to the {@code ImmutableCollection}
312     * being built.
313     *
314     * <p>Note that each builder class overrides this method in order to
315     * covariantly return its own type.
316     *
317     * @param elements the elements to add
318     * @return this {@code Builder} instance
319     * @throws NullPointerException if {@code elements} is null or contains a
320     *     null element
321     */
322    public Builder<E> add(E... elements) {
323      for (E element : elements) {
324        add(element);
325      }
326      return this;
327    }
328
329    /**
330     * Adds each element of {@code elements} to the {@code ImmutableCollection}
331     * being built.
332     *
333     * <p>Note that each builder class overrides this method in order to
334     * covariantly return its own type.
335     *
336     * @param elements the elements to add
337     * @return this {@code Builder} instance
338     * @throws NullPointerException if {@code elements} is null or contains a
339     *     null element
340     */
341    public Builder<E> addAll(Iterable<? extends E> elements) {
342      for (E element : elements) {
343        add(element);
344      }
345      return this;
346    }
347
348    /**
349     * Adds each element of {@code elements} to the {@code ImmutableCollection}
350     * being built.
351     *
352     * <p>Note that each builder class overrides this method in order to
353     * covariantly return its own type.
354     *
355     * @param elements the elements to add
356     * @return this {@code Builder} instance
357     * @throws NullPointerException if {@code elements} is null or contains a
358     *     null element
359     */
360    public Builder<E> addAll(Iterator<? extends E> elements) {
361      while (elements.hasNext()) {
362        add(elements.next());
363      }
364      return this;
365    }
366
367    /**
368     * Returns a newly-created {@code ImmutableCollection} of the appropriate
369     * type, containing the elements provided to this builder.
370     *
371     * <p>Note that each builder class covariantly returns the appropriate type
372     * of {@code ImmutableCollection} from this method.
373     */
374    public abstract ImmutableCollection<E> build();
375  }
376}