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 com.google.errorprone.annotations.CheckReturnValue;
025import com.google.errorprone.annotations.Immutable;
026import java.io.Serializable;
027import java.util.AbstractList;
028import java.util.Arrays;
029import java.util.Collection;
030import java.util.List;
031import java.util.RandomAccess;
032import java.util.Spliterator;
033import java.util.Spliterators;
034import java.util.function.IntConsumer;
035import java.util.stream.IntStream;
036import org.checkerframework.checker.nullness.compatqual.NullableDecl;
037
038/**
039 * An immutable array of {@code int} values, with an API resembling {@link List}.
040 *
041 * <p>Advantages compared to {@code int[]}:
042 *
043 * <ul>
044 *   <li>All the many well-known advantages of immutability (read <i>Effective Java</i>, second
045 *       edition, Item 15).
046 *   <li>Has the value-based (not identity-based) {@link #equals}, {@link #hashCode}, and {@link
047 *       #toString} behavior you expect.
048 *   <li>Offers useful operations beyond just {@code get} and {@code length}, so you don't have to
049 *       hunt through classes like {@link Arrays} and {@link Ints} for them.
050 *   <li>Supports a copy-free {@link #subArray} view, so methods that accept this type don't need to
051 *       add overloads that accept start and end indexes.
052 *   <li>Can be streamed without "breaking the chain": {@code foo.getBarInts().stream()...}.
053 *   <li>Access to all collection-based utilities via {@link #asList} (though at the cost of
054 *       allocating garbage).
055 * </ul>
056 *
057 * <p>Disadvantages compared to {@code int[]}:
058 *
059 * <ul>
060 *   <li>Memory footprint has a fixed overhead (about 24 bytes per instance).
061 *   <li><i>Some</i> construction use cases force the data to be copied (though several construction
062 *       APIs are offered that don't).
063 *   <li>Can't be passed directly to methods that expect {@code int[]} (though the most common
064 *       utilities do have replacements here).
065 *   <li>Dependency on {@code com.google.common} / Guava.
066 * </ul>
067 *
068 * <p>Advantages compared to {@link com.google.common.collect.ImmutableList ImmutableList}{@code
069 * <Integer>}:
070 *
071 * <ul>
072 *   <li>Improved memory compactness and locality.
073 *   <li>Can be queried without allocating garbage.
074 *   <li>Access to {@code IntStream} features (like {@link IntStream#sum}) using {@code stream()}
075 *       instead of the awkward {@code stream().mapToInt(v -> v)}.
076 * </ul>
077 *
078 * <p>Disadvantages compared to {@code ImmutableList<Integer>}:
079 *
080 * <ul>
081 *   <li>Can't be passed directly to methods that expect {@code Iterable}, {@code Collection}, or
082 *       {@code List} (though the most common utilities do have replacements here, and there is a
083 *       lazy {@link #asList} view).
084 * </ul>
085 *
086 * @since 22.0
087 */
088@Beta
089@GwtCompatible
090@Immutable
091public final class ImmutableIntArray implements Serializable {
092  private static final ImmutableIntArray EMPTY = new ImmutableIntArray(new int[0]);
093
094  /** Returns the empty array. */
095  public static ImmutableIntArray of() {
096    return EMPTY;
097  }
098
099  /** 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(@NullableDecl 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(@NullableDecl 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}