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