/*

 * Portions Copyright 1996-2007 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 */

/*

 * Portions Copyright IBM Corporation, 2001. All Rights Reserved.

 */

package java.math;

/**

 * Immutable, arbitrary-precision signed decimal numbers.  A

 * {@code BigDecimal} consists of an arbitrary precision integer

 * <i>unscaled value</i> and a 32-bit integer <i>scale</i>.  If zero

 * or positive, the scale is the number of digits to the right of the

 * decimal point.  If negative, the unscaled value of the number is

 * multiplied by ten to the power of the negation of the scale.  The

 * value of the number represented by the {@code BigDecimal} is

 * therefore <tt>(unscaledValue &times; 10<sup>-scale</sup>)</tt>.

 *

 * <p>The {@code BigDecimal} class provides operations for

 * arithmetic, scale manipulation, rounding, comparison, hashing, and

 * format conversion.  The {@link #toString} method provides a

 * canonical representation of a {@code BigDecimal}.

 *

 * <p>The {@code BigDecimal} class gives its user complete control

 * over rounding behavior.  If no rounding mode is specified and the

 * exact result cannot be represented, an exception is thrown;

 * otherwise, calculations can be carried out to a chosen precision

 * and rounding mode by supplying an appropriate {@link MathContext}

 * object to the operation.  In either case, eight <em>rounding

 * modes</em> are provided for the control of rounding.  Using the

 * integer fields in this class (such as {@link #ROUND_HALF_UP}) to

 * represent rounding mode is largely obsolete; the enumeration values

 * of the {@code RoundingMode} {@code enum}, (such as {@link

 * RoundingMode#HALF_UP}) should be used instead.

 *

 * <p>When a {@code MathContext} object is supplied with a precision

 * setting of 0 (for example, {@link MathContext#UNLIMITED}),

 * arithmetic operations are exact, as are the arithmetic methods

 * which take no {@code MathContext} object.  (This is the only

 * behavior that was supported in releases prior to 5.)  As a

 * corollary of computing the exact result, the rounding mode setting

 * of a {@code MathContext} object with a precision setting of 0 is

 * not used and thus irrelevant.  In the case of divide, the exact

 * quotient could have an infinitely long decimal expansion; for

 * example, 1 divided by 3.  If the quotient has a nonterminating

 * decimal expansion and the operation is specified to return an exact

 * result, an {@code ArithmeticException} is thrown.  Otherwise, the

 * exact result of the division is returned, as done for other

 * operations.

 *

 * <p>When the precision setting is not 0, the rules of

 * {@code BigDecimal} arithmetic are broadly compatible with selected

 * modes of operation of the arithmetic defined in ANSI X3.274-1996

 * and ANSI X3.274-1996/AM 1-2000 (section 7.4).  Unlike those

 * standards, {@code BigDecimal} includes many rounding modes, which

 * were mandatory for division in {@code BigDecimal} releases prior

 * to 5.  Any conflicts between these ANSI standards and the

 * {@code BigDecimal} specification are resolved in favor of

 * {@code BigDecimal}.

 *

 * <p>Since the same numerical value can have different

 * representations (with different scales), the rules of arithmetic

 * and rounding must specify both the numerical result and the scale

 * used in the result's representation.

 *

 *

 * <p>In general the rounding modes and precision setting determine

 * how operations return results with a limited number of digits when

 * the exact result has more digits (perhaps infinitely many in the

 * case of division) than the number of digits returned.

 *

 * First, the

 * total number of digits to return is specified by the

 * {@code MathContext}'s {@code precision} setting; this determines

 * the result's <i>precision</i>.  The digit count starts from the

 * leftmost nonzero digit of the exact result.  The rounding mode

 * determines how any discarded trailing digits affect the returned

 * result.

 *

 * <p>For all arithmetic operators , the operation is carried out as

 * though an exact intermediate result were first calculated and then

 * rounded to the number of digits specified by the precision setting

 * (if necessary), using the selected rounding mode.  If the exact

 * result is not returned, some digit positions of the exact result

 * are discarded.  When rounding increases the magnitude of the

 * returned result, it is possible for a new digit position to be

 * created by a carry propagating to a leading {@literal "9"} digit.

 * For example, rounding the value 999.9 to three digits rounding up

 * would be numerically equal to one thousand, represented as

 * 100&times;10<sup>1</sup>.  In such cases, the new {@literal "1"} is

 * the leading digit position of the returned result.

 *

 * <p>Besides a logical exact result, each arithmetic operation has a

 * preferred scale for representing a result.  The preferred

 * scale for each operation is listed in the table below.

 *

 * <table border>

 * <caption top><h3>Preferred Scales for Results of Arithmetic Operations

 * </h3></caption>

 * <tr><th>Operation</th><th>Preferred Scale of Result</th></tr>

 * <tr><td>Add</td><td>max(addend.scale(), augend.scale())</td>

 * <tr><td>Subtract</td><td>max(minuend.scale(), subtrahend.scale())</td>

 * <tr><td>Multiply</td><td>multiplier.scale() + multiplicand.scale()</td>

 * <tr><td>Divide</td><td>dividend.scale() - divisor.scale()</td>

 * </table>

 *

 * These scales are the ones used by the methods which return exact

 * arithmetic results; except that an exact divide may have to use a

 * larger scale since the exact result may have more digits.  For

 * example, {@code 1/32} is {@code 0.03125}.

 *

 * <p>Before rounding, the scale of the logical exact intermediate

 * result is the preferred scale for that operation.  If the exact

 * numerical result cannot be represented in {@code precision}

 * digits, rounding selects the set of digits to return and the scale

 * of the result is reduced from the scale of the intermediate result

 * to the least scale which can represent the {@code precision}

 * digits actually returned.  If the exact result can be represented

 * with at most {@code precision} digits, the representation

 * of the result with the scale closest to the preferred scale is

 * returned.  In particular, an exactly representable quotient may be

 * represented in fewer than {@code precision} digits by removing

 * trailing zeros and decreasing the scale.  For example, rounding to

 * three digits using the {@linkplain RoundingMode#FLOOR floor}

 * rounding mode, <br>

 *

 * {@code 19/100 = 0.19   // integer=19,  scale=2} <br>

 *

 * but<br>

 *

 * {@code 21/110 = 0.190  // integer=190, scale=3} <br>

 *

 * <p>Note that for add, subtract, and multiply, the reduction in

 * scale will equal the number of digit positions of the exact result

 * which are discarded. If the rounding causes a carry propagation to

 * create a new high-order digit position, an additional digit of the

 * result is discarded than when no new digit position is created.

 *

 * <p>Other methods may have slightly different rounding semantics.

 * For example, the result of the {@code pow} method using the

 * {@linkplain #pow(int, MathContext) specified algorithm} can

 * occasionally differ from the rounded mathematical result by more

 * than one unit in the last place, one <i>{@linkplain #ulp() ulp}</i>.

 *

 * <p>Two types of operations are provided for manipulating the scale

 * of a {@code BigDecimal}: scaling/rounding operations and decimal

 * point motion operations.  Scaling/rounding operations ({@link

 * #setScale setScale} and {@link #round round}) return a

 * {@code BigDecimal} whose value is approximately (or exactly) equal

 * to that of the operand, but whose scale or precision is the

 * specified value; that is, they increase or decrease the precision

 * of the stored number with minimal effect on its value.  Decimal

 * point motion operations ({@link #movePointLeft movePointLeft} and

 * {@link #movePointRight movePointRight}) return a

 * {@code BigDecimal} created from the operand by moving the decimal

 * point a specified distance in the specified direction.

 *

 * <p>For the sake of brevity and clarity, pseudo-code is used

 * throughout the descriptions of {@code BigDecimal} methods.  The

 * pseudo-code expression {@code (i + j)} is shorthand for "a

 * {@code BigDecimal} whose value is that of the {@code BigDecimal}

 * {@code i} added to that of the {@code BigDecimal}

 * {@code j}." The pseudo-code expression {@code (i == j)} is

 * shorthand for "{@code true} if and only if the

 * {@code BigDecimal} {@code i} represents the same value as the

 * {@code BigDecimal} {@code j}." Other pseudo-code expressions

 * are interpreted similarly.  Square brackets are used to represent

 * the particular {@code BigInteger} and scale pair defining a

 * {@code BigDecimal} value; for example [19, 2] is the

 * {@code BigDecimal} numerically equal to 0.19 having a scale of 2.

 *

 * <p>Note: care should be exercised if {@code BigDecimal} objects

 * are used as keys in a {@link java.util.SortedMap SortedMap} or

 * elements in a {@link java.util.SortedSet SortedSet} since

 * {@code BigDecimal}'s <i>natural ordering</i> is <i>inconsistent

 * with equals</i>.  See {@link Comparable}, {@link

 * java.util.SortedMap} or {@link java.util.SortedSet} for more

 * information.

 *

 * <p>All methods and constructors for this class throw

 * {@code NullPointerException} when passed a {@code null} object

 * reference for any input parameter.

 *

 * @see     BigInteger

 * @see     MathContext

 * @see     RoundingMode

 * @see     java.util.SortedMap

 * @see     java.util.SortedSet

 * @author  Josh Bloch

 * @author  Mike Cowlishaw

 * @author  Joseph D. Darcy

 */

