diff options
Diffstat (limited to 'projects/project2_LInfiniteInteger/LInfiniteInteger.java')
| -rw-r--r-- | projects/project2_LInfiniteInteger/LInfiniteInteger.java | 562 |
1 files changed, 562 insertions, 0 deletions
diff --git a/projects/project2_LInfiniteInteger/LInfiniteInteger.java b/projects/project2_LInfiniteInteger/LInfiniteInteger.java new file mode 100644 index 0000000..c74ab41 --- /dev/null +++ b/projects/project2_LInfiniteInteger/LInfiniteInteger.java @@ -0,0 +1,562 @@ + +public class LInfiniteInteger implements InfiniteIntegerInterface +{ + private Node firstNode; + private Node lastNode; + 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) + { + if(s.toCharArray().length > 0 && s.toCharArray()[0] == '-') //Short circuit in case the string is empty + { + isNegative = true; + s = s.substring(1); + } + boolean significantDigit = false; + for(char c : s.toCharArray()) + { + if(!significantDigit && Character.getNumericValue(c) == 0) + { + } + else + { + significantDigit = true; + Node n = new Node(lastNode,Character.getNumericValue(c),null); + if(firstNode == null) + { + firstNode = n; + } + lastNode = n; + numberOfDigits++; + } + } + if(firstNode == null) + { + firstNode = new Node(null,0,null); + lastNode = firstNode; + numberOfDigits++; + } + for(Node tmp = lastNode; tmp != null && tmp.previous != null;tmp = tmp.previous) + { + //System.out.println("[ME] Setting node with data " + tmp.previous.data + " to have corret next."); + tmp.previous.next = tmp; + } + } + + /** + * Constructor: Constructs this infinite integer from an integer. + * @param anInteger an integer + */ + public LInfiniteInteger(int anInteger) + { + isNegative = anInteger < 0; + //System.out.println("[ME] Makeing with integer" + anInteger); + if(isNegative) + { + anInteger *= -1; + } + for(int i = 10; i/10 <= anInteger; i *= 10) + { + //System.out.println("[ME] Makeing a node with " + (anInteger%i)/(i/10)); + Node n = new Node(null,(anInteger%i)/(i/10),firstNode); + firstNode = n; + numberOfDigits++; + } + Node tmp = firstNode; + for(; tmp != null && tmp.next != null;tmp = tmp.next) + { + //System.out.println("[ME] Setting node with data " + tmp.previous.data + " to have corret next."); + tmp.next.previous = tmp; + } + lastNode = tmp; + if(anInteger == 0) + { + Node n = new Node(null,0,null); + firstNode = n; + lastNode = n; + } + //numberOfDigits--; //Subtract 1, because we looped 1 too many times for digits, but needed to take into account potential digits to the left + //System.out.println("[ME]Created from integer, number is " + this.toString()); + } + + /** + * Gets the number of digits of this infinite integer. + * @return an integer representing the number of digits + * of this infinite integer. + */ + public int getNumberOfDigits() + { + numberOfDigits = 0; + for(Node tmp = firstNode; tmp != null; tmp = tmp.next) + { + numberOfDigits++; + } + 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() + { + 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) + { + LInfiniteInteger output = new LInfiniteInteger(""); + + //System.out.println("[ME] Attempting to add " + this.toString() + " and " + anInfiniteInteger.toString()); + + //If both are negative do addition, but the answer is negative + if(this.isNegative() && anInfiniteInteger.compareTo(new LInfiniteInteger("")) <= 0) + { + + //And the other number is zero, set output to negative, and add + output.isNegative = true; + } + else if(this.compareTo(new LInfiniteInteger("")) <= 0 && anInfiniteInteger.isNegative()) + { + output.isNegative = true; + } + //If one is negitive, find out which, and do a subtraction instead + if(this.compareTo(new LInfiniteInteger("")) < 0 && anInfiniteInteger.compareTo(new LInfiniteInteger("")) > 0) + { + //this is negitive, but the other is positive + LInfiniteInteger temp = new LInfiniteInteger(this.toString()); + temp.isNegative = false; + return anInfiniteInteger.minus(temp); + } + if(this.compareTo(new LInfiniteInteger("")) > 0 && anInfiniteInteger.compareTo(new LInfiniteInteger("")) < 0) + { + //anInfiniteInteger is negitive, but we are positive. + LInfiniteInteger temp = new LInfiniteInteger(anInfiniteInteger.toString()); + temp.isNegative = false; + return this.minus(temp); + } + //We should only get to this point if we're really doing addition + int carry = 0; + Node thattemp = new LInfiniteInteger(anInfiniteInteger.toString()).lastNode; + Node temp = this.lastNode; + if(temp == null) + { + //System.out.println("[ME] LAST NODE IS NULL FROM START!"); + } + for(; temp != null || thattemp != null;) + { + int sum = 0; + //System.out.print("[ME] After this interation, "); + if(temp != null) + { + sum += temp.data; + //System.out.print(" " + temp.data + " + "); + temp = temp.previous; + } + else + { + //System.out.print(" NULL + "); + } + if(thattemp != null) + { + //System.out.print(thattemp.data); + sum += thattemp.data; + thattemp = thattemp.previous; + } + else + { + //System.out.print(" NULL "); + } + sum += carry; + carry = sum / 10; + output.addfirst(sum % 10); + //System.out.print(" , sum is " + sum%10 + " and carry is " + carry + "\n"); + } + if(carry > 0) + { + output.addfirst(carry); + } + output.removeLast(); + //Return the result + return output; + } + private void removeLast() + { + Node tmp = lastNode; + if(tmp != null) + { + tmp = lastNode.previous; + if(tmp != null) + { + tmp.next = null; + } + lastNode = tmp; + } + } + private void removeFirst() + { + Node tmp = firstNode; + if(tmp != null) + { + tmp = firstNode.next; + if(tmp != null) + { + tmp.previous = null; + } + firstNode = tmp; + } + } + private void addfirst(int data) + { + Node tmp = firstNode; + Node n = new Node(null,data,firstNode); + firstNode = n; + if(tmp != null) + { + tmp.previous = n; + } + } + private void addlast(int data) + { + Node tmp = lastNode; + Node n = new Node(lastNode,data,null); + lastNode = n; + if(tmp != null) + { + tmp.next = n; + } + } + private Node getLastNode() + { + return lastNode; + } + private Node getFirstNode() + { + return firstNode; + } + /** + * 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) + { + //System.out.println("[ME] Attempting to subtract " + anInfiniteInteger.toString() + " from " + this.toString()); + // Figure out if we're really supposed to subtract, or we need to do a clever add + //Cases: + //We are negative, and anInteger is not negative (-this - that) = (-this + -that) + if(this.isNegative && !anInfiniteInteger.isNegative()) + { + //Just add them as negitive numbers + LInfiniteInteger tmp= new LInfiniteInteger(anInfiniteInteger.toString()); + tmp.isNegative = true; + return this.plus(tmp); + + } + //We are not negative, and anInteger is negative (this - -that) = (this + that) + if(!this.isNegative && anInfiniteInteger.isNegative()) + { + LInfiniteInteger tmp= new LInfiniteInteger(anInfiniteInteger.toString()); + tmp.isNegative = false; + return this.plus(tmp); + } + //We are both negitive(-this - -that) = (-this + that) + if(this.isNegative && anInfiniteInteger.isNegative()) + { + LInfiniteInteger tmp = new LInfiniteInteger(anInfiniteInteger.toString()); + tmp.isNegative = false; + return this.plus(tmp); + } + //Figure out which number is lower in magnitude, and have that the the "fake" negitive, and maybe flip the signs back if nessessarry. + //Find both numbers without magnitude + LInfiniteInteger thisnomag = new LInfiniteInteger(this.toString()); + thisnomag.isNegative = false; + LInfiniteInteger thatnomag = new LInfiniteInteger(anInfiniteInteger.toString()); + thatnomag.isNegative = false; + boolean negateAtEnd = false; + LInfiniteInteger bigger = null; + LInfiniteInteger smaller = null; + if(thisnomag.compareTo(thatnomag) > 0) + { + //We are bigger + negateAtEnd = false; + bigger = new LInfiniteInteger(this.toString()); + smaller = new LInfiniteInteger(anInfiniteInteger.toString()); + } + else if(thisnomag.compareTo(thatnomag) < 0) + { + //The other guy is bigger + //System.out.println("[ME] " + anInfiniteInteger.toString() + " is bigger"); + negateAtEnd = true; + bigger = new LInfiniteInteger(anInfiniteInteger.toString()); + smaller = new LInfiniteInteger(this.toString()); + } + else + { + //They are the same magnitude. + bigger = new LInfiniteInteger(this.toString()); + smaller = new LInfiniteInteger(this.toString()); + } + //System.out.println("[ME] Bigger number is " + bigger.toString() + " and smaller is " + smaller.toString() + " negateing at end: " + negateAtEnd); + //For each digit in the bigger, subtract the bigger - the smaller, borrowing where needed + Node tmp1 = bigger.lastNode; + Node tmp2 = smaller.lastNode; + LInfiniteInteger answer = new LInfiniteInteger(""); + while(tmp1 != null) + { + //Get the numbers + int bignum = tmp1.data; + int smallnum = 0; + if(tmp2 != null) + { + smallnum = tmp2.data; + } + else + { + smallnum = 0; + } + //If the smaller number's digit is larger than the larger number's digit, we need to barrow + if(smallnum > bignum) + { + //System.out.println("[ME] Needing to barrow because " + smallnum + " > " + bignum); + barrow(tmp1.previous); + //System.out.println("[ME] After barrowing, number is " + bigger.toString()); + bignum = bignum+10; + } + //Then do regular subtraction + //System.out.println("[ME] Adding " + (bignum - smallnum) + " to answer, answer is " + answer.toString() + " bigger is " + bigger.toString() + " smaller is " + smaller.toString()); + answer.addfirst(bignum - smallnum); + tmp1 = tmp1.previous; + if(tmp2 != null) + { + tmp2 = tmp2.previous; + } + } + answer.removeLast(); // remove the 0 + //Remove any 0's at the beginning. + for(Node tmp = answer.firstNode; tmp != null && tmp != answer.lastNode; tmp = tmp.next) + { + if(tmp.data == 0) + { + answer.removeFirst(); + } + else + { + break; + } + } + //Retun the answer + answer.isNegative = negateAtEnd; + return answer; + } + private void barrow(Node n) + { + //System.out.println("[ME] Barrowing from " + n.data); + if(n.data != 0) + { + //System.out.println("[ME] Found something to barrow from: " + n.data); + n.data--; + } + else + { + barrow(n.previous); + n.data = 9; + } + } + /** + * 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() + { + String output = ""; + if(isNegative) + { + output += "-"; + } + for(Node tmp = firstNode; tmp != null; tmp = tmp.next) + { + //System.out.println("[ME] this node has " + tmp.data + " and it's next node is " + tmp.next); + output += tmp.data; + } + //System.out.println("[ME] Returning " + output); + return output; + } + + /** + * 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) + { + //System.out.println("[ME] Compareing " + this.toString() + " with " + anInfiniteInteger.toString()); + //If they're different signs, we're done. + if(this.isNegative() && !anInfiniteInteger.isNegative()) + { + return -1; + } + if(!this.isNegative() && anInfiniteInteger.isNegative()) + { + return 1; + } + //Otherwise, they're the same sign, and we need to compare digits. + //If one has more digits than the other, we're also done. + if(this.getNumberOfDigits() > anInfiniteInteger.getNumberOfDigits()) + { + return 1; + } + if(anInfiniteInteger.getNumberOfDigits() > this.getNumberOfDigits()) + { + return -1; + } + Node thattemp = new LInfiniteInteger(anInfiniteInteger.toString()).firstNode; + Node thistemp = this.firstNode; + for(; thistemp != null || thattemp != null;) + { + if(thistemp.data > thattemp.data) + { + return 1; + } + if(thistemp.data < thattemp.data) + { + return -1; + } + if(thistemp != null) + { + thistemp = thistemp.next; + } + if(thattemp != null) + { + thattemp = thattemp.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) + { + //Figure out if we're supposed to be negative or positive + boolean negateAtEnd = false; + //If we are negative and param is not, (- * +) answer will be negative + if(this.isNegative && !anInfiniteInteger.isNegative()) + { + negateAtEnd = true; + } + //If we are positive, and param is negitive (+ * -) answer will be negative + if(!this.isNegative && anInfiniteInteger.isNegative()) + { + negateAtEnd = true; + } + //Otherwise, we will be positive (+ * +) or (- * -) + //Unless one of the numbers is 0, in which case we can just return 0. + LInfiniteInteger thisusigned = new LInfiniteInteger(this.toString()); + LInfiniteInteger thatusigned = new LInfiniteInteger(anInfiniteInteger.toString()); + if((thisusigned.compareTo(new LInfiniteInteger("")) == 0) || (thatusigned.compareTo(new LInfiniteInteger("")) == 0)) + { + return new LInfiniteInteger(""); + } + //Find the number with more digits, and the one with fewer digits + LInfiniteInteger larger = null; + LInfiniteInteger smaller = null; + if(this.getNumberOfDigits() > anInfiniteInteger.getNumberOfDigits()) + { + larger = new LInfiniteInteger(this.toString()); + smaller = new LInfiniteInteger(anInfiniteInteger.toString()); + } + if(anInfiniteInteger.getNumberOfDigits() >= this.getNumberOfDigits()) + { + larger = new LInfiniteInteger(anInfiniteInteger.toString()); + smaller = new LInfiniteInteger(this.toString()); + } + //For every digit, multiply each other number by the digit, in order, and multiply the next answer by 10 (or just add a 0 to it) + LInfiniteInteger answer = new LInfiniteInteger(""); + int mult = 0; //Number to multiply the answers by + //System.out.println("[ME] Multiplying " + larger.toString() + " with " + smaller.toString()); + for(Node n = smaller.lastNode; n != null; n = n.previous) + { + LInfiniteInteger thismult = new LInfiniteInteger(""); + int carry = 0; + for(Node d = larger.lastNode; d != null; d = d.previous) + { + int product = n.data * d.data; + product += carry; + + if(product > 9) + { + carry = product/10; + } + else + { + carry = 0; + } + product %= 10; + //System.out.println("[ME] Product is " + product + " carry is " + carry); + thismult.addfirst(product); + } + if(carry > 0) + { + thismult.addfirst(carry); + } + + //Shift the mult over, so it will add up correctly + for(int i = 0; i < mult; i++) + { + thismult.addlast(0); + } + thismult.removeLast(); + //System.out.println("[ME] Attempting to add " + answer.toString() + " with " + thismult.toString()); + answer = (LInfiniteInteger) answer.plus(thismult); + mult++; + } + //answer.removeLast(); + answer.isNegative = negateAtEnd; + //If it's -something * 0, answer will be -0, just make it +0 + return answer; + } + + 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); + } + } +} |