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