public class BigDecimal extends Number implements Comparable<BigDecimal> {

    /**

     * The unscaled value of this BigDecimal, as returned by {@link

     * #unscaledValue}.

     *

     * @serial

     * @see #unscaledValue

     */

    private volatile BigInteger intVal;

    /**

     * The scale of this BigDecimal, as returned by {@link #scale}.

     *

     * @serial

     * @see #scale

     */

    /**

     * The number of decimal digits in this BigDecimal, or 0 if the

     * number of digits are not known (lookaside information).  If

     * nonzero, the value is guaranteed correct.  Use the precision()

     * method to obtain and set the value if it might be 0.  This

     * field is mutable until set nonzero.

     *

     * @since  1.5

     */

    /**

     * Used to store the canonical string representation, if computed.

     */

    /**

     * Sentinel value for {@link #intCompact} indicating the

     * significand information is only available from {@code intVal}.

     */

    /**

     * If the absolute value of the significand of this BigDecimal is

     * less than or equal to {@code Long.MAX_VALUE}, the value can be

     * compactly stored in this field and used in computations.

     */

    // All 18-digit base ten strings fit into a long; not all 19-digit

    // strings will

    private static final int MAX_COMPACT_DIGITS = 18;

    private static final int MAX_BIGINT_BITS = 62;

