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