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