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.DoubleConsumer;
35 import java.util.stream.DoubleStream;
36 import javax.annotation.CheckForNull;
37
38 /**
39 * An immutable array of {@code double} values, with an API resembling {@link List}.
40 *
41 * <p>Advantages compared to {@code double[]}:
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 Doubles} 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.getBarDoubles().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 double[]}:
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 double[]} (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 * <Double>}:
70 *
71 * <ul>
72 * <li>Improved memory compactness and locality.
73 * <li>Can be queried without allocating garbage.
74 * <li>Access to {@code DoubleStream} features (like {@link DoubleStream#sum}) using {@code
75 * stream()} instead of the awkward {@code stream().mapToDouble(v -> v)}.
76 * </ul>
77 *
78 * <p>Disadvantages compared to {@code ImmutableList<Double>}:
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 ImmutableDoubleArray implements Serializable {
93 private static final ImmutableDoubleArray EMPTY = new ImmutableDoubleArray(new double[0]);
94
95 /** Returns the empty array. */
96 public static ImmutableDoubleArray of() {
97 return EMPTY;
98 }
99
100 /** Returns an immutable array containing a single value. */
101 public static ImmutableDoubleArray of(double e0) {
102 return new ImmutableDoubleArray(new double[] {e0});
103 }
104
105 /** Returns an immutable array containing the given values, in order. */
106 public static ImmutableDoubleArray of(double e0, double e1) {
107 return new ImmutableDoubleArray(new double[] {e0, e1});
108 }
109
110 /** Returns an immutable array containing the given values, in order. */
111 public static ImmutableDoubleArray of(double e0, double e1, double e2) {
112 return new ImmutableDoubleArray(new double[] {e0, e1, e2});
113 }
114
115 /** Returns an immutable array containing the given values, in order. */
116 public static ImmutableDoubleArray of(double e0, double e1, double e2, double e3) {
117 return new ImmutableDoubleArray(new double[] {e0, e1, e2, e3});
118 }
119
120 /** Returns an immutable array containing the given values, in order. */
121 public static ImmutableDoubleArray of(double e0, double e1, double e2, double e3, double e4) {
122 return new ImmutableDoubleArray(new double[] {e0, e1, e2, e3, e4});
123 }
124
125 /** Returns an immutable array containing the given values, in order. */
126 public static ImmutableDoubleArray of(
127 double e0, double e1, double e2, double e3, double e4, double e5) {
128 return new ImmutableDoubleArray(new double[] {e0, e1, e2, e3, e4, e5});
129 }
130
131 // TODO(kevinb): go up to 11?
132
133 /**
134 * Returns an immutable array containing the given values, in order.
135 *
136 * <p>The array {@code rest} must not be longer than {@code Integer.MAX_VALUE - 1}.
137 */
138 // Use (first, rest) so that `of(someDoubleArray)` won't compile (they should use copyOf), which
139 // is okay since we have to copy the just-created array anyway.
140 public static ImmutableDoubleArray of(double first, double... rest) {
141 checkArgument(
142 rest.length <= Integer.MAX_VALUE - 1, "the total number of elements must fit in an int");
143 double[] array = new double[rest.length + 1];
144 array[0] = first;
145 System.arraycopy(rest, 0, array, 1, rest.length);
146 return new ImmutableDoubleArray(array);
147 }
148
149 /** Returns an immutable array containing the given values, in order. */
150 public static ImmutableDoubleArray copyOf(double[] values) {
151 return values.length == 0
152 ? EMPTY
153 : new ImmutableDoubleArray(Arrays.copyOf(values, values.length));
154 }
155
156 /** Returns an immutable array containing the given values, in order. */
157 public static ImmutableDoubleArray copyOf(Collection<Double> values) {
158 return values.isEmpty() ? EMPTY : new ImmutableDoubleArray(Doubles.toArray(values));
159 }
160
161 /**
162 * Returns an immutable array containing the given values, in order.
163 *
164 * <p><b>Performance note:</b> this method delegates to {@link #copyOf(Collection)} if {@code
165 * values} is a {@link Collection}. Otherwise it creates a {@link #builder} and uses {@link
166 * Builder#addAll(Iterable)}, with all the performance implications associated with that.
167 */
168 public static ImmutableDoubleArray copyOf(Iterable<Double> values) {
169 if (values instanceof Collection) {
170 return copyOf((Collection<Double>) values);
171 }
172 return builder().addAll(values).build();
173 }
174
175 /** Returns an immutable array containing all the values from {@code stream}, in order. */
176 public static ImmutableDoubleArray copyOf(DoubleStream stream) {
177 // Note this uses very different growth behavior from copyOf(Iterable) and the builder.
178 double[] array = stream.toArray();
179 return (array.length == 0) ? EMPTY : new ImmutableDoubleArray(array);
180 }
181
182 /**
183 * Returns a new, empty builder for {@link ImmutableDoubleArray} instances, sized to hold up to
184 * {@code initialCapacity} values without resizing. The returned builder is not thread-safe.
185 *
186 * <p><b>Performance note:</b> When feasible, {@code initialCapacity} should be the exact number
187 * of values that will be added, if that knowledge is readily available. It is better to guess a
188 * value slightly too high than slightly too low. If the value is not exact, the {@link
189 * ImmutableDoubleArray} that is built will very likely occupy more memory than strictly
190 * necessary; to trim memory usage, build using {@code builder.build().trimmed()}.
191 */
192 public static Builder builder(int initialCapacity) {
193 checkArgument(initialCapacity >= 0, "Invalid initialCapacity: %s", initialCapacity);
194 return new Builder(initialCapacity);
195 }
196
197 /**
198 * Returns a new, empty builder for {@link ImmutableDoubleArray} instances, with a default initial
199 * capacity. The returned builder is not thread-safe.
200 *
201 * <p><b>Performance note:</b> The {@link ImmutableDoubleArray} that is built will very likely
202 * occupy more memory than necessary; to trim memory usage, build using {@code
203 * builder.build().trimmed()}.
204 */
205 public static Builder builder() {
206 return new Builder(10);
207 }
208
209 /**
210 * A builder for {@link ImmutableDoubleArray} instances; obtained using {@link
211 * ImmutableDoubleArray#builder}.
212 */
213 @CanIgnoreReturnValue
214 public static final class Builder {
215 private double[] array;
216 private int count = 0; // <= array.length
217
218 Builder(int initialCapacity) {
219 array = new double[initialCapacity];
220 }
221
222 /**
223 * Appends {@code value} to the end of the values the built {@link ImmutableDoubleArray} will
224 * contain.
225 */
226 public Builder add(double value) {
227 ensureRoomFor(1);
228 array[count] = value;
229 count += 1;
230 return this;
231 }
232
233 /**
234 * Appends {@code values}, in order, to the end of the values the built {@link
235 * ImmutableDoubleArray} will contain.
236 */
237 public Builder addAll(double[] values) {
238 ensureRoomFor(values.length);
239 System.arraycopy(values, 0, array, count, values.length);
240 count += values.length;
241 return this;
242 }
243
244 /**
245 * Appends {@code values}, in order, to the end of the values the built {@link
246 * ImmutableDoubleArray} will contain.
247 */
248 public Builder addAll(Iterable<Double> values) {
249 if (values instanceof Collection) {
250 return addAll((Collection<Double>) values);
251 }
252 for (Double 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 * ImmutableDoubleArray} will contain.
261 */
262 public Builder addAll(Collection<Double> values) {
263 ensureRoomFor(values.size());
264 for (Double value : values) {
265 array[count++] = value;
266 }
267 return this;
268 }
269
270 /**
271 * Appends all values from {@code stream}, in order, to the end of the values the built {@link
272 * ImmutableDoubleArray} will contain.
273 */
274 public Builder addAll(DoubleStream stream) {
275 Spliterator.OfDouble spliterator = stream.spliterator();
276 long size = spliterator.getExactSizeIfKnown();
277 if (size > 0) { // known *and* nonempty
278 ensureRoomFor(Ints.saturatedCast(size));
279 }
280 spliterator.forEachRemaining((DoubleConsumer) this::add);
281 return this;
282 }
283
284 /**
285 * Appends {@code values}, in order, to the end of the values the built {@link
286 * ImmutableDoubleArray} will contain.
287 */
288 public Builder addAll(ImmutableDoubleArray values) {
289 ensureRoomFor(values.length());
290 System.arraycopy(values.array, values.start, array, count, values.length());
291 count += values.length();
292 return this;
293 }
294
295 private void ensureRoomFor(int numberToAdd) {
296 int newCount = count + numberToAdd; // TODO(kevinb): check overflow now?
297 if (newCount > array.length) {
298 array = Arrays.copyOf(array, expandedCapacity(array.length, newCount));
299 }
300 }
301
302 // Unfortunately this is pasted from ImmutableCollection.Builder.
303 private static int expandedCapacity(int oldCapacity, int minCapacity) {
304 if (minCapacity < 0) {
305 throw new AssertionError("cannot store more than MAX_VALUE elements");
306 }
307 // careful of overflow!
308 int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
309 if (newCapacity < minCapacity) {
310 newCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
311 }
312 if (newCapacity < 0) {
313 newCapacity = Integer.MAX_VALUE; // guaranteed to be >= newCapacity
314 }
315 return newCapacity;
316 }
317
318 /**
319 * Returns a new immutable array. The builder can continue to be used after this call, to append
320 * more values and build again.
321 *
322 * <p><b>Performance note:</b> the returned array is backed by the same array as the builder, so
323 * no data is copied as part of this step, but this may occupy more memory than strictly
324 * necessary. To copy the data to a right-sized backing array, use {@code .build().trimmed()}.
325 */
326 @CheckReturnValue
327 public ImmutableDoubleArray build() {
328 return count == 0 ? EMPTY : new ImmutableDoubleArray(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 double[] 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 ImmutableDoubleArray(double[] array) {
349 this(array, 0, array.length);
350 }
351
352 private ImmutableDoubleArray(double[] 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 double} 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 double 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. Values are compared as if by {@link Double#equals}. Equivalent to {@code
382 * asList().indexOf(target)}.
383 */
384 public int indexOf(double target) {
385 for (int i = start; i < end; i++) {
386 if (areEqual(array[i], target)) {
387 return i - start;
388 }
389 }
390 return -1;
391 }
392
393 /**
394 * Returns the largest index for which {@link #get} returns {@code target}, or {@code -1} if no
395 * such index exists. Values are compared as if by {@link Double#equals}. Equivalent to {@code
396 * asList().lastIndexOf(target)}.
397 */
398 public int lastIndexOf(double target) {
399 for (int i = end - 1; i >= start; i--) {
400 if (areEqual(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. Values are
409 * compared as if by {@link Double#equals}. Equivalent to {@code asList().contains(target)}.
410 */
411 public boolean contains(double 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(DoubleConsumer 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 DoubleStream 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 double[]}. */
429 public double[] 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 ImmutableDoubleArray subArray(int startIndex, int endIndex) {
441 Preconditions.checkPositionIndexes(startIndex, endIndex, length());
442 return startIndex == endIndex
443 ? EMPTY
444 : new ImmutableDoubleArray(array, start + startIndex, start + endIndex);
445 }
446
447 private Spliterator.OfDouble 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 * double} values are boxed into {@link Double} instances on demand, which can be very expensive.
454 * The returned list should be used once and discarded. For any usages beyond that, pass the
455 * returned list to {@link com.google.common.collect.ImmutableList#copyOf(Collection)
456 * ImmutableList.copyOf} and use that list instead.
457 */
458 public List<Double> 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<Double> implements RandomAccess, Serializable {
468 private final ImmutableDoubleArray parent;
469
470 private AsList(ImmutableDoubleArray 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 Double 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 Double ? parent.indexOf((Double) target) : -1;
494 }
495
496 @Override
497 public int lastIndexOf(@CheckForNull Object target) {
498 return target instanceof Double ? parent.lastIndexOf((Double) target) : -1;
499 }
500
501 @Override
502 public List<Double> 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<Double> 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 Double) || !areEqual(parent.array[i++], (Double) 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 ImmutableDoubleArray} containing the same
550 * values as this one, in the same order. Values are compared as if by {@link Double#equals}.
551 */
552 @Override
553 public boolean equals(@CheckForNull Object object) {
554 if (object == this) {
555 return true;
556 }
557 if (!(object instanceof ImmutableDoubleArray)) {
558 return false;
559 }
560 ImmutableDoubleArray that = (ImmutableDoubleArray) object;
561 if (this.length() != that.length()) {
562 return false;
563 }
564 for (int i = 0; i < length(); i++) {
565 if (!areEqual(this.get(i), that.get(i))) {
566 return false;
567 }
568 }
569 return true;
570 }
571
572 // Match the behavior of Double.equals()
573 private static boolean areEqual(double a, double b) {
574 return Double.doubleToLongBits(a) == Double.doubleToLongBits(b);
575 }
576
577 /** Returns an unspecified hash code for the contents of this immutable array. */
578 @Override
579 public int hashCode() {
580 int hash = 1;
581 for (int i = start; i < end; i++) {
582 hash *= 31;
583 hash += Doubles.hashCode(array[i]);
584 }
585 return hash;
586 }
587
588 /**
589 * Returns a string representation of this array in the same form as {@link
590 * Arrays#toString(double[])}, for example {@code "[1, 2, 3]"}.
591 */
592 @Override
593 public String toString() {
594 if (isEmpty()) {
595 return "[]";
596 }
597 StringBuilder builder = new StringBuilder(length() * 5); // rough estimate is fine
598 builder.append('[').append(array[start]);
599
600 for (int i = start + 1; i < end; i++) {
601 builder.append(", ").append(array[i]);
602 }
603 builder.append(']');
604 return builder.toString();
605 }
606
607 /**
608 * Returns an immutable array containing the same values as {@code this} array. This is logically
609 * a no-op, and in some circumstances {@code this} itself is returned. However, if this instance
610 * is a {@link #subArray} view of a larger array, this method will copy only the appropriate range
611 * of values, resulting in an equivalent array with a smaller memory footprint.
612 */
613 public ImmutableDoubleArray trimmed() {
614 return isPartialView() ? new ImmutableDoubleArray(toArray()) : this;
615 }
616
617 private boolean isPartialView() {
618 return start > 0 || end < array.length;
619 }
620
621 Object writeReplace() {
622 return trimmed();
623 }
624
625 Object readResolve() {
626 return isEmpty() ? EMPTY : this;
627 }
628 }