    /* Appease the serialization gods */

    private static final long serialVersionUID = 6108874887143696463L;

    // Cache of common small BigDecimal values.

    private static final BigDecimal zeroThroughTen[] = {

    };

    // Constants

    /**

     * The value 0, with a scale of 0.

     *

     * @since  1.5

     */

    public static final BigDecimal ZERO =

        zeroThroughTen[0];

    /**

     * The value 1, with a scale of 0.

     *

     * @since  1.5

     */

    public static final BigDecimal ONE =

        zeroThroughTen[1];

    /**

     * The value 10, with a scale of 0.

     *

     * @since  1.5

     */

    public static final BigDecimal TEN =

        zeroThroughTen[10];

    // Constructors

    /**

     * Translates a character array representation of a

     * {@code BigDecimal} into a {@code BigDecimal}, accepting the

     * same sequence of characters as the {@link #BigDecimal(String)}

     * constructor, while allowing a sub-array to be specified.

     *

     * <p>Note that if the sequence of characters is already available

     * within a character array, using this constructor is faster than

     * converting the {@code char} array to string and using the

     * {@code BigDecimal(String)} constructor .

     *

     * @param  in {@code char} array that is the source of characters.

     * @param  offset first character in the array to inspect.

     * @param  len number of characters to consider.

     * @throws NumberFormatException if {@code in} is not a valid

     *         representation of a {@code BigDecimal} or the defined subarray

     *         is not wholly within {@code in}.

     * @since  1.5

     */

    public BigDecimal(char[] in, int offset, int len) {

        // This is the primary string to BigDecimal constructor; all

        // incoming strings end up here; it uses explicit (inline)

        // parsing for speed and generates at most one intermediate

        // use array bounds checking to handle too-long, len == 0,

        // bad offset, etc.

        try {

            // handle the sign

            boolean isneg = false;          // assume positive

            if (in[offset] == '-') {

                isneg = true;               // leading minus means negative

                offset++;

                len--;

            } else if (in[offset] == '+') { // leading + allowed

                offset++;

                len--;

            }

            // should now be at numeric part of the significand

            int cfirst = offset;             // record start of integer

            long exp = 0;                    // exponent

            for (; len > 0; offset++, len--) {

                c = in[offset];

                if ((c >= '0' && c <= '9') || Character.isDigit(c)) {

                    continue;

                }

                if (c == '.') {

                    // have dot

                        throw new NumberFormatException();

                    continue;

                }

                // exponent expected

                if ((c != 'e') && (c != 'E'))

                    throw new NumberFormatException();

                offset++;

                c = in[offset];

                len--;

                // optional sign

                    offset++;

                    c = in[offset];

                    len--;

                }

                if (len <= 0)    // no exponent digits

                    throw new NumberFormatException();

                // skip leading zeros in the exponent

                while (len > 10 && Character.digit(c, 10) == 0) {

                }

                if (len > 10)  // too many nonzero exponent digits

                    throw new NumberFormatException();

                // c now holds first digit of exponent

                for (;; len--) {

                    int v;

                    if (c >= '0' && c <= '9') {

                        v = c - '0';

                    } else {

                        v = Character.digit(c, 10);

                        if (v < 0)            // not a digit

                            throw new NumberFormatException();

                    }

                    exp = exp * 10 + v;

                    if (len == 1)

                        break;               // that was final character

                    offset++;

                    c = in[offset];

                }

                if (negexp)                  // apply sign

                    exp = -exp;

                // Next test is required for backwards compatibility

                if ((int)exp != exp)         // overflow

                    throw new NumberFormatException();

                break;                       // [saves a test]

            // here when no characters left

                throw new NumberFormatException();

            if (exp != 0) {                  // had significant exponent