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