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