001/* 002 * Copyright (C) 2017 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.primitives; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.base.Preconditions.checkNotNull; 019 020import com.google.common.annotations.GwtCompatible; 021import com.google.common.base.Preconditions; 022import com.google.errorprone.annotations.CanIgnoreReturnValue; 023import com.google.errorprone.annotations.Immutable; 024import java.io.Serializable; 025import java.util.AbstractList; 026import java.util.Arrays; 027import java.util.Collection; 028import java.util.List; 029import java.util.RandomAccess; 030import java.util.Spliterator; 031import java.util.Spliterators; 032import java.util.function.IntConsumer; 033import java.util.stream.IntStream; 034import javax.annotation.CheckForNull; 035 036/** 037 * An immutable array of {@code int} values, with an API resembling {@link List}. 038 * 039 * <p>Advantages compared to {@code int[]}: 040 * 041 * <ul> 042 * <li>All the many well-known advantages of immutability (read <i>Effective Java</i>, third 043 * edition, Item 17). 044 * <li>Has the value-based (not identity-based) {@link #equals}, {@link #hashCode}, and {@link 045 * #toString} behavior you expect. 046 * <li>Offers useful operations beyond just {@code get} and {@code length}, so you don't have to 047 * hunt through classes like {@link Arrays} and {@link Ints} for them. 048 * <li>Supports a copy-free {@link #subArray} view, so methods that accept this type don't need to 049 * add overloads that accept start and end indexes. 050 * <li>Can be streamed without "breaking the chain": {@code foo.getBarInts().stream()...}. 051 * <li>Access to all collection-based utilities via {@link #asList} (though at the cost of 052 * allocating garbage). 053 * </ul> 054 * 055 * <p>Disadvantages compared to {@code int[]}: 056 * 057 * <ul> 058 * <li>Memory footprint has a fixed overhead (about 24 bytes per instance). 059 * <li><i>Some</i> construction use cases force the data to be copied (though several construction 060 * APIs are offered that don't). 061 * <li>Can't be passed directly to methods that expect {@code int[]} (though the most common 062 * utilities do have replacements here). 063 * <li>Dependency on {@code com.google.common} / Guava. 064 * </ul> 065 * 066 * <p>Advantages compared to {@link com.google.common.collect.ImmutableList ImmutableList}{@code 067 * <Integer>}: 068 * 069 * <ul> 070 * <li>Improved memory compactness and locality. 071 * <li>Can be queried without allocating garbage. 072 * <li>Access to {@code IntStream} features (like {@link IntStream#sum}) using {@code stream()} 073 * instead of the awkward {@code stream().mapToInt(v -> v)}. 074 * </ul> 075 * 076 * <p>Disadvantages compared to {@code ImmutableList<Integer>}: 077 * 078 * <ul> 079 * <li>Can't be passed directly to methods that expect {@code Iterable}, {@code Collection}, or 080 * {@code List} (though the most common utilities do have replacements here, and there is a 081 * lazy {@link #asList} view). 082 * </ul> 083 * 084 * @since 22.0 085 */ 086@GwtCompatible 087@Immutable 088@ElementTypesAreNonnullByDefault 089public final class ImmutableIntArray implements Serializable { 090 private static final ImmutableIntArray EMPTY = new ImmutableIntArray(new int[0]); 091 092 /** Returns the empty array. */ 093 public static ImmutableIntArray of() { 094 return EMPTY; 095 } 096 097 /** Returns an immutable array containing a single value. */ 098 public static ImmutableIntArray of(int e0) { 099 return new ImmutableIntArray(new int[] {e0}); 100 } 101 102 /** Returns an immutable array containing the given values, in order. */ 103 public static ImmutableIntArray of(int e0, int e1) { 104 return new ImmutableIntArray(new int[] {e0, e1}); 105 } 106 107 /** Returns an immutable array containing the given values, in order. */ 108 public static ImmutableIntArray of(int e0, int e1, int e2) { 109 return new ImmutableIntArray(new int[] {e0, e1, e2}); 110 } 111 112 /** Returns an immutable array containing the given values, in order. */ 113 public static ImmutableIntArray of(int e0, int e1, int e2, int e3) { 114 return new ImmutableIntArray(new int[] {e0, e1, e2, e3}); 115 } 116 117 /** Returns an immutable array containing the given values, in order. */ 118 public static ImmutableIntArray of(int e0, int e1, int e2, int e3, int e4) { 119 return new ImmutableIntArray(new int[] {e0, e1, e2, e3, e4}); 120 } 121 122 /** Returns an immutable array containing the given values, in order. */ 123 public static ImmutableIntArray of(int e0, int e1, int e2, int e3, int e4, int e5) { 124 return new ImmutableIntArray(new int[] {e0, e1, e2, e3, e4, e5}); 125 } 126 127 // TODO(kevinb): go up to 11? 128 129 /** 130 * Returns an immutable array containing the given values, in order. 131 * 132 * <p>The array {@code rest} must not be longer than {@code Integer.MAX_VALUE - 1}. 133 */ 134 // Use (first, rest) so that `of(someIntArray)` won't compile (they should use copyOf), which is 135 // okay since we have to copy the just-created array anyway. 136 public static ImmutableIntArray of(int first, int... rest) { 137 checkArgument( 138 rest.length <= Integer.MAX_VALUE - 1, "the total number of elements must fit in an int"); 139 int[] array = new int[rest.length + 1]; 140 array[0] = first; 141 System.arraycopy(rest, 0, array, 1, rest.length); 142 return new ImmutableIntArray(array); 143 } 144 145 /** Returns an immutable array containing the given values, in order. */ 146 public static ImmutableIntArray copyOf(int[] values) { 147 return values.length == 0 ? EMPTY : new ImmutableIntArray(Arrays.copyOf(values, values.length)); 148 } 149 150 /** Returns an immutable array containing the given values, in order. */ 151 public static ImmutableIntArray copyOf(Collection<Integer> values) { 152 return values.isEmpty() ? EMPTY : new ImmutableIntArray(Ints.toArray(values)); 153 } 154 155 /** 156 * Returns an immutable array containing the given values, in order. 157 * 158 * <p><b>Performance note:</b> this method delegates to {@link #copyOf(Collection)} if {@code 159 * values} is a {@link Collection}. Otherwise it creates a {@link #builder} and uses {@link 160 * Builder#addAll(Iterable)}, with all the performance implications associated with that. 161 */ 162 public static ImmutableIntArray copyOf(Iterable<Integer> values) { 163 if (values instanceof Collection) { 164 return copyOf((Collection<Integer>) values); 165 } 166 return builder().addAll(values).build(); 167 } 168 169 /** Returns an immutable array containing all the values from {@code stream}, in order. */ 170 public static ImmutableIntArray copyOf(IntStream stream) { 171 // Note this uses very different growth behavior from copyOf(Iterable) and the builder. 172 int[] array = stream.toArray(); 173 return (array.length == 0) ? EMPTY : new ImmutableIntArray(array); 174 } 175 176 /** 177 * Returns a new, empty builder for {@link ImmutableIntArray} instances, sized to hold up to 178 * {@code initialCapacity} values without resizing. The returned builder is not thread-safe. 179 * 180 * <p><b>Performance note:</b> When feasible, {@code initialCapacity} should be the exact number 181 * of values that will be added, if that knowledge is readily available. It is better to guess a 182 * value slightly too high than slightly too low. If the value is not exact, the {@link 183 * ImmutableIntArray} that is built will very likely occupy more memory than strictly necessary; 184 * to trim memory usage, build using {@code builder.build().trimmed()}. 185 */ 186 public static Builder builder(int initialCapacity) { 187 checkArgument(initialCapacity >= 0, "Invalid initialCapacity: %s", initialCapacity); 188 return new Builder(initialCapacity); 189 } 190 191 /** 192 * Returns a new, empty builder for {@link ImmutableIntArray} instances, with a default initial 193 * capacity. The returned builder is not thread-safe. 194 * 195 * <p><b>Performance note:</b> The {@link ImmutableIntArray} that is built will very likely occupy 196 * more memory than necessary; to trim memory usage, build using {@code 197 * builder.build().trimmed()}. 198 */ 199 public static Builder builder() { 200 return new Builder(10); 201 } 202 203 /** 204 * A builder for {@link ImmutableIntArray} instances; obtained using {@link 205 * ImmutableIntArray#builder}. 206 */ 207 public static final class Builder { 208 private int[] array; 209 private int count = 0; // <= array.length 210 211 Builder(int initialCapacity) { 212 array = new int[initialCapacity]; 213 } 214 215 /** 216 * Appends {@code value} to the end of the values the built {@link ImmutableIntArray} will 217 * contain. 218 */ 219 @CanIgnoreReturnValue 220 public Builder add(int value) { 221 ensureRoomFor(1); 222 array[count] = value; 223 count += 1; 224 return this; 225 } 226 227 /** 228 * Appends {@code values}, in order, to the end of the values the built {@link 229 * ImmutableIntArray} will contain. 230 */ 231 @CanIgnoreReturnValue 232 public Builder addAll(int[] values) { 233 ensureRoomFor(values.length); 234 System.arraycopy(values, 0, array, count, values.length); 235 count += values.length; 236 return this; 237 } 238 239 /** 240 * Appends {@code values}, in order, to the end of the values the built {@link 241 * ImmutableIntArray} will contain. 242 */ 243 @CanIgnoreReturnValue 244 public Builder addAll(Iterable<Integer> values) { 245 if (values instanceof Collection) { 246 return addAll((Collection<Integer>) values); 247 } 248 for (Integer value : values) { 249 add(value); 250 } 251 return this; 252 } 253 254 /** 255 * Appends {@code values}, in order, to the end of the values the built {@link 256 * ImmutableIntArray} will contain. 257 */ 258 @CanIgnoreReturnValue 259 public Builder addAll(Collection<Integer> values) { 260 ensureRoomFor(values.size()); 261 for (Integer value : values) { 262 array[count++] = value; 263 } 264 return this; 265 } 266 267 /** 268 * Appends all values from {@code stream}, in order, to the end of the values the built {@link 269 * ImmutableIntArray} will contain. 270 */ 271 @CanIgnoreReturnValue 272 public Builder addAll(IntStream stream) { 273 Spliterator.OfInt spliterator = stream.spliterator(); 274 long size = spliterator.getExactSizeIfKnown(); 275 if (size > 0) { // known *and* nonempty 276 ensureRoomFor(Ints.saturatedCast(size)); 277 } 278 spliterator.forEachRemaining((IntConsumer) this::add); 279 return this; 280 } 281 282 /** 283 * Appends {@code values}, in order, to the end of the values the built {@link 284 * ImmutableIntArray} will contain. 285 */ 286 @CanIgnoreReturnValue 287 public Builder addAll(ImmutableIntArray values) { 288 ensureRoomFor(values.length()); 289 System.arraycopy(values.array, values.start, array, count, values.length()); 290 count += values.length(); 291 return this; 292 } 293 294 private void ensureRoomFor(int numberToAdd) { 295 int newCount = count + numberToAdd; // TODO(kevinb): check overflow now? 296 if (newCount > array.length) { 297 array = Arrays.copyOf(array, expandedCapacity(array.length, newCount)); 298 } 299 } 300 301 // Unfortunately this is pasted from ImmutableCollection.Builder. 302 private static int expandedCapacity(int oldCapacity, int minCapacity) { 303 if (minCapacity < 0) { 304 throw new AssertionError("cannot store more than MAX_VALUE elements"); 305 } 306 // careful of overflow! 307 int newCapacity = oldCapacity + (oldCapacity >> 1) + 1; 308 if (newCapacity < minCapacity) { 309 newCapacity = Integer.highestOneBit(minCapacity - 1) << 1; 310 } 311 if (newCapacity < 0) { 312 newCapacity = Integer.MAX_VALUE; // guaranteed to be >= newCapacity 313 } 314 return newCapacity; 315 } 316 317 /** 318 * Returns a new immutable array. The builder can continue to be used after this call, to append 319 * more values and build again. 320 * 321 * <p><b>Performance note:</b> the returned array is backed by the same array as the builder, so 322 * no data is copied as part of this step, but this may occupy more memory than strictly 323 * necessary. To copy the data to a right-sized backing array, use {@code .build().trimmed()}. 324 */ 325 public ImmutableIntArray build() { 326 return count == 0 ? EMPTY : new ImmutableIntArray(array, 0, count); 327 } 328 } 329 330 // Instance stuff here 331 332 // The array is never mutated after storing in this field and the construction strategies ensure 333 // it doesn't escape this class 334 @SuppressWarnings("Immutable") 335 private final int[] array; 336 337 /* 338 * TODO(kevinb): evaluate the trade-offs of going bimorphic to save these two fields from most 339 * instances. Note that the instances that would get smaller are the right set to care about 340 * optimizing, because the rest have the option of calling `trimmed`. 341 */ 342 343 private final transient int start; // it happens that we only serialize instances where this is 0 344 private final int end; // exclusive 345 346 private ImmutableIntArray(int[] array) { 347 this(array, 0, array.length); 348 } 349 350 private ImmutableIntArray(int[] array, int start, int end) { 351 this.array = array; 352 this.start = start; 353 this.end = end; 354 } 355 356 /** Returns the number of values in this array. */ 357 public int length() { 358 return end - start; 359 } 360 361 /** Returns {@code true} if there are no values in this array ({@link #length} is zero). */ 362 public boolean isEmpty() { 363 return end == start; 364 } 365 366 /** 367 * Returns the {@code int} value present at the given index. 368 * 369 * @throws IndexOutOfBoundsException if {@code index} is negative, or greater than or equal to 370 * {@link #length} 371 */ 372 public int get(int index) { 373 Preconditions.checkElementIndex(index, length()); 374 return array[start + index]; 375 } 376 377 /** 378 * Returns the smallest index for which {@link #get} returns {@code target}, or {@code -1} if no 379 * such index exists. Equivalent to {@code asList().indexOf(target)}. 380 */ 381 public int indexOf(int target) { 382 for (int i = start; i < end; i++) { 383 if (array[i] == target) { 384 return i - start; 385 } 386 } 387 return -1; 388 } 389 390 /** 391 * Returns the largest index for which {@link #get} returns {@code target}, or {@code -1} if no 392 * such index exists. Equivalent to {@code asList().lastIndexOf(target)}. 393 */ 394 public int lastIndexOf(int target) { 395 for (int i = end - 1; i >= start; i--) { 396 if (array[i] == target) { 397 return i - start; 398 } 399 } 400 return -1; 401 } 402 403 /** 404 * Returns {@code true} if {@code target} is present at any index in this array. Equivalent to 405 * {@code asList().contains(target)}. 406 */ 407 public boolean contains(int target) { 408 return indexOf(target) >= 0; 409 } 410 411 /** Invokes {@code consumer} for each value contained in this array, in order. */ 412 public void forEach(IntConsumer consumer) { 413 checkNotNull(consumer); 414 for (int i = start; i < end; i++) { 415 consumer.accept(array[i]); 416 } 417 } 418 419 /** Returns a stream over the values in this array, in order. */ 420 public IntStream stream() { 421 return Arrays.stream(array, start, end); 422 } 423 424 /** Returns a new, mutable copy of this array's values, as a primitive {@code int[]}. */ 425 public int[] toArray() { 426 return Arrays.copyOfRange(array, start, end); 427 } 428 429 /** 430 * Returns a new immutable array containing the values in the specified range. 431 * 432 * <p><b>Performance note:</b> The returned array has the same full memory footprint as this one 433 * does (no actual copying is performed). To reduce memory usage, use {@code subArray(start, 434 * end).trimmed()}. 435 */ 436 public ImmutableIntArray subArray(int startIndex, int endIndex) { 437 Preconditions.checkPositionIndexes(startIndex, endIndex, length()); 438 return startIndex == endIndex 439 ? EMPTY 440 : new ImmutableIntArray(array, start + startIndex, start + endIndex); 441 } 442 443 private Spliterator.OfInt spliterator() { 444 return Spliterators.spliterator(array, start, end, Spliterator.IMMUTABLE | Spliterator.ORDERED); 445 } 446 447 /** 448 * Returns an immutable <i>view</i> of this array's values as a {@code List}; note that {@code 449 * int} values are boxed into {@link Integer} instances on demand, which can be very expensive. 450 * The returned list should be used once and discarded. For any usages beyond that, pass the 451 * returned list to {@link com.google.common.collect.ImmutableList#copyOf(Collection) 452 * ImmutableList.copyOf} and use that list instead. 453 */ 454 public List<Integer> asList() { 455 /* 456 * Typically we cache this kind of thing, but much repeated use of this view is a performance 457 * anti-pattern anyway. If we cache, then everyone pays a price in memory footprint even if 458 * they never use this method. 459 */ 460 return new AsList(this); 461 } 462 463 static class AsList extends AbstractList<Integer> implements RandomAccess, Serializable { 464 private final ImmutableIntArray parent; 465 466 private AsList(ImmutableIntArray parent) { 467 this.parent = parent; 468 } 469 470 // inherit: isEmpty, containsAll, toArray x2, iterator, listIterator, stream, forEach, mutations 471 472 @Override 473 public int size() { 474 return parent.length(); 475 } 476 477 @Override 478 public Integer get(int index) { 479 return parent.get(index); 480 } 481 482 @Override 483 public boolean contains(@CheckForNull Object target) { 484 return indexOf(target) >= 0; 485 } 486 487 @Override 488 public int indexOf(@CheckForNull Object target) { 489 return target instanceof Integer ? parent.indexOf((Integer) target) : -1; 490 } 491 492 @Override 493 public int lastIndexOf(@CheckForNull Object target) { 494 return target instanceof Integer ? parent.lastIndexOf((Integer) target) : -1; 495 } 496 497 @Override 498 public List<Integer> subList(int fromIndex, int toIndex) { 499 return parent.subArray(fromIndex, toIndex).asList(); 500 } 501 502 // The default List spliterator is not efficiently splittable 503 @Override 504 public Spliterator<Integer> spliterator() { 505 return parent.spliterator(); 506 } 507 508 @Override 509 public boolean equals(@CheckForNull Object object) { 510 if (object instanceof AsList) { 511 AsList that = (AsList) object; 512 return this.parent.equals(that.parent); 513 } 514 // We could delegate to super now but it would still box too much 515 if (!(object instanceof List)) { 516 return false; 517 } 518 List<?> that = (List<?>) object; 519 if (this.size() != that.size()) { 520 return false; 521 } 522 int i = parent.start; 523 // Since `that` is very likely RandomAccess we could avoid allocating this iterator... 524 for (Object element : that) { 525 if (!(element instanceof Integer) || parent.array[i++] != (Integer) element) { 526 return false; 527 } 528 } 529 return true; 530 } 531 532 // Because we happen to use the same formula. If that changes, just don't override this. 533 @Override 534 public int hashCode() { 535 return parent.hashCode(); 536 } 537 538 @Override 539 public String toString() { 540 return parent.toString(); 541 } 542 } 543 544 /** 545 * Returns {@code true} if {@code object} is an {@code ImmutableIntArray} containing the same 546 * values as this one, in the same order. 547 */ 548 @Override 549 public boolean equals(@CheckForNull Object object) { 550 if (object == this) { 551 return true; 552 } 553 if (!(object instanceof ImmutableIntArray)) { 554 return false; 555 } 556 ImmutableIntArray that = (ImmutableIntArray) object; 557 if (this.length() != that.length()) { 558 return false; 559 } 560 for (int i = 0; i < length(); i++) { 561 if (this.get(i) != that.get(i)) { 562 return false; 563 } 564 } 565 return true; 566 } 567 568 /** Returns an unspecified hash code for the contents of this immutable array. */ 569 @Override 570 public int hashCode() { 571 int hash = 1; 572 for (int i = start; i < end; i++) { 573 hash *= 31; 574 hash += Ints.hashCode(array[i]); 575 } 576 return hash; 577 } 578 579 /** 580 * Returns a string representation of this array in the same form as {@link 581 * Arrays#toString(int[])}, for example {@code "[1, 2, 3]"}. 582 */ 583 @Override 584 public String toString() { 585 if (isEmpty()) { 586 return "[]"; 587 } 588 StringBuilder builder = new StringBuilder(length() * 5); // rough estimate is fine 589 builder.append('[').append(array[start]); 590 591 for (int i = start + 1; i < end; i++) { 592 builder.append(", ").append(array[i]); 593 } 594 builder.append(']'); 595 return builder.toString(); 596 } 597 598 /** 599 * Returns an immutable array containing the same values as {@code this} array. This is logically 600 * a no-op, and in some circumstances {@code this} itself is returned. However, if this instance 601 * is a {@link #subArray} view of a larger array, this method will copy only the appropriate range 602 * of values, resulting in an equivalent array with a smaller memory footprint. 603 */ 604 public ImmutableIntArray trimmed() { 605 return isPartialView() ? new ImmutableIntArray(toArray()) : this; 606 } 607 608 private boolean isPartialView() { 609 return start > 0 || end < array.length; 610 } 611 612 Object writeReplace() { 613 return trimmed(); 614 } 615 616 Object readResolve() { 617 return isEmpty() ? EMPTY : this; 618 } 619}