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