1 /*
2 * Copyright (C) 2007 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
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkElementIndex;
21 import static com.google.common.base.Preconditions.checkNotNull;
22 import static com.google.common.base.Preconditions.checkPositionIndexes;
23 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
24 import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
25 import static com.google.common.collect.RegularImmutableList.EMPTY;
26 import static java.util.Objects.requireNonNull;
27
28 import com.google.common.annotations.Beta;
29 import com.google.common.annotations.GwtCompatible;
30 import com.google.common.annotations.VisibleForTesting;
31 import com.google.errorprone.annotations.CanIgnoreReturnValue;
32 import com.google.errorprone.annotations.DoNotCall;
33 import com.google.errorprone.annotations.InlineMe;
34 import java.io.InvalidObjectException;
35 import java.io.ObjectInputStream;
36 import java.io.Serializable;
37 import java.util.Arrays;
38 import java.util.Collection;
39 import java.util.Collections;
40 import java.util.Comparator;
41 import java.util.Iterator;
42 import java.util.List;
43 import java.util.RandomAccess;
44 import java.util.Spliterator;
45 import java.util.function.Consumer;
46 import java.util.function.UnaryOperator;
47 import java.util.stream.Collector;
48 import javax.annotation.CheckForNull;
49 import org.checkerframework.checker.nullness.qual.Nullable;
50
51 /**
52 * A {@link List} whose contents will never change, with many other important properties detailed at
53 * {@link ImmutableCollection}.
54 *
55 * <p>See the Guava User Guide article on <a href=
56 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>.
57 *
58 * @see ImmutableMap
59 * @see ImmutableSet
60 * @author Kevin Bourrillion
61 * @since 2.0
62 */
63 @GwtCompatible(serializable = true, emulated = true)
64 @SuppressWarnings("serial") // we're overriding default serialization
65 @ElementTypesAreNonnullByDefault
66 public abstract class ImmutableList<E> extends ImmutableCollection<E>
67 implements List<E>, RandomAccess {
68
69 /**
70 * Returns a {@code Collector} that accumulates the input elements into a new {@code
71 * ImmutableList}, in encounter order.
72 *
73 * @since 21.0
74 */
75 public static <E> Collector<E, ?, ImmutableList<E>> toImmutableList() {
76 return CollectCollectors.toImmutableList();
77 }
78
79 /**
80 * Returns the empty immutable list. This list behaves and performs comparably to {@link
81 * Collections#emptyList}, and is preferable mainly for consistency and maintainability of your
82 * code.
83 *
84 * <p><b>Performance note:</b> the instance returned is a singleton.
85 */
86 // Casting to any type is safe because the list will never hold any elements.
87 @SuppressWarnings("unchecked")
88 public static <E> ImmutableList<E> of() {
89 return (ImmutableList<E>) EMPTY;
90 }
91
92 /**
93 * Returns an immutable list containing a single element. This list behaves and performs
94 * comparably to {@link Collections#singletonList}, but will not accept a null element. It is
95 * preferable mainly for consistency and maintainability of your code.
96 *
97 * @throws NullPointerException if {@code element} is null
98 */
99 public static <E> ImmutableList<E> of(E element) {
100 return new SingletonImmutableList<E>(element);
101 }
102
103 /**
104 * Returns an immutable list containing the given elements, in order.
105 *
106 * @throws NullPointerException if any element is null
107 */
108 public static <E> ImmutableList<E> of(E e1, E e2) {
109 return construct(e1, e2);
110 }
111
112 /**
113 * Returns an immutable list containing the given elements, in order.
114 *
115 * @throws NullPointerException if any element is null
116 */
117 public static <E> ImmutableList<E> of(E e1, E e2, E e3) {
118 return construct(e1, e2, e3);
119 }
120
121 /**
122 * Returns an immutable list containing the given elements, in order.
123 *
124 * @throws NullPointerException if any element is null
125 */
126 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4) {
127 return construct(e1, e2, e3, e4);
128 }
129
130 /**
131 * Returns an immutable list containing the given elements, in order.
132 *
133 * @throws NullPointerException if any element is null
134 */
135 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5) {
136 return construct(e1, e2, e3, e4, e5);
137 }
138
139 /**
140 * Returns an immutable list containing the given elements, in order.
141 *
142 * @throws NullPointerException if any element is null
143 */
144 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5, E e6) {
145 return construct(e1, e2, e3, e4, e5, e6);
146 }
147
148 /**
149 * Returns an immutable list containing the given elements, in order.
150 *
151 * @throws NullPointerException if any element is null
152 */
153 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
154 return construct(e1, e2, e3, e4, e5, e6, e7);
155 }
156
157 /**
158 * Returns an immutable list containing the given elements, in order.
159 *
160 * @throws NullPointerException if any element is null
161 */
162 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
163 return construct(e1, e2, e3, e4, e5, e6, e7, e8);
164 }
165
166 /**
167 * Returns an immutable list containing the given elements, in order.
168 *
169 * @throws NullPointerException if any element is null
170 */
171 public static <E> ImmutableList<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
172 return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9);
173 }
174
175 /**
176 * Returns an immutable list containing the given elements, in order.
177 *
178 * @throws NullPointerException if any element is null
179 */
180 public static <E> ImmutableList<E> of(
181 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
182 return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10);
183 }
184
185 /**
186 * Returns an immutable list containing the given elements, in order.
187 *
188 * @throws NullPointerException if any element is null
189 */
190 public static <E> ImmutableList<E> of(
191 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10, E e11) {
192 return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11);
193 }
194
195 // These go up to eleven. After that, you just get the varargs form, and
196 // whatever warnings might come along with it. :(
197
198 /**
199 * Returns an immutable list containing the given elements, in order.
200 *
201 * <p>The array {@code others} must not be longer than {@code Integer.MAX_VALUE - 12}.
202 *
203 * @throws NullPointerException if any element is null
204 * @since 3.0 (source-compatible since 2.0)
205 */
206 @SafeVarargs // For Eclipse. For internal javac we have disabled this pointless type of warning.
207 public static <E> ImmutableList<E> of(
208 E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10, E e11, E e12, E... others) {
209 checkArgument(
210 others.length <= Integer.MAX_VALUE - 12, "the total number of elements must fit in an int");
211 Object[] array = new Object[12 + others.length];
212 array[0] = e1;
213 array[1] = e2;
214 array[2] = e3;
215 array[3] = e4;
216 array[4] = e5;
217 array[5] = e6;
218 array[6] = e7;
219 array[7] = e8;
220 array[8] = e9;
221 array[9] = e10;
222 array[10] = e11;
223 array[11] = e12;
224 System.arraycopy(others, 0, array, 12, others.length);
225 return construct(array);
226 }
227
228 /**
229 * Returns an immutable list containing the given elements, in order. If {@code elements} is a
230 * {@link Collection}, this method behaves exactly as {@link #copyOf(Collection)}; otherwise, it
231 * behaves exactly as {@code copyOf(elements.iterator()}.
232 *
233 * @throws NullPointerException if {@code elements} contains a null element
234 */
235 public static <E> ImmutableList<E> copyOf(Iterable<? extends E> elements) {
236 checkNotNull(elements); // TODO(kevinb): is this here only for GWT?
237 return (elements instanceof Collection)
238 ? copyOf((Collection<? extends E>) elements)
239 : copyOf(elements.iterator());
240 }
241
242 /**
243 * Returns an immutable list containing the given elements, in order.
244 *
245 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
246 * safe to do so. The exact circumstances under which a copy will or will not be performed are
247 * undocumented and subject to change.
248 *
249 * <p>Note that if {@code list} is a {@code List<String>}, then {@code ImmutableList.copyOf(list)}
250 * returns an {@code ImmutableList<String>} containing each of the strings in {@code list}, while
251 * ImmutableList.of(list)} returns an {@code ImmutableList<List<String>>} containing one element
252 * (the given list itself).
253 *
254 * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent
255 * collection that is currently being modified by another thread.
256 *
257 * @throws NullPointerException if {@code elements} contains a null element
258 */
259 public static <E> ImmutableList<E> copyOf(Collection<? extends E> elements) {
260 if (elements instanceof ImmutableCollection) {
261 @SuppressWarnings("unchecked") // all supported methods are covariant
262 ImmutableList<E> list = ((ImmutableCollection<E>) elements).asList();
263 return list.isPartialView() ? ImmutableList.<E>asImmutableList(list.toArray()) : list;
264 }
265 return construct(elements.toArray());
266 }
267
268 /**
269 * Returns an immutable list containing the given elements, in order.
270 *
271 * @throws NullPointerException if {@code elements} contains a null element
272 */
273 public static <E> ImmutableList<E> copyOf(Iterator<? extends E> elements) {
274 // We special-case for 0 or 1 elements, but going further is madness.
275 if (!elements.hasNext()) {
276 return of();
277 }
278 E first = elements.next();
279 if (!elements.hasNext()) {
280 return of(first);
281 } else {
282 return new ImmutableList.Builder<E>().add(first).addAll(elements).build();
283 }
284 }
285
286 /**
287 * Returns an immutable list containing the given elements, in order.
288 *
289 * @throws NullPointerException if {@code elements} contains a null element
290 * @since 3.0
291 */
292 public static <E> ImmutableList<E> copyOf(E[] elements) {
293 switch (elements.length) {
294 case 0:
295 return of();
296 case 1:
297 return of(elements[0]);
298 default:
299 return construct(elements.clone());
300 }
301 }
302
303 /**
304 * Returns an immutable list containing the given elements, sorted according to their natural
305 * order. The sorting algorithm used is stable, so elements that compare as equal will stay in the
306 * order in which they appear in the input.
307 *
308 * <p>If your data has no duplicates, or you wish to deduplicate elements, use {@code
309 * ImmutableSortedSet.copyOf(elements)}; if you want a {@code List} you can use its {@code
310 * asList()} view.
311 *
312 * <p><b>Java 8 users:</b> If you want to convert a {@link java.util.stream.Stream} to a sorted
313 * {@code ImmutableList}, use {@code stream.sorted().collect(toImmutableList())}.
314 *
315 * @throws NullPointerException if any element in the input is null
316 * @since 21.0
317 */
318 public static <E extends Comparable<? super E>> ImmutableList<E> sortedCopyOf(
319 Iterable<? extends E> elements) {
320 Comparable<?>[] array = Iterables.toArray(elements, new Comparable<?>[0]);
321 checkElementsNotNull((Object[]) array);
322 Arrays.sort(array);
323 return asImmutableList(array);
324 }
325
326 /**
327 * Returns an immutable list containing the given elements, in sorted order relative to the
328 * specified comparator. The sorting algorithm used is stable, so elements that compare as equal
329 * will stay in the order in which they appear in the input.
330 *
331 * <p>If your data has no duplicates, or you wish to deduplicate elements, use {@code
332 * ImmutableSortedSet.copyOf(comparator, elements)}; if you want a {@code List} you can use its
333 * {@code asList()} view.
334 *
335 * <p><b>Java 8 users:</b> If you want to convert a {@link java.util.stream.Stream} to a sorted
336 * {@code ImmutableList}, use {@code stream.sorted(comparator).collect(toImmutableList())}.
337 *
338 * @throws NullPointerException if any element in the input is null
339 * @since 21.0
340 */
341 public static <E> ImmutableList<E> sortedCopyOf(
342 Comparator<? super E> comparator, Iterable<? extends E> elements) {
343 checkNotNull(comparator);
344 @SuppressWarnings("unchecked") // all supported methods are covariant
345 E[] array = (E[]) Iterables.toArray(elements);
346 checkElementsNotNull(array);
347 Arrays.sort(array, comparator);
348 return asImmutableList(array);
349 }
350
351 /** Views the array as an immutable list. Checks for nulls; does not copy. */
352 private static <E> ImmutableList<E> construct(Object... elements) {
353 return asImmutableList(checkElementsNotNull(elements));
354 }
355
356 /**
357 * Views the array as an immutable list. Does not check for nulls; does not copy.
358 *
359 * <p>The array must be internally created.
360 */
361 static <E> ImmutableList<E> asImmutableList(Object[] elements) {
362 return asImmutableList(elements, elements.length);
363 }
364
365 /**
366 * Views the array as an immutable list. Copies if the specified range does not cover the complete
367 * array. Does not check for nulls.
368 */
369 static <E> ImmutableList<E> asImmutableList(@Nullable Object[] elements, int length) {
370 switch (length) {
371 case 0:
372 return of();
373 case 1:
374 /*
375 * requireNonNull is safe because the callers promise to put non-null objects in the first
376 * `length` array elements.
377 */
378 @SuppressWarnings("unchecked") // our callers put only E instances into the array
379 E onlyElement = (E) requireNonNull(elements[0]);
380 return of(onlyElement);
381 default:
382 /*
383 * The suppression is safe because the callers promise to put non-null objects in the first
384 * `length` array elements.
385 */
386 @SuppressWarnings("nullness")
387 Object[] elementsWithoutTrailingNulls =
388 length < elements.length ? Arrays.copyOf(elements, length) : elements;
389 return new RegularImmutableList<E>(elementsWithoutTrailingNulls);
390 }
391 }
392
393 ImmutableList() {}
394
395 // This declaration is needed to make List.iterator() and
396 // ImmutableCollection.iterator() consistent.
397 @Override
398 public UnmodifiableIterator<E> iterator() {
399 return listIterator();
400 }
401
402 @Override
403 public UnmodifiableListIterator<E> listIterator() {
404 return listIterator(0);
405 }
406
407 @Override
408 public UnmodifiableListIterator<E> listIterator(int index) {
409 return new AbstractIndexedListIterator<E>(size(), index) {
410 @Override
411 protected E get(int index) {
412 return ImmutableList.this.get(index);
413 }
414 };
415 }
416
417 @Override
418 public void forEach(Consumer<? super E> consumer) {
419 checkNotNull(consumer);
420 int n = size();
421 for (int i = 0; i < n; i++) {
422 consumer.accept(get(i));
423 }
424 }
425
426 @Override
427 public int indexOf(@CheckForNull Object object) {
428 return (object == null) ? -1 : Lists.indexOfImpl(this, object);
429 }
430
431 @Override
432 public int lastIndexOf(@CheckForNull Object object) {
433 return (object == null) ? -1 : Lists.lastIndexOfImpl(this, object);
434 }
435
436 @Override
437 public boolean contains(@CheckForNull Object object) {
438 return indexOf(object) >= 0;
439 }
440
441 // constrain the return type to ImmutableList<E>
442
443 /**
444 * Returns an immutable list of the elements between the specified {@code fromIndex}, inclusive,
445 * and {@code toIndex}, exclusive. (If {@code fromIndex} and {@code toIndex} are equal, the empty
446 * immutable list is returned.)
447 */
448 @Override
449 public ImmutableList<E> subList(int fromIndex, int toIndex) {
450 checkPositionIndexes(fromIndex, toIndex, size());
451 int length = toIndex - fromIndex;
452 if (length == size()) {
453 return this;
454 } else if (length == 0) {
455 return of();
456 } else if (length == 1) {
457 return of(get(fromIndex));
458 } else {
459 return subListUnchecked(fromIndex, toIndex);
460 }
461 }
462
463 /**
464 * Called by the default implementation of {@link #subList} when {@code toIndex - fromIndex > 1},
465 * after index validation has already been performed.
466 */
467 ImmutableList<E> subListUnchecked(int fromIndex, int toIndex) {
468 return new SubList(fromIndex, toIndex - fromIndex);
469 }
470
471 class SubList extends ImmutableList<E> {
472 final transient int offset;
473 final transient int length;
474
475 SubList(int offset, int length) {
476 this.offset = offset;
477 this.length = length;
478 }
479
480 @Override
481 public int size() {
482 return length;
483 }
484
485 @Override
486 public E get(int index) {
487 checkElementIndex(index, length);
488 return ImmutableList.this.get(index + offset);
489 }
490
491 @Override
492 public ImmutableList<E> subList(int fromIndex, int toIndex) {
493 checkPositionIndexes(fromIndex, toIndex, length);
494 return ImmutableList.this.subList(fromIndex + offset, toIndex + offset);
495 }
496
497 @Override
498 boolean isPartialView() {
499 return true;
500 }
501 }
502
503 /**
504 * Guaranteed to throw an exception and leave the list unmodified.
505 *
506 * @throws UnsupportedOperationException always
507 * @deprecated Unsupported operation.
508 */
509 @CanIgnoreReturnValue
510 @Deprecated
511 @Override
512 @DoNotCall("Always throws UnsupportedOperationException")
513 public final boolean addAll(int index, Collection<? extends E> newElements) {
514 throw new UnsupportedOperationException();
515 }
516
517 /**
518 * Guaranteed to throw an exception and leave the list unmodified.
519 *
520 * @throws UnsupportedOperationException always
521 * @deprecated Unsupported operation.
522 */
523 @CanIgnoreReturnValue
524 @Deprecated
525 @Override
526 @DoNotCall("Always throws UnsupportedOperationException")
527 public final E set(int index, E element) {
528 throw new UnsupportedOperationException();
529 }
530
531 /**
532 * Guaranteed to throw an exception and leave the list unmodified.
533 *
534 * @throws UnsupportedOperationException always
535 * @deprecated Unsupported operation.
536 */
537 @Deprecated
538 @Override
539 @DoNotCall("Always throws UnsupportedOperationException")
540 public final void add(int index, E element) {
541 throw new UnsupportedOperationException();
542 }
543
544 /**
545 * Guaranteed to throw an exception and leave the list unmodified.
546 *
547 * @throws UnsupportedOperationException always
548 * @deprecated Unsupported operation.
549 */
550 @CanIgnoreReturnValue
551 @Deprecated
552 @Override
553 @DoNotCall("Always throws UnsupportedOperationException")
554 public final E remove(int index) {
555 throw new UnsupportedOperationException();
556 }
557
558 /**
559 * Guaranteed to throw an exception and leave the list unmodified.
560 *
561 * @throws UnsupportedOperationException always
562 * @deprecated Unsupported operation.
563 */
564 @Deprecated
565 @Override
566 @DoNotCall("Always throws UnsupportedOperationException")
567 public final void replaceAll(UnaryOperator<E> operator) {
568 throw new UnsupportedOperationException();
569 }
570
571 /**
572 * Guaranteed to throw an exception and leave the list unmodified.
573 *
574 * @throws UnsupportedOperationException always
575 * @deprecated Unsupported operation.
576 */
577 @Deprecated
578 @Override
579 @DoNotCall("Always throws UnsupportedOperationException")
580 public final void sort(Comparator<? super E> c) {
581 throw new UnsupportedOperationException();
582 }
583
584 /**
585 * Returns this list instance.
586 *
587 * @since 2.0
588 * @deprecated There is no reason to use this; it always returns {@code this}.
589 */
590 @InlineMe(replacement = "this")
591 @Deprecated
592 @Override
593 public final ImmutableList<E> asList() {
594 return this;
595 }
596
597 @Override
598 public Spliterator<E> spliterator() {
599 return CollectSpliterators.indexed(size(), SPLITERATOR_CHARACTERISTICS, this::get);
600 }
601
602 @Override
603 int copyIntoArray(@Nullable Object[] dst, int offset) {
604 // this loop is faster for RandomAccess instances, which ImmutableLists are
605 int size = size();
606 for (int i = 0; i < size; i++) {
607 dst[offset + i] = get(i);
608 }
609 return offset + size;
610 }
611
612 /**
613 * Returns a view of this immutable list in reverse order. For example, {@code ImmutableList.of(1,
614 * 2, 3).reverse()} is equivalent to {@code ImmutableList.of(3, 2, 1)}.
615 *
616 * @return a view of this immutable list in reverse order
617 * @since 7.0
618 */
619 public ImmutableList<E> reverse() {
620 return (size() <= 1) ? this : new ReverseImmutableList<E>(this);
621 }
622
623 private static class ReverseImmutableList<E> extends ImmutableList<E> {
624 private final transient ImmutableList<E> forwardList;
625
626 ReverseImmutableList(ImmutableList<E> backingList) {
627 this.forwardList = backingList;
628 }
629
630 private int reverseIndex(int index) {
631 return (size() - 1) - index;
632 }
633
634 private int reversePosition(int index) {
635 return size() - index;
636 }
637
638 @Override
639 public ImmutableList<E> reverse() {
640 return forwardList;
641 }
642
643 @Override
644 public boolean contains(@CheckForNull Object object) {
645 return forwardList.contains(object);
646 }
647
648 @Override
649 public int indexOf(@CheckForNull Object object) {
650 int index = forwardList.lastIndexOf(object);
651 return (index >= 0) ? reverseIndex(index) : -1;
652 }
653
654 @Override
655 public int lastIndexOf(@CheckForNull Object object) {
656 int index = forwardList.indexOf(object);
657 return (index >= 0) ? reverseIndex(index) : -1;
658 }
659
660 @Override
661 public ImmutableList<E> subList(int fromIndex, int toIndex) {
662 checkPositionIndexes(fromIndex, toIndex, size());
663 return forwardList.subList(reversePosition(toIndex), reversePosition(fromIndex)).reverse();
664 }
665
666 @Override
667 public E get(int index) {
668 checkElementIndex(index, size());
669 return forwardList.get(reverseIndex(index));
670 }
671
672 @Override
673 public int size() {
674 return forwardList.size();
675 }
676
677 @Override
678 boolean isPartialView() {
679 return forwardList.isPartialView();
680 }
681 }
682
683 @Override
684 public boolean equals(@CheckForNull Object obj) {
685 return Lists.equalsImpl(this, obj);
686 }
687
688 @Override
689 public int hashCode() {
690 int hashCode = 1;
691 int n = size();
692 for (int i = 0; i < n; i++) {
693 hashCode = 31 * hashCode + get(i).hashCode();
694
695 hashCode = ~~hashCode;
696 // needed to deal with GWT integer overflow
697 }
698 return hashCode;
699 }
700
701 /*
702 * Serializes ImmutableLists as their logical contents. This ensures that
703 * implementation types do not leak into the serialized representation.
704 */
705 static class SerializedForm implements Serializable {
706 final Object[] elements;
707
708 SerializedForm(Object[] elements) {
709 this.elements = elements;
710 }
711
712 Object readResolve() {
713 return copyOf(elements);
714 }
715
716 private static final long serialVersionUID = 0;
717 }
718
719 private void readObject(ObjectInputStream stream) throws InvalidObjectException {
720 throw new InvalidObjectException("Use SerializedForm");
721 }
722
723 @Override
724 Object writeReplace() {
725 return new SerializedForm(toArray());
726 }
727
728 /**
729 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
730 * Builder} constructor.
731 */
732 public static <E> Builder<E> builder() {
733 return new Builder<E>();
734 }
735
736 /**
737 * Returns a new builder, expecting the specified number of elements to be added.
738 *
739 * <p>If {@code expectedSize} is exactly the number of elements added to the builder before {@link
740 * Builder#build} is called, the builder is likely to perform better than an unsized {@link
741 * #builder()} would have.
742 *
743 * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
744 * but not exactly, the number of elements added to the builder.
745 *
746 * @since 23.1
747 */
748 @Beta
749 public static <E> Builder<E> builderWithExpectedSize(int expectedSize) {
750 checkNonnegative(expectedSize, "expectedSize");
751 return new ImmutableList.Builder<E>(expectedSize);
752 }
753
754 /**
755 * A builder for creating immutable list instances, especially {@code public static final} lists
756 * ("constant lists"). Example:
757 *
758 * <pre>{@code
759 * public static final ImmutableList<Color> GOOGLE_COLORS
760 * = new ImmutableList.Builder<Color>()
761 * .addAll(WEBSAFE_COLORS)
762 * .add(new Color(0, 191, 255))
763 * .build();
764 * }</pre>
765 *
766 * <p>Elements appear in the resulting list in the same order they were added to the builder.
767 *
768 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
769 * multiple lists in series. Each new list contains all the elements of the ones created before
770 * it.
771 *
772 * @since 2.0
773 */
774 public static final class Builder<E> extends ImmutableCollection.Builder<E> {
775 // The first `size` elements are non-null.
776 @VisibleForTesting @Nullable Object[] contents;
777 private int size;
778 private boolean forceCopy;
779
780 /**
781 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
782 * ImmutableList#builder}.
783 */
784 public Builder() {
785 this(DEFAULT_INITIAL_CAPACITY);
786 }
787
788 Builder(int capacity) {
789 this.contents = new @Nullable Object[capacity];
790 this.size = 0;
791 }
792
793 private void getReadyToExpandTo(int minCapacity) {
794 if (contents.length < minCapacity) {
795 this.contents = Arrays.copyOf(contents, expandedCapacity(contents.length, minCapacity));
796 forceCopy = false;
797 } else if (forceCopy) {
798 contents = Arrays.copyOf(contents, contents.length);
799 forceCopy = false;
800 }
801 }
802
803 /**
804 * Adds {@code element} to the {@code ImmutableList}.
805 *
806 * @param element the element to add
807 * @return this {@code Builder} object
808 * @throws NullPointerException if {@code element} is null
809 */
810 @CanIgnoreReturnValue
811 @Override
812 public Builder<E> add(E element) {
813 checkNotNull(element);
814 getReadyToExpandTo(size + 1);
815 contents[size++] = element;
816 return this;
817 }
818
819 /**
820 * Adds each element of {@code elements} to the {@code ImmutableList}.
821 *
822 * @param elements the {@code Iterable} to add to the {@code ImmutableList}
823 * @return this {@code Builder} object
824 * @throws NullPointerException if {@code elements} is null or contains a null element
825 */
826 @CanIgnoreReturnValue
827 @Override
828 public Builder<E> add(E... elements) {
829 checkElementsNotNull(elements);
830 add(elements, elements.length);
831 return this;
832 }
833
834 private void add(@Nullable Object[] elements, int n) {
835 getReadyToExpandTo(size + n);
836 /*
837 * The following call is not statically checked, since arraycopy accepts plain Object for its
838 * parameters. If it were statically checked, the checker would still be OK with it, since
839 * we're copying into a `contents` array whose type allows it to contain nulls. Still, it's
840 * worth noting that we promise not to put nulls into the array in the first `size` elements.
841 * We uphold that promise here because our callers promise that `elements` will not contain
842 * nulls in its first `n` elements.
843 */
844 System.arraycopy(elements, 0, contents, size, n);
845 size += n;
846 }
847
848 /**
849 * Adds each element of {@code elements} to the {@code ImmutableList}.
850 *
851 * @param elements the {@code Iterable} to add to the {@code ImmutableList}
852 * @return this {@code Builder} object
853 * @throws NullPointerException if {@code elements} is null or contains a null element
854 */
855 @CanIgnoreReturnValue
856 @Override
857 public Builder<E> addAll(Iterable<? extends E> elements) {
858 checkNotNull(elements);
859 if (elements instanceof Collection) {
860 Collection<?> collection = (Collection<?>) elements;
861 getReadyToExpandTo(size + collection.size());
862 if (collection instanceof ImmutableCollection) {
863 ImmutableCollection<?> immutableCollection = (ImmutableCollection<?>) collection;
864 size = immutableCollection.copyIntoArray(contents, size);
865 return this;
866 }
867 }
868 super.addAll(elements);
869 return this;
870 }
871
872 /**
873 * Adds each element of {@code elements} to the {@code ImmutableList}.
874 *
875 * @param elements the {@code Iterator} to add to the {@code ImmutableList}
876 * @return this {@code Builder} object
877 * @throws NullPointerException if {@code elements} is null or contains a null element
878 */
879 @CanIgnoreReturnValue
880 @Override
881 public Builder<E> addAll(Iterator<? extends E> elements) {
882 super.addAll(elements);
883 return this;
884 }
885
886 @CanIgnoreReturnValue
887 Builder<E> combine(Builder<E> builder) {
888 checkNotNull(builder);
889 add(builder.contents, builder.size);
890 return this;
891 }
892
893 /**
894 * Returns a newly-created {@code ImmutableList} based on the contents of the {@code Builder}.
895 */
896 @Override
897 public ImmutableList<E> build() {
898 forceCopy = true;
899 return asImmutableList(contents, size);
900 }
901 }
902 }