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