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