Rational.java revision 72f9f0a96e4476ef231d5001cb30521ad4ce5b1e 
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
18/**
19 * <p>An immutable data type representation a rational number.</p>
20 *
21 * <p>Contains a pair of {@code int}s representing the numerator and denominator of a
22 * Rational number. </p>
23 */
24public final class Rational {
25    private final int mNumerator;
26    private final int mDenominator;
27
28    /**
29     * <p>Create a Rational with a given numerator and denominator.</p>
30     *
31     * <p>The signs of the numerator and the denominator may be flipped such that the denominator
32     * is always positive.</p>
33     *
34     * <p>A rational value with a 0-denominator may be constructed, but will have similar semantics
35     * as float {@code NaN} and {@code INF} values. For {@code NaN},
36     * both {@link #getNumerator} and {@link #getDenominator} functions will return 0. For
37     * positive or negative {@code INF}, only the {@link #getDenominator} will return 0.</p>
38     *
39     * @param numerator the numerator of the rational
40     * @param denominator the denominator of the rational
41     */
42    public Rational(int numerator, int denominator) {
43
44        if (denominator < 0) {
45            numerator = -numerator;
46            denominator = -denominator;
47        }
48
49        mNumerator = numerator;
50        mDenominator = denominator;
51    }
52
53    /**
54     * Gets the numerator of the rational.
55     */
56    public int getNumerator() {
57        if (mDenominator == 0) {
58            return 0;
59        }
60        return mNumerator;
61    }
62
63    /**
64     * Gets the denominator of the rational
65     */
66    public int getDenominator() {
67        return mDenominator;
68    }
69
70    private boolean isNaN() {
71        return mDenominator == 0 && mNumerator == 0;
72    }
73
74    private boolean isInf() {
75        return mDenominator == 0 && mNumerator > 0;
76    }
77
78    private boolean isNegInf() {
79        return mDenominator == 0 && mNumerator < 0;
80    }
81
82    /**
83     * <p>Compare this Rational to another object and see if they are equal.</p>
84     *
85     * <p>A Rational object can only be equal to another Rational object (comparing against any other
86     * type will return false).</p>
87     *
88     * <p>A Rational object is considered equal to another Rational object if and only if one of
89     * the following holds</p>:
90     * <ul><li>Both are NaN</li>
91     *     <li>Both are infinities of the same sign</li>
92     *     <li>Both have the same numerator and denominator in their reduced form</li>
93     * </ul>
94     *
95     * <p>A reduced form of a Rational is calculated by dividing both the numerator and the
96     * denominator by their greatest common divisor.</p>
97     *
98     * <pre>{@code
99     *      (new Rational(1, 2)).equals(new Rational(1, 2)) == true   // trivially true
100     *      (new Rational(2, 3)).equals(new Rational(1, 2)) == false  // trivially false
101     *      (new Rational(1, 2)).equals(new Rational(2, 4)) == true   // true after reduction
102     *      (new Rational(0, 0)).equals(new Rational(0, 0)) == true   // NaN.equals(NaN)
103     *      (new Rational(1, 0)).equals(new Rational(5, 0)) == true   // both are +infinity
104     *      (new Rational(1, 0)).equals(new Rational(-1, 0)) == false // +infinity != -infinity
105     * }</pre>
106     *
107     * @param obj a reference to another object
108     *
109     * @return A boolean that determines whether or not the two Rational objects are equal.
110     */
111    @Override
112    public boolean equals(Object obj) {
113        if (obj == null) {
114            return false;
115        } else if (obj instanceof Rational) {
116            Rational other = (Rational) obj;
117            if (mDenominator == 0 || other.mDenominator == 0) {
118                if (isNaN() && other.isNaN()) {
119                    return true;
120                } else if (isInf() && other.isInf() || isNegInf() && other.isNegInf()) {
121                    return true;
122                } else {
123                    return false;
124                }
125            } else if (mNumerator == other.mNumerator && mDenominator == other.mDenominator) {
126                return true;
127            } else {
128                int thisGcd = gcd();
129                int otherGcd = other.gcd();
130
131                int thisNumerator = mNumerator / thisGcd;
132                int thisDenominator = mDenominator / thisGcd;
133
134                int otherNumerator = other.mNumerator / otherGcd;
135                int otherDenominator = other.mDenominator / otherGcd;
136
137                return (thisNumerator == otherNumerator && thisDenominator == otherDenominator);
138            }
139        }
140        return false;
141    }
142
143    @Override
144    public String toString() {
145        if (isNaN()) {
146            return "NaN";
147        } else if (isInf()) {
148            return "Infinity";
149        } else if (isNegInf()) {
150            return "-Infinity";
151        } else {
152            return mNumerator + "/" + mDenominator;
153        }
154    }
155
156    /**
157     * <p>Convert to a floating point representation.</p>
158     *
159     * @return The floating point representation of this rational number.
160     * @hide
161     */
162    public float toFloat() {
163        return (float) mNumerator / (float) mDenominator;
164    }
165
166    /**
167     * {@inheritDoc}
168     */
169    @Override
170    public int hashCode() {
171        // Bias the hash code for the first (2^16) values for both numerator and denominator
172        int numeratorFlipped = mNumerator << 16 | mNumerator >>> 16;
173
174        return mDenominator ^ numeratorFlipped;
175    }
176
177    /**
178     * Calculates the greatest common divisor using Euclid's algorithm.
179     *
180     * @return An int value representing the gcd. Always positive.
181     * @hide
182     */
183    public int gcd() {
184        /**
185         * Non-recursive implementation of Euclid's algorithm:
186         *
187         *  gcd(a, 0) := a
188         *  gcd(a, b) := gcd(b, a mod b)
189         *
190         */
191
192        int a = mNumerator;
193        int b = mDenominator;
194
195        while (b != 0) {
196            int oldB = b;
197
198            b = a % b;
199            a = oldB;
200        }
201
202        return Math.abs(a);
203    }
204}
205