//--------------------------------------------------------------------------- // 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 ch06.largeInts;

import java.util.Iterator; public class LargeInt { 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

public void setNegative() { sign = MINUS; } public String toString() { Byte element; String largeIntString; if (sign == PLUS) largeIntString = "+"; else largeIntString = "-"; int count = numbers.size(); Iterator forward = numbers.forward(); 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()

// Set up loop int length = first.size(); boolean keepChecking = true; int count = 1; while ((count digitSecond) { greater = true; keepChecking = false; } else if (digitFirst

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 largerReverse = larger.reverse(); Iterator smallerReverse = smaller.reverse(); // Process both lists while both have digits for (int count = 1; count

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 largerReverse = larger.reverse(); Iterator smallerReverse = smaller.reverse(); // Process both lists while both have digits. for (int count = 1; count

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 secondForward = second.numbers.forward(); int length = second.numbers.size(); for (int count = 1; count

//--------------------------------------------------------------------------- // LargeIntList.java by Dale/Joyce/Weems Chapter 6 // // A specialized list to support Large Integer ADT //--------------------------------------------------------------------------- package ch06.largeInts;

import support.DLLNode; import java.util.Iterator; public class LargeIntList { protected DLLNode listFirst; // Ref to the first node on list protected DLLNode listLast; // Ref to the last node on the list 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 forward() // Returns an Iterator that iterates from front to rear. { return new Iterator() { private DLLNode next = listFirst; // next node to return

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 reverse() // Returns an Iterator that iterates rear to front. { return new Iterator() { private DLLNode next = listLast; // next node to return

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 = new DLLNode(element); // node being added 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 = new DLLNode(element); // node being added 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 for a doubly linked list. //----------------------------------------------------------------------------

package support;

public class DLLNode { private T info; private DLLNode forward, back; 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 forward){this.forward = forward;} public void setBack(DLLNode back){this.back = back;} public DLLNode getForward(){return forward;} public DLLNode getBack(){return back;} }

CSC 241 Lab 6 tion I Implement and test the multiply method of the LargeInt class on the following two numbers 123456789 and 123456789 The multiply method can use the LargeInt 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 LargeIntDriveri public static void main(Stringl] args)t Largent x = new Largelnt("123456789"); LargeInt y = new Large!nt("123456789"); LargeInt z - LargeInt.add(x, y); Largelnt product = Large!nt.n ultiply(x, y); CSC 241 Lab 6 tion I Implement and test the multiply method of the LargeInt class on the following two numbers 123456789 and 123456789 The multiply method can use the LargeInt 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 LargeIntDriveri public static void main(Stringl] args)t Largent x = new Largelnt("123456789"); LargeInt y = new Large!nt("123456789"); LargeInt z - LargeInt.add(x, y); Largelnt product = Large!nt.n ultiply(x, y)