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