001 /*
002 * Copyright (C) 2007 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 static com.google.common.base.Preconditions.checkElementIndex;
020 import static com.google.common.base.Preconditions.checkNotNull;
021 import static com.google.common.base.Preconditions.checkPositionIndex;
022 import static com.google.common.base.Preconditions.checkPositionIndexes;
023 import static com.google.common.collect.ObjectArrays.checkElementNotNull;
024
025 import com.google.common.annotations.GwtCompatible;
026
027 import java.io.InvalidObjectException;
028 import java.io.ObjectInputStream;
029 import java.io.Serializable;
030 import java.util.Collection;
031 import java.util.Collections;
032 import java.util.Iterator;
033 import java.util.List;
034 import java.util.RandomAccess;
035
036 import javax.annotation.Nullable;
037
038 /**
039 * A high-performance, immutable, random-access {@code List} implementation.
040 * Does not permit null elements.
041 *
042 * <p>Unlike {@link Collections#unmodifiableList}, which is a <i>view</i> of a
043 * separate collection that can still change, an instance of {@code
044 * ImmutableList} contains its own private data and will <i>never</i> change.
045 * {@code ImmutableList} is convenient for {@code public static final} lists
046 * ("constant lists") and also lets you easily make a "defensive copy" of a list
047 * provided to your class by a caller.
048 *
049 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
050 * it has no public or protected constructors. Thus, instances of this type are
051 * guaranteed to be immutable.
052 *
053 * <p>See the Guava User Guide article on <a href=
054 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
055 * immutable collections</a>.
056 *
057 * @see ImmutableMap
058 * @see ImmutableSet
059 * @author Kevin Bourrillion
060 * @since 2.0 (imported from Google Collections Library)
061 */
062 @GwtCompatible(serializable = true, emulated = true)
063 @SuppressWarnings("serial") // we're overriding default serialization
064 public abstract class ImmutableList<E> extends ImmutableCollection<E>
065 implements List<E>, RandomAccess {
066 /**
067 * Returns the empty immutable list. This set behaves and performs comparably
068 * to {@link Collections#emptyList}, and is preferable mainly for consistency
069 * and maintainability of your code.
070 */
071 // Casting to any type is safe because the list will never hold any elements.
072 @SuppressWarnings("unchecked")
073 public static <E> ImmutableList<E> of() {
074 return (ImmutableList<E>) EmptyImmutableList.INSTANCE;
075 }
076
077 /**
078 * Returns an immutable list containing a single element. This list behaves
079 * and performs comparably to {@link Collections#singleton}, but will not
080 * accept a null element. It is preferable mainly for consistency and
081 * maintainability of your code.
082 *
083 * @throws NullPointerException if {@code element} is null
084 */
085 public static <E> ImmutableList<E> of(E element) {
086 return new SingletonImmutableList<E>(element);
087 }
088
089 /**
090 * Returns an immutable list containing the given elements, in order.
091 *
092 * @throws NullPointerException if any element is null
093 */
094 public static <E> ImmutableList<E> of(E e1, E e2) {
095 return construct(e1, e2);
096 }
097
098 /**
099 * Returns an immutable list containing the given elements, in order.
100 *
101 * @throws NullPointerException if any element is null
102 */
103 public static <E> ImmutableList<E> of(E e1, E e2, E e3) {
104 return construct(e1, e2, e3);
105 }
106
107 /**
108 * Returns an immutable list containing the given elements, in order.
109 *
110 * @throws NullPointerException if any element is null
111 */
112 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4) {
113 return construct(e1, e2, e3, e4);
114 }
115
116 /**
117 * Returns an immutable list containing the given elements, in order.
118 *
119 * @throws NullPointerException if any element is null
120 */
121 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5) {
122 return construct(e1, e2, e3, e4, e5);
123 }
124
125 /**
126 * Returns an immutable list containing the given elements, in order.
127 *
128 * @throws NullPointerException if any element is null
129 */
130 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5, E e6) {
131 return construct(e1, e2, e3, e4, e5, e6);
132 }
133
134 /**
135 * Returns an immutable list containing the given elements, in order.
136 *
137 * @throws NullPointerException if any element is null
138 */
139 public static <E> ImmutableList<E> of(
140 E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
141 return construct(e1, e2, e3, e4, e5, e6, e7);
142 }
143
144 /**
145 * Returns an immutable list containing the given elements, in order.
146 *
147 * @throws NullPointerException if any element is null
148 */
149 public static <E> ImmutableList<E> of(
150 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
151 return construct(e1, e2, e3, e4, e5, e6, e7, e8);
152 }
153
154 /**
155 * Returns an immutable list containing the given elements, in order.
156 *
157 * @throws NullPointerException if any element is null
158 */
159 public static <E> ImmutableList<E> of(
160 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
161 return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9);
162 }
163
164 /**
165 * Returns an immutable list containing the given elements, in order.
166 *
167 * @throws NullPointerException if any element is null
168 */
169 public static <E> ImmutableList<E> of(
170 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
171 return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10);
172 }
173
174 /**
175 * Returns an immutable list containing the given elements, in order.
176 *
177 * @throws NullPointerException if any element is null
178 */
179 public static <E> ImmutableList<E> of(
180 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10, E e11) {
181 return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11);
182 }
183
184 // These go up to eleven. After that, you just get the varargs form, and
185 // whatever warnings might come along with it. :(
186
187 /**
188 * Returns an immutable list containing the given elements, in order.
189 *
190 * @throws NullPointerException if any element is null
191 * @since 3.0 (source-compatible since 2.0)
192 */
193 public static <E> ImmutableList<E> of(
194 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10, E e11, E e12,
195 E... others) {
196 Object[] array = new Object[12 + others.length];
197 array[0] = e1;
198 array[1] = e2;
199 array[2] = e3;
200 array[3] = e4;
201 array[4] = e5;
202 array[5] = e6;
203 array[6] = e7;
204 array[7] = e8;
205 array[8] = e9;
206 array[9] = e10;
207 array[10] = e11;
208 array[11] = e12;
209 System.arraycopy(others, 0, array, 12, others.length);
210 return construct(array);
211 }
212
213 /**
214 * Returns an immutable list containing the given elements, in order. If
215 * {@code elements} is a {@link Collection}, this method behaves exactly as
216 * {@link #copyOf(Collection)}; otherwise, it behaves exactly as {@code
217 * copyOf(elements.iterator()}.
218 *
219 * @throws NullPointerException if any of {@code elements} is null
220 */
221 public static <E> ImmutableList<E> copyOf(Iterable<? extends E> elements) {
222 checkNotNull(elements); // TODO(kevinb): is this here only for GWT?
223 return (elements instanceof Collection)
224 ? copyOf(Collections2.cast(elements))
225 : copyOf(elements.iterator());
226 }
227
228 /**
229 * Returns an immutable list containing the given elements, in order.
230 *
231 * <p>Despite the method name, this method attempts to avoid actually copying
232 * the data when it is safe to do so. The exact circumstances under which a
233 * copy will or will not be performed are undocumented and subject to change.
234 *
235 * <p>Note that if {@code list} is a {@code List<String>}, then {@code
236 * ImmutableList.copyOf(list)} returns an {@code ImmutableList<String>}
237 * containing each of the strings in {@code list}, while
238 * ImmutableList.of(list)} returns an {@code ImmutableList<List<String>>}
239 * containing one element (the given list itself).
240 *
241 * <p>This method is safe to use even when {@code elements} is a synchronized
242 * or concurrent collection that is currently being modified by another
243 * thread.
244 *
245 * @throws NullPointerException if any of {@code elements} is null
246 */
247 public static <E> ImmutableList<E> copyOf(Collection<? extends E> elements) {
248 if (elements instanceof ImmutableCollection) {
249 @SuppressWarnings("unchecked") // all supported methods are covariant
250 ImmutableList<E> list = ((ImmutableCollection<E>) elements).asList();
251 return list.isPartialView() ? copyFromCollection(list) : list;
252 }
253 return copyFromCollection(elements);
254 }
255
256 /**
257 * Returns an immutable list containing the given elements, in order.
258 *
259 * @throws NullPointerException if any of {@code elements} is null
260 */
261 public static <E> ImmutableList<E> copyOf(Iterator<? extends E> elements) {
262 // We special-case for 0 or 1 elements, but going further is madness.
263 if (!elements.hasNext()) {
264 return of();
265 }
266 E first = elements.next();
267 if (!elements.hasNext()) {
268 return of(first);
269 } else {
270 return new ImmutableList.Builder<E>()
271 .add(first)
272 .addAll(elements)
273 .build();
274 }
275 }
276
277 /**
278 * Returns an immutable list containing the given elements, in order.
279 *
280 * @throws NullPointerException if any of {@code elements} is null
281 * @since 3.0
282 */
283 public static <E> ImmutableList<E> copyOf(E[] elements) {
284 switch (elements.length) {
285 case 0:
286 return ImmutableList.of();
287 case 1:
288 return new SingletonImmutableList<E>(elements[0]);
289 default:
290 return construct(elements.clone());
291 }
292 }
293
294 /**
295 * Views the array as an immutable list. The array must have only non-null {@code E} elements.
296 *
297 * <p>The array must be internally created.
298 */
299 static <E> ImmutableList<E> asImmutableList(Object[] elements) {
300 switch (elements.length) {
301 case 0:
302 return of();
303 case 1:
304 @SuppressWarnings("unchecked") // collection had only Es in it
305 ImmutableList<E> list = new SingletonImmutableList<E>((E) elements[0]);
306 return list;
307 default:
308 return construct(elements);
309 }
310 }
311
312 private static <E> ImmutableList<E> copyFromCollection(
313 Collection<? extends E> collection) {
314 return asImmutableList(collection.toArray());
315 }
316
317 /** {@code elements} has to be internally created array. */
318 private static <E> ImmutableList<E> construct(Object... elements) {
319 for (int i = 0; i < elements.length; i++) {
320 ObjectArrays.checkElementNotNull(elements[i], i);
321 }
322 return new RegularImmutableList<E>(elements);
323 }
324
325 ImmutableList() {}
326
327 // This declaration is needed to make List.iterator() and
328 // ImmutableCollection.iterator() consistent.
329 @Override public UnmodifiableIterator<E> iterator() {
330 return listIterator();
331 }
332
333 @Override public UnmodifiableListIterator<E> listIterator() {
334 return listIterator(0);
335 }
336
337 @Override public UnmodifiableListIterator<E> listIterator(int index) {
338 return new AbstractIndexedListIterator<E>(size(), index) {
339 @Override
340 protected E get(int index) {
341 return ImmutableList.this.get(index);
342 }
343 };
344 }
345
346 @Override
347 public int indexOf(@Nullable Object object) {
348 return (object == null) ? -1 : Lists.indexOfImpl(this, object);
349 }
350
351 @Override
352 public int lastIndexOf(@Nullable Object object) {
353 return (object == null) ? -1 : Lists.lastIndexOfImpl(this, object);
354 }
355
356 @Override
357 public boolean contains(@Nullable Object object) {
358 return indexOf(object) >= 0;
359 }
360
361 // constrain the return type to ImmutableList<E>
362
363 /**
364 * Returns an immutable list of the elements between the specified {@code
365 * fromIndex}, inclusive, and {@code toIndex}, exclusive. (If {@code
366 * fromIndex} and {@code toIndex} are equal, the empty immutable list is
367 * returned.)
368 */
369 @Override
370 public ImmutableList<E> subList(int fromIndex, int toIndex) {
371 checkPositionIndexes(fromIndex, toIndex, size());
372 int length = toIndex - fromIndex;
373 switch (length) {
374 case 0:
375 return of();
376 case 1:
377 return of(get(fromIndex));
378 default:
379 return subListUnchecked(fromIndex, toIndex);
380 }
381 }
382
383 /**
384 * Called by the default implementation of {@link #subList} when {@code
385 * toIndex - fromIndex > 1}, after index validation has already been
386 * performed.
387 */
388 ImmutableList<E> subListUnchecked(int fromIndex, int toIndex) {
389 return new SubList(fromIndex, toIndex - fromIndex);
390 }
391
392 class SubList extends ImmutableList<E> {
393 transient final int offset;
394 transient final int length;
395
396 SubList(int offset, int length) {
397 this.offset = offset;
398 this.length = length;
399 }
400
401 @Override
402 public int size() {
403 return length;
404 }
405
406 @Override
407 public E get(int index) {
408 checkElementIndex(index, length);
409 return ImmutableList.this.get(index + offset);
410 }
411
412 @Override
413 public ImmutableList<E> subList(int fromIndex, int toIndex) {
414 checkPositionIndexes(fromIndex, toIndex, length);
415 return ImmutableList.this.subList(fromIndex + offset, toIndex + offset);
416 }
417
418 @Override
419 boolean isPartialView() {
420 return true;
421 }
422 }
423
424 /**
425 * Guaranteed to throw an exception and leave the list unmodified.
426 *
427 * @throws UnsupportedOperationException always
428 */
429 @Override
430 public final boolean addAll(int index, Collection<? extends E> newElements) {
431 throw new UnsupportedOperationException();
432 }
433
434 /**
435 * Guaranteed to throw an exception and leave the list unmodified.
436 *
437 * @throws UnsupportedOperationException always
438 */
439 @Override
440 public final E set(int index, E element) {
441 throw new UnsupportedOperationException();
442 }
443
444 /**
445 * Guaranteed to throw an exception and leave the list unmodified.
446 *
447 * @throws UnsupportedOperationException always
448 */
449 @Override
450 public final void add(int index, E element) {
451 throw new UnsupportedOperationException();
452 }
453
454 /**
455 * Guaranteed to throw an exception and leave the list unmodified.
456 *
457 * @throws UnsupportedOperationException always
458 */
459 @Override
460 public final E remove(int index) {
461 throw new UnsupportedOperationException();
462 }
463
464 /**
465 * Returns this list instance.
466 *
467 * @since 2.0
468 */
469 @Override public ImmutableList<E> asList() {
470 return this;
471 }
472
473 /**
474 * Returns a view of this immutable list in reverse order. For example, {@code
475 * ImmutableList.of(1, 2, 3).reverse()} is equivalent to {@code
476 * ImmutableList.of(3, 2, 1)}.
477 *
478 * @return a view of this immutable list in reverse order
479 * @since 7.0
480 */
481 public ImmutableList<E> reverse() {
482 return new ReverseImmutableList<E>(this);
483 }
484
485 private static class ReverseImmutableList<E> extends ImmutableList<E> {
486 private final transient ImmutableList<E> forwardList;
487 private final transient int size;
488
489 ReverseImmutableList(ImmutableList<E> backingList) {
490 this.forwardList = backingList;
491 this.size = backingList.size();
492 }
493
494 private int reverseIndex(int index) {
495 return (size - 1) - index;
496 }
497
498 private int reversePosition(int index) {
499 return size - index;
500 }
501
502 @Override public ImmutableList<E> reverse() {
503 return forwardList;
504 }
505
506 @Override public boolean contains(@Nullable Object object) {
507 return forwardList.contains(object);
508 }
509
510 @Override public boolean containsAll(Collection<?> targets) {
511 return forwardList.containsAll(targets);
512 }
513
514 @Override public int indexOf(@Nullable Object object) {
515 int index = forwardList.lastIndexOf(object);
516 return (index >= 0) ? reverseIndex(index) : -1;
517 }
518
519 @Override public int lastIndexOf(@Nullable Object object) {
520 int index = forwardList.indexOf(object);
521 return (index >= 0) ? reverseIndex(index) : -1;
522 }
523
524 @Override public ImmutableList<E> subList(int fromIndex, int toIndex) {
525 checkPositionIndexes(fromIndex, toIndex, size);
526 return forwardList.subList(
527 reversePosition(toIndex), reversePosition(fromIndex)).reverse();
528 }
529
530 @Override public E get(int index) {
531 checkElementIndex(index, size);
532 return forwardList.get(reverseIndex(index));
533 }
534
535 @Override public UnmodifiableListIterator<E> listIterator(int index) {
536 checkPositionIndex(index, size);
537 final UnmodifiableListIterator<E> forward =
538 forwardList.listIterator(reversePosition(index));
539 return new UnmodifiableListIterator<E>() {
540 @Override public boolean hasNext() {
541 return forward.hasPrevious();
542 }
543
544 @Override public boolean hasPrevious() {
545 return forward.hasNext();
546 }
547
548 @Override public E next() {
549 return forward.previous();
550 }
551
552 @Override public int nextIndex() {
553 return reverseIndex(forward.previousIndex());
554 }
555
556 @Override public E previous() {
557 return forward.next();
558 }
559
560 @Override public int previousIndex() {
561 return reverseIndex(forward.nextIndex());
562 }
563 };
564 }
565
566 @Override public int size() {
567 return size;
568 }
569
570 @Override public boolean isEmpty() {
571 return forwardList.isEmpty();
572 }
573
574 @Override boolean isPartialView() {
575 return forwardList.isPartialView();
576 }
577 }
578
579 @Override public boolean equals(Object obj) {
580 return Lists.equalsImpl(this, obj);
581 }
582
583 @Override public int hashCode() {
584 return Lists.hashCodeImpl(this);
585 }
586
587 /*
588 * Serializes ImmutableLists as their logical contents. This ensures that
589 * implementation types do not leak into the serialized representation.
590 */
591 private static class SerializedForm implements Serializable {
592 final Object[] elements;
593 SerializedForm(Object[] elements) {
594 this.elements = elements;
595 }
596 Object readResolve() {
597 return copyOf(elements);
598 }
599 private static final long serialVersionUID = 0;
600 }
601
602 private void readObject(ObjectInputStream stream)
603 throws InvalidObjectException {
604 throw new InvalidObjectException("Use SerializedForm");
605 }
606
607 @Override Object writeReplace() {
608 return new SerializedForm(toArray());
609 }
610
611 /**
612 * Returns a new builder. The generated builder is equivalent to the builder
613 * created by the {@link Builder} constructor.
614 */
615 public static <E> Builder<E> builder() {
616 return new Builder<E>();
617 }
618
619 /**
620 * A builder for creating immutable list instances, especially {@code public
621 * static final} lists ("constant lists"). Example: <pre> {@code
622 *
623 * public static final ImmutableList<Color> GOOGLE_COLORS
624 * = new ImmutableList.Builder<Color>()
625 * .addAll(WEBSAFE_COLORS)
626 * .add(new Color(0, 191, 255))
627 * .build();}</pre>
628 *
629 * Builder instances can be reused; it is safe to call {@link #build} multiple
630 * times to build multiple lists in series. Each new list contains all the
631 * elements of the ones created before it.
632 *
633 * @since 2.0 (imported from Google Collections Library)
634 */
635 public static final class Builder<E> extends ImmutableCollection.Builder<E> {
636 private Object[] contents;
637 private int size;
638
639 /**
640 * Creates a new builder. The returned builder is equivalent to the builder
641 * generated by {@link ImmutableList#builder}.
642 */
643 public Builder() {
644 this(DEFAULT_INITIAL_CAPACITY);
645 }
646
647 // TODO(user): consider exposing this
648 Builder(int capacity) {
649 this.contents = new Object[capacity];
650 this.size = 0;
651 }
652
653 /**
654 * Expand capacity to allow the specified number of elements to be added.
655 */
656 Builder<E> expandFor(int count) {
657 int minCapacity = size + count;
658 if (contents.length < minCapacity) {
659 this.contents = ObjectArrays.arraysCopyOf(
660 this.contents, expandedCapacity(contents.length, minCapacity));
661 }
662 return this;
663 }
664
665 /**
666 * Adds {@code element} to the {@code ImmutableList}.
667 *
668 * @param element the element to add
669 * @return this {@code Builder} object
670 * @throws NullPointerException if {@code element} is null
671 */
672 @Override public Builder<E> add(E element) {
673 checkNotNull(element);
674 expandFor(1);
675 contents[size++] = element;
676 return this;
677 }
678
679 /**
680 * Adds each element of {@code elements} to the {@code ImmutableList}.
681 *
682 * @param elements the {@code Iterable} to add to the {@code ImmutableList}
683 * @return this {@code Builder} object
684 * @throws NullPointerException if {@code elements} is null or contains a
685 * null element
686 */
687 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
688 if (elements instanceof Collection) {
689 Collection<?> collection = (Collection<?>) elements;
690 expandFor(collection.size());
691 }
692 super.addAll(elements);
693 return this;
694 }
695
696 /**
697 * Adds each element of {@code elements} to the {@code ImmutableList}.
698 *
699 * @param elements the {@code Iterable} to add to the {@code ImmutableList}
700 * @return this {@code Builder} object
701 * @throws NullPointerException if {@code elements} is null or contains a
702 * null element
703 */
704 @Override public Builder<E> add(E... elements) {
705 for (int i = 0; i < elements.length; i++) {
706 checkElementNotNull(elements[i], i);
707 }
708 expandFor(elements.length);
709 System.arraycopy(elements, 0, contents, size, elements.length);
710 size += elements.length;
711 return this;
712 }
713
714 /**
715 * Adds each element of {@code elements} to the {@code ImmutableList}.
716 *
717 * @param elements the {@code Iterable} to add to the {@code ImmutableList}
718 * @return this {@code Builder} object
719 * @throws NullPointerException if {@code elements} is null or contains a
720 * null element
721 */
722 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
723 super.addAll(elements);
724 return this;
725 }
726
727 /**
728 * Returns a newly-created {@code ImmutableList} based on the contents of
729 * the {@code Builder}.
730 */
731 @Override public ImmutableList<E> build() {
732 switch (size) {
733 case 0:
734 return of();
735 case 1:
736 @SuppressWarnings("unchecked") // guaranteed to be an E
737 E singleElement = (E) contents[0];
738 return of(singleElement);
739 default:
740 if (size == contents.length) {
741 // no need to copy; any further add operations on the builder will copy the buffer
742 return new RegularImmutableList<E>(contents);
743 } else {
744 return new RegularImmutableList<E>(ObjectArrays.arraysCopyOf(contents, size));
745 }
746 }
747 }
748 }
749 }