public class LInfiniteInteger implements InfiniteIntegerInterface
{
    private Node firstNode;
    private Node lastNode;
        private Node middleNode;
        private int middlePosition;
    private int numberOfDigits;
    private boolean isNegative;

    /**
     * Constructor: Constructs this infinite integer from a string
     * representing an integer.
     * @param s  a string represents an integer
     */
    public LInfiniteInteger(String s)
    {
        // TO DO
            int newDigit = 0;
            isNegative = false;
            numberOfDigits = 0;
            middlePosition = 0;
            firstNode = null;
            middleNode = null;
            lastNode = null;
            for(int i = 0; i < s.length(); i++)
            {
                newDigit = (int)s.charAt(i) - 48;
                if((newDigit >= 0) && (newDigit <= 9))
                {
                    this.add(newDigit);
                }
                else if((newDigit == ((int)'-') - 48))
                    isNegative = true;
            }
    }

    /**
     * Constructor: Constructs this infinite integer from an integer.
     * @param anInteger  an integer
     */
    public LInfiniteInteger(int anInteger)
    {
        // TO DO
            isNegative = false;
            numberOfDigits = 0;
            middlePosition = 0;
            firstNode = null;
            middleNode = null;
            lastNode = null;
            if(anInteger < 0)
            {
                isNegative = true;
                anInteger = -1 * anInteger;
            }
            //while(anInteger > 0)
            //{
                //this.add(anInteger % 10);
                //anInteger = anInteger / 10;
            //}
            while(anInteger > 0)
            {
                this.addToFront(anInteger % 10);
                anInteger = anInteger / 10;
            }

    }

    /**
     * Gets the number of digits of this infinite integer.
     * @return an integer representing the number of digits
     * of this infinite integer.
     */
    public int getNumberOfDigits()
    {
        // TO DO
            removeExtraZeros(this);
            return numberOfDigits;
    }

    /**
     * Checks whether this infinite integer is a negative number.
     * @return true if this infinite integer is a negative number.
     * Otherwise, return false.
     */
    public boolean isNegative()
    {
        // TO DO
            return isNegative;
    }

