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