/*
 *  VeryLargeInteger - manipulate N-digit integer numbers. (N <= RAM)
 *  Copyright (C) 2014  Daniel Latham
 *  
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *
 * VERSION: 
 * 1.1.2 Changed some method names, mod and remainder confused, clarified
 *       text in LargeIntTest, resubmitted FINAL
 * 1.1.1 - Fixed mod bug where returned could be more than dividend
 *         Turned this version in, 3rd, //NOT//FINAL
 * 1.1 - Optimized file length(Deleted extra muldiv method)
 * 1.0 - Working FAST div and mod! Documentation improved!
 * 0.7 everything working.
 * 0.6 div and mod buggy, quit for the night
 * 0.5 multiplication working
 * 0.1 add/subtract working
 *
 *
 */
public class VeryLargeInteger
{
	/**
	 * number declared to hold the value of given number in user
	 * code.
	 */
	public String number;
	/**
	 * revnumber is just the reversed version of the number string
	 */
	public String revnumber;
	/**
	 * Sign of number, true for positive numbers and
	 * false for negative numbers.
	 */
	public boolean sign; // true is pos, false is neg
	/** VeryLargeInteger constructor, So far it can add, subtract, multiply,
	 * divide, compare and modulo any two VeryLargeInteger objects that 
	 * have less than or equal to 2^32 digits because of all my calls to 
	 * the length function of the String class
	 * @param a Long number to be set as this.number
	 * @param sig Sign (+, - referred to true, false) of this
	 * @author Daniel_Latham
	 * @author l3li3l@uab.edu
	 */
	public VeryLargeInteger(long a, boolean sig)
	{
		number = String.valueOf(a);
		sign = sig;
		StringBuffer temp = new StringBuffer(number);
		temp = temp.reverse();
		revnumber = temp.toString();
	}
	/** VeryLargeIteger constructor
	 * @param b String of number to set as this.number
	 * @param sig Sign (+, - referred to true, false) of this
	 */
	public VeryLargeInteger(String b, boolean sig)
	{
		number = b.toString();
		//self explanatory but makes sure this.number != "" ; EmptyStringVal
		assert (number.length() != 0) : "Empty String Value!";
		sign = sig;
		StringBuffer temp = new StringBuffer(number);
		temp = temp.reverse();
		revnumber = temp.toString();
	}
	/** Prints our the number with sign prepended
	 */
	public void print()
	{
		if (number.length() == 1 && (int) number.charAt(0) - '0' == 0)
		{
			System.out.println(number);
		}
		else if (sign == true) 
		{
			String newnumber = number.replaceFirst ("^0*", "");
			System.out.println(newnumber);
		}
		else
		{
			String newnumber = number.replaceFirst ("^0*", "");
			System.out.println("-"+newnumber);
		}
	}
	/** Returns string of number with sign prepended
	 * @return number
	 */
	public String toString()
	{
		if (number.length() == 1 && (int) number.charAt(0) - '0' == 0) 
		{
			return(number);
		}
		else if (sign == true)
		{
			String newnumber = number.replaceFirst ("^0*", "");
			return newnumber;
		}
		else 
		{
			String newnumber = number.replaceFirst ("^0*", "");
			return("-" + newnumber);
		}
	}
	/** Checks to see if the two VLInumbers are the same
	 * @param other VLInumber you want to compare
	 * @return      The boolean of this.number == other.number
	 */
	public boolean equalTo(VeryLargeInteger other)
	{
		boolean isequal = false;
		boolean equals = (number.length() == other.number.length());
		if (equals == true)
		{
			for(int i = number.length()-1; i >= 0; i--)
			{
				if (((int) number.charAt(i)-'0') != ((int) other.number.charAt(i)-'0'))
				{
					isequal = false;
					break;
				}
				if (i == 0)//exact same number because previous if block was never tripped, sans sign
				{
					isequal = true;
				}
			}
		}
		isequal = isequal && (sign == other.sign); //same trick as seen in greaterThan method
		//thank you CS250
		return isequal;
	}
	/** Checks if this.number is larger than other.number
	 * @param other VLInumber to capare against, is this.number > other.number?
	 * @return      The boolean of this.number > other.number
	 */
	public boolean greaterThan(VeryLargeInteger other)
	{
		boolean isgreater = (number.length() > other.number.length());//Final value to be returned
		boolean isequal = false; //if equals block is tripped, this will be set true if the two strings are actually equal
		boolean equals = (number.length() == other.number.length());
		if (equals == true)
		{
			for(int i = number.length()-1; i >= 0; i--)
			{
				if (((int) revnumber.charAt(i)-'0') > ((int) other.revnumber.charAt(i)-'0'))
				{
					isgreater = true;
					break;
				}
				else if (((int) other.revnumber.charAt(i)-'0') > ((int) revnumber.charAt(i)-'0'))
				{
					isgreater = false;
					break;
				}
				if (i == 0)//exact same number sans sign
				{
					isequal = true;
				}
			}
		}
		isequal = isequal && (sign == other.sign);//true if signs are the same and isequal is true, not if not
		if (isequal == true)
		{
			return false;//if they are equal, they are the "same" VLI x, then x is not greater than x
		}
		if (isgreater == true)
		{
			if (sign != other.sign)
			{
				isgreater = sign;//if signs differ, then value will equal whatever this.sign  is
			}
		}
		else if (isgreater == false)
		{
			if (sign != other.sign)
			{
				isgreater = sign;//if signs differ
			}
		}
		return isgreater;
	}

