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