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