View Javadoc
1   /*
2    * Copyright (C) 2017 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5    * in compliance with the License. You may obtain a copy of the License at
6    *
7    * http://www.apache.org/licenses/LICENSE-2.0
8    *
9    * Unless required by applicable law or agreed to in writing, software distributed under the License
10   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11   * or implied. See the License for the specific language governing permissions and limitations under
12   * the License.
13   */
14  
15  package com.google.common.primitives;
16  
17  import static com.google.common.base.Preconditions.checkArgument;
18  import static com.google.common.base.Preconditions.checkNotNull;
19  
20  import com.google.common.annotations.Beta;
21  import com.google.common.annotations.GwtCompatible;
22  import com.google.common.base.Preconditions;
23  import com.google.errorprone.annotations.CanIgnoreReturnValue;
24  import com.google.errorprone.annotations.Immutable;
25  import java.io.Serializable;
26  import java.util.AbstractList;
27  import java.util.Arrays;
28  import java.util.Collection;
29  import java.util.List;
30  import java.util.RandomAccess;
31  import java.util.Spliterator;
32  import java.util.Spliterators;
33  import java.util.function.LongConsumer;
34  import java.util.stream.LongStream;
35  import javax.annotation.CheckReturnValue;
36  import javax.annotation.Nullable;
37  
38  /**
39   * An immutable array of {@code long} values, with an API resembling {@link List}.
40   *
41   * <p>Advantages compared to {@code long[]}:
42   *
43   * <ul>
44   *   <li>All the many well-known advantages of immutability (read <i>Effective Java</i>, second
45   *       edition, Item 15).
46   *   <li>Has the value-based (not identity-based) {@link #equals}, {@link #hashCode}, and {@link
47   *       #toString} behavior you expect.
48   *   <li>Offers useful operations beyond just {@code get} and {@code length}, so you don't have to
49   *       hunt through classes like {@link Arrays} and {@link Longs} for them.
50   *   <li>Supports a copy-free {@link #subArray} view, so methods that accept this type don't need to
51   *       add overloads that accept start and end indexes.
52   *   <li>Can be streamed without "breaking the chain": {@code foo.getBarLongs().stream()...}.
53   *   <li>Access to all collection-based utilities via {@link #asList} (though at the cost of
54   *       allocating garbage).
55   * </ul>
56   *
57   * <p>Disadvantages compared to {@code long[]}:
58   *
59   * <ul>
60   *   <li>Memory footprint has a fixed overhead (about 24 bytes per instance).
61   *   <li><i>Some</i> construction use cases force the data to be copied (though several construction
62   *       APIs are offered that don't).
63   *   <li>Can't be passed directly to methods that expect {@code long[]} (though the most common
64   *       utilities do have replacements here).
65   *   <li>Dependency on {@code com.google.common} / Guava.
66   * </ul>
67   *
68   * <p>Advantages compared to {@link com.google.common.collect.ImmutableList ImmutableList}{@code
69   * <Long>}:
70   *
71   * <ul>
72   *   <li>Improved memory compactness and locality.
73   *   <li>Can be queried without allocating garbage.
74   *   <li>Access to {@code LongStream} features (like {@link LongStream#sum}) using {@code stream()}
75   *       instead of the awkward {@code stream().mapToLong(v -> v)}.
76   * </ul>
77   *
78   * <p>Disadvantages compared to {@code ImmutableList<Long>}:
79   *
80   * <ul>
81   *   <li>Can't be passed directly to methods that expect {@code Iterable}, {@code Collection}, or
82   *       {@code List} (though the most common utilities do have replacements here, and there is a
83   *       lazy {@link #asList} view).
84   * </ul>
85   *
86   * @since 22.0
87   */
88  @Beta
89  @GwtCompatible
90  @Immutable
91  public final class ImmutableLongArray implements Serializable {
92    private static final ImmutableLongArray EMPTY = new ImmutableLongArray(new long[0]);
93  
94    /** Returns the empty array. */
95    public static ImmutableLongArray of() {
96      return EMPTY;
97    }
98  
99    /** 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(@Nullable 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(@Nullable 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 }