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 &lt; 0, then leading zeros between
067     * the decimal point and the first nonzero digit are implied.  If decimalAt
068     * is &gt; 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 &le; f &lt; 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 &le; 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 &le; 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