1 /*
2 * Copyright (C) 2017 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15 package com.google.common.primitives;
16
17 import static com.google.common.base.Preconditions.checkArgument;
18 import static com.google.common.base.Preconditions.checkNotNull;
19
20 import com.google.common.annotations.Beta;
21 import com.google.common.annotations.GwtCompatible;
22 import com.google.common.base.Preconditions;
23 import com.google.errorprone.annotations.CanIgnoreReturnValue;
24 import com.google.errorprone.annotations.CheckReturnValue;
25 import com.google.errorprone.annotations.Immutable;
26 import java.io.Serializable;
27 import java.util.AbstractList;
28 import java.util.Arrays;
29 import java.util.Collection;
30 import java.util.List;
31 import java.util.RandomAccess;
32 import java.util.Spliterator;
33 import java.util.Spliterators;
34 import java.util.function.IntConsumer;
35 import java.util.stream.IntStream;
36 import javax.annotation.CheckForNull;
37
38 /**
39 * An immutable array of {@code int} values, with an API resembling {@link List}.
40 *
41 * <p>Advantages compared to {@code int[]}:
42 *
43 * <ul>
44 * <li>All the many well-known advantages of immutability (read <i>Effective Java</i>, third
45 * edition, Item 17).
46 * <li>Has the value-based (not identity-based) {@link #equals}, {@link #hashCode}, and {@link
47 * #toString} behavior you expect.
48 * <li>Offers useful operations beyond just {@code get} and {@code length}, so you don't have to
49 * hunt through classes like {@link Arrays} and {@link Ints} for them.
50 * <li>Supports a copy-free {@link #subArray} view, so methods that accept this type don't need to
51 * add overloads that accept start and end indexes.
52 * <li>Can be streamed without "breaking the chain": {@code foo.getBarInts().stream()...}.
53 * <li>Access to all collection-based utilities via {@link #asList} (though at the cost of
54 * allocating garbage).
55 * </ul>
56 *
57 * <p>Disadvantages compared to {@code int[]}:
58 *
59 * <ul>
60 * <li>Memory footprint has a fixed overhead (about 24 bytes per instance).
61 * <li><i>Some</i> construction use cases force the data to be copied (though several construction
62 * APIs are offered that don't).
63 * <li>Can't be passed directly to methods that expect {@code int[]} (though the most common
64 * utilities do have replacements here).
65 * <li>Dependency on {@code com.google.common} / Guava.
66 * </ul>
67 *
68 * <p>Advantages compared to {@link com.google.common.collect.ImmutableList ImmutableList}{@code
69 * <Integer>}:
70 *
71 * <ul>
72 * <li>Improved memory compactness and locality.
73 * <li>Can be queried without allocating garbage.
74 * <li>Access to {@code IntStream} features (like {@link IntStream#sum}) using {@code stream()}
75 * instead of the awkward {@code stream().mapToInt(v -> v)}.
76 * </ul>
77 *
78 * <p>Disadvantages compared to {@code ImmutableList<Integer>}:
79 *
80 * <ul>
81 * <li>Can't be passed directly to methods that expect {@code Iterable}, {@code Collection}, or
82 * {@code List} (though the most common utilities do have replacements here, and there is a
83 * lazy {@link #asList} view).
84 * </ul>
85 *
86 * @since 22.0
87 */
88 @Beta
89 @GwtCompatible
90 @Immutable
91 @ElementTypesAreNonnullByDefault
92 public final class ImmutableIntArray implements Serializable {
93 private static final ImmutableIntArray EMPTY = new ImmutableIntArray(new int[0]);
94
95 /** Returns the empty array. */
96 public static ImmutableIntArray of() {
97 return EMPTY;
98 }
99
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 }