View Javadoc
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.Immutable;
25  import java.io.Serializable;
26  import java.util.AbstractList;
27  import java.util.Arrays;
28  import java.util.Collection;
29  import java.util.List;
30  import java.util.RandomAccess;
31  import java.util.Spliterator;
32  import java.util.Spliterators;
33  import java.util.function.IntConsumer;
34  import java.util.stream.IntStream;
35  import javax.annotation.CheckReturnValue;
36  import javax.annotation.Nullable;
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>, second
45   *       edition, Item 15).
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  public final class ImmutableIntArray implements Serializable {
92    private static final ImmutableIntArray EMPTY = new ImmutableIntArray(new int[0]);
93  
94    /** Returns the empty array. */
95    public static ImmutableIntArray of() {
96      return EMPTY;
97    }
98  
99    /** 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   /**
539    * Returns {@code true} if {@code object} is an {@code ImmutableIntArray} containing the same
540    * values as this one, in the same order.
541    */
542   @Override
543   public boolean equals(@Nullable Object object) {
544     if (object == this) {
545       return true;
546     }
547     if (!(object instanceof ImmutableIntArray)) {
548       return false;
549     }
550     ImmutableIntArray that = (ImmutableIntArray) object;
551     if (this.length() != that.length()) {
552       return false;
553     }
554     for (int i = 0; i < length(); i++) {
555       if (this.get(i) != that.get(i)) {
556         return false;
557       }
558     }
559     return true;
560   }
561 
562   /** Returns an unspecified hash code for the contents of this immutable array. */
563   @Override
564   public int hashCode() {
565     int hash = 1;
566     for (int i = start; i < end; i++) {
567       hash *= 31;
568       hash += Ints.hashCode(array[i]);
569     }
570     return hash;
571   }
572 
573   /**
574    * Returns a string representation of this array in the same form as {@link
575    * Arrays#toString(int[])}, for example {@code "[1, 2, 3]"}.
576    */
577   @Override
578   public String toString() {
579     if (isEmpty()) {
580       return "[]";
581     }
582     StringBuilder builder = new StringBuilder(length() * 5); // rough estimate is fine
583     builder.append('[').append(array[start]);
584 
585     for (int i = start + 1; i < end; i++) {
586       builder.append(", ").append(array[i]);
587     }
588     builder.append(']');
589     return builder.toString();
590   }
591 
592   /**
593    * Returns an immutable array containing the same values as {@code this} array. This is logically
594    * a no-op, and in some circumstances {@code this} itself is returned. However, if this instance
595    * is a {@link #subArray} view of a larger array, this method will copy only the appropriate range
596    * of values, resulting in an equivalent array with a smaller memory footprint.
597    */
598   public ImmutableIntArray trimmed() {
599     return isPartialView() ? new ImmutableIntArray(toArray()) : this;
600   }
601 
602   private boolean isPartialView() {
603     return start > 0 || end < array.length;
604   }
605 
606   Object writeReplace() {
607     return trimmed();
608   }
609 
610   Object readResolve() {
611     return isEmpty() ? EMPTY : this;
612   }
613 }