Inital commitHEADmaster

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);
+		}
+	}
+}