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