From 007bfb14d2d720cdd699cfbb36ce206246901cef Mon Sep 17 00:00:00 2001 From: Igor Murashkin Date: Thu, 5 Jun 2014 18:02:22 -0700 Subject: util: Make Rational a Number/Comparable; add Range#inRange * Also changes Rational to reduce the numerator/denominator by its greatest common divisor at construction time (e.g. (2/4 -> 1/2)). Bug: 15432042 Change-Id: Ib827abccf44a040667e5931cf9442afc86b57e2d --- core/java/android/util/Range.java | 30 ++- core/java/android/util/Rational.java | 457 ++++++++++++++++++++++++++++++----- 2 files changed, 422 insertions(+), 65 deletions(-) (limited to 'core/java/android') diff --git a/core/java/android/util/Range.java b/core/java/android/util/Range.java index d7e8cf0..3907e77 100644 --- a/core/java/android/util/Range.java +++ b/core/java/android/util/Range.java @@ -97,6 +97,27 @@ public final class Range> { } /** + * Checks if the {@code value} is within the bounds of this range. + * + *

A value is considered to be within this range if it's {@code >=} then + * the lower endpoint and {@code <=} to the upper endpoint (using the {@link Comparable} + * interface.

+ * + * @param value a non-{@code null} {@code T} reference + * @return {@code true} if the value is within this inclusive range, {@code false} otherwise + * + * @throws NullPointerException if {@code value} was {@code null} + */ + public boolean inRange(T value) { + checkNotNull(value, "value must not be null"); + + boolean gteLower = value.compareTo(mLower) >= 0; + boolean lteUpper = value.compareTo(mUpper) <= 0; + + return gteLower && lteUpper; + } + + /** * Compare two ranges for equality. * *

A range is considered equal if and only if both the lower and upper endpoints @@ -105,16 +126,13 @@ public final class Range> { * @return {@code true} if the ranges are equal, {@code false} otherwise */ @Override - public boolean equals(final Object obj) { + public boolean equals(Object obj) { if (obj == null) { return false; - } - if (this == obj) { + } else if (this == obj) { return true; - } - if (obj instanceof Range) { + } else if (obj instanceof Range) { @SuppressWarnings("rawtypes") - final Range other = (Range) obj; return mLower.equals(other.mLower) && mUpper.equals(other.mUpper); } diff --git a/core/java/android/util/Rational.java b/core/java/android/util/Rational.java index 8d4c67f..9952859 100644 --- a/core/java/android/util/Rational.java +++ b/core/java/android/util/Rational.java @@ -15,29 +15,88 @@ */ package android.util; +import static com.android.internal.util.Preconditions.*; + +import java.io.IOException; +import java.io.InvalidObjectException; + /** *

An immutable data type representation a rational number.

* *

Contains a pair of {@code int}s representing the numerator and denominator of a * Rational number.

*/ -public final class Rational { +public final class Rational extends Number implements Comparable { + /** + * Constant for the Not-a-Number (NaN) value of the {@code Rational} type. + * + *

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}).

+ * + *

Equivalent to constructing a new rational with both the numerator and denominator + * equal to {@code 0}.

+ */ + public static final Rational NaN = new Rational(0, 0); + + /** + * Constant for the positive infinity value of the {@code Rational} type. + * + *

Equivalent to constructing a new rational with a positive numerator and a denominator + * equal to {@code 0}.

+ */ + public static final Rational POSITIVE_INFINITY = new Rational(1, 0); + + /** + * Constant for the negative infinity value of the {@code Rational} type. + * + *

Equivalent to constructing a new rational with a negative numerator and a denominator + * equal to {@code 0}.

+ */ + public static final Rational NEGATIVE_INFINITY = new Rational(-1, 0); + + /** + * Constant for the zero value of the {@code Rational} type. + * + *

Equivalent to constructing a new rational with a numerator equal to {@code 0} and + * any non-zero denominator.

+ */ + public static final Rational ZERO = new Rational(0, 1); + + /** + * Unique version number per class to be compliant with {@link java.io.Serializable}. + * + *

Increment each time the fields change in any way.

+ */ + 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. + */ private final int mNumerator; private final int mDenominator; /** - *

Create a Rational with a given numerator and denominator.

+ *

Create a {@code Rational} with a given numerator and denominator.

* *

The signs of the numerator and the denominator may be flipped such that the denominator - * is always positive.

+ * is always positive. Both the numerator and denominator will be converted to their reduced + * forms (see {@link #equals} for more details).

* - *

A rational value with a 0-denominator may be constructed, but will have similar semantics - * as float {@code NaN} and {@code INF} values. For {@code NaN}, - * both {@link #getNumerator} and {@link #getDenominator} functions will return 0. For - * positive or negative {@code INF}, only the {@link #getDenominator} will return 0.

+ *

For example, + *

    + *
  • a rational of {@code 2/4} will be reduced to {@code 1/2}. + *
  • a rational of {@code 1/-1} will be flipped to {@code -1/1} + *
  • a rational of {@code 5/0} will be reduced to {@code 1/0} + *
  • a rational of {@code 0/5} will be reduced to {@code 0/1} + *
+ *

* * @param numerator the numerator of the rational * @param denominator the denominator of the rational + * + * @see #equals */ public Rational(int numerator, int denominator) { @@ -46,32 +105,100 @@ public final class Rational { denominator = -denominator; } - mNumerator = numerator; - mDenominator = 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. + * + *

The numerator will always return {@code 1} if this rational represents + * infinity (that is, the denominator is {@code 0}).

*/ public int getNumerator() { - if (mDenominator == 0) { - return 0; - } return mNumerator; } /** * Gets the denominator of the rational + * + *

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}).

+ * + *

The denominator will always return {@code 1} if the numerator is {@code 0}. */ public int getDenominator() { return mDenominator; } - private boolean isNaN() { + /** + * Indicates whether this rational is a Not-a-Number (NaN) value. + * + *

A {@code NaN} value occurs when both the numerator and the denominator are {@code 0}.

+ * + * @return {@code true} if this rational is a Not-a-Number (NaN) value; + * {@code false} if this is a (potentially infinite) number value + */ + public boolean isNaN() { return mDenominator == 0 && mNumerator == 0; } - private boolean isInf() { + /** + * Indicates whether this rational represents an infinite value. + * + *

An infinite value occurs when the denominator is {@code 0} (but the numerator is not).

+ * + * @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. + * + *

A finite value occurs when the denominator is not {@code 0}; in other words + * the rational is neither infinity or {@code NaN}.

+ * + * @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. + * + *

A zero value is a {@link #isFinite finite} rational with a numerator of {@code 0}.

+ * + * @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; } @@ -82,12 +209,12 @@ public final class Rational { /** *

Compare this Rational to another object and see if they are equal.

* - *

A Rational object can only be equal to another Rational object (comparing against any other - * type will return false).

+ *

A Rational object can only be equal to another Rational object (comparing against any + * other type will return {@code false}).

* *

A Rational object is considered equal to another Rational object if and only if one of - * the following holds

: - *
  • Both are NaN
    • + * the following holds:

    + *
    • Both are {@code NaN}
      • *
    • Both are infinities of the same sign
      • *
    • Both have the same numerator and denominator in their reduced form
      • *
    @@ -96,12 +223,12 @@ public final class Rational { * denominator by their greatest common divisor.

    * * 
    {@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
+     * (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
      * }
    * * @param obj a reference to another object @@ -110,41 +237,31 @@ public final class Rational { */ @Override public boolean equals(Object obj) { - if (obj == null) { - return false; - } else if (obj instanceof Rational) { - Rational other = (Rational) obj; - if (mDenominator == 0 || other.mDenominator == 0) { - if (isNaN() && other.isNaN()) { - return true; - } else if (isInf() && other.isInf() || isNegInf() && other.isNegInf()) { - return true; - } else { - return false; - } - } else if (mNumerator == other.mNumerator && mDenominator == other.mDenominator) { - return true; - } else { - int thisGcd = gcd(); - int otherGcd = other.gcd(); - - int thisNumerator = mNumerator / thisGcd; - int thisDenominator = mDenominator / thisGcd; - - int otherNumerator = other.mNumerator / otherGcd; - int otherDenominator = other.mDenominator / otherGcd; - - return (thisNumerator == otherNumerator && thisDenominator == otherDenominator); - } - } - return false; + 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"}. + * + *

    The following rules of conversion apply: + *

      + *
    • {@code NaN} values will return {@code "NaN"} + *
    • Positive infinity values will return {@code "Infinity"} + *
    • Negative infinity values will return {@code "-Infinity"} + *
    • All other values will return {@code "numerator/denominator"} where {@code numerator} + * and {@code denominator} are substituted with the appropriate numerator and denominator + * values. + *

    + */ @Override public String toString() { if (isNaN()) { return "NaN"; - } else if (isInf()) { + } else if (isPosInf()) { return "Infinity"; } else if (isNegInf()) { return "-Infinity"; @@ -160,7 +277,8 @@ public final class Rational { * @hide */ public float toFloat() { - return (float) mNumerator / (float) mDenominator; + // TODO: remove this duplicate function (used in CTS and the shim) + return floatValue(); } /** @@ -177,20 +295,24 @@ public final class Rational { /** * Calculates the greatest common divisor using Euclid's algorithm. * + *

    Visible for testing only.

    + * + * @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 int gcd() { - /** + 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 = mNumerator; - int b = mDenominator; + int a = numerator; + int b = denominator; while (b != 0) { int oldB = b; @@ -201,4 +323,221 @@ public final class Rational { return Math.abs(a); } + + /** + * Returns the value of the specified number as a {@code double}. + * + *

    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.

    + * + * @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}. + * + *

    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.

    + * + * @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}. + * + *

    {@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: + * + *

    + *

      + *
    • Positive infinity saturates to the largest maximum integer + * {@link Integer#MAX_VALUE}
      • + *
    • Negative infinity saturates to the smallest maximum integer + * {@link Integer#MIN_VALUE}
      • + *
    • Not-A-Number (NaN) returns {@code 0}.
      • + *
    + *

    + * + * @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}. + * + *

    {@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: + * + *

    + *

      + *
    • Positive infinity saturates to the largest maximum long + * {@link Long#MAX_VALUE}
      • + *
    • Negative infinity saturates to the smallest maximum long + * {@link Long#MIN_VALUE}
      • + *
    • Not-A-Number (NaN) returns {@code 0}.
      • + *
    + *

    + * + * @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}. + * + *

    {@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.

    + * + * @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. + * + *

    {@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:

    + * + *
      + *
    • Positive infinity is greater than any other finite number (or negative infinity) + *
    • Negative infinity is less than any other finite number (or positive infinity) + *
    • 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. + *
    + * + * @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"); + } + } + } } -- cgit v1.1