    /**
     * Calculates the result of this infinite integer plus anInfiniteInteger
     * @param anInfiniteInteger the infinite integer to be added to this
     * infinite integer.
     * @return a NEW infinite integer representing the result of this
     * infinite integer plus anInfiniteInteger
     */
    public InfiniteIntegerInterface plus(final InfiniteIntegerInterface anInfiniteInteger)
    {
        // TO DO
            int carry = 0;
            int tempResult = 0;
            boolean resultIsNegative = false;
            LInfiniteInteger firstOperand = new LInfiniteInteger(this.toString());
            LInfiniteInteger secondOperand = new LInfiniteInteger(anInfiniteInteger.toString());
            LInfiniteInteger returnResult = new LInfiniteInteger("");
            Node currentOne = firstOperand.lastNode;
            Node currentTwo = secondOperand.lastNode;
            if((firstOperand.isNegative == true) && (secondOperand.isNegative == true))
            {
                firstOperand.isNegative = false;
                secondOperand.isNegative = false;
                LInfiniteInteger tempReturnResult = new LInfiniteInteger(firstOperand.plus(secondOperand).toString());
                Node currentOneInner = tempReturnResult.firstNode;
                while(currentOneInner != null)
                {
                    returnResult.add(currentOneInner.data);
                    currentOneInner = currentOneInner.next;
                }
                returnResult.isNegative = true;
                //removeExtraZeros(returnResult); //problem
                return returnResult;
            }
            else if((firstOperand.isNegative == true) && (secondOperand.isNegative == false))
            {
                if(firstOperand.compareMag(secondOperand) == 1)
                {
                    firstOperand.isNegative = false;
                    LInfiniteInteger tempReturnResult = new LInfiniteInteger(firstOperand.minus(secondOperand).toString());
                    Node currentOneInner = tempReturnResult.firstNode;
                    while(currentOneInner != null)
                    {
                        returnResult.add(currentOneInner.data);
                        currentOneInner = currentOneInner.next;
                    }
                    returnResult.isNegative = true;
                    return returnResult;
                }
                else if(firstOperand.compareMag(secondOperand) == 0)
                {
                    returnResult.add(0);
                    return returnResult;
                }
                else
                {
                    firstOperand.isNegative = false;
                    LInfiniteInteger tempReturnResult = new LInfiniteInteger(secondOperand.minus(firstOperand).toString());
                    Node currentOneInner = tempReturnResult.firstNode;
                    while(currentOneInner != null)
                    {
                        returnResult.add(currentOneInner.data);
                        currentOneInner = currentOneInner.next;
                    }
                    return returnResult;
                }
            }
            else if((firstOperand.isNegative == false) && (secondOperand.isNegative == true))
            {
                if(firstOperand.compareMag(secondOperand) == 1)
                {
                    secondOperand.isNegative = false;
                    LInfiniteInteger tempReturnResult = new LInfiniteInteger(firstOperand.minus(secondOperand).toString());
                    Node currentOneInner = tempReturnResult.firstNode;
                    while(currentOneInner != null)
                    {
                        returnResult.add(currentOneInner.data);
                        currentOneInner = currentOneInner.next;
                    }
                    return returnResult;
                }
                else if(firstOperand.compareMag(secondOperand) == 0)
                {
                    returnResult.add(0);
                    return returnResult;
                }
                else
                {
                    secondOperand.isNegative = false;
                    LInfiniteInteger tempReturnResult = new LInfiniteInteger(secondOperand.minus(firstOperand).toString());
                    Node currentOneInner = tempReturnResult.firstNode;
                    while(currentOneInner != null)
                    {
                        returnResult.add(currentOneInner.data);
                        currentOneInner = currentOneInner.next;
                    }
                    returnResult.isNegative = true;
                    return returnResult;
                }
            }
            else
            {
                while((currentOne != null) && (currentTwo != null))
                {
                    tempResult = currentOne.data + currentTwo.data + carry;
                    returnResult.addToFront((tempResult % 10));
                    //result = (tempResult % 10) + result;
                    carry = tempResult/10;
                    currentOne = currentOne.previous;
                    currentTwo = currentTwo.previous;
                }
                if(currentOne == null)
                {
                    while(currentTwo != null)
                    {
                        tempResult = currentTwo.data + carry;
                        //result = (tempResult % 10) + result;
                        returnResult.addToFront((tempResult % 10));
                        carry = tempResult/10;
                    }
                }
                else if(currentTwo == null)
                {
                    while(currentOne != null)
                    {
                        tempResult = currentOne.data + carry;
                        //result = (tempResult % 10) + result;
                        returnResult.addToFront((tempResult % 10));
                        carry = tempResult/10;
                    }
                }
                //result = carry + result;
                if(carry > 0)
                {
                    returnResult.addToFront((carry));
                }

                //LInfiniteInteger returnResult = new LInfiniteInteger(result);
                removeExtraZeros(returnResult);
                return returnResult;
            }
    }
    /**
     * Calculates the result of this infinite integer subtracted by anInfiniteInteger
     * @param anInfiniteInteger the infinite integer to subtract.
     * @return a NEW infinite integer representing the result of this
     * infinite integer subtracted by anInfiniteInteger
     */
    public InfiniteIntegerInterface minus(final InfiniteIntegerInterface anInfiniteInteger)
    {
        // TO DO
            LInfiniteInteger firstOperand = new LInfiniteInteger(this.toString());
            LInfiniteInteger secondOperand = new LInfiniteInteger(anInfiniteInteger.toString());
            LInfiniteInteger returnResult = new LInfiniteInteger("");
            int tempResult;
            boolean resultIsNegative = false;
            Node currentOne = firstOperand.lastNode;
            Node currentTwo = secondOperand.lastNode;
            if((firstOperand.isNegative == false) && (secondOperand.isNegative == false))
            {
                if(firstOperand.compareMag(secondOperand) == 1)
                {
                    //algorithm
                    while((currentOne != null) && (currentTwo != null))
                    {

                        if(currentOne.data > currentTwo.data)
                        {
                            tempResult = currentOne.data - currentTwo.data;
                            //result = tempResult + result;
                            returnResult.addToFront(tempResult);
                        }
                        else if(currentOne.data < currentTwo.data)
                        {
                            currentOne.previous.data -= 1;
                            currentOne.data += 10;
                            tempResult = currentOne.data - currentTwo.data;
                            //result = tempResult + result;
                            returnResult.addToFront(tempResult);
                        }
                    }
                    if(currentOne == null)
                    {
                        while(currentTwo != null)
                        {
                            //result = currentTwo.data + result;
                            returnResult.addToFront(currentTwo.data);
                            currentTwo = currentTwo.previous;
                        }
                    }
                    else if(currentTwo == null)
                    {
                        while(currentTwo != null)
                        {
                            //result = currentTwo.data + result;
                            returnResult.addToFront(currentTwo.data);
                            currentTwo = currentTwo.previous;
                        }
                    }
                    return returnResult;
                }
                else if(firstOperand.compareMag(secondOperand) == 0)
                {
                    returnResult.add(0);
                    return returnResult;
                }
                else
                {
                    LInfiniteInteger tempReturnResult = new LInfiniteInteger(secondOperand.minus(firstOperand).toString());
                    Node currentOneInner = tempReturnResult.firstNode;
                    while(currentOneInner != null)
                    {
                        returnResult.add(currentOneInner.data);
                        currentOneInner = currentOneInner.next;
                    }
                    returnResult.isNegative = true;
                    return returnResult;
                }
            }
            else if((firstOperand.isNegative == false) && (secondOperand.isNegative == true))
            {
                secondOperand.isNegative = false;
                LInfiniteInteger tempReturnResult = new LInfiniteInteger(firstOperand.plus(secondOperand).toString());
                Node currentOneInner = tempReturnResult.firstNode;
                while(currentOneInner != null)
                {
                    returnResult.add(currentOneInner.data);
                    currentOneInner = currentOneInner.next;
                }
                return returnResult;
            }
            else if((firstOperand.isNegative == true) && (secondOperand.isNegative == false))
            {
                firstOperand.isNegative = false;
                LInfiniteInteger tempReturnResult = new LInfiniteInteger(firstOperand.plus(secondOperand).toString());
                Node currentOneInner = tempReturnResult.firstNode;
                while(currentOneInner != null)
                {
                    returnResult.add(currentOneInner.data);
                    currentOneInner = currentOneInner.next;
                }
                returnResult.isNegative = true;
                return returnResult;
            }
            else
            {
                if(firstOperand.compareMag(secondOperand) == -1)
                {
                    firstOperand.isNegative = false;
                    secondOperand.isNegative = false;
                    LInfiniteInteger tempReturnResult = new LInfiniteInteger(firstOperand.minus(secondOperand).toString());
                    Node currentOneInner = tempReturnResult.firstNode;
                    while(currentOneInner != null)
                    {
                        returnResult.add(currentOneInner.data);
                        currentOneInner = currentOneInner.next;
                    }
                    return returnResult;
                }
                else if(firstOperand.compareMag(secondOperand) == 0)
                {
                    returnResult.add(0);
                    return returnResult;
                }
                else
                {
                    firstOperand.isNegative = false;
                    secondOperand.isNegative = false;
                    LInfiniteInteger tempReturnResult = new LInfiniteInteger(firstOperand.minus(secondOperand).toString());
                    Node currentOneInner = tempReturnResult.firstNode;
                    while(currentOneInner != null)
                    {
                        returnResult.add(currentOneInner.data);
                        currentOneInner = currentOneInner.next;
                    }
                    returnResult.isNegative = true;
                    return returnResult;
                }
            }

    }

