content: /*
   * Copyright (C) 2013 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package android.util;
  
  import static com.android.internal.util.Preconditions.*;
  
  import android.annotation.UnsupportedAppUsage;
  import java.io.IOException;
  import java.io.InvalidObjectException;
  
  /**
   * <p>An immutable data type representation a rational number.</p>
   *
   * <p>Contains a pair of {@code int}s representing the numerator and denominator of a
   * Rational number. </p>
   */
  public final class Rational extends Number implements Comparable<Rational> {
      /**
       * Constant for the <em>Not-a-Number (NaN)</em> value of the {@code Rational} type.
       *
       * <p>A {@code NaN} value is considered to be equal to itself (that is {@code NaN.equals(NaN)}
       * will return {@code true}; it is always greater than any non-{@code NaN} value (that is
       * {@code NaN.compareTo(notNaN)} will return a number greater than {@code 0}).</p>
       *
       * <p>Equivalent to constructing a new rational with both the numerator and denominator
       * equal to {@code 0}.</p>
       */
      public static final Rational NaN = new Rational(0, 0);
  
      /**
       * Constant for the positive infinity value of the {@code Rational} type.
       *
       * <p>Equivalent to constructing a new rational with a positive numerator and a denominator
       * equal to {@code 0}.</p>
       */
      public static final Rational POSITIVE_INFINITY = new Rational(1, 0);
  
      /**
       * Constant for the negative infinity value of the {@code Rational} type.
       *
       * <p>Equivalent to constructing a new rational with a negative numerator and a denominator
       * equal to {@code 0}.</p>
       */
      public static final Rational NEGATIVE_INFINITY = new Rational(-1, 0);
  
      /**
       * Constant for the zero value of the {@code Rational} type.
       *
       * <p>Equivalent to constructing a new rational with a numerator equal to {@code 0} and
       * any non-zero denominator.</p>
       */
      public static final Rational ZERO = new Rational(0, 1);
  
      /**
       * Unique version number per class to be compliant with {@link java.io.Serializable}.
       *
       * <p>Increment each time the fields change in any way.</p>
       */
      private static final long serialVersionUID = 1L;
  
      /*
       * Do not change the order of these fields or add new instance fields to maintain the
       * Serializable compatibility across API revisions.
       */
      @UnsupportedAppUsage
      private final int mNumerator;
      @UnsupportedAppUsage
      private final int mDenominator;
  
      /**
       * <p>Create a {@code Rational} with a given numerator and denominator.</p>
       *
       * <p>The signs of the numerator and the denominator may be flipped such that the denominator
       * is always positive. Both the numerator and denominator will be converted to their reduced
       * forms (see {@link #equals} for more details).</p>
       *
       * <p>For example,
       * <ul>
       * <li>a rational of {@code 2/4} will be reduced to {@code 1/2}.
       * <li>a rational of {@code 1/-1} will be flipped to {@code -1/1}
       * <li>a rational of {@code 5/0} will be reduced to {@code 1/0}
       * <li>a rational of {@code 0/5} will be reduced to {@code 0/1}
       * </ul>
       * </p>
       *
       * @param numerator the numerator of the rational
       * @param denominator the denominator of the rational
       *
       * @see #equals
       */
      public Rational(int numerator, int denominator) {
  
          if (denominator < 0) {
              numerator = -numerator;
              denominator = -denominator;
          }
  
          // Convert to reduced form
          if (denominator == 0 && numerator > 0) {
              mNumerator = 1; // +Inf
              mDenominator = 0;
          } else if (denominator == 0 && numerator < 0) {
              mNumerator = -1; // -Inf
              mDenominator = 0;
          } else if (denominator == 0 && numerator == 0) {
              mNumerator = 0; // NaN
              mDenominator = 0;
          } else if (numerator == 0) {
              mNumerator = 0;
              mDenominator = 1;
          } else {
              int gcd = gcd(numerator, denominator);
  
              mNumerator = numerator / gcd;
              mDenominator = denominator / gcd;
          }
      }
  
      /**
       * Gets the numerator of the rational.
       *
       * <p>The numerator will always return {@code 1} if this rational represents
       * infinity (that is, the denominator is {@code 0}).</p>
       */
      public int getNumerator() {
          return mNumerator;
      }
  
      /**
       * Gets the denominator of the rational
       *
       * <p>The denominator may return {@code 0}, in which case the rational may represent
       * positive infinity (if the numerator was positive), negative infinity (if the numerator
       * was negative), or {@code NaN} (if the numerator was {@code 0}).</p>
       *
       * <p>The denominator will always return {@code 1} if the numerator is {@code 0}.
       */
      public int getDenominator() {
          return mDenominator;
      }
  
      /**
       * Indicates whether this rational is a <em>Not-a-Number (NaN)</em> value.
       *
       * <p>A {@code NaN} value occurs when both the numerator and the denominator are {@code 0}.</p>
       *
       * @return {@code true} if this rational is a <em>Not-a-Number (NaN)</em> value;
       *         {@code false} if this is a (potentially infinite) number value
       */
      public boolean isNaN() {
          return mDenominator == 0 && mNumerator == 0;
      }
  
      /**
       * Indicates whether this rational represents an infinite value.
       *
       * <p>An infinite value occurs when the denominator is {@code 0} (but the numerator is not).</p>
       *
       * @return {@code true} if this rational is a (positive or negative) infinite value;
       *         {@code false} if this is a finite number value (or {@code NaN})
       */
      public boolean isInfinite() {
          return mNumerator != 0 && mDenominator == 0;
      }
  
      /**
       * Indicates whether this rational represents a finite value.
       *
       * <p>A finite value occurs when the denominator is not {@code 0}; in other words
       * the rational is neither infinity or {@code NaN}.</p>
       *
       * @return {@code true} if this rational is a (positive or negative) infinite value;
       *         {@code false} if this is a finite number value (or {@code NaN})
       */
      public boolean isFinite() {
          return mDenominator != 0;
      }
  
      /**
       * Indicates whether this rational represents a zero value.
       *
       * <p>A zero value is a {@link #isFinite finite} rational with a numerator of {@code 0}.</p>
       *
       * @return {@code true} if this rational is finite zero value;
       *         {@code false} otherwise
       */
      public boolean isZero() {
          return isFinite() && mNumerator == 0;
      }
  
      private boolean isPosInf() {
          return mDenominator == 0 && mNumerator > 0;
      }
  
      private boolean isNegInf() {
          return mDenominator == 0 && mNumerator < 0;
      }
  
      /**
       * <p>Compare this Rational to another object and see if they are equal.</p>
       *
       * <p>A Rational object can only be equal to another Rational object (comparing against any
       * other type will return {@code false}).</p>
       *
       * <p>A Rational object is considered equal to another Rational object if and only if one of
       * the following holds:</p>
       * <ul><li>Both are {@code NaN}</li>
       *     <li>Both are infinities of the same sign</li>
       *     <li>Both have the same numerator and denominator in their reduced form</li>
       * </ul>
       *
       * <p>A reduced form of a Rational is calculated by dividing both the numerator and the
       * denominator by their greatest common divisor.</p>
       *
       * <pre>{@code
       * (new Rational(1, 2)).equals(new Rational(1, 2)) == true   // trivially true
       * (new Rational(2, 3)).equals(new Rational(1, 2)) == false  // trivially false
       * (new Rational(1, 2)).equals(new Rational(2, 4)) == true   // true after reduction
       * (new Rational(0, 0)).equals(new Rational(0, 0)) == true   // NaN.equals(NaN)
       * (new Rational(1, 0)).equals(new Rational(5, 0)) == true   // both are +infinity
       * (new Rational(1, 0)).equals(new Rational(-1, 0)) == false // +infinity != -infinity
       * }</pre>
       *
       * @param obj a reference to another object
       *
       * @return A boolean that determines whether or not the two Rational objects are equal.
       */
      @Override
      public boolean equals(Object obj) {
          return obj instanceof Rational && equals((Rational) obj);
      }
  
      private boolean equals(Rational other) {
          return (mNumerator == other.mNumerator && mDenominator == other.mDenominator);
      }
  
      /**
       * Return a string representation of this rational, e.g. {@code "1/2"}.
       *
       * <p>The following rules of conversion apply:
       * <ul>
       * <li>{@code NaN} values will return {@code "NaN"}
       * <li>Positive infinity values will return {@code "Infinity"}
       * <li>Negative infinity values will return {@code "-Infinity"}
       * <li>All other values will return {@code "numerator/denominator"} where {@code numerator}
       * and {@code denominator} are substituted with the appropriate numerator and denominator
       * values.
       * </ul></p>
       */
      @Override
      public String toString() {
          if (isNaN()) {
              return "NaN";
          } else if (isPosInf()) {
              return "Infinity";
          } else if (isNegInf()) {
              return "-Infinity";
          } else {
              return mNumerator + "/" + mDenominator;
          }
      }
  
      /**
       * <p>Convert to a floating point representation.</p>
       *
       * @return The floating point representation of this rational number.
       * @hide
       */
      public float toFloat() {
          // TODO: remove this duplicate function (used in CTS and the shim)
          return floatValue();
      }
  
      /**
       * {@inheritDoc}
       */
      @Override
      public int hashCode() {
          // Bias the hash code for the first (2^16) values for both numerator and denominator
          int numeratorFlipped = mNumerator << 16 | mNumerator >>> 16;
  
          return mDenominator ^ numeratorFlipped;
      }
  
      /**
       * Calculates the greatest common divisor using Euclid's algorithm.
       *
       * <p><em>Visible for testing only.</em></p>
       *
       * @param numerator the numerator in a fraction
       * @param denominator the denominator in a fraction
       *
       * @return An int value representing the gcd. Always positive.
       * @hide
       */
      public static int gcd(int numerator, int denominator) {
          /*
           * Non-recursive implementation of Euclid's algorithm:
           *
           *  gcd(a, 0) := a
           *  gcd(a, b) := gcd(b, a mod b)
           *
           */
          int a = numerator;
          int b = denominator;
  
          while (b != 0) {
              int oldB = b;
  
              b = a % b;
              a = oldB;
          }
  
          return Math.abs(a);
      }
  
      /**
       * Returns the value of the specified number as a {@code double}.
       *
       * <p>The {@code double} is calculated by converting both the numerator and denominator
       * to a {@code double}; then returning the result of dividing the numerator by the
       * denominator.</p>
       *
       * @return the divided value of the numerator and denominator as a {@code double}.
       */
      @Override
      public double doubleValue() {
          double num = mNumerator;
          double den = mDenominator;
  
          return num / den;
      }
  
      /**
       * Returns the value of the specified number as a {@code float}.
       *
       * <p>The {@code float} is calculated by converting both the numerator and denominator
       * to a {@code float}; then returning the result of dividing the numerator by the
       * denominator.</p>
       *
       * @return the divided value of the numerator and denominator as a {@code float}.
       */
      @Override
      public float floatValue() {
          float num = mNumerator;
          float den = mDenominator;
  
          return num / den;
      }
  
      /**
       * Returns the value of the specified number as a {@code int}.
       *
       * <p>{@link #isInfinite Finite} rationals are converted to an {@code int} value
       * by dividing the numerator by the denominator; conversion for non-finite values happens
       * identically to casting a floating point value to an {@code int}, in particular:
       *
       * <p>
       * <ul>
       * <li>Positive infinity saturates to the largest maximum integer
       * {@link Integer#MAX_VALUE}</li>
       * <li>Negative infinity saturates to the smallest maximum integer
       * {@link Integer#MIN_VALUE}</li>
       * <li><em>Not-A-Number (NaN)</em> returns {@code 0}.</li>
       * </ul>
       * </p>
       *
       * @return the divided value of the numerator and denominator as a {@code int}.
       */
      @Override
      public int intValue() {
          // Mimic float to int conversion rules from JLS 5.1.3
  
          if (isPosInf()) {
              return Integer.MAX_VALUE;
          } else if (isNegInf()) {
              return Integer.MIN_VALUE;
          } else if (isNaN()) {
              return 0;
          } else { // finite
              return mNumerator / mDenominator;
          }
      }
  
      /**
       * Returns the value of the specified number as a {@code long}.
       *
       * <p>{@link #isInfinite Finite} rationals are converted to an {@code long} value
       * by dividing the numerator by the denominator; conversion for non-finite values happens
       * identically to casting a floating point value to a {@code long}, in particular:
       *
       * <p>
       * <ul>
       * <li>Positive infinity saturates to the largest maximum long
       * {@link Long#MAX_VALUE}</li>
       * <li>Negative infinity saturates to the smallest maximum long
       * {@link Long#MIN_VALUE}</li>
       * <li><em>Not-A-Number (NaN)</em> returns {@code 0}.</li>
       * </ul>
       * </p>
       *
       * @return the divided value of the numerator and denominator as a {@code long}.
       */
      @Override
      public long longValue() {
          // Mimic float to long conversion rules from JLS 5.1.3
  
          if (isPosInf()) {
              return Long.MAX_VALUE;
          } else if (isNegInf()) {
              return Long.MIN_VALUE;
          } else if (isNaN()) {
              return 0;
          } else { // finite
              return mNumerator / mDenominator;
          }
      }
  
      /**
       * Returns the value of the specified number as a {@code short}.
       *
       * <p>{@link #isInfinite Finite} rationals are converted to a {@code short} value
       * identically to {@link #intValue}; the {@code int} result is then truncated to a
       * {@code short} before returning the value.</p>
       *
       * @return the divided value of the numerator and denominator as a {@code short}.
       */
      @Override
      public short shortValue() {
          return (short) intValue();
      }
  
      /**
       * Compare this rational to the specified rational to determine their natural order.
       *
       * <p>{@link #NaN} is considered to be equal to itself and greater than all other
       * {@code Rational} values. Otherwise, if the objects are not {@link #equals equal}, then
       * the following rules apply:</p>
       *
       * <ul>
       * <li>Positive infinity is greater than any other finite number (or negative infinity)
       * <li>Negative infinity is less than any other finite number (or positive infinity)
       * <li>The finite number represented by this rational is checked numerically
       * against the other finite number by converting both rationals to a common denominator multiple
       * and comparing their numerators.
       * </ul>
       *
       * @param another the rational to be compared
       *
       * @return a negative integer, zero, or a positive integer as this object is less than,
       *         equal to, or greater than the specified rational.
       *
       * @throws NullPointerException if {@code another} was {@code null}
       */
      @Override
      public int compareTo(Rational another) {
          checkNotNull(another, "another must not be null");
  
          if (equals(another)) {
              return 0;
          } else if (isNaN()) { // NaN is greater than the other non-NaN value
              return 1;
          } else if (another.isNaN()) { // the other NaN is greater than this non-NaN value
              return -1;
          } else if (isPosInf() || another.isNegInf()) {
              return 1; // positive infinity is greater than any non-NaN/non-posInf value
          } else if (isNegInf() || another.isPosInf()) {
              return -1; // negative infinity is less than any non-NaN/non-negInf value
          }
  
          // else both this and another are finite numbers
  
          // make the denominators the same, then compare numerators
          long thisNumerator = ((long)mNumerator) * another.mDenominator; // long to avoid overflow
          long otherNumerator = ((long)another.mNumerator) * mDenominator; // long to avoid overflow
  
          // avoid underflow from subtraction by doing comparisons
          if (thisNumerator < otherNumerator) {
              return -1;
          } else if (thisNumerator > otherNumerator) {
              return 1;
          } else {
              // This should be covered by #equals, but have this code path just in case
              return 0;
          }
      }
  
      /*
       * Serializable implementation.
       *
       * The following methods are omitted:
       * >> writeObject - the default is sufficient (field by field serialization)
       * >> readObjectNoData - the default is sufficient (0s for both fields is a NaN)
       */
  
      /**
       * writeObject with default serialized form - guards against
       * deserializing non-reduced forms of the rational.
       *
       * @throws InvalidObjectException if the invariants were violated
       */
      private void readObject(java.io.ObjectInputStream in)
              throws IOException, ClassNotFoundException {
          in.defaultReadObject();
  
          /*
           * Guard against trying to deserialize illegal values (in this case, ones
           * that don't have a standard reduced form).
           *
           * - Non-finite values must be one of [0, 1], [0, 0], [0, 1], [0, -1]
           * - Finite values must always have their greatest common divisor as 1
           */
  
          if (mNumerator == 0) { // either zero or NaN
              if (mDenominator == 1 || mDenominator == 0) {
                  return;
              }
              throw new InvalidObjectException(
                      "Rational must be deserialized from a reduced form for zero values");
          } else if (mDenominator == 0) { // either positive or negative infinity
              if (mNumerator == 1 || mNumerator == -1) {
                  return;
              }
              throw new InvalidObjectException(
                      "Rational must be deserialized from a reduced form for infinity values");
          } else { // finite value
              if (gcd(mNumerator, mDenominator) > 1) {
                  throw new InvalidObjectException(
                          "Rational must be deserialized from a reduced form for finite values");
              }
          }
      }
  
      private static NumberFormatException invalidRational(String s) {
          throw new NumberFormatException("Invalid Rational: \"" + s + "\"");
      }
  
      /**
       * Parses the specified string as a rational value.
       * <p>The ASCII characters {@code \}{@code u003a} (':') and
       * {@code \}{@code u002f} ('/') are recognized as separators between
       * the numerator and denumerator.</p>
       * <p>
       * For any {@code Rational r}: {@code Rational.parseRational(r.toString()).equals(r)}.
       * However, the method also handles rational numbers expressed in the
       * following forms:</p>
       * <p>
       * "<i>num</i>{@code /}<i>den</i>" or
       * "<i>num</i>{@code :}<i>den</i>" {@code => new Rational(num, den);},
       * where <i>num</i> and <i>den</i> are string integers potentially
       * containing a sign, such as "-10", "+7" or "5".</p>
       *
       * <pre>{@code
       * Rational.parseRational("3:+6").equals(new Rational(1, 2)) == true
       * Rational.parseRational("-3/-6").equals(new Rational(1, 2)) == true
       * Rational.parseRational("4.56") => throws NumberFormatException
       * }</pre>
       *
       * @param string the string representation of a rational value.
       * @return the rational value represented by {@code string}.
       *
       * @throws NumberFormatException if {@code string} cannot be parsed
       * as a rational value.
       * @throws NullPointerException if {@code string} was {@code null}
       */
      public static Rational parseRational(String string)
              throws NumberFormatException {
          checkNotNull(string, "string must not be null");
  
          if (string.equals("NaN")) {
              return NaN;
          } else if (string.equals("Infinity")) {
              return POSITIVE_INFINITY;
          } else if (string.equals("-Infinity")) {
              return NEGATIVE_INFINITY;
          }
  
          int sep_ix = string.indexOf(':');
          if (sep_ix < 0) {
              sep_ix = string.indexOf('/');
          }
          if (sep_ix < 0) {
              throw invalidRational(string);
          }
          try {
              return new Rational(Integer.parseInt(string.substring(0, sep_ix)),
                      Integer.parseInt(string.substring(sep_ix + 1)));
          } catch (NumberFormatException e) {
              throw invalidRational(string);
          }
      }
  }
  