/*
 * Copyright Derek Park 2001
 * All rights reserved
 */
import java.lang.NumberFormatException;
import java.lang.Math;

/**
 * HugeInteger allows an integer of up to forty digits to be stored 
 * and have modifications, such as addition and subtraction, enacted upon it.
 * 
 * @author Derek Park
 */
public class HugeInteger {
    
    /**
     * The arrays used cannot have more than forty elements
     */
    public static final int MAX_ARRAY_LENGTH = 40;
    
    byte [] digitArray; // hold the digits
    
    /**
     * Constructs a new HugeInteger with the value Zero
     */
    HugeInteger() {
        digitArray = new byte[MAX_ARRAY_LENGTH];
    }
    
    /**
     * Constructs a new HugeInteger with the value of the int 
     * parameter
     *
     * @param inputInt the integer to be converted to a HugeInteger
     */
    HugeInteger(String s) throws NumberFormatException{
        this();
        inputHugeInteger(s);    
    }
    
    /**
     * Constructs a new HugeInteger with the value represented by the 
     * byte array parameter.  inputByteArray is not modified by this 
     * constructor
     *
     * @param inputByteArray the array of bytes to be converted to 
     *  a HugeInteger
     *
     * @throws NumberFormatException if the array parameter has more than
     * forty elements or if one of those elements has more than one digit
     */
    HugeInteger(byte [] b) throws NumberFormatException{
        this();
        inputHugeInteger(b);
    }
    

    /**
     * Adds another HugeInteger to this HugeInteger
     *
     * @param h the parameter added to this HugeInteger
     */
    public void add(HugeInteger h) {
        if (isNegative()) {
            addN(h);
        } else {
            addP(h);
        }
    }

    /**
     * Subtracts another HugeInteger from this HugeInteger
     *
     * @param h the parameter subtracted from this HugeInteger
     */
    public void subtract(HugeInteger h) {
        if (isNegative()) {
            subtractN(h);
        } else {
            subtractP(h);
        }
    }

    // add method to use if "this" is positive
    private void addP(HugeInteger h) {
        if(h.isNegative()){
            h.makePositive();
            subtractP(h);
            h.makeNegative();
        } else {
            for (byte i = 0; i < MAX_ARRAY_LENGTH; i++) {
                this.digitArray[i] += h.digitArray[i];
                if(this.digitArray[i] > 9) {
                    this.digitArray[i] -= 10;
                    this.digitArray[i + 1] += 1; // carry
                }
            }
        }
    }
    
    // subtract method to use if "this" is positive
    private void subtractP(HugeInteger h) {
        if(h.isNegative()){
            h.makePositive();
            addP(h);
            h.makeNegative();
        } else {
            for (byte i = 0; i < MAX_ARRAY_LENGTH; i++) {
                this.digitArray[i] += h.digitArray[i];
                if(this.digitArray[i] < 0) {
                    this.digitArray[i] += 10;
                    this.digitArray[i + 1] -= 1; // borrow
                }
            }
        }
    }

    // add method to use if "this" is negative
    private void addN(HugeInteger h) {
        if(h.isPositive()){
            h.makeNegative();
            subtractN(h);
            h.makePositive();
        } else {
            for (byte i = 0; i < MAX_ARRAY_LENGTH; i++) {
                this.digitArray[i] += h.digitArray[i];
                if(this.digitArray[i] < -9) {
                    this.digitArray[i] += 10;
                    this.digitArray[i + 1] -= 1; // negative carry
                }
            }
        }
    }
    
    // subtract method to use if "this" is negative
    private void subtractN(HugeInteger h) {
        if(h.isPositive()){
            h.makeNegative();
            addN(h);
            h.makePositive();
        } else {
            for (byte i = 0; i < MAX_ARRAY_LENGTH; i++) {
                this.digitArray[i] += h.digitArray[i];
                if(this.digitArray[i] > 0) {
                    this.digitArray[i] -= 10;
                    this.digitArray[i + 1] += 1; // negative borrow
                }
            }
        }
    }
    
    // set every value in digitArray to it's positive equivalent
    void makePositive() {
        for (byte i = 0; i < MAX_ARRAY_LENGTH; i++) {
            digitArray[i] = (byte)Math.abs((int)digitArray[i]);
        }
    }
    
    // set every value in digitArray to it's negative equivalent
    void makeNegative() {
        makePositive();
        for (byte i = 0; i < MAX_ARRAY_LENGTH; i++) {
            digitArray[i] *= -1;
        }
    }
    
    
    /**
     * Changes the value of HugeInteger to equal the value represented by the 
     * string
     *
     * @param s a String containing a HugeInteger value
     *
     * @throws NumberFormatException if the String has non-numeric value or if
     * the elements are not either all positive or all negative
     */
    public void inputHugeInteger(String s) throws NumberFormatException{
        boolean isNegative = false;
        for (byte i = 0; (i < MAX_ARRAY_LENGTH) && (i < s.length()); i++) {
            if (i == 0 && s.charAt(0) == '-'){
                isNegative = true;
            } else {
                digitArray[i] =
                      Byte.parseByte(new Character(s.charAt(i)).toString());
            }
        }
        if (isNegative) {
            makeNegative();
        }
    }
    
