/*

 * Copyright 1999-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.

 */

package java.math;

/**

 * A class used to represent multiprecision integers that makes efficient

 * use of allocated space by allowing a number to occupy only part of

 * an array so that the arrays do not have to be reallocated as often.

 * When performing an operation with many iterations the array used to

 * hold a number is only reallocated when necessary and does not have to

 * be the same size as the number it represents. A mutable number allows

 * calculations to occur on the same number without having to create

 * a new number for every step of the calculation as occurs with

 * BigIntegers.

 *

 * @see     BigInteger

 * @author  Michael McCloskey

 * @since   1.3

 */

class MutableBigInteger {

    /**

     * Holds the magnitude of this MutableBigInteger in big endian order.

     * The magnitude may start at an offset into the value array, and it may

     * end before the length of the value array.

     */

    int[] value;

    /**

     * The number of ints of the value array that are currently used

     * to hold the magnitude of this MutableBigInteger. The magnitude starts

     * at an offset and offset + intLen may be less than value.length.

     */

    int intLen;

    /**

     * The offset into the value array where the magnitude of this

     * MutableBigInteger begins.

     */

    int offset = 0;

    /**

     */

    // Constructors

    /**

     * The default constructor. An empty MutableBigInteger is created with

     * a one word capacity.

     */

    MutableBigInteger() {

        value = new int[1];

        intLen = 0;

    }

    /**

     * Construct a new MutableBigInteger with a magnitude specified by

     * the int val.

     */

    MutableBigInteger(int val) {

        value = new int[1];

        intLen = 1;

        value[0] = val;

    }

    /**

     * Construct a new MutableBigInteger with the specified value array

     * up to the length of the array supplied.

     */

    MutableBigInteger(int[] val) {

        value = val;

        intLen = val.length;

    }

    /**

     * Construct a new MutableBigInteger with a magnitude equal to the

     * specified BigInteger.

     */

    MutableBigInteger(BigInteger b) {

    }

    /**

     * Construct a new MutableBigInteger with a magnitude equal to the

     * specified MutableBigInteger.

     */

    MutableBigInteger(MutableBigInteger val) {

        intLen = val.intLen;

    }

    /**

     * Clear out a MutableBigInteger for reuse.

     */

    void clear() {

        offset = intLen = 0;

        for (int index=0, n=value.length; index < n; index++)

            value[index] = 0;

    }

    /**

     * Set a MutableBigInteger to zero, removing its offset.

     */

    void reset() {

        offset = intLen = 0;

    }

    /**

     * Compare the magnitude of two MutableBigIntegers. Returns -1, 0 or 1

     * as this MutableBigInteger is numerically less than, equal to, or

     */

    final int compare(MutableBigInteger b) {

            return -1;

            if (b1 < b2)

                return -1;

            if (b1 > b2)

                return 1;

        }

