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