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