001/* 002// This software is subject to the terms of the Eclipse Public License v1.0 003// Agreement, available at the following URL: 004// http://www.eclipse.org/legal/epl-v10.html. 005// You must accept the terms of that agreement to use this software. 006// 007// Copyright (C) 2012-2012 Pentaho and others 008// All Rights Reserved. 009// 010// ----------------------------------------------------------------------------- 011// Copied from the ICU project's DigitList class. 012// 013// Copyright (C) 1996-2011, International Business Machines Corporation and 014// others. All Rights Reserved. 015*/ 016package mondrian.util; 017 018import java.math.BigInteger; 019 020/** 021 * <code>DigitList</code> handles the transcoding between numeric values and 022 * strings of characters. It only represents non-negative numbers. The 023 * division of labor between <code>DigitList</code> and 024 * <code>DecimalFormat</code> is that <code>DigitList</code> handles the radix 025 * 10 representation issues and numeric conversion, including rounding; 026 * <code>DecimalFormat</code> handles the locale-specific issues such as 027 * positive and negative representation, digit grouping, decimal point, 028 * currency, and so on. 029 * 030 * <p>A <code>DigitList</code> is a representation of a finite numeric value. 031 * <code>DigitList</code> objects do not represent <code>NaN</code> or infinite 032 * values. A <code>DigitList</code> value can be converted to a 033 * <code>BigDecimal</code> without loss of precision. Conversion to other 034 * numeric formats may involve loss of precision, depending on the specific 035 * value. 036 * 037 * <p>The <code>DigitList</code> representation consists of a string of 038 * characters, which are the digits radix 10, from '0' to '9'. It also has a 039 * base 10 exponent associated with it. The value represented by a 040 * <code>DigitList</code> object can be computed by mulitplying the fraction 041 * <em>f</em>, where 0 <= <em>f</em> < 1, derived by placing all the digits of 042 * the list to the right of the decimal point, by 10^exponent. 043 * 044 * @see java.util.Locale 045 * @see java.text.Format 046 * @see java.text.ChoiceFormat 047 * @see java.text.MessageFormat 048 * @version 1.18 08/12/98 049 * @author Mark Davis, Alan Liu 050 */ 051final class DigitList { 052 /** 053 * The maximum number of significant digits in an IEEE 754 double, that 054 * is, in a Java double. This must not be increased, or garbage digits 055 * will be generated, and should not be decreased, or accuracy will be lost. 056 */ 057 public static final int MAX_LONG_DIGITS = 19; 058 static { 059 assert MAX_LONG_DIGITS == Long.toString(Long.MAX_VALUE).length(); 060 } 061 062 /** 063 * These data members are intentionally public and can be set directly. 064 * 065 * <p>The value represented is given by placing the decimal point before 066 * digits[decimalAt]. If decimalAt is < 0, then leading zeros between 067 * the decimal point and the first nonzero digit are implied. If decimalAt 068 * is > count, then trailing zeros between the digits[count-1] and the 069 * decimal point are implied.</p> 070 * 071 * <p>Equivalently, the represented value is given by f * 10^decimalAt. 072 * Here f is a value 0.1 ≤ f < 1 arrived at by placing the digits in 073 * Digits to the right of the decimal.</p> 074 * 075 * <p>DigitList is normalized, so if it is non-zero, figits[0] is non-zero. 076 * We don't allow denormalized numbers because our exponent is effectively 077 * of unlimited magnitude. The count value contains the number of 078 * significant digits present in digits[].</p> 079 * 080 * <p>Zero is represented by any DigitList with count == 0 or with each 081 * digits[i] for all i ≤ count == '0'.</p> 082 */ 083 public int decimalAt = 0; 084 public int count = 0; 085 public byte[] digits = new byte[MAX_LONG_DIGITS]; 086 087 private void ensureCapacity(int digitCapacity, int digitsToCopy) { 088 if (digitCapacity > digits.length) { 089 byte[] newDigits = new byte[digitCapacity * 2]; 090 System.arraycopy(digits, 0, newDigits, 0, digitsToCopy); 091 digits = newDigits; 092 } 093 } 094 095 /** 096 * Appends digits to the list. 097 */ 098 public void append(int digit) { 099 ensureCapacity(count + 1, count); 100 digits[count++] = (byte) digit; 101 } 102 103 /** 104 * Set the digit list to a representation of the given double value. 105 * This method supports both fixed-point and exponential notation. 106 * @param source Value to be converted; must not be Inf, -Inf, Nan, 107 * or a value ≤ 0. 108 * @param maximumDigits The most fractional or total digits which should 109 * be converted. 110 * @param fixedPoint If true, then maximumDigits is the maximum 111 * fractional digits to be converted. If false, total digits. 112 */ 113 final void set(double source, int maximumDigits, boolean fixedPoint) 114 { 115 if (source == 0) { 116 source = 0; 117 } 118 // Generate a representation of the form DDDDD, DDDDD.DDDDD, or 119 // DDDDDE+/-DDDDD. 120 String rep = Double.toString(source); 121 122 set(rep, MAX_LONG_DIGITS); 123 124 if (fixedPoint) { 125 // The negative of the exponent represents the number of leading 126 // zeros between the decimal and the first non-zero digit, for a 127 // value < 0.1 (e.g., for 0.00123, -decimalAt == 2). If this is 128 // more than the maximum fraction digits, then we have an underflow 129 // for the printed representation. 130 if (-decimalAt > maximumDigits) { 131 count = 0; 132 return; 133 } else if (-decimalAt == maximumDigits) { 134 if (shouldRoundUp(0)) { 135 count = 1; 136 ++decimalAt; 137 digits[0] = (byte)'1'; 138 } else { 139 count = 0; 140 } 141 return; 142 } 143 // else fall through 144 } 145 146 // Eliminate trailing zeros. 147 while (count > 1 && digits[count - 1] == '0') { 148 --count; 149 } 150 // Eliminate digits beyond maximum digits to be displayed. 151 // Round up if appropriate. 152 round( 153 fixedPoint 154 ? (maximumDigits + decimalAt) 155 : maximumDigits == 0 156 ? -1 157 : maximumDigits); 158 } 159 160 /** 161 * Given a string representation of the form DDDDD, DDDDD.DDDDD, 162 * or DDDDDE+/-DDDDD, set this object's value to it. Ignore 163 * any leading '-'. 164 */ 165 private void set(String rep, int maxCount) { 166 decimalAt = -1; 167 count = 0; 168 int exponent = 0; 169 // Number of zeros between decimal point and first non-zero digit after 170 // decimal point, for numbers < 1. 171 int leadingZerosAfterDecimal = 0; 172 boolean nonZeroDigitSeen = false; 173 // Skip over leading '-' 174 int i = 0; 175 if (rep.charAt(i) == '-') { 176 ++i; 177 } 178 for (; i < rep.length(); ++i) { 179 char c = rep.charAt(i); 180 if (c == '.') { 181 decimalAt = count; 182 } else if (c == 'e' || c == 'E') { 183 ++i; 184 // Integer.parseInt doesn't handle leading '+' signs 185 if (rep.charAt(i) == '+') { 186 ++i; 187 } 188 exponent = Integer.parseInt(rep.substring(i)); 189 break; 190 } else if (count < maxCount) { 191 if (!nonZeroDigitSeen) { 192 nonZeroDigitSeen = (c != '0'); 193 if (!nonZeroDigitSeen && decimalAt != -1) { 194 ++leadingZerosAfterDecimal; 195 } 196 } 197 198 if (nonZeroDigitSeen) { 199 ensureCapacity(count + 1, count); 200 digits[count++] = (byte)c; 201 } 202 } 203 } 204 if (decimalAt == -1) { 205 decimalAt = count; 206 } 207 decimalAt += exponent - leadingZerosAfterDecimal; 208 } 209 210 /** 211 * Return true if truncating the representation to the given number 212 * of digits will result in an increment to the last digit. This 213 * method implements half-even rounding, the default rounding mode. 214 * 215 * @param maximumDigits the number of digits to keep, from 0 to 216 * <code>count-1</code>. If 0, then all digits are rounded away, and 217 * this method returns true if a one should be generated (e.g., formatting 218 * 0.09 with "#.#"). 219 * @return true if digit <code>maximumDigits-1</code> should be 220 * incremented 221 */ 222 private boolean shouldRoundUp(int maximumDigits) { 223 // variable not used boolean increment = false; 224 // Implement IEEE half-even rounding 225 if (maximumDigits < count) { 226 if (digits[maximumDigits] > '5') { 227 return true; 228 } else if (digits[maximumDigits] == '5') { 229 for (int i = maximumDigits + 1; i < count; ++i) { 230 if (digits[i] != '0') { 231 return true; 232 } 233 } 234 return maximumDigits > 0 235 && (digits[maximumDigits - 1] % 2 != 0); 236 } 237 } 238 return false; 239 } 240 241 /** 242 * Round the representation to the given number of digits. 243 * @param maximumDigits The maximum number of digits to be shown. 244 * Upon return, count will be less than or equal to maximumDigits. 245 * This now performs rounding when maximumDigits is 0, formerly it did not. 246 */ 247 public final void round(int maximumDigits) { 248 // Eliminate digits beyond maximum digits to be displayed. 249 // Round up if appropriate. 250 // [bnf] rewritten to fix 4179818 251 if (maximumDigits >= 0 && maximumDigits < count) { 252 if (shouldRoundUp(maximumDigits)) { 253 // Rounding up involves incrementing digits from LSD to MSD. 254 // In most cases this is simple, but in a worst case situation 255 // (9999..99) we have to adjust the decimalAt value. 256 for (;;) { 257 --maximumDigits; 258 if (maximumDigits < 0) { 259 // We have all 9's, so we increment to a single digit 260 // of one and adjust the exponent. 261 digits[0] = (byte) '1'; 262 ++decimalAt; 263 maximumDigits = 0; // Adjust the count 264 break; 265 } 266 267 ++digits[maximumDigits]; 268 if (digits[maximumDigits] <= '9') { 269 break; 270 } 271 // Unnecessary since we'll truncate this: 272 // digits[maximumDigits] = '0'; 273 } 274 ++maximumDigits; // Increment for use as count 275 } 276 count = maximumDigits; 277 } 278 // Bug 4217661 DecimalFormat formats 1.001 to "1.00" instead of "1" 279 // Eliminate trailing zeros. [Richard/GCL] 280 // [dlf] moved outside if block, see ticket #6408 281 while (count > 1 && digits[count - 1] == '0') { 282 --count; 283 } 284 } 285 286 /** 287 * Utility routine to set the value of the digit list from a long 288 */ 289 public final void set(long source) 290 { 291 set(source, 0); 292 } 293 294 /** 295 * Set the digit list to a representation of the given long value. 296 * @param source Value to be converted; must be >= 0 or == 297 * Long.MIN_VALUE. 298 * @param maximumDigits The most digits which should be converted. 299 * If maximumDigits is lower than the number of significant digits 300 * in source, the representation will be rounded. Ignored if <= 0. 301 */ 302 public final void set(long source, int maximumDigits) 303 { 304 // This method does not expect a negative number. However, 305 // "source" can be a Long.MIN_VALUE (-9223372036854775808), 306 // if the number being formatted is a Long.MIN_VALUE. In that 307 // case, it will be formatted as -Long.MIN_VALUE, a number 308 // which is outside the legal range of a long, but which can 309 // be represented by DigitList. 310 // [NEW] Faster implementation 311 if (source <= 0) { 312 if (source == Long.MIN_VALUE) { 313 decimalAt = count = MAX_LONG_DIGITS; 314 System.arraycopy(LONG_MIN_REP, 0, digits, 0, count); 315 } else { 316 count = 0; 317 decimalAt = 0; 318 } 319 } else { 320 int left = MAX_LONG_DIGITS; 321 int right; 322 while (source > 0) { 323 digits[--left] = (byte) (((long) '0') + (source % 10)); 324 source /= 10; 325 } 326 decimalAt = MAX_LONG_DIGITS - left; 327 // Don't copy trailing zeros 328 // we are guaranteed that there is at least one non-zero digit, 329 // so we don't have to check lower bounds 330 for (right = MAX_LONG_DIGITS - 1; 331 digits[right] == (byte) '0'; 332 --right) 333 { 334 } 335 count = right - left + 1; 336 System.arraycopy(digits, left, digits, 0, count); 337 } 338 if (maximumDigits > 0) { 339 round(maximumDigits); 340 } 341 } 342 343 /** 344 * Set the digit list to a representation of the given BigInteger value. 345 * 346 * @param source Value to be converted 347 * @param maximumDigits The most digits which should be converted. 348 * If maximumDigits is lower than the number of significant digits 349 * in source, the representation will be rounded. Ignored if <= 0. 350 */ 351 public final void set(BigInteger source, int maximumDigits) { 352 String stringDigits = source.toString(); 353 354 count = decimalAt = stringDigits.length(); 355 356 // Don't copy trailing zeros 357 while (count > 1 && stringDigits.charAt(count - 1) == '0') { 358 --count; 359 } 360 int offset = 0; 361 if (stringDigits.charAt(0) == '-') { 362 ++offset; 363 --count; 364 --decimalAt; 365 } 366 367 ensureCapacity(count, 0); 368 for (int i = 0; i < count; ++i) { 369 digits[i] = (byte) stringDigits.charAt(i + offset); 370 } 371 372 if (maximumDigits > 0) { 373 round(maximumDigits); 374 } 375 } 376 377 private static byte[] LONG_MIN_REP; 378 379 static 380 { 381 // Store the representation of LONG_MIN without the leading '-' 382 String s = Long.toString(Long.MIN_VALUE); 383 LONG_MIN_REP = new byte[MAX_LONG_DIGITS]; 384 for (int i = 0; i < MAX_LONG_DIGITS; ++i) { 385 LONG_MIN_REP[i] = (byte)s.charAt(i + 1); 386 } 387 } 388} 389 390// End DigitList.java