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