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