| /* |
| * 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); |
| } |
| } |
| } |