1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package android.util; 17 18 import static com.android.internal.util.Preconditions.checkNotNull; 19 20 import android.annotation.Nullable; 21 import android.compat.annotation.UnsupportedAppUsage; 22 import android.os.Build; 23 24 import java.io.IOException; 25 import java.io.InvalidObjectException; 26 27 /** 28 * <p>An immutable data type representation a rational number.</p> 29 * 30 * <p>Contains a pair of {@code int}s representing the numerator and denominator of a 31 * Rational number. </p> 32 */ 33 // Exported to Mainline modules; cannot use annotations 34 // @android.ravenwood.annotation.RavenwoodKeepWholeClass 35 public final class Rational extends Number implements Comparable<Rational> { 36 /** 37 * Constant for the <em>Not-a-Number (NaN)</em> value of the {@code Rational} type. 38 * 39 * <p>A {@code NaN} value is considered to be equal to itself (that is {@code NaN.equals(NaN)} 40 * will return {@code true}; it is always greater than any non-{@code NaN} value (that is 41 * {@code NaN.compareTo(notNaN)} will return a number greater than {@code 0}).</p> 42 * 43 * <p>Equivalent to constructing a new rational with both the numerator and denominator 44 * equal to {@code 0}.</p> 45 */ 46 public static final Rational NaN = new Rational(0, 0); 47 48 /** 49 * Constant for the positive infinity value of the {@code Rational} type. 50 * 51 * <p>Equivalent to constructing a new rational with a positive numerator and a denominator 52 * equal to {@code 0}.</p> 53 */ 54 public static final Rational POSITIVE_INFINITY = new Rational(1, 0); 55 56 /** 57 * Constant for the negative infinity value of the {@code Rational} type. 58 * 59 * <p>Equivalent to constructing a new rational with a negative numerator and a denominator 60 * equal to {@code 0}.</p> 61 */ 62 public static final Rational NEGATIVE_INFINITY = new Rational(-1, 0); 63 64 /** 65 * Constant for the zero value of the {@code Rational} type. 66 * 67 * <p>Equivalent to constructing a new rational with a numerator equal to {@code 0} and 68 * any non-zero denominator.</p> 69 */ 70 public static final Rational ZERO = new Rational(0, 1); 71 72 /** 73 * Unique version number per class to be compliant with {@link java.io.Serializable}. 74 * 75 * <p>Increment each time the fields change in any way.</p> 76 */ 77 private static final long serialVersionUID = 1L; 78 79 /* 80 * Do not change the order of these fields or add new instance fields to maintain the 81 * Serializable compatibility across API revisions. 82 */ 83 @UnsupportedAppUsage(maxTargetSdk = Build.VERSION_CODES.R, trackingBug = 170729553) 84 private final int mNumerator; 85 @UnsupportedAppUsage(maxTargetSdk = Build.VERSION_CODES.R, trackingBug = 170729553) 86 private final int mDenominator; 87 88 /** 89 * <p>Create a {@code Rational} with a given numerator and denominator.</p> 90 * 91 * <p>The signs of the numerator and the denominator may be flipped such that the denominator 92 * is always positive. Both the numerator and denominator will be converted to their reduced 93 * forms (see {@link #equals} for more details).</p> 94 * 95 * <p>For example, 96 * <ul> 97 * <li>a rational of {@code 2/4} will be reduced to {@code 1/2}. 98 * <li>a rational of {@code 1/-1} will be flipped to {@code -1/1} 99 * <li>a rational of {@code 5/0} will be reduced to {@code 1/0} 100 * <li>a rational of {@code 0/5} will be reduced to {@code 0/1} 101 * </ul> 102 * </p> 103 * 104 * @param numerator the numerator of the rational 105 * @param denominator the denominator of the rational 106 * 107 * @see #equals 108 */ Rational(int numerator, int denominator)109 public Rational(int numerator, int denominator) { 110 111 if (denominator < 0) { 112 numerator = -numerator; 113 denominator = -denominator; 114 } 115 116 // Convert to reduced form 117 if (denominator == 0 && numerator > 0) { 118 mNumerator = 1; // +Inf 119 mDenominator = 0; 120 } else if (denominator == 0 && numerator < 0) { 121 mNumerator = -1; // -Inf 122 mDenominator = 0; 123 } else if (denominator == 0 && numerator == 0) { 124 mNumerator = 0; // NaN 125 mDenominator = 0; 126 } else if (numerator == 0) { 127 mNumerator = 0; 128 mDenominator = 1; 129 } else { 130 int gcd = gcd(numerator, denominator); 131 132 mNumerator = numerator / gcd; 133 mDenominator = denominator / gcd; 134 } 135 } 136 137 /** 138 * Gets the numerator of the rational. 139 * 140 * <p>The numerator will always return {@code 1} if this rational represents 141 * infinity (that is, the denominator is {@code 0}).</p> 142 */ getNumerator()143 public int getNumerator() { 144 return mNumerator; 145 } 146 147 /** 148 * Gets the denominator of the rational 149 * 150 * <p>The denominator may return {@code 0}, in which case the rational may represent 151 * positive infinity (if the numerator was positive), negative infinity (if the numerator 152 * was negative), or {@code NaN} (if the numerator was {@code 0}).</p> 153 * 154 * <p>The denominator will always return {@code 1} if the numerator is {@code 0}. 155 */ getDenominator()156 public int getDenominator() { 157 return mDenominator; 158 } 159 160 /** 161 * Indicates whether this rational is a <em>Not-a-Number (NaN)</em> value. 162 * 163 * <p>A {@code NaN} value occurs when both the numerator and the denominator are {@code 0}.</p> 164 * 165 * @return {@code true} if this rational is a <em>Not-a-Number (NaN)</em> value; 166 * {@code false} if this is a (potentially infinite) number value 167 */ isNaN()168 public boolean isNaN() { 169 return mDenominator == 0 && mNumerator == 0; 170 } 171 172 /** 173 * Indicates whether this rational represents an infinite value. 174 * 175 * <p>An infinite value occurs when the denominator is {@code 0} (but the numerator is not).</p> 176 * 177 * @return {@code true} if this rational is a (positive or negative) infinite value; 178 * {@code false} if this is a finite number value (or {@code NaN}) 179 */ isInfinite()180 public boolean isInfinite() { 181 return mNumerator != 0 && mDenominator == 0; 182 } 183 184 /** 185 * Indicates whether this rational represents a finite value. 186 * 187 * <p>A finite value occurs when the denominator is not {@code 0}; in other words 188 * the rational is neither infinity or {@code NaN}.</p> 189 * 190 * @return {@code true} if this rational is a (positive or negative) infinite value; 191 * {@code false} if this is a finite number value (or {@code NaN}) 192 */ isFinite()193 public boolean isFinite() { 194 return mDenominator != 0; 195 } 196 197 /** 198 * Indicates whether this rational represents a zero value. 199 * 200 * <p>A zero value is a {@link #isFinite finite} rational with a numerator of {@code 0}.</p> 201 * 202 * @return {@code true} if this rational is finite zero value; 203 * {@code false} otherwise 204 */ isZero()205 public boolean isZero() { 206 return isFinite() && mNumerator == 0; 207 } 208 isPosInf()209 private boolean isPosInf() { 210 return mDenominator == 0 && mNumerator > 0; 211 } 212 isNegInf()213 private boolean isNegInf() { 214 return mDenominator == 0 && mNumerator < 0; 215 } 216 217 /** 218 * <p>Compare this Rational to another object and see if they are equal.</p> 219 * 220 * <p>A Rational object can only be equal to another Rational object (comparing against any 221 * other type will return {@code false}).</p> 222 * 223 * <p>A Rational object is considered equal to another Rational object if and only if one of 224 * the following holds:</p> 225 * <ul><li>Both are {@code NaN}</li> 226 * <li>Both are infinities of the same sign</li> 227 * <li>Both have the same numerator and denominator in their reduced form</li> 228 * </ul> 229 * 230 * <p>A reduced form of a Rational is calculated by dividing both the numerator and the 231 * denominator by their greatest common divisor.</p> 232 * 233 * <pre>{@code 234 * (new Rational(1, 2)).equals(new Rational(1, 2)) == true // trivially true 235 * (new Rational(2, 3)).equals(new Rational(1, 2)) == false // trivially false 236 * (new Rational(1, 2)).equals(new Rational(2, 4)) == true // true after reduction 237 * (new Rational(0, 0)).equals(new Rational(0, 0)) == true // NaN.equals(NaN) 238 * (new Rational(1, 0)).equals(new Rational(5, 0)) == true // both are +infinity 239 * (new Rational(1, 0)).equals(new Rational(-1, 0)) == false // +infinity != -infinity 240 * }</pre> 241 * 242 * @param obj a reference to another object 243 * 244 * @return A boolean that determines whether or not the two Rational objects are equal. 245 */ 246 @Override equals(@ullable Object obj)247 public boolean equals(@Nullable Object obj) { 248 return obj instanceof Rational && equals((Rational) obj); 249 } 250 equals(Rational other)251 private boolean equals(Rational other) { 252 return (mNumerator == other.mNumerator && mDenominator == other.mDenominator); 253 } 254 255 /** 256 * Return a string representation of this rational, e.g. {@code "1/2"}. 257 * 258 * <p>The following rules of conversion apply: 259 * <ul> 260 * <li>{@code NaN} values will return {@code "NaN"} 261 * <li>Positive infinity values will return {@code "Infinity"} 262 * <li>Negative infinity values will return {@code "-Infinity"} 263 * <li>All other values will return {@code "numerator/denominator"} where {@code numerator} 264 * and {@code denominator} are substituted with the appropriate numerator and denominator 265 * values. 266 * </ul></p> 267 */ 268 @Override toString()269 public String toString() { 270 if (isNaN()) { 271 return "NaN"; 272 } else if (isPosInf()) { 273 return "Infinity"; 274 } else if (isNegInf()) { 275 return "-Infinity"; 276 } else { 277 return mNumerator + "/" + mDenominator; 278 } 279 } 280 281 /** 282 * <p>Convert to a floating point representation.</p> 283 * 284 * @return The floating point representation of this rational number. 285 * @hide 286 */ toFloat()287 public float toFloat() { 288 // TODO: remove this duplicate function (used in CTS and the shim) 289 return floatValue(); 290 } 291 292 /** 293 * {@inheritDoc} 294 */ 295 @Override hashCode()296 public int hashCode() { 297 // Bias the hash code for the first (2^16) values for both numerator and denominator 298 int numeratorFlipped = mNumerator << 16 | mNumerator >>> 16; 299 300 return mDenominator ^ numeratorFlipped; 301 } 302 303 /** 304 * Calculates the greatest common divisor using Euclid's algorithm. 305 * 306 * <p><em>Visible for testing only.</em></p> 307 * 308 * @param numerator the numerator in a fraction 309 * @param denominator the denominator in a fraction 310 * 311 * @return An int value representing the gcd. Always positive. 312 * @hide 313 */ gcd(int numerator, int denominator)314 public static int gcd(int numerator, int denominator) { 315 /* 316 * Non-recursive implementation of Euclid's algorithm: 317 * 318 * gcd(a, 0) := a 319 * gcd(a, b) := gcd(b, a mod b) 320 * 321 */ 322 int a = numerator; 323 int b = denominator; 324 325 while (b != 0) { 326 int oldB = b; 327 328 b = a % b; 329 a = oldB; 330 } 331 332 return Math.abs(a); 333 } 334 335 /** 336 * Returns the value of the specified number as a {@code double}. 337 * 338 * <p>The {@code double} is calculated by converting both the numerator and denominator 339 * to a {@code double}; then returning the result of dividing the numerator by the 340 * denominator.</p> 341 * 342 * @return the divided value of the numerator and denominator as a {@code double}. 343 */ 344 @Override doubleValue()345 public double doubleValue() { 346 double num = mNumerator; 347 double den = mDenominator; 348 349 return num / den; 350 } 351 352 /** 353 * Returns the value of the specified number as a {@code float}. 354 * 355 * <p>The {@code float} is calculated by converting both the numerator and denominator 356 * to a {@code float}; then returning the result of dividing the numerator by the 357 * denominator.</p> 358 * 359 * @return the divided value of the numerator and denominator as a {@code float}. 360 */ 361 @Override floatValue()362 public float floatValue() { 363 float num = mNumerator; 364 float den = mDenominator; 365 366 return num / den; 367 } 368 369 /** 370 * Returns the value of the specified number as a {@code int}. 371 * 372 * <p>{@link #isInfinite Finite} rationals are converted to an {@code int} value 373 * by dividing the numerator by the denominator; conversion for non-finite values happens 374 * identically to casting a floating point value to an {@code int}, in particular: 375 * 376 * <p> 377 * <ul> 378 * <li>Positive infinity saturates to the largest maximum integer 379 * {@link Integer#MAX_VALUE}</li> 380 * <li>Negative infinity saturates to the smallest maximum integer 381 * {@link Integer#MIN_VALUE}</li> 382 * <li><em>Not-A-Number (NaN)</em> returns {@code 0}.</li> 383 * </ul> 384 * </p> 385 * 386 * @return the divided value of the numerator and denominator as a {@code int}. 387 */ 388 @Override intValue()389 public int intValue() { 390 // Mimic float to int conversion rules from JLS 5.1.3 391 392 if (isPosInf()) { 393 return Integer.MAX_VALUE; 394 } else if (isNegInf()) { 395 return Integer.MIN_VALUE; 396 } else if (isNaN()) { 397 return 0; 398 } else { // finite 399 return mNumerator / mDenominator; 400 } 401 } 402 403 /** 404 * Returns the value of the specified number as a {@code long}. 405 * 406 * <p>{@link #isInfinite Finite} rationals are converted to an {@code long} value 407 * by dividing the numerator by the denominator; conversion for non-finite values happens 408 * identically to casting a floating point value to a {@code long}, in particular: 409 * 410 * <p> 411 * <ul> 412 * <li>Positive infinity saturates to the largest maximum long 413 * {@link Long#MAX_VALUE}</li> 414 * <li>Negative infinity saturates to the smallest maximum long 415 * {@link Long#MIN_VALUE}</li> 416 * <li><em>Not-A-Number (NaN)</em> returns {@code 0}.</li> 417 * </ul> 418 * </p> 419 * 420 * @return the divided value of the numerator and denominator as a {@code long}. 421 */ 422 @Override longValue()423 public long longValue() { 424 // Mimic float to long conversion rules from JLS 5.1.3 425 426 if (isPosInf()) { 427 return Long.MAX_VALUE; 428 } else if (isNegInf()) { 429 return Long.MIN_VALUE; 430 } else if (isNaN()) { 431 return 0; 432 } else { // finite 433 return mNumerator / mDenominator; 434 } 435 } 436 437 /** 438 * Returns the value of the specified number as a {@code short}. 439 * 440 * <p>{@link #isInfinite Finite} rationals are converted to a {@code short} value 441 * identically to {@link #intValue}; the {@code int} result is then truncated to a 442 * {@code short} before returning the value.</p> 443 * 444 * @return the divided value of the numerator and denominator as a {@code short}. 445 */ 446 @Override shortValue()447 public short shortValue() { 448 return (short) intValue(); 449 } 450 451 /** 452 * Compare this rational to the specified rational to determine their natural order. 453 * 454 * <p>{@link #NaN} is considered to be equal to itself and greater than all other 455 * {@code Rational} values. Otherwise, if the objects are not {@link #equals equal}, then 456 * the following rules apply:</p> 457 * 458 * <ul> 459 * <li>Positive infinity is greater than any other finite number (or negative infinity) 460 * <li>Negative infinity is less than any other finite number (or positive infinity) 461 * <li>The finite number represented by this rational is checked numerically 462 * against the other finite number by converting both rationals to a common denominator multiple 463 * and comparing their numerators. 464 * </ul> 465 * 466 * @param another the rational to be compared 467 * 468 * @return a negative integer, zero, or a positive integer as this object is less than, 469 * equal to, or greater than the specified rational. 470 * 471 * @throws NullPointerException if {@code another} was {@code null} 472 */ 473 @Override compareTo(Rational another)474 public int compareTo(Rational another) { 475 checkNotNull(another, "another must not be null"); 476 477 if (equals(another)) { 478 return 0; 479 } else if (isNaN()) { // NaN is greater than the other non-NaN value 480 return 1; 481 } else if (another.isNaN()) { // the other NaN is greater than this non-NaN value 482 return -1; 483 } else if (isPosInf() || another.isNegInf()) { 484 return 1; // positive infinity is greater than any non-NaN/non-posInf value 485 } else if (isNegInf() || another.isPosInf()) { 486 return -1; // negative infinity is less than any non-NaN/non-negInf value 487 } 488 489 // else both this and another are finite numbers 490 491 // make the denominators the same, then compare numerators 492 long thisNumerator = ((long)mNumerator) * another.mDenominator; // long to avoid overflow 493 long otherNumerator = ((long)another.mNumerator) * mDenominator; // long to avoid overflow 494 495 // avoid underflow from subtraction by doing comparisons 496 if (thisNumerator < otherNumerator) { 497 return -1; 498 } else if (thisNumerator > otherNumerator) { 499 return 1; 500 } else { 501 // This should be covered by #equals, but have this code path just in case 502 return 0; 503 } 504 } 505 506 /* 507 * Serializable implementation. 508 * 509 * The following methods are omitted: 510 * >> writeObject - the default is sufficient (field by field serialization) 511 * >> readObjectNoData - the default is sufficient (0s for both fields is a NaN) 512 */ 513 514 /** 515 * writeObject with default serialized form - guards against 516 * deserializing non-reduced forms of the rational. 517 * 518 * @throws InvalidObjectException if the invariants were violated 519 */ readObject(java.io.ObjectInputStream in)520 private void readObject(java.io.ObjectInputStream in) 521 throws IOException, ClassNotFoundException { 522 in.defaultReadObject(); 523 524 /* 525 * Guard against trying to deserialize illegal values (in this case, ones 526 * that don't have a standard reduced form). 527 * 528 * - Non-finite values must be one of [0, 1], [0, 0], [0, 1], [0, -1] 529 * - Finite values must always have their greatest common divisor as 1 530 */ 531 532 if (mNumerator == 0) { // either zero or NaN 533 if (mDenominator == 1 || mDenominator == 0) { 534 return; 535 } 536 throw new InvalidObjectException( 537 "Rational must be deserialized from a reduced form for zero values"); 538 } else if (mDenominator == 0) { // either positive or negative infinity 539 if (mNumerator == 1 || mNumerator == -1) { 540 return; 541 } 542 throw new InvalidObjectException( 543 "Rational must be deserialized from a reduced form for infinity values"); 544 } else { // finite value 545 if (gcd(mNumerator, mDenominator) > 1) { 546 throw new InvalidObjectException( 547 "Rational must be deserialized from a reduced form for finite values"); 548 } 549 } 550 } 551 invalidRational(String s)552 private static NumberFormatException invalidRational(String s) { 553 throw new NumberFormatException("Invalid Rational: \"" + s + "\""); 554 } 555 556 /** 557 * Parses the specified string as a rational value. 558 * <p>The ASCII characters {@code \}{@code u003a} (':') and 559 * {@code \}{@code u002f} ('/') are recognized as separators between 560 * the numerator and denumerator.</p> 561 * <p> 562 * For any {@code Rational r}: {@code Rational.parseRational(r.toString()).equals(r)}. 563 * However, the method also handles rational numbers expressed in the 564 * following forms:</p> 565 * <p> 566 * "<i>num</i>{@code /}<i>den</i>" or 567 * "<i>num</i>{@code :}<i>den</i>" {@code => new Rational(num, den);}, 568 * where <i>num</i> and <i>den</i> are string integers potentially 569 * containing a sign, such as "-10", "+7" or "5".</p> 570 * 571 * <pre>{@code 572 * Rational.parseRational("3:+6").equals(new Rational(1, 2)) == true 573 * Rational.parseRational("-3/-6").equals(new Rational(1, 2)) == true 574 * Rational.parseRational("4.56") => throws NumberFormatException 575 * }</pre> 576 * 577 * @param string the string representation of a rational value. 578 * @return the rational value represented by {@code string}. 579 * 580 * @throws NumberFormatException if {@code string} cannot be parsed 581 * as a rational value. 582 * @throws NullPointerException if {@code string} was {@code null} 583 */ parseRational(String string)584 public static Rational parseRational(String string) 585 throws NumberFormatException { 586 checkNotNull(string, "string must not be null"); 587 588 if (string.equals("NaN")) { 589 return NaN; 590 } else if (string.equals("Infinity")) { 591 return POSITIVE_INFINITY; 592 } else if (string.equals("-Infinity")) { 593 return NEGATIVE_INFINITY; 594 } 595 596 int sep_ix = string.indexOf(':'); 597 if (sep_ix < 0) { 598 sep_ix = string.indexOf('/'); 599 } 600 if (sep_ix < 0) { 601 throw invalidRational(string); 602 } 603 try { 604 return new Rational(Integer.parseInt(string.substring(0, sep_ix)), 605 Integer.parseInt(string.substring(sep_ix + 1))); 606 } catch (NumberFormatException e) { 607 throw invalidRational(string); 608 } 609 } 610 } 611