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