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