    /**
     * Sets HugeInteger equal to the value represented by the array
     *
     * @param b the byte array representing a HugeInteger value.  
     * b is not modified by this method.
     *
     * @throws NumberFormatException if the array parameter has more than 
     * forty elements or if one of those elements has more than one digit
     */
    public void inputHugeInteger(byte [] b) throws NumberFormatException {
        if (b.length > MAX_ARRAY_LENGTH) {
            throw new NumberFormatException("Array length greater than 40");
        }
        boolean isNegative = false;
        boolean isPositive = false;
        for (byte i = 0; i < b.length; i++) {
            digitArray[i] = b[i];
            if (digitArray[i] > 0) {
                isPositive = true;
            }
            if (digitArray[i] < 0) {
                isNegative = true;
            }
        }
        if (isNegative && isPositive) {
            throw new NumberFormatException("Array elements must all be" +
                                            " negative if one is");
        }
    }
    
    /**
     * Returns a string containing the value within this HugeInteger
     *
     * @return a String representing the value contained within this 
     * HugeInteger
     */
    public String outputHugeInteger() {
        boolean foundFirstDigit = false;
        String returnString = "";
        
        for(byte i =( MAX_ARRAY_LENGTH - 1); i >= 0; i--) {
            if (foundFirstDigit == true) {
                returnString += Math.abs(digitArray[i]);
            } else if (digitArray[i] != 0){
                returnString += digitArray[i];
                foundFirstDigit = true;
            }
        }
        if (returnString == "") {
            returnString = "0";
        }
        return returnString;
    }
    
    /**
     * Returns a byte array representing the HugeInteger
     *
     * @return the array representing the numeric value contained within this
     * HugeInteger
     */
    public byte [] toByteArray() {
        byte [] returnArray = new byte [MAX_ARRAY_LENGTH];
        
        for (byte i = 0; i < MAX_ARRAY_LENGTH; i++) {
            returnArray[i] = digitArray[i];
        }
        
        return returnArray;
    }
    
    /**
     * Returns true if this HugeInteger contains a value greater than the 
     * parameter
     *
     * @param h the HugeInteger to base the comparison upon
     *
     * @return the boolean value that the comparison between this HugeInteger
     * and the parameter yeilds
     */
    public boolean isGreaterThan(HugeInteger h) {
        for (byte i = (MAX_ARRAY_LENGTH - 1); i >= 0; i--) {
            if (this.digitArray[i] > h.digitArray[i]) {
                return true;
            }
        }
        return false;
    }
    

    /**
     * Returns true if this HugeInteger contains a value less than the parameter
     *
     * @param h HugeInteger to base the comparison upon
     *
     * @return the boolean value that the comparison between this HugeInteger
     * and the parameter yeilds
     */    
    public boolean isLessThan(HugeInteger h) {
        for (byte i = (MAX_ARRAY_LENGTH - 1); i >= 0; i--) {
            if (this.digitArray[i] < h.digitArray[i]) {
                return true;
            }
        }
        return false;
    }
    
    /**
     * Returns true if the HugeIntegers contain equivalent values
     *
     * @param h the HugeInteger to base the comparison upon
     *
     * @return the boolean value that the comparison between this HugeInteger
     * and the parameter yeilds
     */
    public boolean isEqualTo(HugeInteger h) {
        return !isGreaterThan(h) && !isLessThan(h);
    }
    
    /**
     * Returns true if the HugeIntegers do not contain equivalent values
     *
     * @param h the HugeInteger to base the comparison upon
     *
     * @return the boolean value that the comparison between this HugeInteger
     * and the parameter yeilds
     */
    public boolean isNotEqualTo(HugeInteger h) {
        return !isEqualTo(h);
    }
    
    /**
     * Returns true if this HugeInteger contains a value greater than or equal 
     * to the parameter
     *
     * @param h the HugeInteger to base the comparison upon
     *
     * @return the boolean value that the comparison between this HugeInteger
     * and the parameter yeilds
     */
    public boolean isGreaterThanOrEqualTo(HugeInteger h) {
        return !isLessThan(h);
    }
    
    /**
     * Returns true if this HugeInteger contains a value less than or equal to 
     * the parameter
     *
     * @param h the HugeInteger to base the comparison upon
     *
     * @return the boolean value that the comparison between this HugeInteger
     * and the parameter yeilds
     */
    public boolean isLessThanOrEqualTo(HugeInteger h) {
        return !isGreaterThan(h);
    }
    
    // returns true if this HugeInteger is negative
    private boolean isNegative() {
        for (byte i = (MAX_ARRAY_LENGTH - 1); i >= 0; i--) {
            if (digitArray[i] < 0) {
                return true;
            }
        }
        return false;
    }
    
    // returns true if this HugeInteger is positive
    private boolean isPositive() {
        for (byte i = (MAX_ARRAY_LENGTH - 1); i >= 0; i--) {
            if (digitArray[i] > 0) {
                return true;
            }
        }
        return false;
    }
    
    /**
     * Returns true if the HugeInteger is equal to Zero
     *
     * @return true if this HugeInteger contains the value zero
     */
    public boolean isZero(){
        return !isPositive() && !isNegative();
    }
}