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