1/*
2 * Copyright (C) 2008 Google Inc.
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 com.google.common.annotations.GwtCompatible;
20import static com.google.common.base.Preconditions.checkNotNull;
21
22import java.io.Serializable;
23import java.util.Collection;
24import java.util.Iterator;
25
26import javax.annotation.Nullable;
27
28/**
29 * An immutable collection. Does not permit null elements.
30 *
31 * <p>In addition to the {@link Collection} methods, this class has an {@link
32 * #asList()} method, which returns a list view of the collection's elements.
33 *
34 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed
35 * outside of this package as it has no public or protected constructors. Thus,
36 * instances of this type are guaranteed to be immutable.
37 *
38 * @author Jesse Wilson
39 * @since 2010.01.04 <b>stable</b> (imported from Google Collections Library)
40 */
41@GwtCompatible
42@SuppressWarnings("serial") // we're overriding default serialization
43public abstract class ImmutableCollection<E>
44    implements Collection<E>, Serializable {
45  static final ImmutableCollection<Object> EMPTY_IMMUTABLE_COLLECTION
46      = new EmptyImmutableCollection();
47
48  ImmutableCollection() {}
49
50  /**
51   * Returns an unmodifiable iterator across the elements in this collection.
52   */
53  public abstract UnmodifiableIterator<E> iterator();
54
55  public Object[] toArray() {
56    Object[] newArray = new Object[size()];
57    return toArray(newArray);
58  }
59
60  public <T> T[] toArray(T[] other) {
61    int size = size();
62    if (other.length < size) {
63      other = ObjectArrays.newArray(other, size);
64    } else if (other.length > size) {
65      other[size] = null;
66    }
67
68    // Writes will produce ArrayStoreException when the toArray() doc requires.
69    Object[] otherAsObjectArray = other;
70    int index = 0;
71    for (E element : this) {
72      otherAsObjectArray[index++] = element;
73    }
74    return other;
75  }
76
77  public boolean contains(@Nullable Object object) {
78    if (object == null) {
79      return false;
80    }
81    for (E element : this) {
82      if (element.equals(object)) {
83        return true;
84      }
85    }
86    return false;
87  }
88
89  public boolean containsAll(Collection<?> targets) {
90    for (Object target : targets) {
91      if (!contains(target)) {
92        return false;
93      }
94    }
95    return true;
96  }
97
98  public boolean isEmpty() {
99    return size() == 0;
100  }
101
102  @Override public String toString() {
103    StringBuilder sb = new StringBuilder(size() * 16).append('[');
104    Collections2.standardJoiner.appendTo(sb, this);
105    return sb.append(']').toString();
106  }
107
108  /**
109   * Guaranteed to throw an exception and leave the collection unmodified.
110   *
111   * @throws UnsupportedOperationException always
112   */
113  public final boolean add(E e) {
114    throw new UnsupportedOperationException();
115  }
116
117  /**
118   * Guaranteed to throw an exception and leave the collection unmodified.
119   *
120   * @throws UnsupportedOperationException always
121   */
122  public final boolean remove(Object object) {
123    throw new UnsupportedOperationException();
124  }
125
126  /**
127   * Guaranteed to throw an exception and leave the collection unmodified.
128   *
129   * @throws UnsupportedOperationException always
130   */
131  public final boolean addAll(Collection<? extends E> newElements) {
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  public final boolean removeAll(Collection<?> oldElements) {
141    throw new UnsupportedOperationException();
142  }
143
144  /**
145   * Guaranteed to throw an exception and leave the collection unmodified.
146   *
147   * @throws UnsupportedOperationException always
148   */
149  public final boolean retainAll(Collection<?> elementsToKeep) {
150    throw new UnsupportedOperationException();
151  }
152
153  /**
154   * Guaranteed to throw an exception and leave the collection unmodified.
155   *
156   * @throws UnsupportedOperationException always
157   */
158  public final void clear() {
159    throw new UnsupportedOperationException();
160  }
161
162  // TODO: Restructure code so ImmutableList doesn't contain this variable,
163  // which it doesn't use.
164  private transient ImmutableList<E> asList;
165
166  /**
167   * Returns a list view of the collection.
168   *
169   * @since 2010.01.04 <b>tentative</b>
170   */
171  public ImmutableList<E> asList() {
172    ImmutableList<E> list = asList;
173    return (list == null) ? (asList = createAsList()) : list;
174  }
175
176  ImmutableList<E> createAsList() {
177    switch (size()) {
178      case 0:
179        return ImmutableList.of();
180      case 1:
181        return ImmutableList.of(iterator().next());
182      default:
183        return new ImmutableAsList<E>(toArray(), this);
184    }
185  }
186
187  private static class EmptyImmutableCollection
188      extends ImmutableCollection<Object> {
189    public int size() {
190      return 0;
191    }
192
193    @Override public boolean isEmpty() {
194      return true;
195    }
196
197    @Override public boolean contains(@Nullable Object object) {
198      return false;
199    }
200
201    @Override public UnmodifiableIterator<Object> iterator() {
202      return Iterators.EMPTY_ITERATOR;
203    }
204
205    private static final Object[] EMPTY_ARRAY = new Object[0];
206
207    @Override public Object[] toArray() {
208      return EMPTY_ARRAY;
209    }
210
211    @Override public <T> T[] toArray(T[] array) {
212      if (array.length > 0) {
213        array[0] = null;
214      }
215      return array;
216    }
217  }
218
219  private static class ArrayImmutableCollection<E>
220      extends ImmutableCollection<E> {
221    private final E[] elements;
222
223    ArrayImmutableCollection(E[] elements) {
224      this.elements = elements;
225    }
226
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
240  /*
241   * Serializes ImmutableCollections as their logical contents. This ensures
242   * that implementation types do not leak into the serialized representation.
243   */
244  private static class SerializedForm implements Serializable {
245    final Object[] elements;
246    SerializedForm(Object[] elements) {
247      this.elements = elements;
248    }
249    Object readResolve() {
250      return elements.length == 0
251          ? EMPTY_IMMUTABLE_COLLECTION
252          : new ArrayImmutableCollection<Object>(Platform.clone(elements));
253    }
254    private static final long serialVersionUID = 0;
255  }
256
257  Object writeReplace() {
258    return new SerializedForm(toArray());
259  }
260
261  /**
262   * Abstract base class for builders of {@link ImmutableCollection} types.
263   */
264  abstract static class Builder<E> {
265    /**
266     * Adds {@code element} to the {@code ImmutableCollection} being built.
267     *
268     * <p>Note that each builder class covariantly returns its own type from
269     * this method.
270     *
271     * @param element the element to add
272     * @return this {@code Builder} instance
273     * @throws NullPointerException if {@code element} is null
274     */
275    public abstract Builder<E> add(E element);
276
277    /**
278     * Adds each element of {@code elements} to the {@code ImmutableCollection}
279     * being built.
280     *
281     * <p>Note that each builder class overrides this method in order to
282     * covariantly return its own type.
283     *
284     * @param elements the elements to add
285     * @return this {@code Builder} instance
286     * @throws NullPointerException if {@code elements} is null or contains a
287     *     null element
288     */
289    public Builder<E> add(E... elements) {
290      checkNotNull(elements); // for GWT
291      for (E element : elements) {
292        add(element);
293      }
294      return this;
295    }
296
297    /**
298     * Adds each element of {@code elements} to the {@code ImmutableCollection}
299     * being built.
300     *
301     * <p>Note that each builder class overrides this method in order to
302     * covariantly return its own type.
303     *
304     * @param elements the elements to add
305     * @return this {@code Builder} instance
306     * @throws NullPointerException if {@code elements} is null or contains a
307     *     null element
308     */
309    public Builder<E> addAll(Iterable<? extends E> elements) {
310      checkNotNull(elements); // for GWT
311      for (E element : elements) {
312        add(element);
313      }
314      return this;
315    }
316
317    /**
318     * Adds each element of {@code elements} to the {@code ImmutableCollection}
319     * being built.
320     *
321     * <p>Note that each builder class overrides this method in order to
322     * covariantly return its own type.
323     *
324     * @param elements the elements to add
325     * @return this {@code Builder} instance
326     * @throws NullPointerException if {@code elements} is null or contains a
327     *     null element
328     */
329    public Builder<E> addAll(Iterator<? extends E> elements) {
330      checkNotNull(elements); // for GWT
331      while (elements.hasNext()) {
332        add(elements.next());
333      }
334      return this;
335    }
336
337    /**
338     * Returns a newly-created {@code ImmutableCollection} of the appropriate
339     * type, containing the elements provided to this builder.
340     *
341     * <p>Note that each builder class covariantly returns the appropriate type
342     * of {@code ImmutableCollection} from this method.
343     */
344    public abstract ImmutableCollection<E> build();
345  }
346}
347