001/*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.primitives;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkElementIndex;
021import static com.google.common.base.Preconditions.checkNotNull;
022import static com.google.common.base.Preconditions.checkPositionIndexes;
023import static java.lang.Double.NEGATIVE_INFINITY;
024import static java.lang.Double.POSITIVE_INFINITY;
025
026import com.google.common.annotations.Beta;
027import com.google.common.annotations.GwtCompatible;
028import com.google.common.annotations.GwtIncompatible;
029import com.google.common.base.Converter;
030
031import java.io.Serializable;
032import java.util.AbstractList;
033import java.util.Arrays;
034import java.util.Collection;
035import java.util.Collections;
036import java.util.Comparator;
037import java.util.List;
038import java.util.RandomAccess;
039import java.util.regex.Pattern;
040
041import javax.annotation.Nullable;
042
043/**
044 * Static utility methods pertaining to {@code double} primitives, that are not
045 * already found in either {@link Double} or {@link Arrays}.
046 *
047 * <p>See the Guava User Guide article on <a href=
048 * "http://code.google.com/p/guava-libraries/wiki/PrimitivesExplained">
049 * primitive utilities</a>.
050 *
051 * @author Kevin Bourrillion
052 * @since 1.0
053 */
054@GwtCompatible(emulated = true)
055public final class Doubles {
056  private Doubles() {}
057
058  /**
059   * The number of bytes required to represent a primitive {@code double}
060   * value.
061   *
062   * @since 10.0
063   */
064  public static final int BYTES = Double.SIZE / Byte.SIZE;
065
066  /**
067   * Returns a hash code for {@code value}; equal to the result of invoking
068   * {@code ((Double) value).hashCode()}.
069   *
070   * @param value a primitive {@code double} value
071   * @return a hash code for the value
072   */
073  public static int hashCode(double value) {
074    return ((Double) value).hashCode();
075    // TODO(kevinb): do it this way when we can (GWT problem):
076    // long bits = Double.doubleToLongBits(value);
077    // return (int) (bits ^ (bits >>> 32));
078  }
079
080  /**
081   * Compares the two specified {@code double} values. The sign of the value
082   * returned is the same as that of <code>((Double) a).{@linkplain
083   * Double#compareTo compareTo}(b)</code>. As with that method, {@code NaN} is
084   * treated as greater than all other values, and {@code 0.0 > -0.0}.
085   *
086   * <p><b>Note:</b> this method simply delegates to the JDK method {@link
087   * Double#compare}. It is provided for consistency with the other primitive
088   * types, whose compare methods were not added to the JDK until JDK 7.
089   *
090   * @param a the first {@code double} to compare
091   * @param b the second {@code double} to compare
092   * @return a negative value if {@code a} is less than {@code b}; a positive
093   *     value if {@code a} is greater than {@code b}; or zero if they are equal
094   */
095  // TODO(kevinb): if Ints.compare etc. are ever removed, remove this one too
096  public static int compare(double a, double b) {
097    return Double.compare(a, b);
098  }
099
100  /**
101   * Returns {@code true} if {@code value} represents a real number. This is
102   * equivalent to, but not necessarily implemented as,
103   * {@code !(Double.isInfinite(value) || Double.isNaN(value))}.
104   *
105   * @since 10.0
106   */
107  public static boolean isFinite(double value) {
108    return NEGATIVE_INFINITY < value & value < POSITIVE_INFINITY;
109  }
110
111  /**
112   * Returns {@code true} if {@code target} is present as an element anywhere in
113   * {@code array}. Note that this always returns {@code false} when {@code
114   * target} is {@code NaN}.
115   *
116   * @param array an array of {@code double} values, possibly empty
117   * @param target a primitive {@code double} value
118   * @return {@code true} if {@code array[i] == target} for some value of {@code
119   *     i}
120   */
121  public static boolean contains(double[] array, double target) {
122    for (double value : array) {
123      if (value == target) {
124        return true;
125      }
126    }
127    return false;
128  }
129
130  /**
131   * Returns the index of the first appearance of the value {@code target} in
132   * {@code array}. Note that this always returns {@code -1} when {@code target}
133   * is {@code NaN}.
134   *
135   * @param array an array of {@code double} values, possibly empty
136   * @param target a primitive {@code double} value
137   * @return the least index {@code i} for which {@code array[i] == target}, or
138   *     {@code -1} if no such index exists.
139   */
140  public static int indexOf(double[] array, double target) {
141    return indexOf(array, target, 0, array.length);
142  }
143
144  // TODO(kevinb): consider making this public
145  private static int indexOf(
146      double[] array, double target, int start, int end) {
147    for (int i = start; i < end; i++) {
148      if (array[i] == target) {
149        return i;
150      }
151    }
152    return -1;
153  }
154
155  /**
156   * Returns the start position of the first occurrence of the specified {@code
157   * target} within {@code array}, or {@code -1} if there is no such occurrence.
158   *
159   * <p>More formally, returns the lowest index {@code i} such that {@code
160   * java.util.Arrays.copyOfRange(array, i, i + target.length)} contains exactly
161   * the same elements as {@code target}.
162   *
163   * <p>Note that this always returns {@code -1} when {@code target} contains
164   * {@code NaN}.
165   *
166   * @param array the array to search for the sequence {@code target}
167   * @param target the array to search for as a sub-sequence of {@code array}
168   */
169  public static int indexOf(double[] array, double[] target) {
170    checkNotNull(array, "array");
171    checkNotNull(target, "target");
172    if (target.length == 0) {
173      return 0;
174    }
175
176    outer:
177    for (int i = 0; i < array.length - target.length + 1; i++) {
178      for (int j = 0; j < target.length; j++) {
179        if (array[i + j] != target[j]) {
180          continue outer;
181        }
182      }
183      return i;
184    }
185    return -1;
186  }
187
188  /**
189   * Returns the index of the last appearance of the value {@code target} in
190   * {@code array}. Note that this always returns {@code -1} when {@code target}
191   * is {@code NaN}.
192   *
193   * @param array an array of {@code double} values, possibly empty
194   * @param target a primitive {@code double} value
195   * @return the greatest index {@code i} for which {@code array[i] == target},
196   *     or {@code -1} if no such index exists.
197   */
198  public static int lastIndexOf(double[] array, double target) {
199    return lastIndexOf(array, target, 0, array.length);
200  }
201
202  // TODO(kevinb): consider making this public
203  private static int lastIndexOf(
204      double[] array, double target, int start, int end) {
205    for (int i = end - 1; i >= start; i--) {
206      if (array[i] == target) {
207        return i;
208      }
209    }
210    return -1;
211  }
212
213  /**
214   * Returns the least value present in {@code array}, using the same rules of
215   * comparison as {@link Math#min(double, double)}.
216   *
217   * @param array a <i>nonempty</i> array of {@code double} values
218   * @return the value present in {@code array} that is less than or equal to
219   *     every other value in the array
220   * @throws IllegalArgumentException if {@code array} is empty
221   */
222  public static double min(double... array) {
223    checkArgument(array.length > 0);
224    double min = array[0];
225    for (int i = 1; i < array.length; i++) {
226      min = Math.min(min, array[i]);
227    }
228    return min;
229  }
230
231  /**
232   * Returns the greatest value present in {@code array}, using the same rules
233   * of comparison as {@link Math#max(double, double)}.
234   *
235   * @param array a <i>nonempty</i> array of {@code double} values
236   * @return the value present in {@code array} that is greater than or equal to
237   *     every other value in the array
238   * @throws IllegalArgumentException if {@code array} is empty
239   */
240  public static double max(double... array) {
241    checkArgument(array.length > 0);
242    double max = array[0];
243    for (int i = 1; i < array.length; i++) {
244      max = Math.max(max, array[i]);
245    }
246    return max;
247  }
248
249  /**
250   * Returns the values from each provided array combined into a single array.
251   * For example, {@code concat(new double[] {a, b}, new double[] {}, new
252   * double[] {c}} returns the array {@code {a, b, c}}.
253   *
254   * @param arrays zero or more {@code double} arrays
255   * @return a single array containing all the values from the source arrays, in
256   *     order
257   */
258  public static double[] concat(double[]... arrays) {
259    int length = 0;
260    for (double[] array : arrays) {
261      length += array.length;
262    }
263    double[] result = new double[length];
264    int pos = 0;
265    for (double[] array : arrays) {
266      System.arraycopy(array, 0, result, pos, array.length);
267      pos += array.length;
268    }
269    return result;
270  }
271
272  private static final class DoubleConverter
273      extends Converter<String, Double> implements Serializable {
274    static final DoubleConverter INSTANCE = new DoubleConverter();
275
276    @Override
277    protected Double doForward(String value) {
278      // TODO(kevinb): remove null boilerplate (convert() will do it
279      // automatically)
280      return value == null ? null : Double.valueOf(value);
281    }
282
283    @Override
284    protected String doBackward(Double value) {
285      // TODO(kevinb): remove null boilerplate (convert() will do it
286      // automatically)
287      return value == null ? null : value.toString();
288    }
289
290    @Override
291    public String toString() {
292      return "Doubles.stringConverter()";
293    }
294
295    private Object readResolve() {
296      return INSTANCE;
297    }
298    private static final long serialVersionUID = 1;
299  }
300
301  /**
302   * Returns a serializable converter object that converts between strings and
303   * doubles using {@link Double#valueOf} and {@link Double#toString()}.
304   *
305   * @since 16.0
306   */
307  @Beta
308  public static Converter<String, Double> stringConverter() {
309    return DoubleConverter.INSTANCE;
310  }
311
312  /**
313   * Returns an array containing the same values as {@code array}, but
314   * guaranteed to be of a specified minimum length. If {@code array} already
315   * has a length of at least {@code minLength}, it is returned directly.
316   * Otherwise, a new array of size {@code minLength + padding} is returned,
317   * containing the values of {@code array}, and zeroes in the remaining places.
318   *
319   * @param array the source array
320   * @param minLength the minimum length the returned array must guarantee
321   * @param padding an extra amount to "grow" the array by if growth is
322   *     necessary
323   * @throws IllegalArgumentException if {@code minLength} or {@code padding} is
324   *     negative
325   * @return an array containing the values of {@code array}, with guaranteed
326   *     minimum length {@code minLength}
327   */
328  public static double[] ensureCapacity(
329      double[] array, int minLength, int padding) {
330    checkArgument(minLength >= 0, "Invalid minLength: %s", minLength);
331    checkArgument(padding >= 0, "Invalid padding: %s", padding);
332    return (array.length < minLength)
333        ? copyOf(array, minLength + padding)
334        : array;
335  }
336
337  // Arrays.copyOf() requires Java 6
338  private static double[] copyOf(double[] original, int length) {
339    double[] copy = new double[length];
340    System.arraycopy(original, 0, copy, 0, Math.min(original.length, length));
341    return copy;
342  }
343
344  /**
345   * Returns a string containing the supplied {@code double} values, converted
346   * to strings as specified by {@link Double#toString(double)}, and separated
347   * by {@code separator}. For example, {@code join("-", 1.0, 2.0, 3.0)} returns
348   * the string {@code "1.0-2.0-3.0"}.
349   *
350   * <p>Note that {@link Double#toString(double)} formats {@code double}
351   * differently in GWT sometimes.  In the previous example, it returns the
352   * string {@code "1-2-3"}.
353   *
354   * @param separator the text that should appear between consecutive values in
355   *     the resulting string (but not at the start or end)
356   * @param array an array of {@code double} values, possibly empty
357   */
358  public static String join(String separator, double... array) {
359    checkNotNull(separator);
360    if (array.length == 0) {
361      return "";
362    }
363
364    // For pre-sizing a builder, just get the right order of magnitude
365    StringBuilder builder = new StringBuilder(array.length * 12);
366    builder.append(array[0]);
367    for (int i = 1; i < array.length; i++) {
368      builder.append(separator).append(array[i]);
369    }
370    return builder.toString();
371  }
372
373  /**
374   * Returns a comparator that compares two {@code double} arrays
375   * lexicographically. That is, it compares, using {@link
376   * #compare(double, double)}), the first pair of values that follow any
377   * common prefix, or when one array is a prefix of the other, treats the
378   * shorter array as the lesser. For example,
379   * {@code [] < [1.0] < [1.0, 2.0] < [2.0]}.
380   *
381   * <p>The returned comparator is inconsistent with {@link
382   * Object#equals(Object)} (since arrays support only identity equality), but
383   * it is consistent with {@link Arrays#equals(double[], double[])}.
384   *
385   * @see <a href="http://en.wikipedia.org/wiki/Lexicographical_order">
386   *     Lexicographical order article at Wikipedia</a>
387   * @since 2.0
388   */
389  public static Comparator<double[]> lexicographicalComparator() {
390    return LexicographicalComparator.INSTANCE;
391  }
392
393  private enum LexicographicalComparator implements Comparator<double[]> {
394    INSTANCE;
395
396    @Override
397    public int compare(double[] left, double[] right) {
398      int minLength = Math.min(left.length, right.length);
399      for (int i = 0; i < minLength; i++) {
400        int result = Doubles.compare(left[i], right[i]);
401        if (result != 0) {
402          return result;
403        }
404      }
405      return left.length - right.length;
406    }
407  }
408
409  /**
410   * Returns an array containing each value of {@code collection}, converted to
411   * a {@code double} value in the manner of {@link Number#doubleValue}.
412   *
413   * <p>Elements are copied from the argument collection as if by {@code
414   * collection.toArray()}.  Calling this method is as thread-safe as calling
415   * that method.
416   *
417   * @param collection a collection of {@code Number} instances
418   * @return an array containing the same values as {@code collection}, in the
419   *     same order, converted to primitives
420   * @throws NullPointerException if {@code collection} or any of its elements
421   *     is null
422   * @since 1.0 (parameter was {@code Collection<Double>} before 12.0)
423   */
424  public static double[] toArray(Collection<? extends Number> collection) {
425    if (collection instanceof DoubleArrayAsList) {
426      return ((DoubleArrayAsList) collection).toDoubleArray();
427    }
428
429    Object[] boxedArray = collection.toArray();
430    int len = boxedArray.length;
431    double[] array = new double[len];
432    for (int i = 0; i < len; i++) {
433      // checkNotNull for GWT (do not optimize)
434      array[i] = ((Number) checkNotNull(boxedArray[i])).doubleValue();
435    }
436    return array;
437  }
438
439  /**
440   * Returns a fixed-size list backed by the specified array, similar to {@link
441   * Arrays#asList(Object[])}. The list supports {@link List#set(int, Object)},
442   * but any attempt to set a value to {@code null} will result in a {@link
443   * NullPointerException}.
444   *
445   * <p>The returned list maintains the values, but not the identities, of
446   * {@code Double} objects written to or read from it.  For example, whether
447   * {@code list.get(0) == list.get(0)} is true for the returned list is
448   * unspecified.
449   *
450   * <p>The returned list may have unexpected behavior if it contains {@code
451   * NaN}, or if {@code NaN} is used as a parameter to any of its methods.
452   *
453   * @param backingArray the array to back the list
454   * @return a list view of the array
455   */
456  public static List<Double> asList(double... backingArray) {
457    if (backingArray.length == 0) {
458      return Collections.emptyList();
459    }
460    return new DoubleArrayAsList(backingArray);
461  }
462
463  @GwtCompatible
464  private static class DoubleArrayAsList extends AbstractList<Double>
465      implements RandomAccess, Serializable {
466    final double[] array;
467    final int start;
468    final int end;
469
470    DoubleArrayAsList(double[] array) {
471      this(array, 0, array.length);
472    }
473
474    DoubleArrayAsList(double[] array, int start, int end) {
475      this.array = array;
476      this.start = start;
477      this.end = end;
478    }
479
480    @Override public int size() {
481      return end - start;
482    }
483
484    @Override public boolean isEmpty() {
485      return false;
486    }
487
488    @Override public Double get(int index) {
489      checkElementIndex(index, size());
490      return array[start + index];
491    }
492
493    @Override public boolean contains(Object target) {
494      // Overridden to prevent a ton of boxing
495      return (target instanceof Double)
496          && Doubles.indexOf(array, (Double) target, start, end) != -1;
497    }
498
499    @Override public int indexOf(Object target) {
500      // Overridden to prevent a ton of boxing
501      if (target instanceof Double) {
502        int i = Doubles.indexOf(array, (Double) target, start, end);
503        if (i >= 0) {
504          return i - start;
505        }
506      }
507      return -1;
508    }
509
510    @Override public int lastIndexOf(Object target) {
511      // Overridden to prevent a ton of boxing
512      if (target instanceof Double) {
513        int i = Doubles.lastIndexOf(array, (Double) target, start, end);
514        if (i >= 0) {
515          return i - start;
516        }
517      }
518      return -1;
519    }
520
521    @Override public Double set(int index, Double element) {
522      checkElementIndex(index, size());
523      double oldValue = array[start + index];
524      // checkNotNull for GWT (do not optimize)
525      array[start + index] = checkNotNull(element);
526      return oldValue;
527    }
528
529    @Override public List<Double> subList(int fromIndex, int toIndex) {
530      int size = size();
531      checkPositionIndexes(fromIndex, toIndex, size);
532      if (fromIndex == toIndex) {
533        return Collections.emptyList();
534      }
535      return new DoubleArrayAsList(array, start + fromIndex, start + toIndex);
536    }
537
538    @Override public boolean equals(Object object) {
539      if (object == this) {
540        return true;
541      }
542      if (object instanceof DoubleArrayAsList) {
543        DoubleArrayAsList that = (DoubleArrayAsList) object;
544        int size = size();
545        if (that.size() != size) {
546          return false;
547        }
548        for (int i = 0; i < size; i++) {
549          if (array[start + i] != that.array[that.start + i]) {
550            return false;
551          }
552        }
553        return true;
554      }
555      return super.equals(object);
556    }
557
558    @Override public int hashCode() {
559      int result = 1;
560      for (int i = start; i < end; i++) {
561        result = 31 * result + Doubles.hashCode(array[i]);
562      }
563      return result;
564    }
565
566    @Override public String toString() {
567      StringBuilder builder = new StringBuilder(size() * 12);
568      builder.append('[').append(array[start]);
569      for (int i = start + 1; i < end; i++) {
570        builder.append(", ").append(array[i]);
571      }
572      return builder.append(']').toString();
573    }
574
575    double[] toDoubleArray() {
576      // Arrays.copyOfRange() is not available under GWT
577      int size = size();
578      double[] result = new double[size];
579      System.arraycopy(array, start, result, 0, size);
580      return result;
581    }
582
583    private static final long serialVersionUID = 0;
584  }
585
586  /**
587   * This is adapted from the regex suggested by {@link Double#valueOf(String)}
588   * for prevalidating inputs.  All valid inputs must pass this regex, but it's
589   * semantically fine if not all inputs that pass this regex are valid --
590   * only a performance hit is incurred, not a semantics bug.
591   */
592  @GwtIncompatible("regular expressions")
593  static final Pattern FLOATING_POINT_PATTERN = fpPattern();
594
595  @GwtIncompatible("regular expressions")
596  private static Pattern fpPattern() {
597    String decimal = "(?:\\d++(?:\\.\\d*+)?|\\.\\d++)";
598    String completeDec = decimal + "(?:[eE][+-]?\\d++)?[fFdD]?";
599    String hex = "(?:\\p{XDigit}++(?:\\.\\p{XDigit}*+)?|\\.\\p{XDigit}++)";
600    String completeHex = "0[xX]" + hex + "[pP][+-]?\\d++[fFdD]?";
601    String fpPattern = "[+-]?(?:NaN|Infinity|" + completeDec + "|" + completeHex + ")";
602    return Pattern.compile(fpPattern);
603  }
604
605  /**
606   * Parses the specified string as a double-precision floating point value.
607   * The ASCII character {@code '-'} (<code>'&#92;u002D'</code>) is recognized
608   * as the minus sign.
609   *
610   * <p>Unlike {@link Double#parseDouble(String)}, this method returns
611   * {@code null} instead of throwing an exception if parsing fails.
612   * Valid inputs are exactly those accepted by {@link Double#valueOf(String)},
613   * except that leading and trailing whitespace is not permitted.
614   *
615   * <p>This implementation is likely to be faster than {@code
616   * Double.parseDouble} if many failures are expected.
617   *
618   * @param string the string representation of a {@code double} value
619   * @return the floating point value represented by {@code string}, or
620   *     {@code null} if {@code string} has a length of zero or cannot be
621   *     parsed as a {@code double} value
622   * @since 14.0
623   */
624  @GwtIncompatible("regular expressions")
625  @Nullable
626  @Beta
627  public static Double tryParse(String string) {
628    if (FLOATING_POINT_PATTERN.matcher(string).matches()) {
629      // TODO(user): could be potentially optimized, but only with
630      // extensive testing
631      try {
632        return Double.parseDouble(string);
633      } catch (NumberFormatException e) {
634        // Double.parseDouble has changed specs several times, so fall through
635        // gracefully
636      }
637    }
638    return null;
639  }
640}