001/*
002 * Copyright (C) 2017 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.primitives;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkNotNull;
019
020import com.google.common.annotations.Beta;
021import com.google.common.annotations.GwtCompatible;
022import com.google.common.base.Preconditions;
023import com.google.errorprone.annotations.CanIgnoreReturnValue;
024import com.google.errorprone.annotations.CheckReturnValue;
025import com.google.errorprone.annotations.Immutable;
026import java.io.Serializable;
027import java.util.AbstractList;
028import java.util.Arrays;
029import java.util.Collection;
030import java.util.List;
031import java.util.RandomAccess;
032import java.util.Spliterator;
033import java.util.Spliterators;
034import java.util.function.DoubleConsumer;
035import java.util.stream.DoubleStream;
036import org.checkerframework.checker.nullness.qual.Nullable;
037
038/**
039 * An immutable array of {@code double} values, with an API resembling {@link List}.
040 *
041 * <p>Advantages compared to {@code double[]}:
042 *
043 * <ul>
044 *   <li>All the many well-known advantages of immutability (read <i>Effective Java</i>, second
045 *       edition, Item 15).
046 *   <li>Has the value-based (not identity-based) {@link #equals}, {@link #hashCode}, and {@link
047 *       #toString} behavior you expect.
048 *   <li>Offers useful operations beyond just {@code get} and {@code length}, so you don't have to
049 *       hunt through classes like {@link Arrays} and {@link Doubles} for them.
050 *   <li>Supports a copy-free {@link #subArray} view, so methods that accept this type don't need to
051 *       add overloads that accept start and end indexes.
052 *   <li>Can be streamed without "breaking the chain": {@code foo.getBarDoubles().stream()...}.
053 *   <li>Access to all collection-based utilities via {@link #asList} (though at the cost of
054 *       allocating garbage).
055 * </ul>
056 *
057 * <p>Disadvantages compared to {@code double[]}:
058 *
059 * <ul>
060 *   <li>Memory footprint has a fixed overhead (about 24 bytes per instance).
061 *   <li><i>Some</i> construction use cases force the data to be copied (though several construction
062 *       APIs are offered that don't).
063 *   <li>Can't be passed directly to methods that expect {@code double[]} (though the most common
064 *       utilities do have replacements here).
065 *   <li>Dependency on {@code com.google.common} / Guava.
066 * </ul>
067 *
068 * <p>Advantages compared to {@link com.google.common.collect.ImmutableList ImmutableList}{@code
069 * <Double>}:
070 *
071 * <ul>
072 *   <li>Improved memory compactness and locality.
073 *   <li>Can be queried without allocating garbage.
074 *   <li>Access to {@code DoubleStream} features (like {@link DoubleStream#sum}) using {@code
075 *       stream()} instead of the awkward {@code stream().mapToDouble(v -> v)}.
076 * </ul>
077 *
078 * <p>Disadvantages compared to {@code ImmutableList<Double>}:
079 *
080 * <ul>
081 *   <li>Can't be passed directly to methods that expect {@code Iterable}, {@code Collection}, or
082 *       {@code List} (though the most common utilities do have replacements here, and there is a
083 *       lazy {@link #asList} view).
084 * </ul>
085 *
086 * @since 22.0
087 */
088@Beta
089@GwtCompatible
090@Immutable
091public final class ImmutableDoubleArray implements Serializable {
092  private static final ImmutableDoubleArray EMPTY = new ImmutableDoubleArray(new double[0]);
093
094  /** Returns the empty array. */
095  public static ImmutableDoubleArray of() {
096    return EMPTY;
097  }
098
099  /** 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  /**
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(someDoubleArray)` won't compile (they should use copyOf), which
138  // is okay since we have to copy the just-created array anyway.
139  public static ImmutableDoubleArray of(double first, double... rest) {
140    checkArgument(
141        rest.length <= Integer.MAX_VALUE - 1,
142        "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        double[] newArray = new double[expandedCapacity(array.length, newCount)];
299        System.arraycopy(array, 0, newArray, 0, count);
300        this.array = newArray;
301      }
302    }
303
304    // Unfortunately this is pasted from ImmutableCollection.Builder.
305    private static int expandedCapacity(int oldCapacity, int minCapacity) {
306      if (minCapacity < 0) {
307        throw new AssertionError("cannot store more than MAX_VALUE elements");
308      }
309      // careful of overflow!
310      int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
311      if (newCapacity < minCapacity) {
312        newCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
313      }
314      if (newCapacity < 0) {
315        newCapacity = Integer.MAX_VALUE; // guaranteed to be >= newCapacity
316      }
317      return newCapacity;
318    }
319
320    /**
321     * Returns a new immutable array. The builder can continue to be used after this call, to append
322     * more values and build again.
323     *
324     * <p><b>Performance note:</b> the returned array is backed by the same array as the builder, so
325     * no data is copied as part of this step, but this may occupy more memory than strictly
326     * necessary. To copy the data to a right-sized backing array, use {@code .build().trimmed()}.
327     */
328    @CheckReturnValue
329    public ImmutableDoubleArray build() {
330      return count == 0 ? EMPTY : new ImmutableDoubleArray(array, 0, count);
331    }
332  }
333
334  // Instance stuff here
335
336  // The array is never mutated after storing in this field and the construction strategies ensure
337  // it doesn't escape this class
338  @SuppressWarnings("Immutable")
339  private final double[] array;
340
341  /*
342   * TODO(kevinb): evaluate the trade-offs of going bimorphic to save these two fields from most
343   * instances. Note that the instances that would get smaller are the right set to care about
344   * optimizing, because the rest have the option of calling `trimmed`.
345   */
346
347  private final transient int start; // it happens that we only serialize instances where this is 0
348  private final int end; // exclusive
349
350  private ImmutableDoubleArray(double[] array) {
351    this(array, 0, array.length);
352  }
353
354  private ImmutableDoubleArray(double[] array, int start, int end) {
355    this.array = array;
356    this.start = start;
357    this.end = end;
358  }
359
360  /** Returns the number of values in this array. */
361  public int length() {
362    return end - start;
363  }
364
365  /** Returns {@code true} if there are no values in this array ({@link #length} is zero). */
366  public boolean isEmpty() {
367    return end == start;
368  }
369
370  /**
371   * Returns the {@code double} value present at the given index.
372   *
373   * @throws IndexOutOfBoundsException if {@code index} is negative, or greater than or equal to
374   *     {@link #length}
375   */
376  public double get(int index) {
377    Preconditions.checkElementIndex(index, length());
378    return array[start + index];
379  }
380
381  /**
382   * Returns the smallest index for which {@link #get} returns {@code target}, or {@code -1} if no
383   * such index exists. Values are compared as if by {@link Double#equals}. Equivalent to {@code
384   * asList().indexOf(target)}.
385   */
386  public int indexOf(double target) {
387    for (int i = start; i < end; i++) {
388      if (areEqual(array[i], target)) {
389        return i - start;
390      }
391    }
392    return -1;
393  }
394
395  /**
396   * Returns the largest index for which {@link #get} returns {@code target}, or {@code -1} if no
397   * such index exists. Values are compared as if by {@link Double#equals}. Equivalent to {@code
398   * asList().lastIndexOf(target)}.
399   */
400  public int lastIndexOf(double target) {
401    for (int i = end - 1; i >= start; i--) {
402      if (areEqual(array[i], target)) {
403        return i - start;
404      }
405    }
406    return -1;
407  }
408
409  /**
410   * Returns {@code true} if {@code target} is present at any index in this array. Values are
411   * compared as if by {@link Double#equals}. Equivalent to {@code asList().contains(target)}.
412   */
413  public boolean contains(double target) {
414    return indexOf(target) >= 0;
415  }
416
417  /** Invokes {@code consumer} for each value contained in this array, in order. */
418  public void forEach(DoubleConsumer consumer) {
419    checkNotNull(consumer);
420    for (int i = start; i < end; i++) {
421      consumer.accept(array[i]);
422    }
423  }
424
425  /** Returns a stream over the values in this array, in order. */
426  public DoubleStream stream() {
427    return Arrays.stream(array, start, end);
428  }
429
430  /** Returns a new, mutable copy of this array's values, as a primitive {@code double[]}. */
431  public double[] toArray() {
432    return Arrays.copyOfRange(array, start, end);
433  }
434
435  /**
436   * Returns a new immutable array containing the values in the specified range.
437   *
438   * <p><b>Performance note:</b> The returned array has the same full memory footprint as this one
439   * does (no actual copying is performed). To reduce memory usage, use {@code subArray(start,
440   * end).trimmed()}.
441   */
442  public ImmutableDoubleArray subArray(int startIndex, int endIndex) {
443    Preconditions.checkPositionIndexes(startIndex, endIndex, length());
444    return startIndex == endIndex
445        ? EMPTY
446        : new ImmutableDoubleArray(array, start + startIndex, start + endIndex);
447  }
448
449  private Spliterator.OfDouble spliterator() {
450    return Spliterators.spliterator(array, start, end, Spliterator.IMMUTABLE | Spliterator.ORDERED);
451  }
452
453  /**
454   * Returns an immutable <i>view</i> of this array's values as a {@code List}; note that {@code
455   * double} values are boxed into {@link Double} instances on demand, which can be very expensive.
456   * The returned list should be used once and discarded. For any usages beyond that, pass the
457   * returned list to {@link com.google.common.collect.ImmutableList#copyOf(Collection)
458   * ImmutableList.copyOf} and use that list instead.
459   */
460  public List<Double> asList() {
461    /*
462     * Typically we cache this kind of thing, but much repeated use of this view is a performance
463     * anti-pattern anyway. If we cache, then everyone pays a price in memory footprint even if
464     * they never use this method.
465     */
466    return new AsList(this);
467  }
468
469  static class AsList extends AbstractList<Double> implements RandomAccess, Serializable {
470    private final ImmutableDoubleArray parent;
471
472    private AsList(ImmutableDoubleArray parent) {
473      this.parent = parent;
474    }
475
476    // inherit: isEmpty, containsAll, toArray x2, iterator, listIterator, stream, forEach, mutations
477
478    @Override
479    public int size() {
480      return parent.length();
481    }
482
483    @Override
484    public Double get(int index) {
485      return parent.get(index);
486    }
487
488    @Override
489    public boolean contains(Object target) {
490      return indexOf(target) >= 0;
491    }
492
493    @Override
494    public int indexOf(Object target) {
495      return target instanceof Double ? parent.indexOf((Double) target) : -1;
496    }
497
498    @Override
499    public int lastIndexOf(Object target) {
500      return target instanceof Double ? parent.lastIndexOf((Double) target) : -1;
501    }
502
503    @Override
504    public List<Double> subList(int fromIndex, int toIndex) {
505      return parent.subArray(fromIndex, toIndex).asList();
506    }
507
508    // The default List spliterator is not efficiently splittable
509    @Override
510    public Spliterator<Double> spliterator() {
511      return parent.spliterator();
512    }
513
514    @Override
515    public boolean equals(@Nullable Object object) {
516      if (object instanceof AsList) {
517        AsList that = (AsList) object;
518        return this.parent.equals(that.parent);
519      }
520      // We could delegate to super now but it would still box too much
521      if (!(object instanceof List)) {
522        return false;
523      }
524      List<?> that = (List<?>) object;
525      if (this.size() != that.size()) {
526        return false;
527      }
528      int i = parent.start;
529      // Since `that` is very likely RandomAccess we could avoid allocating this iterator...
530      for (Object element : that) {
531        if (!(element instanceof Double) || !areEqual(parent.array[i++], (Double) element)) {
532          return false;
533        }
534      }
535      return true;
536    }
537
538    // Because we happen to use the same formula. If that changes, just don't override this.
539    @Override
540    public int hashCode() {
541      return parent.hashCode();
542    }
543
544    @Override
545    public String toString() {
546      return parent.toString();
547    }
548  }
549
550  /**
551   * Returns {@code true} if {@code object} is an {@code ImmutableDoubleArray} containing the same
552   * values as this one, in the same order. Values are compared as if by {@link Double#equals}.
553   */
554  @Override
555  public boolean equals(@Nullable Object object) {
556    if (object == this) {
557      return true;
558    }
559    if (!(object instanceof ImmutableDoubleArray)) {
560      return false;
561    }
562    ImmutableDoubleArray that = (ImmutableDoubleArray) object;
563    if (this.length() != that.length()) {
564      return false;
565    }
566    for (int i = 0; i < length(); i++) {
567      if (!areEqual(this.get(i), that.get(i))) {
568        return false;
569      }
570    }
571    return true;
572  }
573
574  // Match the behavior of Double.equals()
575  private static boolean areEqual(double a, double b) {
576    return Double.doubleToLongBits(a) == Double.doubleToLongBits(b);
577  }
578
579  /** Returns an unspecified hash code for the contents of this immutable array. */
580  @Override
581  public int hashCode() {
582    int hash = 1;
583    for (int i = start; i < end; i++) {
584      hash *= 31;
585      hash += Doubles.hashCode(array[i]);
586    }
587    return hash;
588  }
589
590  /**
591   * Returns a string representation of this array in the same form as {@link
592   * Arrays#toString(double[])}, for example {@code "[1, 2, 3]"}.
593   */
594  @Override
595  public String toString() {
596    if (isEmpty()) {
597      return "[]";
598    }
599    StringBuilder builder = new StringBuilder(length() * 5); // rough estimate is fine
600    builder.append('[').append(array[start]);
601
602    for (int i = start + 1; i < end; i++) {
603      builder.append(", ").append(array[i]);
604    }
605    builder.append(']');
606    return builder.toString();
607  }
608
609  /**
610   * Returns an immutable array containing the same values as {@code this} array. This is logically
611   * a no-op, and in some circumstances {@code this} itself is returned. However, if this instance
612   * is a {@link #subArray} view of a larger array, this method will copy only the appropriate range
613   * of values, resulting in an equivalent array with a smaller memory footprint.
614   */
615  public ImmutableDoubleArray trimmed() {
616    return isPartialView() ? new ImmutableDoubleArray(toArray()) : this;
617  }
618
619  private boolean isPartialView() {
620    return start > 0 || end < array.length;
621  }
622
623  Object writeReplace() {
624    return trimmed();
625  }
626
627  Object readResolve() {
628    return isEmpty() ? EMPTY : this;
629  }
630}