        return 0;

    }

    /**

     * Return the index of the lowest set bit in this MutableBigInteger. If the

     * magnitude of this MutableBigInteger is zero, -1 is returned.

     */

    private final int getLowestSetBit() {

        if (intLen == 0)

            return -1;

        int j, b;

        for (j=intLen-1; (j>0) && (value[j+offset]==0); j--)

            ;

        b = value[j+offset];

        if (b==0)

            return -1;

    }

    /**

     * Return the int in use in this MutableBigInteger at the specified

     * index. This method is not used because it is not inlined on all

     * platforms.

     */

    private final int getInt(int index) {

        return value[offset+index];

    }

    /**

     * Return a long which is equal to the unsigned value of the int in

     * use in this MutableBigInteger at the specified index. This method is

     * not used because it is not inlined on all platforms.

     */

    private final long getLong(int index) {

        return value[offset+index] & LONG_MASK;

    }

    /**

     * Ensure that the MutableBigInteger is in normal form, specifically

     * making sure that there are no leading zeros, and that if the

     * magnitude is zero, then intLen is zero.

     */

    final void normalize() {

        if (intLen == 0) {

            offset = 0;

            return;

        }

        int index = offset;

        if (value[index] != 0)

            return;

        int indexBound = index+intLen;

        do {

            index++;

        } while(index < indexBound && value[index]==0);

        int numZeros = index - offset;

        intLen -= numZeros;

        offset = (intLen==0 ?  0 : offset+numZeros);

    }

    /**

     * If this MutableBigInteger cannot hold len words, increase the size

     * of the value array to len words.

     */

    private final void ensureCapacity(int len) {

        if (value.length < len) {

            value = new int[len];

            offset = 0;

            intLen = len;

        }

    }

    /**

     * Convert this MutableBigInteger into an int array with no leading

     * zeros, of a length that is equal to this MutableBigInteger's intLen.

     */

    int[] toIntArray() {

        int[] result = new int[intLen];

        for(int i=0; i<intLen; i++)

            result[i] = value[offset+i];

        return result;

    }

    /**

     * Sets the int at index+offset in this MutableBigInteger to val.

     * This does not get inlined on all platforms so it is not used

     * as often as originally intended.

     */

    void setInt(int index, int val) {

        value[offset + index] = val;

    }

    /**

     * Sets this MutableBigInteger's value array to the specified array.

     * The intLen is set to the specified length.

     */

    void setValue(int[] val, int length) {

        value = val;

        intLen = length;

        offset = 0;

    }

    /**

     * Sets this MutableBigInteger's value array to a copy of the specified

     * array. The intLen is set to the length of the new array.

     */

        if (value.length < len)

            value = new int[len];

        intLen = len;

        offset = 0;

    }

    /**

     * Sets this MutableBigInteger's value array to a copy of the specified

     * array. The intLen is set to the length of the specified array.

     */

    void copyValue(int[] val) {

        int len = val.length;

        if (value.length < len)

            value = new int[len];

        intLen = len;

        offset = 0;

    }

    /**

     * Returns true iff this MutableBigInteger has a value of one.

     */

    boolean isOne() {

        return (intLen == 1) && (value[offset] == 1);

    }

    /**

     * Returns true iff this MutableBigInteger has a value of zero.

     */

    boolean isZero() {

        return (intLen == 0);

    }

    /**

     * Returns true iff this MutableBigInteger is even.

     */

    boolean isEven() {

        return (intLen == 0) || ((value[offset + intLen - 1] & 1) == 0);

    }

    /**

     * Returns true iff this MutableBigInteger is odd.

     */

    boolean isOdd() {

    }

    /**

     * Returns true iff this MutableBigInteger is in normal form. A

     * MutableBigInteger is in normal form if it has no leading zeros

     * after the offset, and intLen + offset <= value.length.

     */

    boolean isNormal() {

        if (intLen + offset > value.length)

            return false;

        if (intLen ==0)

            return true;

        return (value[offset] != 0);

    }

    /**

     * Returns a String representation of this MutableBigInteger in radix 10.

     */

    public String toString() {

        return b.toString();

    }

    /**

     * Right shift this MutableBigInteger n bits. The MutableBigInteger is left

     * in normal form.

     */

    void rightShift(int n) {

        if (intLen == 0)

            return;

        int nInts = n >>> 5;

        int nBits = n & 0x1F;

        this.intLen -= nInts;

        if (nBits == 0)

            return;

        if (nBits >= bitsInHighWord) {

            this.primitiveLeftShift(32 - nBits);

            this.intLen--;

        } else {

            primitiveRightShift(nBits);

        }

    }

    /**

     * Left shift this MutableBigInteger n bits.

     */

    void leftShift(int n) {

        /*

         * If there is enough storage space in this MutableBigInteger already

         * the available space will be used. Space to the right of the used

         * ints in the value array is faster to utilize, so the extra space

         * will be taken from the right if possible.

         */

        if (intLen == 0)

           return;

        int nInts = n >>> 5;

        int nBits = n&0x1F;

        // If shift can be done without moving words, do so

        if (n <= (32-bitsInHighWord)) {

            primitiveLeftShift(nBits);

            return;

        }

        int newLen = intLen + nInts +1;

        if (nBits <= (32-bitsInHighWord))

            newLen--;

        if (value.length < newLen) {

            // The array must grow

            int[] result = new int[newLen];

            for (int i=0; i<intLen; i++)

                result[i] = value[offset+i];

            setValue(result, newLen);

        } else if (value.length - offset >= newLen) {

            // Use space on right

            for(int i=0; i<newLen - intLen; i++)

                value[offset+intLen+i] = 0;

        } else {

            // Must use space on left

            for (int i=0; i<intLen; i++)

                value[i] = value[offset+i];

            for (int i=intLen; i<newLen; i++)

                value[i] = 0;

            offset = 0;

        }

        intLen = newLen;

        if (nBits == 0)

            return;

        if (nBits <= (32-bitsInHighWord))

            primitiveLeftShift(nBits);

        else

            primitiveRightShift(32 -nBits);

    }

    /**

     * A primitive used for division. This method adds in one multiple of the

     * divisor a back to the dividend result at a specified offset. It is used

     * when qhat was estimated too large, and must be adjusted.

     */

    private int divadd(int[] a, int[] result, int offset) {

        long carry = 0;

        for (int j=a.length-1; j >= 0; j--) {

            long sum = (a[j] & LONG_MASK) +

                       (result[j+offset] & LONG_MASK) + carry;