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, inprecise 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 public static RationalNumber valueOf(double value) { 146 if (value >= Integer.MAX_VALUE) { 147 return new RationalNumber(Integer.MAX_VALUE, 1); 148 } else if (value <= -Integer.MAX_VALUE) { 149 return new RationalNumber(-Integer.MAX_VALUE, 1); 150 } 151 152 boolean negative = false; 153 if (value < 0) { 154 negative = true; 155 value = Math.abs(value); 156 } 157 158 RationalNumber l; 159 RationalNumber h; 160 161 if (value == 0) { 162 return new RationalNumber(0, 1); 163 } else if (value >= 1) { 164 final int approx = (int) value; 165 if (approx < value) { 166 l = new RationalNumber(approx, 1); 167 h = new RationalNumber(approx + 1, 1); 168 } else { 169 l = new RationalNumber(approx - 1, 1); 170 h = new RationalNumber(approx, 1); 171 } 172 } else { 173 final int approx = (int) (1.0 / value); 174 if ((1.0 / approx) < value) { 175 l = new RationalNumber(1, approx); 176 h = new RationalNumber(1, approx - 1); 177 } else { 178 l = new RationalNumber(1, approx + 1); 179 h = new RationalNumber(1, approx); 180 } 181 } 182 Option low = Option.factory(l, value); 183 Option high = Option.factory(h, value); 184 185 Option bestOption = (low.error < high.error) ? low : high; 186 187 final int maxIterations = 100; // value is quite high, actually. 188 // shouldn't matter. 189 for (int count = 0; bestOption.error > TOLERANCE 190 && count < maxIterations; count++) { 191 final RationalNumber mediant = RationalNumber.factoryMethod( 192 (long) low.rationalNumber.numerator 193 + (long) high.rationalNumber.numerator, 194 (long) low.rationalNumber.divisor 195 + (long) high.rationalNumber.divisor); 196 final Option mediantOption = Option.factory(mediant, value); 197 198 if (value < mediant.doubleValue()) { 199 if (high.error <= mediantOption.error) { 200 break; 201 } 202 203 high = mediantOption; 204 } else { 205 if (low.error <= mediantOption.error) { 206 break; 207 } 208 209 low = mediantOption; 210 } 211 212 if (mediantOption.error < bestOption.error) { 213 bestOption = mediantOption; 214 } 215 } 216 217 return negative ? bestOption.rationalNumber.negate() 218 : bestOption.rationalNumber; 219 } 220 221}