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