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