    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 */
    024public class RationalNumber extends Number {
    025
    026    private static final long serialVersionUID = -8412262656468158691L;
    027
    028    // int-precision tolerance
    029    private static final double TOLERANCE = 1E-8;
    030
    031    public final int numerator;
    032    public final int divisor;
    033
    034    public RationalNumber(final int numerator, final int divisor) {
    035        this.numerator = numerator;
    036        this.divisor = divisor;
    037    }
    038
    039    static RationalNumber factoryMethod(long n, long d) {
    040        // safer than constructor - handles values outside min/max range.
    041        // also does some simple finding of common denominators.
    042
    043        if (n > Integer.MAX_VALUE || n < Integer.MIN_VALUE
    044                || d > Integer.MAX_VALUE || d < Integer.MIN_VALUE) {
    045            while ((n > Integer.MAX_VALUE || n < Integer.MIN_VALUE
    046                    || d > Integer.MAX_VALUE || d < Integer.MIN_VALUE)
    047                    && (Math.abs(n) > 1) && (Math.abs(d) > 1)) {
    048                // brutal, imprecise truncation =(
    049                // use the sign-preserving right shift operator.
    050                n >>= 1;
    051                d >>= 1;
    052            }
    053
    054            if (d == 0) {
    055                throw new NumberFormatException("Invalid value, numerator: " + n + ", divisor: " + d);
    056            }
    057        }
    058
    059        final long gcd = gcd(n, d);
    060        d = d / gcd;
    061        n = n / gcd;
    062
    063        return new RationalNumber((int) n, (int) d);
    064    }
    065
    066    /**
    067     * Return the greatest common divisor
    068     */
    069    private static long gcd(final long a, final long b) {
    070        if (b == 0) {
    071            return a;
    072        } else {
    073            return gcd(b, a % b);
    074        }
    075    }
    076
    077    public RationalNumber negate() {
    078        return new RationalNumber(-numerator, divisor);
    079    }
    080
    081    @Override
    082    public double doubleValue() {
    083        return (double) numerator / (double) divisor;
    084    }
    085
    086    @Override
    087    public float floatValue() {
    088        return (float) numerator / (float) divisor;
    089    }
    090
    091    @Override
    092    public int intValue() {
    093        return numerator / divisor;
    094    }
    095
    096    @Override
    097    public long longValue() {
    098        return (long) numerator / (long) divisor;
    099    }
    100
    101    @Override
    102    public String toString() {
    103        if (divisor == 0) {
    104            return "Invalid rational (" + numerator + "/" + divisor + ")";
    105        }
    106        final NumberFormat nf = NumberFormat.getInstance();
    107
    108        if ((numerator % divisor) == 0) {
    109            return nf.format(numerator / divisor);
    110        }
    111        return numerator + "/" + divisor + " (" + nf.format((double) numerator / divisor) + ")";
    112    }
    113
    114    public String toDisplayString() {
    115        if ((numerator % divisor) == 0) {
    116            return Integer.toString(numerator / divisor);
    117        }
    118        final NumberFormat nf = NumberFormat.getInstance();
    119        nf.setMaximumFractionDigits(3);
    120        return nf.format((double) numerator / (double) divisor);
    121    }
    122
    123    private static final class Option {
    124        public final RationalNumber rationalNumber;
    125        public final double error;
    126
    127        private Option(final RationalNumber rationalNumber, final double error) {
    128            this.rationalNumber = rationalNumber;
    129            this.error = error;
    130        }
    131
    132        public static Option factory(final RationalNumber rationalNumber, final double value) {
    133            return new Option(rationalNumber, Math.abs(rationalNumber .doubleValue() - value));
    134        }
    135
    136        @Override
    137        public String toString() {
    138            return rationalNumber.toString();
    139        }
    140    }
    141
    142    /**
    143     * Calculate rational number using successive approximations.
    144     *
    145     * @param value rational number double value
    146     * @return the RationalNumber representation of the double value
    147     */
    148    public static RationalNumber valueOf(double value) {
    149        if (value >= Integer.MAX_VALUE) {
    150            return new RationalNumber(Integer.MAX_VALUE, 1);
    151        } else if (value <= -Integer.MAX_VALUE) {
    152            return new RationalNumber(-Integer.MAX_VALUE, 1);
    153        }
    154
    155        boolean negative = false;
    156        if (value < 0) {
    157            negative = true;
    158            value = Math.abs(value);
    159        }
    160
    161        RationalNumber l;
    162        RationalNumber h;
    163
    164        if (value == 0) {
    165            return new RationalNumber(0, 1);
    166        } else if (value >= 1) {
    167            final int approx = (int) value;
    168            if (approx < value) {
    169                l = new RationalNumber(approx, 1);
    170                h = new RationalNumber(approx + 1, 1);
    171            } else {
    172                l = new RationalNumber(approx - 1, 1);
    173                h = new RationalNumber(approx, 1);
    174            }
    175        } else {
    176            final int approx = (int) (1.0 / value);
    177            if ((1.0 / approx) < value) {
    178                l = new RationalNumber(1, approx);
    179                h = new RationalNumber(1, approx - 1);
    180            } else {
    181                l = new RationalNumber(1, approx + 1);
    182                h = new RationalNumber(1, approx);
    183            }
    184        }
    185        Option low = Option.factory(l, value);
    186        Option high = Option.factory(h, value);
    187
    188        Option bestOption = (low.error < high.error) ? low : high;
    189
    190        final int maxIterations = 100; // value is quite high, actually.
    191                                       // shouldn't matter.
    192        for (int count = 0; bestOption.error > TOLERANCE
    193                && count < maxIterations; count++) {
    194            final RationalNumber mediant = RationalNumber.factoryMethod(
    195                    (long) low.rationalNumber.numerator
    196                            + (long) high.rationalNumber.numerator,
    197                    (long) low.rationalNumber.divisor
    198                            + (long) high.rationalNumber.divisor);
    199            final Option mediantOption = Option.factory(mediant, value);
    200
    201            if (value < mediant.doubleValue()) {
    202                if (high.error <= mediantOption.error) {
    203                    break;
    204                }
    205
    206                high = mediantOption;
    207            } else {
    208                if (low.error <= mediantOption.error) {
    209                    break;
    210                }
    211
    212                low = mediantOption;
    213            }
    214
    215            if (mediantOption.error < bestOption.error) {
    216                bestOption = mediantOption;
    217            }
    218        }
    219
    220        return negative ? bestOption.rationalNumber.negate()
    221                : bestOption.rationalNumber;
    222    }
    223
    224}