Question: //--------------------------------------------------------------------------- // LargeInt.java by Dale/Joyce/Weems Chapter 6 // // Provides a Large Integer ADT. Large integers can consist of any number // of digits, plus
//---------------------------------------------------------------------------
// LargeInt.java by Dale/Joyce/Weems Chapter 6
//
// Provides a Large Integer ADT. Large integers can consist of any number
// of digits, plus a sign. Supports an add and a subtract operation.
//---------------------------------------------------------------------------
package lab6;
import java.util.Iterator;
public class LargeInt extends LargeIntList
{
protected LargeIntList numbers; // Holds digits
// Constants for sign variable
protected static final boolean PLUS = true;
protected static final boolean MINUS = false;
protected boolean sign;
public LargeInt()
// Instantiates an "empty" large integer.
{
numbers = new LargeIntList();
sign = PLUS;
}
public LargeInt(String intString)
// Precondition: intString contains a well-formatted integer
//
// Instantiates a large integer as indicated by intString
{
numbers = new LargeIntList();
sign = PLUS;
int firstDigitPosition; // Position of first digit in intString
int lastDigitPosition; // Position of last digit in intString
// Used to translate character to byte
char digitChar;
int digitInt;
byte digitByte;
firstDigitPosition = 0;
if (intString.charAt(0) == '+') // Skip leading plus sign
firstDigitPosition = 1;
else
if (intString.charAt(0) == '-') // Handle leading minus sign
{
firstDigitPosition = 1;
sign = MINUS;
}
lastDigitPosition = intString.length() - 1;
for (int count = firstDigitPosition; count
{
digitChar = intString.charAt(count);
digitInt = Character.digit(digitChar, 10);
digitByte = (byte)digitInt;
numbers.addEnd(digitByte);
}
}
public void setNegative()
{
sign = MINUS;
}
public String toString()
{
Byte element;
String largeIntString;
if (sign == PLUS)
largeIntString = "+";
else
largeIntString = "-";
int count = numbers.size();
Iterator
while (forward.hasNext())
{
element = forward.next();
largeIntString = largeIntString + element;
if ((((count - 1) % 3) == 0) && (count != 1))
largeIntString = largeIntString + ",";
count--;
}
return(largeIntString);
}
protected static boolean greaterList(LargeIntList first,
LargeIntList second)
// Precondition: first and second have no leading zeros
//
// Returns true if first represents a larger number than second;
// otherwise, returns false
{
boolean greater = false;
if (first.size() > second.size())
greater = true;
else
if (first.size()
greater = false;
else
{
byte digitFirst;
byte digitSecond;
Iterator
Iterator
// Set up loop
int length = first.size();
boolean keepChecking = true;
int count = 1;
while ((count
{
digitFirst = firstForward.next();
digitSecond = secondForward.next();
if (digitFirst > digitSecond)
{
greater = true;
keepChecking = false;
}
else
if (digitFirst
{
greater = false;
keepChecking = false;
}
count++;
}
}
return greater;
}
protected static LargeIntList addLists(LargeIntList larger,
LargeIntList smaller)
// Precondition: larger > smaller
//
// Returns a specialized list that is a byte-by-byte sum of the two
// argument lists
{
byte digit1;
byte digit2;
byte temp;
byte carry = 0;
int largerLength = larger.size();
int smallerLength = smaller.size();
int lengthDiff;
LargeIntList result = new LargeIntList();
Iterator
Iterator
// Process both lists while both have digits
for (int count = 1; count
{
digit1 = largerReverse.next();
digit2 = smallerReverse.next();
temp = (byte)(digit1 + digit2 + carry);
carry = (byte)(temp / 10);
result.addFront((byte)(temp % 10));
}
// Finish processing of leftover digits
lengthDiff = (largerLength - smallerLength);
for (int count = 1; count
{
digit1 = largerReverse.next();
temp = (byte)(digit1 + carry);
carry = (byte)(temp / 10);
result.addFront((byte)(temp % 10));
}
if (carry != 0)
result.addFront((byte)carry);
return result;
}
protected static LargeIntList subtractLists(LargeIntList larger,
LargeIntList smaller)
// Precondition: larger >= smaller
//
// Returns a specialized list that is the difference of the two argument lists
{
byte digit1;
byte digit2;
byte temp;
boolean borrow = false;
int largerLength = larger.size();
int smallerLength = smaller.size();
int lengthDiff;
LargeIntList result = new LargeIntList();
Iterator
Iterator
// Process both lists while both have digits.
for (int count = 1; count
{
digit1 = largerReverse.next();
if (borrow)
{
if (digit1 != 0)
{
digit1 = (byte)(digit1 - 1);
borrow = false;
}
else
{
digit1 = 9;
borrow = true;
}
}
digit2 = smallerReverse.next();
if (digit2
result.addFront((byte)(digit1 - digit2));
else
{
borrow = true;
result.addFront((byte)(digit1 + 10 - digit2));
}
}
// Finish processing of leftover digits
lengthDiff = (largerLength - smallerLength);
for (int count = 1; count
{
digit1 = largerReverse.next();
if (borrow)
{
if (digit1 != 0)
{
digit1 = (byte)(digit1 - 1);
borrow = false;
}
else
{
digit1 = 9;
borrow = true;
}
}
result.addFront(digit1);
}
return result;
}
public static LargeInt add(LargeInt first, LargeInt second)
// Returns a LargeInt that is the sum of the two argument LargeInts
{
LargeInt sum = new LargeInt();
if (first.sign == second.sign)
{
if (greaterList(first.numbers, second.numbers))
sum.numbers = addLists(first.numbers, second.numbers);
else
sum.numbers = addLists(second.numbers, first.numbers);
sum.sign = first.sign;
}
else // Signs are different
{
if (greaterList(first.numbers, second.numbers))
{
sum.numbers = subtractLists(first.numbers, second.numbers);
sum.sign = first.sign;
}
else
{
sum.numbers = subtractLists(second.numbers, first.numbers);
sum.sign = second.sign;
}
}
return sum;
}
public static LargeInt subtract(LargeInt first, LargeInt second)
// Returns a LargeInt that is the difference of the two argument LargeInts
{
LargeInt diff = new LargeInt();
// Create an inverse of second
LargeInt negSecond = new LargeInt();
negSecond.sign = !second.sign;
Iterator
int length = second.numbers.size();
for (int count = 1; count
negSecond.numbers.addEnd(secondForward.next());
// Add first to inverse of second
diff = add(first, negSecond);
return diff;
}
}
//---------------------------------------------------------------------------
// LargeIntList.java by Dale/Joyce/Weems Chapter 6
//
// A specialized list to support Large Integer ADT
//---------------------------------------------------------------------------
package lab6;
import java.util.Iterator;
public class LargeIntList
{
protected DLLNode
protected DLLNode
protected int numElements; // Number of elements in the list
public LargeIntList()
// Creates an empty list object
{
numElements = 0;
listFirst = null;
listLast = null;
}
public int size()
// Returns the number of elements on this list.
{
return numElements;
}
public Iterator
// Returns an Iterator that iterates from front to rear.
{
return new Iterator
{
private DLLNode
public boolean hasNext()
// Returns true if the iteration has more elements; otherwise false.
{
return (next != null);
}
public Byte next()
// Returns the next element in the iteration.
// Throws NoSuchElementException - if no more elements
{
if (!hasNext())
throw new IndexOutOfBoundsException("Illegal invocation of " +
" next in LargeIntList forward iterator. ");
Byte hold = next.getInfo(); // holds info for return
next = next.getForward();
return hold;
}
public void remove()
// Throws UnsupportedOperationException.
{
throw new UnsupportedOperationException("Unsupported remove " +
"attempted on LargeIntList forward iterator.");
}
};
}
public Iterator
// Returns an Iterator that iterates rear to front.
{
return new Iterator
{
private DLLNode
public boolean hasNext()
// Returns true if the iteration has more elements; otherwise false.
{
return (next != null);
}
public Byte next()
// Returns the next element in the iteration.
// Throws NoSuchElementException - if no more elements
{
if (!hasNext())
throw new IndexOutOfBoundsException("Illegal invocation of " +
"next in LargeIntList reverse iterator. ");
Byte hold = next.getInfo(); // holds info for return
next = next.getBack();
return hold;
}
public void remove()
// Throws UnsupportedOperationException.
{
throw new UnsupportedOperationException("Unsupported remove " +
"attempted on LargeIntList forward iterator.");
}
};
}
public void addFront (byte element)
// Adds the value of element to the beginning of this list
{
DLLNode
newNode.setForward(listFirst);
newNode.setBack(null);
if (listFirst == null) // Adding into an empty list
{
listFirst = newNode;
listLast = newNode;
}
else // Adding into a non-empty list
{
listFirst.setBack(newNode);
listFirst = newNode;
}
numElements++;
}
public void addEnd (byte element)
// Adds the value of element to the end of this list
{
DLLNode
newNode.setForward(null);
newNode.setBack(listLast);
if (listFirst == null) // Adding into an empty list
{
listFirst = newNode;
listLast = newNode;
}
else // Adding into a non-empty list
{
listLast.setForward(newNode);
listLast = newNode;
}
numElements++;
}
}
//----------------------------------------------------------------------------
// DLLNode.java by Dale/Joyce/Weems Chapter 4
//
// Implements nodes holding info of class
//----------------------------------------------------------------------------
package lab6;
public class DLLNode
{
private T info;
private DLLNode
public DLLNode(T info)
{
this.info = info; forward = null; back = null;
}
public void setInfo(T info){this.info = info;}
public T getInfo(){return info;}
public void setForward(DLLNode
public void setBack(DLLNode
public DLLNode getForward(){return forward;}
public DLLNode getBack(){return back;}
}
Implement and test the multiply method of the Largelnt class on the following two numbers: 123456789 and 123456789 The multiply method can use the Largelnt add method. For example: 345 x 123 1035 6900 +34500 42435 Take 345 x 3-add 345 to itself 3 times- 1035, 345 x 2-add 345 to itself 2 times-690 and append "0" to it because the 2 is in the tens place 6900 345 x 1- add 345 to itself 1 time - 345 and append "00" to it because the 1 is in the hundreds place 34500; all using the add method. Now add the 1035, 6900, and 34500 using the add method again. This approach would work. Also, make sure your commas are in the right place. Here is a sample driver: public class LargeIntDriver { public static void main(Stringll args)t Largelnt x- new Largelnt("123456789"); Largelnt y- new LargeInt("123456789"); Largelnt z = Largelnt.add(x, y); Largelnt product LargeInt.multiply(x, y); System.out.println(product); The correct output should be: +15,241,578,750,190,521 Be sure to test your multiply method on positive and negative combinations (+)x (+), (-)x(-), (+)x (-), and (-) x (+). Implement and test the multiply method of the Largelnt class on the following two numbers: 123456789 and 123456789 The multiply method can use the Largelnt add method. For example: 345 x 123 1035 6900 +34500 42435 Take 345 x 3-add 345 to itself 3 times- 1035, 345 x 2-add 345 to itself 2 times-690 and append "0" to it because the 2 is in the tens place 6900 345 x 1- add 345 to itself 1 time - 345 and append "00" to it because the 1 is in the hundreds place 34500; all using the add method. Now add the 1035, 6900, and 34500 using the add method again. This approach would work. Also, make sure your commas are in the right place. Here is a sample driver: public class LargeIntDriver { public static void main(Stringll args)t Largelnt x- new Largelnt("123456789"); Largelnt y- new LargeInt("123456789"); Largelnt z = Largelnt.add(x, y); Largelnt product LargeInt.multiply(x, y); System.out.println(product); The correct output should be: +15,241,578,750,190,521 Be sure to test your multiply method on positive and negative combinations (+)x (+), (-)x(-), (+)x (-), and (-) x (+)
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help