    /**
     * Generates a string representing this infinite integer. If this infinite integer
     * is a negative number a minus symbol should be in the front of numbers. For example,
     * "-12345678901234567890". But if the infinite integer is a positive number, no symbol
     * should be in the front of the numbers (e.g., "12345678901234567890").
     * @return a string representing this infinite integer number.
     */
    public String toString()
    {
        // TO DO
            Node currentNode = firstNode;
            String infiniteIntString = "";
            if(isNegative == true)
            {
                infiniteIntString = "-";
            }
            while(currentNode != null)
            {
                infiniteIntString = infiniteIntString + currentNode.data;
                currentNode = currentNode.next;
            }
            return infiniteIntString;
    }

    /**
     * Compares this infinite integer with anInfiniteInteger
     * @return either -1, 0, or 1 as follows:
     * If this infinite integer is less than anInfiniteInteger, return -1.
     * If this infinite integer is equal to anInfiniteInteger, return 0.
     * If this infinite integer is greater than anInfiniteInteger, return 1.
     */
    public int compareTo(InfiniteIntegerInterface anInfiniteInteger)
    {
        // TO DO
            LInfiniteInteger first = new LInfiniteInteger(this.toString());
            LInfiniteInteger second = new LInfiniteInteger(anInfiniteInteger.toString());
            removeExtraZeros(first);
            removeExtraZeros(second);
            if((first.isNegative == true) && (second.isNegative == false))
            {
                return -1;
            }
            else if((first.isNegative == false) && (second.isNegative == true))
            {
                return 1;
            }
            else if((first.isNegative == false) && (second.isNegative == false))
            {
                if(first.numberOfDigits > second.numberOfDigits)
                {
                 return 1;
                }
                else if(first.numberOfDigits < second.numberOfDigits)
                {
                    return -1;
                }
                else
                {
                    Node currentOne = first.firstNode;
                    Node currentTwo = second.firstNode;
                    while((currentOne != null) && (currentTwo != null))
                    {
                        if(currentOne.data > currentTwo.data)
                        {
                            return 1;
                        }
                        else if(currentOne.data < currentTwo.data)
                        {
                            return -1;
                        }
                        else
                        {
                            currentOne = currentOne.next;
                            currentTwo = currentTwo.next;
                        }
                    }
                }
            }
            else
            {
                if(first.numberOfDigits > second.numberOfDigits)
                {
                    return -1;
                }
                else if(first.numberOfDigits < second.numberOfDigits)
                {
                    return 1;
                }
                else
                {
                    Node currentOne = first.firstNode;
                    Node currentTwo = second.firstNode;
                    while((currentOne != null) && (currentTwo != null))
                    {
                        if(currentOne.data > currentTwo.data)
                        {
                            return -1;
                        }
                        else if(currentOne.data < currentTwo.data)
                        {
                            return 1;
                        }
                        else
                        {
                            currentOne = currentOne.next;
                            currentTwo = currentTwo.next;
                        }
                    }
                    return 0;
                }
            }
            return 0;
    }
        public int compareMag(InfiniteIntegerInterface anInfiniteInteger)
        {
            LInfiniteInteger first = new LInfiniteInteger(this.toString());
            LInfiniteInteger second = new LInfiniteInteger(anInfiniteInteger.toString());
            removeExtraZeros(first);
            removeExtraZeros(second);
            first.isNegative = false;
            second.isNegative = false;

            if(first.numberOfDigits > second.numberOfDigits)
                {
                 return 1;
                }
                else if(first.numberOfDigits < second.numberOfDigits)
                {
                    return -1;
                }
                else
                {
                    Node currentOne = first.firstNode;
                    Node currentTwo = second.firstNode;
                    while((currentOne != null) && (currentTwo != null))
                    {
                        if(currentOne.data > currentTwo.data)
                        {
                            return 1;
                        }
                        else if(currentOne.data < currentTwo.data)
                        {
                            return -1;
                        }
                        else
                        {
                            currentOne = currentOne.next;
                            currentTwo = currentTwo.next;
                        }
                    }
                }
            return 0;
        }
    /**
     * Calculates the result of this infinite integer multiplied by anInfiniteInteger
     * @param anInfiniteInteger the multiplier.
     * @return a NEW infinite integer representing the result of this
     * infinite integer multiplied by anInfiniteInteger.
     */
    public InfiniteIntegerInterface multiply(final InfiniteIntegerInterface anInfiniteInteger)
    {
        // TO DO
            int place1 = 0;
            int place2 = 0;
            LInfiniteInteger tempFirstOp = new LInfiniteInteger(this.toString());
            LInfiniteInteger tempSecondOp = new LInfiniteInteger(anInfiniteInteger.toString());
            LInfiniteInteger firstOperand = new LInfiniteInteger("");
            LInfiniteInteger secondOperand = new LInfiniteInteger("");
            LInfiniteInteger result = new LInfiniteInteger("");
            LInfiniteInteger tempResult = new LInfiniteInteger("");
            String tempResultString = "";
            Integer tempResultInt = new Integer(0);
            if((tempFirstOp.compareTo(tempSecondOp) == 1) || (tempFirstOp.compareTo(tempSecondOp) == 0))
            {
                firstOperand = tempFirstOp;
                secondOperand = tempSecondOp;
            }
            else
            {
                firstOperand = tempSecondOp;
                secondOperand = tempFirstOp;
            }

            Node currentTwo = secondOperand.lastNode;
            while(currentTwo != null)
            {
                place1 = 0;
                Node currentOne = firstOperand.lastNode;
                while(currentOne != null)
                {
                    tempResultInt = currentOne.data * currentTwo.data;
                    tempResultString = tempResultInt.toString();
                    for(int i = 0; i <= (place1 + place2); i++)
                    {
                        tempResultString = tempResultString + "0";
                    }
                    tempResult = new LInfiniteInteger(tempResultString);
                    result.plus(tempResult);
                    place1++;
                    currentOne = currentOne.next;
                }
                place2++;
            }
            return result;
    }
        public void add(int newDigit)
    {
        if(firstNode == null)
        {
            firstNode = new Node(null, newDigit, null);
            lastNode = firstNode;
        } //if the list is empty create a new node with newEntry as the data, but no previous or next node
        else
        {
            Node newNode = new Node(lastNode, newDigit, null);
            lastNode.next = newNode;
            lastNode = newNode;
        } //otherwise, (there is at least one node in the list already) add a new node such that "lastNode" is before it, data = neEntry, and there is nothing after it

        numberOfDigits++; //either way, add 1 to numberOfDigits

        if(numberOfDigits % 2 == 1)
        {
                    if(middleNode == null)
                    {
                        middleNode = firstNode;
                    }// if numberOfDigits is not divisible by 2, and there is no middle node assigned yet, make the middle node equal to first node
                    else
                    {
                        middleNode = middleNode.next;
                    }//if numberOfEntries is not divisible by 2, and there is a middle node assigned, move middle node up one in the chain
                    middlePosition++; // either way, increment the middlePosition variable
        }
    }
        public void addToFront(int newDigit)
        {
            if(firstNode == null)
            {
                firstNode = new Node(null, newDigit, null);
                lastNode = firstNode;
            }
            else
            {
                Node newNode = new Node(null, newDigit, firstNode);
                firstNode.previous = newNode;
                firstNode = newNode;
            }
            numberOfDigits++;
            if(numberOfDigits % 2 == 1)
            {
                if(middleNode == null)
                {
                    middleNode = firstNode;
                }// if numberOfDigits is not divisible by 2, and there is no middle node assigned yet, make the middle node equal to first node
                else
                {
                    middleNode = middleNode.previous;
                }//if numberOfEntries is not divisible by 2, and there is a middle node assigned, move middle node up one in the chain
                middlePosition++; // either way, increment the middlePosition variable
            }
        }
        public void removeExtraZeros(LInfiniteInteger anInfiniteInteger)
        {
            Node currentNode = firstNode;
            while((currentNode.data == 0) && (currentNode.next != null))
            {
                firstNode = currentNode.next;
                currentNode = currentNode.next;
                numberOfDigits--;
            }
        }

    private class Node
    {
        private int data;
        private Node next;
        private Node previous;

        private Node(Node previousNode, int aData, Node nextNode)
        {
            previous = previousNode;
            data = aData;
            next = nextNode;
        }

        private Node(int aData)
        {
            this(null, aData, null);
        }
    }
}