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
017 package com.google.common.collect;
018
019 import com.google.common.annotations.GwtCompatible;
020 import com.google.common.annotations.VisibleForTesting;
021
022 import java.io.Serializable;
023 import java.util.Collection;
024 import java.util.Iterator;
025
026 import 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
043 public 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 }