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;
024
025import java.io.Serializable;
026import java.util.AbstractCollection;
027import java.util.Collection;
028import java.util.Iterator;
029
030import javax.annotation.Nullable;
031
032/**
033 * An immutable collection. Does not permit null elements.
034 *
035 * <p>In addition to the {@link Collection} methods, this class has an {@link
036 * #asList()} method, which returns a list view of the collection's elements.
037 *
038 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed
039 * outside of this package as it has no public or protected constructors. Thus,
040 * instances of this type are guaranteed to be immutable.
041 *
042 * @author Jesse Wilson
043 * @since 2.0 (imported from Google Collections Library)
044 */
045@GwtCompatible(emulated = true)
046@SuppressWarnings("serial") // we're overriding default serialization
047public abstract class ImmutableCollection<E> extends AbstractCollection<E>
048    implements Serializable {
049
050  ImmutableCollection() {}
051
052  /**
053   * Returns an unmodifiable iterator across the elements in this collection.
054   */
055  @Override
056  public abstract UnmodifiableIterator<E> iterator();
057
058  @Override
059  public final Object[] toArray() {
060    int size = size();
061    if (size == 0) {
062      return ObjectArrays.EMPTY_ARRAY;
063    }
064    Object[] result = new Object[size];
065    copyIntoArray(result, 0);
066    return result;
067  }
068
069  @Override
070  public final <T> T[] toArray(T[] other) {
071    checkNotNull(other);
072    int size = size();
073    if (other.length < size) {
074      other = ObjectArrays.newArray(other, size);
075    } else if (other.length > size) {
076      other[size] = null;
077    }
078    copyIntoArray(other, 0);
079    return other;
080  }
081
082  @Override
083  public boolean contains(@Nullable Object object) {
084    return object != null && super.contains(object);
085  }
086
087  /**
088   * Guaranteed to throw an exception and leave the collection unmodified.
089   *
090   * @throws UnsupportedOperationException always
091   * @deprecated Unsupported operation.
092   */
093  @Deprecated
094  @Override
095  public final boolean add(E e) {
096    throw new UnsupportedOperationException();
097  }
098
099  /**
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}