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