	/** Adds this.number to other.number
	 * @param other
	 * @return       VLInumber
	 */
	public VeryLargeInteger add(VeryLargeInteger other)
	{
		/* Check sign values, decide if we want numPlusPlus(same signs)
		 * or numPlusMin(different signs).
		 */
		VeryLargeInteger newvli = null;
		if ((sign == false && other.sign == false) || (sign == true && other.sign == true))
		{
			if (number.length() >= other.number.length())// size of self >= other
			{
				newvli = numPlusPlus(revnumber, other.revnumber, 0);
			}
			else if (number.length() < other.number.length())//size of self < other
			{
				newvli = numPlusPlus(other.revnumber, revnumber, 0);
			}
		}
		else if(sign == true && other.sign == false)
		{
			newvli = numPlusMin(revnumber, other.revnumber, 0);
		}
		else if(sign == false && other.sign == true)
		{
			newvli = numPlusMin(other.revnumber, revnumber, 0);
		}
		
		return newvli;
	}
	/** Subtracts other.number from this.number
	 * @param other
	 * @return       VLInumber
	 */
	public VeryLargeInteger sub(VeryLargeInteger other)
	{
		VeryLargeInteger newvli = null;
		VeryLargeInteger a = new VeryLargeInteger(number, true);
		VeryLargeInteger b = new VeryLargeInteger(other.number, true);
		if (sign == true && other.sign == true)//both are positive
		{
			newvli = numPlusMin(revnumber, other.revnumber, 0);
		}
		else if (sign == false && other.sign == false)//both are negative
		{
			newvli = numPlusMin(other.revnumber, revnumber, -1);
		}
		else if (sign == true && other.sign == false)// -- makes plus of other.number
		{
			if (a.greaterThan(b)) //BIGGER not GREATER in this case, since both are set to positive
			{
				newvli = numPlusPlus(revnumber, other.revnumber, 0);
			}
			else
			{
				newvli = numPlusPlus(other.revnumber, revnumber, 0);
			}
		}
		else if (sign == false && other.sign == true)
		{
			if (a.greaterThan(b))
			{
				newvli = numPlusPlus(revnumber, other.revnumber, -1);
			}
			else
			{
				newvli = numPlusPlus(other.revnumber, revnumber, -1);
			}
		}
		return newvli;
	}

