1/*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkNotNull;
20import static com.google.common.collect.CollectPreconditions.checkNonnegative;
21import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
22
23import com.google.common.annotations.GwtCompatible;
24
25import java.io.Serializable;
26import java.util.AbstractCollection;
27import java.util.Collection;
28import java.util.Iterator;
29
30import javax.annotation.Nullable;
31
32/**
33 * An immutable collection. Does not permit null elements.
34 *
35 * <p>In addition to the {@link Collection} methods, this class has an {@link
36 * #asList()} method, which returns a list view of the collection's elements.
37 *
38 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed
39 * outside of this package as it has no public or protected constructors. Thus,
40 * instances of this type are guaranteed to be immutable.
41 *
42 * @author Jesse Wilson
43 * @since 2.0 (imported from Google Collections Library)
44 */
45@GwtCompatible(emulated = true)
46@SuppressWarnings("serial") // we're overriding default serialization
47public abstract class ImmutableCollection<E> extends AbstractCollection<E>
48    implements Serializable {
49
50  ImmutableCollection() {}
51
52  /**
53   * Returns an unmodifiable iterator across the elements in this collection.
54   */
55  @Override
56  public abstract UnmodifiableIterator<E> iterator();
57
58  @Override
59  public final Object[] toArray() {
60    int size = size();
61    if (size == 0) {
62      return ObjectArrays.EMPTY_ARRAY;
63    }
64    Object[] result = new Object[size];
65    copyIntoArray(result, 0);
66    return result;
67  }
68
69  @Override
70  public final <T> T[] toArray(T[] other) {
71    checkNotNull(other);
72    int size = size();
73    if (other.length < size) {
74      other = ObjectArrays.newArray(other, size);
75    } else if (other.length > size) {
76      other[size] = null;
77    }
78    copyIntoArray(other, 0);
79    return other;
80  }
81
82  @Override
83  public boolean contains(@Nullable Object object) {
84    return object != null && super.contains(object);
85  }
86
87  /**
88   * Guaranteed to throw an exception and leave the collection unmodified.
89   *
90   * @throws UnsupportedOperationException always
91   * @deprecated Unsupported operation.
92   */
93  @Deprecated
94  @Override
95  public final boolean add(E e) {
96    throw new UnsupportedOperationException();
97  }
98
99  /**
100   * Guaranteed to throw an exception and leave the collection unmodified.
101   *
102   * @throws UnsupportedOperationException always
103   * @deprecated Unsupported operation.
104   */
105  @Deprecated
106  @Override
107  public final boolean remove(Object object) {
108    throw new UnsupportedOperationException();
109  }
110
111  /**
112   * Guaranteed to throw an exception and leave the collection unmodified.
113   *
114   * @throws UnsupportedOperationException always
115   * @deprecated Unsupported operation.
116   */
117  @Deprecated
118  @Override
119  public final boolean addAll(Collection<? extends E> newElements) {
120    throw new UnsupportedOperationException();
121  }
122
123  /**
124   * Guaranteed to throw an exception and leave the collection unmodified.
125   *
126   * @throws UnsupportedOperationException always
127   * @deprecated Unsupported operation.
128   */
129  @Deprecated
130  @Override
131  public final boolean removeAll(Collection<?> oldElements) {
132    throw new UnsupportedOperationException();
133  }
134
135  /**
136   * Guaranteed to throw an exception and leave the collection unmodified.
137   *
138   * @throws UnsupportedOperationException always
139   * @deprecated Unsupported operation.
140   */
141  @Deprecated
142  @Override
143  public final boolean retainAll(Collection<?> elementsToKeep) {
144    throw new UnsupportedOperationException();
145  }
146
147  /**
148   * Guaranteed to throw an exception and leave the collection unmodified.
149   *
150   * @throws UnsupportedOperationException always
151   * @deprecated Unsupported operation.
152   */
153  @Deprecated
154  @Override
155  public final void clear() {
156    throw new UnsupportedOperationException();
157  }
158
159  /*
160   * TODO(kevinb): Restructure code so ImmutableList doesn't contain this
161   * variable, which it doesn't use.
162   */
163  private transient ImmutableList<E> asList;
164
165  /**
166   * Returns a list view of the collection.
167   *
168   * @since 2.0
169   */
170  public ImmutableList<E> asList() {
171    ImmutableList<E> list = asList;
172    return (list == null) ? (asList = createAsList()) : list;
173  }
174
175  ImmutableList<E> createAsList() {
176    switch (size()) {
177      case 0:
178        return ImmutableList.of();
179      case 1:
180        return ImmutableList.of(iterator().next());
181      default:
182        return new RegularImmutableAsList<E>(this, toArray());
183    }
184  }
185
186  /**
187   * Returns {@code true} if this immutable collection's implementation contains references to
188   * user-created objects that aren't accessible via this collection's methods. This is generally
189   * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid
190   * memory leaks.
191   */
192  abstract boolean isPartialView();
193
194  /**
195   * Copies the contents of this immutable collection into the specified array at the specified
196   * offset.  Returns {@code offset + size()}.
197   */
198  int copyIntoArray(Object[] dst, int offset) {
199    for (E e : this) {
200      dst[offset++] = e;
201    }
202    return offset;
203  }
204
205  Object writeReplace() {
206    // We serialize by default to ImmutableList, the simplest thing that works.
207    return new ImmutableList.SerializedForm(toArray());
208  }
209
210  /**
211   * Abstract base class for builders of {@link ImmutableCollection} types.
212   *
213   * @since 10.0
214   */
215  public abstract static class Builder<E> {
216    static final int DEFAULT_INITIAL_CAPACITY = 4;
217
218    static int expandedCapacity(int oldCapacity, int minCapacity) {
219      if (minCapacity < 0) {
220        throw new AssertionError("cannot store more than MAX_VALUE elements");
221      }
222      // careful of overflow!
223      int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
224      if (newCapacity < minCapacity) {
225        newCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
226      }
227      if (newCapacity < 0) {
228        newCapacity = Integer.MAX_VALUE;
229        // guaranteed to be >= newCapacity
230      }
231      return newCapacity;
232    }
233
234    Builder() {
235    }
236
237    /**
238     * Adds {@code element} to the {@code ImmutableCollection} being built.
239     *
240     * <p>Note that each builder class covariantly returns its own type from
241     * this method.
242     *
243     * @param element the element to add
244     * @return this {@code Builder} instance
245     * @throws NullPointerException if {@code element} is null
246     */
247    public abstract Builder<E> add(E element);
248
249    /**
250     * Adds each element of {@code elements} to the {@code ImmutableCollection}
251     * being built.
252     *
253     * <p>Note that each builder class overrides this method in order to
254     * covariantly return its own type.
255     *
256     * @param elements the elements to add
257     * @return this {@code Builder} instance
258     * @throws NullPointerException if {@code elements} is null or contains a
259     *     null element
260     */
261    public Builder<E> add(E... elements) {
262      for (E element : elements) {
263        add(element);
264      }
265      return this;
266    }
267
268    /**
269     * Adds each element of {@code elements} to the {@code ImmutableCollection}
270     * being built.
271     *
272     * <p>Note that each builder class overrides this method in order to
273     * covariantly return its own type.
274     *
275     * @param elements the elements to add
276     * @return this {@code Builder} instance
277     * @throws NullPointerException if {@code elements} is null or contains a
278     *     null element
279     */
280    public Builder<E> addAll(Iterable<? extends E> elements) {
281      for (E element : elements) {
282        add(element);
283      }
284      return this;
285    }
286
287    /**
288     * Adds each element of {@code elements} to the {@code ImmutableCollection}
289     * being built.
290     *
291     * <p>Note that each builder class overrides this method in order to
292     * covariantly return its own type.
293     *
294     * @param elements the elements to add
295     * @return this {@code Builder} instance
296     * @throws NullPointerException if {@code elements} is null or contains a
297     *     null element
298     */
299    public Builder<E> addAll(Iterator<? extends E> elements) {
300      while (elements.hasNext()) {
301        add(elements.next());
302      }
303      return this;
304    }
305
306    /**
307     * Returns a newly-created {@code ImmutableCollection} of the appropriate
308     * type, containing the elements provided to this builder.
309     *
310     * <p>Note that each builder class covariantly returns the appropriate type
311     * of {@code ImmutableCollection} from this method.
312     */
313    public abstract ImmutableCollection<E> build();
314  }
315
316  abstract static class ArrayBasedBuilder<E> extends ImmutableCollection.Builder<E> {
317    Object[] contents;
318    int size;
319
320    ArrayBasedBuilder(int initialCapacity) {
321      checkNonnegative(initialCapacity, "initialCapacity");
322      this.contents = new Object[initialCapacity];
323      this.size = 0;
324    }
325
326    /**
327     * Expand the absolute capacity of the builder so it can accept at least
328     * the specified number of elements without being resized.
329     */
330    private void ensureCapacity(int minCapacity) {
331      if (contents.length < minCapacity) {
332        this.contents = ObjectArrays.arraysCopyOf(
333            this.contents, expandedCapacity(contents.length, minCapacity));
334      }
335    }
336
337    @Override
338    public ArrayBasedBuilder<E> add(E element) {
339      checkNotNull(element);
340      ensureCapacity(size + 1);
341      contents[size++] = element;
342      return this;
343    }
344
345    @Override
346    public Builder<E> add(E... elements) {
347      checkElementsNotNull(elements);
348      ensureCapacity(size + elements.length);
349      System.arraycopy(elements, 0, contents, size, elements.length);
350      size += elements.length;
351      return this;
352    }
353
354    @Override
355    public Builder<E> addAll(Iterable<? extends E> elements) {
356      if (elements instanceof Collection) {
357        Collection<?> collection = (Collection<?>) elements;
358        ensureCapacity(size + collection.size());
359      }
360      super.addAll(elements);
361      return this;
362    }
363  }
364}
365