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}