	/** Multiplies this.number by other.number
	 * @param other 
	 * @return          VLInumber
	 */
	public VeryLargeInteger mul(VeryLargeInteger other)
	{
		VeryLargeInteger newvli = null;
		if ((number.length() == 1 && ((int) revnumber.charAt(0) - '0') == 0) || //0 * num or num * 0 returns 0
			(other.number.length() == 1 && ((int) other.revnumber.charAt(0) - '0') == 0))
		{
			newvli = new VeryLargeInteger(0L, true);
		}
		else
		{
			newvli = emult(number, other.number);
		}
		boolean newsign = (other.sign == sign); //false if dif signs, so neg is dif
		newvli = new VeryLargeInteger(newvli.number, newsign);
		return newvli;
	}
	/** Divides this.number by other.number, deals with sign rules
	 * @param other
	 * @throws Exception
	 * @return        VLInumber
	 */
	public VeryLargeInteger div(VeryLargeInteger other)
	throws Exception
	{
		VeryLargeInteger newvli = null;
		VeryLargeInteger[] vliarray = null;
		VeryLargeInteger a = new VeryLargeInteger(number, true);
		VeryLargeInteger b = new VeryLargeInteger(other.number, true);
		 //If other == 0, exit()
		if (other.number.length() == 1 && (((int) other.number.charAt(0) - '0') == 0))
		{
			System.out.println("You can't divide by 0!");
			System.exit(0);
		}
		 //If self == 0, return 0
		if (number.length() == 1 && ((int) revnumber.charAt(0) - '0') == 0)
		{
			newvli = new VeryLargeInteger(0L, true);
		}
		//If same number, return 1
		else if (this.equalTo(other) == true) 
		{
			newvli = new VeryLargeInteger(1L, true);
		}
		//If trying to divide this int by a larger int
		else if (b.greaterThan(a))
		{
			newvli = new VeryLargeInteger(0L, true);
		}
		//Else dividing by same signs, normal
		else if (other.sign == sign)
		{
			newvli = moddiv(number, other.number)[0];
			newvli = new VeryLargeInteger(newvli.number, true);
		}
		//Else dividing by dif signs, negative
		else if (other.sign != sign)
		{
			newvli = moddiv(number, other.number)[0];
			newvli = new VeryLargeInteger(newvli.number, false);
		}
		
		return newvli;
	}
	/** Calaculates this.number / other.number returning the remainder 
	 * and deals with weird sign rules
	 * @param other
	 * @throws Exception
	 * @return        VLInumber
	 */
	public VeryLargeInteger mod(VeryLargeInteger other)
	throws Exception
	{
		VeryLargeInteger newvli = null;
		VeryLargeInteger a = new VeryLargeInteger(number, true);
		VeryLargeInteger b = new VeryLargeInteger(other.number, true);
		//If trying to mod by 0, exit()
		if (other.number.length() == 1 && ((int) other.revnumber.charAt(0) - '0') == 0)
		{
			System.out.println("You can't divide by 0!");
			System.exit(0);
		}
		//if self == 0, return 0
		if (number.length() == 1 && (((int) revnumber.charAt(0) - '0') == 0))
		{
			newvli = new VeryLargeInteger(0L, true);
		}
		//if same number, return 0
		else if (a.equalTo(b) == true)
		{
			newvli = new VeryLargeInteger(0L, true);
		}
		//if this < that, return this
		else if (b.greaterThan(a))
		{
			newvli = this;
		}
		//if same signs
		else if (other.sign == sign && sign == true)
		{
			newvli = moddiv(number, other.number)[2];
			newvli = new VeryLargeInteger(newvli.number, true);
		}
		//dif signs
		else if (sign == false && other.sign == true)
		{
			newvli = moddiv(number, other.number)[2];
			newvli = new VeryLargeInteger(newvli.number, false);
		}
		//same signs, weird for mod
		else if (other.sign == sign && sign == false)
		{
			newvli = moddiv(number, other.number)[2];
			newvli = new VeryLargeInteger(newvli.number, false);
		}
		//everything else
		else
		{
			newvli = moddiv(number, other.number)[2];
			newvli = new VeryLargeInteger(newvli.number, true);
		}
		
		return newvli;
	}
	/** Helper method Adds two positive or two negative numbers
	 * @param bigger The larger of the two VLInumber by number of digits
	 * @param smaller The smaller of the two VLInumbers by number of digits
	 * @param forcedsign If -1, then the computed new VLInumber will have
	 *                   a negative sign
	 * @throws ArrayOutOfBoundsException
	 * @return           VLInumber that is the addition of the two numbers, 
	 *                   forcing a negative sign if needed
	 */
	private VeryLargeInteger numPlusPlus(String bigger, String smaller, int forcedsign)
	{
		VeryLargeInteger newvli = null;
		String newnumber = ""; // Must reverse this at end
		boolean rollover = false;
		
		for (int i = 0; i < bigger.length(); i++)
		{
			int k; //placeholder value
			try
			{
				k = ((int) bigger.charAt(i)-'0') + ((int) smaller.charAt(i)-'0'); //throws AIOOB E
				//System.out.println((int) '9' - '0'); //DEBUG
				if (rollover == true) { k+=1; rollover = false; }//if rollover, add 1 to placeholder
				if (k >= 10) { k -=10; rollover = true; }
				newnumber+=k;
			}
			catch (Exception e) //Expected ArrayIndexOOB exception
			{
				k = ((int) bigger.charAt(i)-'0');
				if (rollover == true)
				{
					k+=1;
					if (k >= 10) { k -=10; rollover = true; }
					else rollover = false;
				}
				newnumber+=k; //add placeholder to stack, start again
			}
			if (i == bigger.length()-1 && rollover == true) { newnumber+=1; rollover = false; }
		}
		StringBuffer vjk = new StringBuffer(newnumber); //Convert to StringBuffer object to reverse string easily
		vjk.reverse();
		newnumber = vjk.toString(); //convert back to string, initialize newvli;
		if (forcedsign == -1)
		{
			newvli = new VeryLargeInteger(newnumber, false); //forces a negative sign
		}
		else
		{
			newvli = new VeryLargeInteger(newnumber, sign);
		}
		return newvli;
	}
	/** Helper method Adds a two different signed VLInumbers or subtracts two same signed
	 * VLInumbers
	 * @param bigger Bigger number as in number of digits
	 * @param smaller Smaller number as in number of digits
	 * @throws ArrayOutOfBoundsException
	 * @return          String value of new number to numPlusMin, which then
	 *                  computes the sign
	 */
	private String subtralpha(String bigger, String smaller)
	{ //I'm so sorry
		String newnumber = "";
		for(int i = 0; i < bigger.length(); i++)
		{
			int k; //placeholder value
			int tempnum; //don't remember why I put this here
			try
			{
				k = ((int) bigger.charAt(i)-'0') - ((int) smaller.charAt(i)-'0');
				// DEBUG System.out.println(k);
			}
			catch (Exception e)
			{
				k = ((int) bigger.charAt(i)-'0');
			}
			if (k < 0)
			{
				k = ((int) bigger.charAt(i)-'0');
				int j = 1;
				while(k < ((int) smaller.charAt(i)-'0'))
				{
					if (((int) bigger.charAt(i+j)-'0') >= 1) //Borrow from number
					{
						int tempint = ((int) bigger.charAt(i+j)-'0');
						tempint -= 1;
						StringBuffer temp = new StringBuffer(bigger);
						/* Took a while to understand
						 * StringBuffer.replace uses inclusive/exclusive/int
						 * I kept doing incl/incl/int and couldn't understand what
						 * I was doing wrong
						 */
						temp.replace(i+j,i+j+1,Integer.toString(tempint)); 
						bigger = temp.toString();
						k+=10;
					}
					else /*If can't borrow from next number, next number must
						* be zero, so changed zero to 9, and iterate again
						*/
					{
						StringBuffer temp = new StringBuffer(bigger);
						temp.replace(i+j,i+j+1, "9");
						bigger = temp.toString();
					}
					j++;//capable of iterating infinitely if needed
				}
				k = k - ((int) smaller.charAt(i)-'0');
			}
			// DEBUG System.out.println(k);
			newnumber += k;
			// DEBUG System.out.println(newnumber);
		}
		//System.out.println(newnumber);
		return newnumber;
	}
	/** Helper method Tests which number has more digits/is larger and then calls subtralpha 
	 * on the two numbers, only then computing the sign of the new VLInumber
	 * @param pos Positive number
	 * @param neg Negative number
	 * @param forcedsign If -1 then forces result to a negative
	 * @return            VLInumber to add/sub
	 */
	private VeryLargeInteger numPlusMin(String pos, String neg, int forcedsign)
	{
		VeryLargeInteger newvli = null;
		boolean longer = (pos.length() > neg.length());
		boolean equals = (pos.length() == neg.length());
		if (equals == true)
		{
			//find which one, pos or neg, is actually the greater number
			//through iteration, high to low values
			for(int i = pos.length()-1; i >= 0; i--)
			{
				if (((int) pos.charAt(i)-'0') > ((int) neg.charAt(i)-'0'))
				{
					longer = true; //see above
					break;
				}
				else if (((int) neg.charAt(i)-'0') > ((int) pos.charAt(i)-'0'))
				{
					longer = false;
					break;
				}
				if (i == 0)//exact same number wow you win wowow
				{
					newvli = new VeryLargeInteger(0L, true);
					return newvli;
				}
			}
		}

		String newnumber = "";
		if (longer == true)//pos is bigger
		{
			newnumber = subtralpha(pos, neg);
		}
		if(longer == false)//neg is bigger
		{
			newnumber = subtralpha(neg, pos);
		}
		StringBuffer newbuffer = new StringBuffer(newnumber);
		newbuffer.reverse();
		newnumber = newbuffer.toString();
		newnumber = newnumber.replaceFirst ("^0*", "");
		
		newvli = new VeryLargeInteger(newnumber, longer);
		return newvli;
	}
	/** Helper method that multiplies two numbers using a string stack for the current computation
	 * and a VLInumber for the total
	 * @param self
	 * @param other
	 * @return       VLInumber
	 */
	private VeryLargeInteger emult(String self, String other)
	{
		int place = -1;
		VeryLargeInteger total = new VeryLargeInteger(0L, true); //add newvli to total every iteration
		for (int i = self.length()-1; i >= 0; i--)//iterate over number on "bottom"
		{
			VeryLargeInteger newvli = null; //newvli to hold value temporarily of stack
			String stack = ""; //stack of integers for each line computed, just like on paper
			place += 1; //perm holder for number of zeros to prepend
			int k = place; //set to place because need to add place number of zeroes each time
			int rollover = 0;
			for (int j = other.length()-1; j >= 0; j--)//iterate over number on "top"
									//multiplying by digit on "bottom", adding to stack
			{
				while (k > 0)//iterate through all prepended zeros and add them to stack
				{
					stack += "0";
					k -= 1;
				}
				int temp = ((int) self.charAt(i)-'0') * ((int) other.charAt(j)-'0');
				if (temp >= 10) //2 or more digits
				{
					if (j == 0) //if last digit on "top", add the rollover number if there is one, split and append to stack
					{
						temp += rollover;
						rollover -= rollover;
						String tempsplit = Integer.toString(temp);
						stack += (int) tempsplit.charAt(1) - '0';
						stack += (int) tempsplit.charAt(0) - '0';
					}
					else //split, add to rollover, append
					{
						if (rollover > 0) //if rollover already init, add to temp
						{
							temp += rollover;
							rollover -= rollover;
						}
						String tempsplit = Integer.toString(temp);
						rollover = (int) tempsplit.charAt(0) - '0';
						stack += (int) tempsplit.charAt(1) - '0';
					}
				}
				else
				{
					stack+=temp;
				}
				// DEBUG System.out.println("Stack " +i+" "+ stack);
				
			}
			StringBuffer bufftemp = new StringBuffer(stack);
			bufftemp = bufftemp.reverse();
			stack = bufftemp.toString();
			newvli = new VeryLargeInteger(stack, true);
			total = total.add(newvli);
			
		}
		return total;
	}
	/** Final quick-and-dirty helper method for the mod(remainder, not modular arithmetic) and div by power-of-2 multiplication
	 * @param self Dividend
	 * @param other Divisor
	 * @throws Exception
	 * @return VeryLargeInteger Array
	 * 
	 */
	private VeryLargeInteger[] moddiv(String self, String other)//returns array of VLIs instead of boolean deciding
	throws Exception
	{
		VeryLargeInteger selfvli = new VeryLargeInteger(self, true);
		VeryLargeInteger othervli = new VeryLargeInteger(other, true);
		VeryLargeInteger totalvli = new VeryLargeInteger(other, true);//total
		VeryLargeInteger countvli = new VeryLargeInteger(1L, true);//div
		VeryLargeInteger newadd = new VeryLargeInteger(0L, true);//placeholder
		VeryLargeInteger lastadd = new VeryLargeInteger(totalvli.number, true); //placeholder
		VeryLargeInteger lastcount = new VeryLargeInteger(countvli.number, true);//placeholder
		VeryLargeInteger remvli = new VeryLargeInteger(0L, true);//remainder
		final VeryLargeInteger MULT_BY_2 = new VeryLargeInteger(2L, true);
		while (!totalvli.equalTo(selfvli) && selfvli.greaterThan(totalvli))//powers of 2 until total >= self
		{
			lastcount = new VeryLargeInteger(countvli.number, true);
			lastadd = new VeryLargeInteger(totalvli.number, true);
			newadd = totalvli.mul(MULT_BY_2);
			totalvli = new VeryLargeInteger(newadd.number, true);
			countvli = countvli.mul(MULT_BY_2);
		}
		if (totalvli.equalTo(selfvli))//total == self, return {x, y, 0}
		{
			VeryLargeInteger[] final1 = {countvli, totalvli, remvli};
			return final1;
		}
		else
		{
			countvli = lastcount;
			totalvli = lastadd;
			remvli = selfvli.sub(totalvli);
			if (othervli.greaterThan(remvli)) //if this, then remainder != 0
			{
				VeryLargeInteger[] final1 = {countvli, totalvli, remvli};
				return final1;
			}
			//recursion for all smaller values :)
			//Base cases are above if blocks
			VeryLargeInteger[] newbarray = this.moddiv(remvli.number, othervli.number);
			remvli = newbarray[2]; //remainder
			totalvli = totalvli.add(newbarray[1]);
			countvli = countvli.add(newbarray[0]);
			VeryLargeInteger[] final1 = {countvli, totalvli, remvli};
			return final1;//this VLInumber is actually returned
		}
	}
}