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.CheckReturnValue;
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 javax.annotation.CheckForNull;
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>, third
040 *       edition, Item 17).
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
083@ElementTypesAreNonnullByDefault
084public final class ImmutableDoubleArray implements Serializable {
085  private static final ImmutableDoubleArray EMPTY = new ImmutableDoubleArray(new double[0]);
086
087  /** Returns the empty array. */
088  public static ImmutableDoubleArray of() {
089    return EMPTY;
090  }
091
092  /** Returns an immutable array containing a single value. */
093  public static ImmutableDoubleArray of(double e0) {
094    return new ImmutableDoubleArray(new double[] {e0});
095  }
096
097  /** Returns an immutable array containing the given values, in order. */
098  public static ImmutableDoubleArray of(double e0, double e1) {
099    return new ImmutableDoubleArray(new double[] {e0, e1});
100  }
101
102  /** Returns an immutable array containing the given values, in order. */
103  public static ImmutableDoubleArray of(double e0, double e1, double e2) {
104    return new ImmutableDoubleArray(new double[] {e0, e1, e2});
105  }
106
107  /** Returns an immutable array containing the given values, in order. */
108  public static ImmutableDoubleArray of(double e0, double e1, double e2, double e3) {
109    return new ImmutableDoubleArray(new double[] {e0, e1, e2, e3});
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, double e4) {
114    return new ImmutableDoubleArray(new double[] {e0, e1, e2, e3, e4});
115  }
116
117  /** Returns an immutable array containing the given values, in order. */
118  public static ImmutableDoubleArray of(
119      double e0, double e1, double e2, double e3, double e4, double e5) {
120    return new ImmutableDoubleArray(new double[] {e0, e1, e2, e3, e4, e5});
121  }
122
123  // TODO(kevinb): go up to 11?
124
125  /**
126   * Returns an immutable array containing the given values, in order.
127   *
128   * <p>The array {@code rest} must not be longer than {@code Integer.MAX_VALUE - 1}.
129   */
130  // Use (first, rest) so that `of(someDoubleArray)` won't compile (they should use copyOf), which
131  // is okay since we have to copy the just-created array anyway.
132  public static ImmutableDoubleArray of(double first, double... rest) {
133    checkArgument(
134        rest.length <= Integer.MAX_VALUE - 1, "the total number of elements must fit in an int");
135    double[] array = new double[rest.length + 1];
136    array[0] = first;
137    System.arraycopy(rest, 0, array, 1, rest.length);
138    return new ImmutableDoubleArray(array);
139  }
140
141  /** Returns an immutable array containing the given values, in order. */
142  public static ImmutableDoubleArray copyOf(double[] values) {
143    return values.length == 0
144        ? EMPTY
145        : new ImmutableDoubleArray(Arrays.copyOf(values, values.length));
146  }
147
148  /** Returns an immutable array containing the given values, in order. */
149  public static ImmutableDoubleArray copyOf(Collection<Double> values) {
150    return values.isEmpty() ? EMPTY : new ImmutableDoubleArray(Doubles.toArray(values));
151  }
152
153  /**
154   * Returns an immutable array containing the given values, in order.
155   *
156   * <p><b>Performance note:</b> this method delegates to {@link #copyOf(Collection)} if {@code
157   * values} is a {@link Collection}. Otherwise it creates a {@link #builder} and uses {@link
158   * Builder#addAll(Iterable)}, with all the performance implications associated with that.
159   */
160  public static ImmutableDoubleArray copyOf(Iterable<Double> values) {
161    if (values instanceof Collection) {
162      return copyOf((Collection<Double>) values);
163    }
164    return builder().addAll(values).build();
165  }
166
167  /**
168   * Returns a new, empty builder for {@link ImmutableDoubleArray} instances, sized to hold up to
169   * {@code initialCapacity} values without resizing. The returned builder is not thread-safe.
170   *
171   * <p><b>Performance note:</b> When feasible, {@code initialCapacity} should be the exact number
172   * of values that will be added, if that knowledge is readily available. It is better to guess a
173   * value slightly too high than slightly too low. If the value is not exact, the {@link
174   * ImmutableDoubleArray} that is built will very likely occupy more memory than strictly
175   * necessary; to trim memory usage, build using {@code builder.build().trimmed()}.
176   */
177  public static Builder builder(int initialCapacity) {
178    checkArgument(initialCapacity >= 0, "Invalid initialCapacity: %s", initialCapacity);
179    return new Builder(initialCapacity);
180  }
181
182  /**
183   * Returns a new, empty builder for {@link ImmutableDoubleArray} instances, with a default initial
184   * capacity. The returned builder is not thread-safe.
185   *
186   * <p><b>Performance note:</b> The {@link ImmutableDoubleArray} that is built will very likely
187   * occupy more memory than necessary; to trim memory usage, build using {@code
188   * builder.build().trimmed()}.
189   */
190  public static Builder builder() {
191    return new Builder(10);
192  }
193
194  /**
195   * A builder for {@link ImmutableDoubleArray} instances; obtained using {@link
196   * ImmutableDoubleArray#builder}.
197   */
198  @CanIgnoreReturnValue
199  public static final class Builder {
200    private double[] array;
201    private int count = 0; // <= array.length
202
203    Builder(int initialCapacity) {
204      array = new double[initialCapacity];
205    }
206
207    /**
208     * Appends {@code value} to the end of the values the built {@link ImmutableDoubleArray} will
209     * contain.
210     */
211    public Builder add(double value) {
212      ensureRoomFor(1);
213      array[count] = value;
214      count += 1;
215      return this;
216    }
217
218    /**
219     * Appends {@code values}, in order, to the end of the values the built {@link
220     * ImmutableDoubleArray} will contain.
221     */
222    public Builder addAll(double[] values) {
223      ensureRoomFor(values.length);
224      System.arraycopy(values, 0, array, count, values.length);
225      count += values.length;
226      return this;
227    }
228
229    /**
230     * Appends {@code values}, in order, to the end of the values the built {@link
231     * ImmutableDoubleArray} will contain.
232     */
233    public Builder addAll(Iterable<Double> values) {
234      if (values instanceof Collection) {
235        return addAll((Collection<Double>) values);
236      }
237      for (Double value : values) {
238        add(value);
239      }
240      return this;
241    }
242
243    /**
244     * Appends {@code values}, in order, to the end of the values the built {@link
245     * ImmutableDoubleArray} will contain.
246     */
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    public Builder addAll(ImmutableDoubleArray values) {
260      ensureRoomFor(values.length());
261      System.arraycopy(values.array, values.start, array, count, values.length());
262      count += values.length();
263      return this;
264    }
265
266    private void ensureRoomFor(int numberToAdd) {
267      int newCount = count + numberToAdd; // TODO(kevinb): check overflow now?
268      if (newCount > array.length) {
269        array = Arrays.copyOf(array, expandedCapacity(array.length, newCount));
270      }
271    }
272
273    // Unfortunately this is pasted from ImmutableCollection.Builder.
274    private static int expandedCapacity(int oldCapacity, int minCapacity) {
275      if (minCapacity < 0) {
276        throw new AssertionError("cannot store more than MAX_VALUE elements");
277      }
278      // careful of overflow!
279      int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
280      if (newCapacity < minCapacity) {
281        newCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
282      }
283      if (newCapacity < 0) {
284        newCapacity = Integer.MAX_VALUE; // guaranteed to be >= newCapacity
285      }
286      return newCapacity;
287    }
288
289    /**
290     * Returns a new immutable array. The builder can continue to be used after this call, to append
291     * more values and build again.
292     *
293     * <p><b>Performance note:</b> the returned array is backed by the same array as the builder, so
294     * no data is copied as part of this step, but this may occupy more memory than strictly
295     * necessary. To copy the data to a right-sized backing array, use {@code .build().trimmed()}.
296     */
297    @CheckReturnValue
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}