001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.imaging.common;
018
019import java.text.NumberFormat;
020
021/**
022 * Rational number, as used by the TIFF image format.
023 * <p>
024 * The TIFF format specifies two data types for rational numbers based on a pair of 32-bit integers. Rational is based on unsigned 32-bit integers and SRational
025 * is based on signed 32-bit integers. This treatment is problematic in Java because Java does not support unsigned types. To address this challenge, this class
026 * stores the numerator and divisor in long (64-bit) integers, applying masks as necessary for the unsigned type.
027 */
028public class RationalNumber extends Number {
029
030    private static final class Option {
031        public static Option factory(final RationalNumber rationalNumber, final double value) {
032            return new Option(rationalNumber, Math.abs(rationalNumber.doubleValue() - value));
033        }
034
035        public final RationalNumber rationalNumber;
036
037        public final double error;
038
039        private Option(final RationalNumber rationalNumber, final double error) {
040            this.rationalNumber = rationalNumber;
041            this.error = error;
042        }
043
044        @Override
045        public String toString() {
046            return rationalNumber.toString();
047        }
048    }
049
050    private static final long serialVersionUID = -1;
051
052    // int-precision tolerance
053    private static final double TOLERANCE = 1E-8;
054    public static final int SHALLOW_SIZE = 32;
055
056    static RationalNumber factoryMethod(long n, long d) {
057        // safer than constructor - handles values outside min/max range.
058        // also does some simple finding of common denominators.
059
060        if (n > Integer.MAX_VALUE || n < Integer.MIN_VALUE || d > Integer.MAX_VALUE || d < Integer.MIN_VALUE) {
061            while ((n > Integer.MAX_VALUE || n < Integer.MIN_VALUE || d > Integer.MAX_VALUE || d < Integer.MIN_VALUE) && Math.abs(n) > 1 && Math.abs(d) > 1) {
062                // brutal, imprecise truncation =(
063                // use the sign-preserving right shift operator.
064                n >>= 1;
065                d >>= 1;
066            }
067
068            if (d == 0) {
069                throw new NumberFormatException("Invalid value, numerator: " + n + ", divisor: " + d);
070            }
071        }
072
073        final long gcd = gcd(n, d);
074        d /= gcd;
075        n /= gcd;
076
077        return new RationalNumber((int) n, (int) d);
078    }
079
080    /**
081     * Gets the greatest common divisor
082     */
083    private static long gcd(final long a, final long b) {
084        if (b == 0) {
085            return a;
086        }
087        return gcd(b, a % b);
088    }
089
090    /**
091     * Calculate rational number using successive approximations.
092     *
093     * @param value rational number double value
094     * @return the RationalNumber representation of the double value
095     */
096    public static RationalNumber valueOf(double value) {
097        if (value >= Integer.MAX_VALUE) {
098            return new RationalNumber(Integer.MAX_VALUE, 1);
099        }
100        if (value <= -Integer.MAX_VALUE) {
101            return new RationalNumber(-Integer.MAX_VALUE, 1);
102        }
103
104        boolean negative = false;
105        if (value < 0) {
106            negative = true;
107            value = Math.abs(value);
108        }
109
110        RationalNumber l;
111        RationalNumber h;
112
113        if (value == 0) {
114            return new RationalNumber(0, 1);
115        }
116        if (value >= 1) {
117            final int approx = (int) value;
118            if (approx < value) {
119                l = new RationalNumber(approx, 1);
120                h = new RationalNumber(approx + 1, 1);
121            } else {
122                l = new RationalNumber(approx - 1, 1);
123                h = new RationalNumber(approx, 1);
124            }
125        } else {
126            final int approx = (int) (1.0 / value);
127            if (1.0 / approx < value) {
128                l = new RationalNumber(1, approx);
129                h = new RationalNumber(1, approx - 1);
130            } else {
131                l = new RationalNumber(1, approx + 1);
132                h = new RationalNumber(1, approx);
133            }
134        }
135        Option low = Option.factory(l, value);
136        Option high = Option.factory(h, value);
137
138        Option bestOption = low.error < high.error ? low : high;
139
140        final int maxIterations = 100; // value is quite high, actually.
141                                       // shouldn't matter.
142        for (int count = 0; bestOption.error > TOLERANCE && count < maxIterations; count++) {
143            final RationalNumber mediant = RationalNumber.factoryMethod(low.rationalNumber.numerator + high.rationalNumber.numerator,
144                    low.rationalNumber.divisor + high.rationalNumber.divisor);
145            final Option mediantOption = Option.factory(mediant, value);
146
147            if (value < mediant.doubleValue()) {
148                if (high.error <= mediantOption.error) {
149                    break;
150                }
151
152                high = mediantOption;
153            } else {
154                if (low.error <= mediantOption.error) {
155                    break;
156                }
157
158                low = mediantOption;
159            }
160
161            if (mediantOption.error < bestOption.error) {
162                bestOption = mediantOption;
163            }
164        }
165
166        return negative ? bestOption.rationalNumber.negate() : bestOption.rationalNumber;
167    }
168
169    // The TIFF and EXIF specifications call for the use
170    // of 32 bit unsigned integers. Since Java does not have an
171    // unsigned type, this class widens the type to long in order
172    // to avoid unintended negative numbers.
173    public final long numerator;
174
175    public final long divisor;
176
177    public final boolean unsignedType;
178
179    /**
180     * Constructs an instance based on signed integers
181     *
182     * @param numerator a 32-bit signed integer
183     * @param divisor   a non-zero 32-bit signed integer
184     */
185    public RationalNumber(final int numerator, final int divisor) {
186        this.numerator = numerator;
187        this.divisor = divisor;
188        this.unsignedType = false;
189    }
190
191    /**
192     * Constructs an instance supports either signed or unsigned integers.
193     *
194     * @param numerator    a numerator in the indicated form (signed or unsigned)
195     * @param divisor      a non-zero divisor in the indicated form (signed or unsigned)
196     * @param unsignedType indicates whether the input values are to be treated as unsigned.
197     */
198    public RationalNumber(final int numerator, final int divisor, final boolean unsignedType) {
199        this.unsignedType = unsignedType;
200        if (unsignedType) {
201            this.numerator = numerator & 0xffffffffL;
202            this.divisor = divisor & 0xffffffffL;
203        } else {
204            this.numerator = numerator;
205            this.divisor = divisor;
206        }
207    }
208
209    /**
210     * A private constructor for methods such as negate() that create instances of this class using the content of the current instance.
211     *
212     * @param numerator    a valid numerator
213     * @param divisor      a valid denominator
214     * @param unsignedType indicates how numerator and divisor values are to be interpreted.
215     */
216    private RationalNumber(final long numerator, final long divisor, final boolean unsignedType) {
217        this.numerator = numerator;
218        this.divisor = divisor;
219        this.unsignedType = unsignedType;
220    }
221
222    @Override
223    public double doubleValue() {
224        return (double) numerator / (double) divisor;
225    }
226
227    @Override
228    public float floatValue() {
229        // The computation uses double value in order to preserve
230        // as much of the precision of the source numerator and denominator
231        // as possible. Note that the expression
232        // return (float)numerator/(float) denominator
233        // could lose precision since a Java float only carries 24 bits
234        // of precision while an integer carries 32.
235        return (float) doubleValue();
236    }
237
238    @Override
239    public int intValue() {
240        return (int) (numerator / divisor);
241    }
242
243    @Override
244    public long longValue() {
245        return numerator / divisor;
246    }
247
248    /**
249     * Negates the value of the RationalNumber. If the numerator of this instance has its high-order bit set, then its value is too large to be treated as a
250     * Java 32-bit signed integer. In such a case, the only way that a RationalNumber instance can be negated is to divide both terms by a common divisor, if a
251     * non-zero common divisor exists. However, if no such divisor exists, there is no numerically correct way to perform the negation. When a negation cannot
252     * be performed correctly, this method throws an unchecked exception.
253     *
254     * @return a valid instance with a negated value.
255     */
256    public RationalNumber negate() {
257        long n = numerator;
258        long d = divisor;
259        if (unsignedType) {
260            // An instance of an unsigned type can be negated if and only if
261            // its high-order bit (the sign bit) is clear. If the bit is set,
262            // the value will be too large to convert to a signed type.
263            // In such a case it is necessary to adjust the numerator and denominator
264            // by their greatest common divisor (gcd), if one exists.
265            // If no non-zero common divisor exists, an exception is thrown.
266            if (n >> 31 == 1) {
267                // the unsigned value is so large that the high-order bit is set
268                // it cannot be converted to a negative number. Check to see
269                // whether there is an option to reduce its magnitude.
270                final long g = gcd(numerator, divisor);
271                if (g != 0) {
272                    n /= g;
273                    d /= g;
274                }
275                if (n >> 31 == 1) {
276                    throw new NumberFormatException("Unsigned numerator is too large to negate " + numerator);
277                }
278            }
279        }
280        return new RationalNumber(-n, d, false);
281    }
282
283    public String toDisplayString() {
284        if (numerator % divisor == 0) {
285            return Long.toString(numerator / divisor);
286        }
287        final NumberFormat nf = NumberFormat.getInstance();
288        nf.setMaximumFractionDigits(3);
289        return nf.format((double) numerator / (double) divisor);
290    }
291
292    @Override
293    public String toString() {
294        if (divisor == 0) {
295            return "Invalid rational (" + numerator + "/" + divisor + ")";
296        }
297        final NumberFormat nf = NumberFormat.getInstance();
298
299        if (numerator % divisor == 0) {
300            return nf.format(numerator / divisor);
301        }
302        return numerator + "/" + divisor + " (" + nf.format((double) numerator / divisor) + ")";
303    }
304
305}