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.Immutable;
025import java.io.Serializable;
026import java.util.AbstractList;
027import java.util.Arrays;
028import java.util.Collection;
029import java.util.List;
030import java.util.RandomAccess;
031import java.util.Spliterator;
032import java.util.Spliterators;
033import java.util.function.DoubleConsumer;
034import java.util.stream.DoubleStream;
035import javax.annotation.CheckForNull;
036
037/**
038 * An immutable array of {@code double} values, with an API resembling {@link List}.
039 *
040 * <p>Advantages compared to {@code double[]}:
041 *
042 * <ul>
043 *   <li>All the many well-known advantages of immutability (read <i>Effective Java</i>, third
044 *       edition, Item 17).
045 *   <li>Has the value-based (not identity-based) {@link #equals}, {@link #hashCode}, and {@link
046 *       #toString} behavior you expect.
047 *   <li>Offers useful operations beyond just {@code get} and {@code length}, so you don't have to
048 *       hunt through classes like {@link Arrays} and {@link Doubles} for them.
049 *   <li>Supports a copy-free {@link #subArray} view, so methods that accept this type don't need to
050 *       add overloads that accept start and end indexes.
051 *   <li>Can be streamed without "breaking the chain": {@code foo.getBarDoubles().stream()...}.
052 *   <li>Access to all collection-based utilities via {@link #asList} (though at the cost of
053 *       allocating garbage).
054 * </ul>
055 *
056 * <p>Disadvantages compared to {@code double[]}:
057 *
058 * <ul>
059 *   <li>Memory footprint has a fixed overhead (about 24 bytes per instance).
060 *   <li><i>Some</i> construction use cases force the data to be copied (though several construction
061 *       APIs are offered that don't).
062 *   <li>Can't be passed directly to methods that expect {@code double[]} (though the most common
063 *       utilities do have replacements here).
064 *   <li>Dependency on {@code com.google.common} / Guava.
065 * </ul>
066 *
067 * <p>Advantages compared to {@link com.google.common.collect.ImmutableList ImmutableList}{@code
068 * <Double>}:
069 *
070 * <ul>
071 *   <li>Improved memory compactness and locality.
072 *   <li>Can be queried without allocating garbage.
073 *   <li>Access to {@code DoubleStream} features (like {@link DoubleStream#sum}) using {@code
074 *       stream()} instead of the awkward {@code stream().mapToDouble(v -> v)}.
075 * </ul>
076 *
077 * <p>Disadvantages compared to {@code ImmutableList<Double>}:
078 *
079 * <ul>
080 *   <li>Can't be passed directly to methods that expect {@code Iterable}, {@code Collection}, or
081 *       {@code List} (though the most common utilities do have replacements here, and there is a
082 *       lazy {@link #asList} view).
083 * </ul>
084 *
085 * @since 22.0
086 */
087@Beta
088@GwtCompatible
089@Immutable
090@ElementTypesAreNonnullByDefault
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, "the total number of elements must fit in an int");
142    double[] array = new double[rest.length + 1];
143    array[0] = first;
144    System.arraycopy(rest, 0, array, 1, rest.length);
145    return new ImmutableDoubleArray(array);
146  }
147
148  /** Returns an immutable array containing the given values, in order. */
149  public static ImmutableDoubleArray copyOf(double[] values) {
150    return values.length == 0
151        ? EMPTY
152        : new ImmutableDoubleArray(Arrays.copyOf(values, values.length));
153  }
154
155  /** Returns an immutable array containing the given values, in order. */
156  public static ImmutableDoubleArray copyOf(Collection<Double> values) {
157    return values.isEmpty() ? EMPTY : new ImmutableDoubleArray(Doubles.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 ImmutableDoubleArray copyOf(Iterable<Double> values) {
168    if (values instanceof Collection) {
169      return copyOf((Collection<Double>) 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 ImmutableDoubleArray copyOf(DoubleStream stream) {
176    // Note this uses very different growth behavior from copyOf(Iterable) and the builder.
177    double[] array = stream.toArray();
178    return (array.length == 0) ? EMPTY : new ImmutableDoubleArray(array);
179  }
180
181  /**
182   * Returns a new, empty builder for {@link ImmutableDoubleArray} 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   * ImmutableDoubleArray} that is built will very likely occupy more memory than strictly
189   * necessary; 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 ImmutableDoubleArray} instances, with a default initial
198   * capacity. The returned builder is not thread-safe.
199   *
200   * <p><b>Performance note:</b> The {@link ImmutableDoubleArray} 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 ImmutableDoubleArray} instances; obtained using {@link
210   * ImmutableDoubleArray#builder}.
211   */
212  public static final class Builder {
213    private double[] array;
214    private int count = 0; // <= array.length
215
216    Builder(int initialCapacity) {
217      array = new double[initialCapacity];
218    }
219
220    /**
221     * Appends {@code value} to the end of the values the built {@link ImmutableDoubleArray} will
222     * contain.
223     */
224    @CanIgnoreReturnValue
225    public Builder add(double 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     * ImmutableDoubleArray} will contain.
235     */
236    @CanIgnoreReturnValue
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    @CanIgnoreReturnValue
249    public Builder addAll(Iterable<Double> values) {
250      if (values instanceof Collection) {
251        return addAll((Collection<Double>) values);
252      }
253      for (Double value : values) {
254        add(value);
255      }
256      return this;
257    }
258
259    /**
260     * Appends {@code values}, in order, to the end of the values the built {@link
261     * ImmutableDoubleArray} will contain.
262     */
263    @CanIgnoreReturnValue
264    public Builder addAll(Collection<Double> values) {
265      ensureRoomFor(values.size());
266      for (Double value : values) {
267        array[count++] = value;
268      }
269      return this;
270    }
271
272    /**
273     * Appends all values from {@code stream}, in order, to the end of the values the built {@link
274     * ImmutableDoubleArray} will contain.
275     */
276    @CanIgnoreReturnValue
277    public Builder addAll(DoubleStream stream) {
278      Spliterator.OfDouble spliterator = stream.spliterator();
279      long size = spliterator.getExactSizeIfKnown();
280      if (size > 0) { // known *and* nonempty
281        ensureRoomFor(Ints.saturatedCast(size));
282      }
283      spliterator.forEachRemaining((DoubleConsumer) this::add);
284      return this;
285    }
286
287    /**
288     * Appends {@code values}, in order, to the end of the values the built {@link
289     * ImmutableDoubleArray} will contain.
290     */
291    @CanIgnoreReturnValue
292    public Builder addAll(ImmutableDoubleArray values) {
293      ensureRoomFor(values.length());
294      System.arraycopy(values.array, values.start, array, count, values.length());
295      count += values.length();
296      return this;
297    }
298
299    private void ensureRoomFor(int numberToAdd) {
300      int newCount = count + numberToAdd; // TODO(kevinb): check overflow now?
301      if (newCount > array.length) {
302        array = Arrays.copyOf(array, expandedCapacity(array.length, newCount));
303      }
304    }
305
306    // Unfortunately this is pasted from ImmutableCollection.Builder.
307    private static int expandedCapacity(int oldCapacity, int minCapacity) {
308      if (minCapacity < 0) {
309        throw new AssertionError("cannot store more than MAX_VALUE elements");
310      }
311      // careful of overflow!
312      int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
313      if (newCapacity < minCapacity) {
314        newCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
315      }
316      if (newCapacity < 0) {
317        newCapacity = Integer.MAX_VALUE; // guaranteed to be >= newCapacity
318      }
319      return newCapacity;
320    }
321
322    /**
323     * Returns a new immutable array. The builder can continue to be used after this call, to append
324     * more values and build again.
325     *
326     * <p><b>Performance note:</b> the returned array is backed by the same array as the builder, so
327     * no data is copied as part of this step, but this may occupy more memory than strictly
328     * necessary. To copy the data to a right-sized backing array, use {@code .build().trimmed()}.
329     */
330    public ImmutableDoubleArray build() {
331      return count == 0 ? EMPTY : new ImmutableDoubleArray(array, 0, count);
332    }
333  }
334
335  // Instance stuff here
336
337  // The array is never mutated after storing in this field and the construction strategies ensure
338  // it doesn't escape this class
339  @SuppressWarnings("Immutable")
340  private final double[] array;
341
342  /*
343   * TODO(kevinb): evaluate the trade-offs of going bimorphic to save these two fields from most
344   * instances. Note that the instances that would get smaller are the right set to care about
345   * optimizing, because the rest have the option of calling `trimmed`.
346   */
347
348  private final transient int start; // it happens that we only serialize instances where this is 0
349  private final int end; // exclusive
350
351  private ImmutableDoubleArray(double[] array) {
352    this(array, 0, array.length);
353  }
354
355  private ImmutableDoubleArray(double[] array, int start, int end) {
356    this.array = array;
357    this.start = start;
358    this.end = end;
359  }
360
361  /** Returns the number of values in this array. */
362  public int length() {
363    return end - start;
364  }
365
366  /** Returns {@code true} if there are no values in this array ({@link #length} is zero). */
367  public boolean isEmpty() {
368    return end == start;
369  }
370
371  /**
372   * Returns the {@code double} value present at the given index.
373   *
374   * @throws IndexOutOfBoundsException if {@code index} is negative, or greater than or equal to
375   *     {@link #length}
376   */
377  public double get(int index) {
378    Preconditions.checkElementIndex(index, length());
379    return array[start + index];
380  }
381
382  /**
383   * Returns the smallest index for which {@link #get} returns {@code target}, or {@code -1} if no
384   * such index exists. Values are compared as if by {@link Double#equals}. Equivalent to {@code
385   * asList().indexOf(target)}.
386   */
387  public int indexOf(double target) {
388    for (int i = start; i < end; i++) {
389      if (areEqual(array[i], target)) {
390        return i - start;
391      }
392    }
393    return -1;
394  }
395
396  /**
397   * Returns the largest index for which {@link #get} returns {@code target}, or {@code -1} if no
398   * such index exists. Values are compared as if by {@link Double#equals}. Equivalent to {@code
399   * asList().lastIndexOf(target)}.
400   */
401  public int lastIndexOf(double target) {
402    for (int i = end - 1; i >= start; i--) {
403      if (areEqual(array[i], target)) {
404        return i - start;
405      }
406    }
407    return -1;
408  }
409
410  /**
411   * Returns {@code true} if {@code target} is present at any index in this array. Values are
412   * compared as if by {@link Double#equals}. Equivalent to {@code asList().contains(target)}.
413   */
414  public boolean contains(double target) {
415    return indexOf(target) >= 0;
416  }
417
418  /** Invokes {@code consumer} for each value contained in this array, in order. */
419  public void forEach(DoubleConsumer consumer) {
420    checkNotNull(consumer);
421    for (int i = start; i < end; i++) {
422      consumer.accept(array[i]);
423    }
424  }
425
426  /** Returns a stream over the values in this array, in order. */
427  public DoubleStream stream() {
428    return Arrays.stream(array, start, end);
429  }
430
431  /** Returns a new, mutable copy of this array's values, as a primitive {@code double[]}. */
432  public double[] toArray() {
433    return Arrays.copyOfRange(array, start, end);
434  }
435
436  /**
437   * Returns a new immutable array containing the values in the specified range.
438   *
439   * <p><b>Performance note:</b> The returned array has the same full memory footprint as this one
440   * does (no actual copying is performed). To reduce memory usage, use {@code subArray(start,
441   * end).trimmed()}.
442   */
443  public ImmutableDoubleArray subArray(int startIndex, int endIndex) {
444    Preconditions.checkPositionIndexes(startIndex, endIndex, length());
445    return startIndex == endIndex
446        ? EMPTY
447        : new ImmutableDoubleArray(array, start + startIndex, start + endIndex);
448  }
449
450  private Spliterator.OfDouble spliterator() {
451    return Spliterators.spliterator(array, start, end, Spliterator.IMMUTABLE | Spliterator.ORDERED);
452  }
453
454  /**
455   * Returns an immutable <i>view</i> of this array's values as a {@code List}; note that {@code
456   * double} values are boxed into {@link Double} instances on demand, which can be very expensive.
457   * The returned list should be used once and discarded. For any usages beyond that, pass the
458   * returned list to {@link com.google.common.collect.ImmutableList#copyOf(Collection)
459   * ImmutableList.copyOf} and use that list instead.
460   */
461  public List<Double> asList() {
462    /*
463     * Typically we cache this kind of thing, but much repeated use of this view is a performance
464     * anti-pattern anyway. If we cache, then everyone pays a price in memory footprint even if
465     * they never use this method.
466     */
467    return new AsList(this);
468  }
469
470  static class AsList extends AbstractList<Double> implements RandomAccess, Serializable {
471    private final ImmutableDoubleArray parent;
472
473    private AsList(ImmutableDoubleArray parent) {
474      this.parent = parent;
475    }
476
477    // inherit: isEmpty, containsAll, toArray x2, iterator, listIterator, stream, forEach, mutations
478
479    @Override
480    public int size() {
481      return parent.length();
482    }
483
484    @Override
485    public Double get(int index) {
486      return parent.get(index);
487    }
488
489    @Override
490    public boolean contains(@CheckForNull Object target) {
491      return indexOf(target) >= 0;
492    }
493
494    @Override
495    public int indexOf(@CheckForNull Object target) {
496      return target instanceof Double ? parent.indexOf((Double) target) : -1;
497    }
498
499    @Override
500    public int lastIndexOf(@CheckForNull Object target) {
501      return target instanceof Double ? parent.lastIndexOf((Double) target) : -1;
502    }
503
504    @Override
505    public List<Double> subList(int fromIndex, int toIndex) {
506      return parent.subArray(fromIndex, toIndex).asList();
507    }
508
509    // The default List spliterator is not efficiently splittable
510    @Override
511    public Spliterator<Double> spliterator() {
512      return parent.spliterator();
513    }
514
515    @Override
516    public boolean equals(@CheckForNull Object object) {
517      if (object instanceof AsList) {
518        AsList that = (AsList) object;
519        return this.parent.equals(that.parent);
520      }
521      // We could delegate to super now but it would still box too much
522      if (!(object instanceof List)) {
523        return false;
524      }
525      List<?> that = (List<?>) object;
526      if (this.size() != that.size()) {
527        return false;
528      }
529      int i = parent.start;
530      // Since `that` is very likely RandomAccess we could avoid allocating this iterator...
531      for (Object element : that) {
532        if (!(element instanceof Double) || !areEqual(parent.array[i++], (Double) element)) {
533          return false;
534        }
535      }
536      return true;
537    }
538
539    // Because we happen to use the same formula. If that changes, just don't override this.
540    @Override
541    public int hashCode() {
542      return parent.hashCode();
543    }
544
545    @Override
546    public String toString() {
547      return parent.toString();
548    }
549  }
550
551  /**
552   * Returns {@code true} if {@code object} is an {@code ImmutableDoubleArray} containing the same
553   * values as this one, in the same order. Values are compared as if by {@link Double#equals}.
554   */
555  @Override
556  public boolean equals(@CheckForNull Object object) {
557    if (object == this) {
558      return true;
559    }
560    if (!(object instanceof ImmutableDoubleArray)) {
561      return false;
562    }
563    ImmutableDoubleArray that = (ImmutableDoubleArray) object;
564    if (this.length() != that.length()) {
565      return false;
566    }
567    for (int i = 0; i < length(); i++) {
568      if (!areEqual(this.get(i), that.get(i))) {
569        return false;
570      }
571    }
572    return true;
573  }
574
575  // Match the behavior of Double.equals()
576  private static boolean areEqual(double a, double b) {
577    return Double.doubleToLongBits(a) == Double.doubleToLongBits(b);
578  }
579
580  /** Returns an unspecified hash code for the contents of this immutable array. */
581  @Override
582  public int hashCode() {
583    int hash = 1;
584    for (int i = start; i < end; i++) {
585      hash *= 31;
586      hash += Doubles.hashCode(array[i]);
587    }
588    return hash;
589  }
590
591  /**
592   * Returns a string representation of this array in the same form as {@link
593   * Arrays#toString(double[])}, for example {@code "[1, 2, 3]"}.
594   */
595  @Override
596  public String toString() {
597    if (isEmpty()) {
598      return "[]";
599    }
600    StringBuilder builder = new StringBuilder(length() * 5); // rough estimate is fine
601    builder.append('[').append(array[start]);
602
603    for (int i = start + 1; i < end; i++) {
604      builder.append(", ").append(array[i]);
605    }
606    builder.append(']');
607    return builder.toString();
608  }
609
610  /**
611   * Returns an immutable array containing the same values as {@code this} array. This is logically
612   * a no-op, and in some circumstances {@code this} itself is returned. However, if this instance
613   * is a {@link #subArray} view of a larger array, this method will copy only the appropriate range
614   * of values, resulting in an equivalent array with a smaller memory footprint.
615   */
616  public ImmutableDoubleArray trimmed() {
617    return isPartialView() ? new ImmutableDoubleArray(toArray()) : this;
618  }
619
620  private boolean isPartialView() {
621    return start > 0 || end < array.length;
622  }
623
624  Object writeReplace() {
625    return trimmed();
626  }
627
628  Object readResolve() {
629    return isEmpty() ? EMPTY : this;
630  }
631}