//CMPT 212-Assignment 1
//Raymond Kin Hei Lee
//Feb 7, 2008
//
//Every number, I broke into sections of 9 digits, and put them each in a long variable, then
//I put them into an vector for data manipulation.
//
//Addition/Subtraction - I made two functions (Sum() and Difference()) for adding the 
//ABSOLUTE values of two values. I purposely broke the numbers up into chunks of 9 digits 
//(long holds 10), so I could store the result (long)a+(long)b back into a long variable. 
//After that, I took the carry and moved it onto the next vector component. Subtraction is 
//a similar idea. Afterwards, I made another function called Add and Subtract for performing 
//different Sum() and Difference() depending on the sign. ie. Subtract(-a,+b) = Difference(a,b)... 
//Add(-a,-b) = -Sum(a,b), etc.
//
//Multiplication - No special algorithms, just the same way as I would do on paper. However, I treated each 
//component within a vector (a long with 9 digits) as a single number when multiplying.
//
//Division - Since I couldn't come out with a good division algorithm, I decided to do it using a 
//Multiplication-Iteration method. ie. if a/b = c, then b*c = a. I used the midway iteration method, 
//which cuts down the possibility of getting the nx answers by 1/2 for every iteration.
//
//Other Functions - Most of them were just for my own convenience.. comparing vector sizes, 
//displaying the vector on dos prompt, etc.

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

int CompareV(vector<long> a, vector<long> b); // Compares the ABSOLUTE value of the two 
											//vectors, returns 1 if a>b, returns 2 if a<b, 0 if a=b
vector<long> readInput(string stringA, bool *sign, long *digit); // Takes the Cin input as a form of a 
																//string, then turns it into a 
																//vector the method I mentioned before.

void DisplayValue(vector<long> v_in, bool sign); //cout the values of the vector

bool checkValid(string stringA); //Check for "Invalid Inputs"

vector<long> Sum(vector<long> accum, vector<long> input); //Adds the ABSOLUTE value of two vectors

vector<long> Difference(vector<long> accum, vector<long> input, bool *sign);//Takes the ABSOLUTE difference of two vectors

vector<long> Add(vector<long> a, vector<long> b, bool *a_sign, bool *b_sign); //Adds two vectors. This function considers 
																			//the sign of vectors

vector<long> Subtract(vector<long> a, vector<long> b, bool *a_sign, bool *b_sign); //Finds a-b. Considers the sign

vector<long> Multiply(vector<long> a, vector<long> b, bool *a_sign, bool *b_sign); //Calculates a*b. Sign is considered

vector<long> DivideTwo(vector<long> a); //Finds A/2. Used for the iteration method I used for my division algorithm

vector<long> Division(vector<long> a, vector<long> b, bool *a_sign, bool *b_sign, long *a_digit, long *b_digit);
//Calculates the division of two vectors. A/B. Only the integer portion.


int CompareV(vector<long> a, vector<long> b) // Compares the ABSOLUTE value of the two 
											//vectors, returns 1 if a>b, returns 2 if a<b, 0 if a=b

{
	if(a.size()>b.size())
		return 1;
	else if(a.size()<b.size())
		return 2;
	else
	{
		for(long i = a.size()-1; i>=0;i--)
		{
		if(a[i]>b[i])
			return 1;
		else if(a[i]<b[i])
			return 2;
		}
		return 0;
	}
}

vector<long> Sum(vector<long> accum, vector<long> input) //Adds the ABSOLUTE value of accum and input
{
	vector<long> v_temp;
	long temp=0;
	long n=0;


	if(accum.size()>input.size())
	{
		n=accum.size();
		input.resize(n);
	}
	else
	{
		n=input.size();
		accum.resize(n);
	}
	

	int carrier =0;

	for(long i = 0; i < n; i++)
	{
	temp = accum[i] + input[i] + carrier;
	carrier =0;
	while(temp>=1000000000)
	{
		temp = temp - 1000000000;
		carrier++;
	}
	
	v_temp.push_back(temp);
	}
	if(carrier!=0)
	v_temp.push_back(carrier);
	return v_temp;
}

vector<long> Difference(vector<long> accum, vector<long> input, bool *sign) // Subtracts the absolute value, |accum|-|input|
{
	vector<long> v_temp;
	long temp=0;
	long n=0;
	switch(CompareV(accum,input))
	{
		case 1://accum bigger than input
		{
		input.resize(accum.size());
		for(unsigned long i=0; i< accum.size(); i++) 
			{
				if((accum[i] - input[i])<0)
				{
					v_temp.push_back(accum[i] + 1000000000 - input[i]);
					accum[i+1]--;
				}
				else
					v_temp.push_back(accum[i] - input[i]);
				
			}
			*sign = true;
			break;
		}
		case 2: //input bigger than accum
		{
		accum.resize(input.size());
		for(unsigned long i=0; i< input.size(); i++) 
			{
				if(input[i] - accum[i]<0)
				{
					v_temp.push_back( input[i] + 1000000000 - accum[i]);
					input[i+1]--;
				}
				else
					v_temp.push_back( input[i] - accum[i]);
				
			}
			*sign = false;
			break;
		}
		case 3:
			{
			v_temp.push_back( 0);
			*sign = true;
			break;
			}
	}
return v_temp;
}

vector<long> Add(vector<long> a, vector<long> b, bool *a_sign, bool *b_sign) // Adds A and B, will consider the signs
{
	if(((*a_sign == true) && (*b_sign == true)))
		return Sum(a,b);
	else if(((*a_sign == true) && (*b_sign == false)))
		return Difference(a,b,a_sign);
	else if(((*a_sign == false) && (*b_sign == true)))
		return Difference(b,a,a_sign);
	else if(((*a_sign == false) && (*b_sign == false)))
	{	
		*a_sign = false;
		return Sum(a,b);
	}
	return Sum(a,b);
}

vector<long> Subtract(vector<long> a, vector<long> b, bool *a_sign, bool *b_sign) //Subtracts, A-B, will consider sign
{
	if(((*a_sign == true) && (*b_sign == true)))
		return Difference(a,b,a_sign);
	else if(((*a_sign == true) && (*b_sign == false)))
		return Sum(a,b);
	else if(((*a_sign == false) && (*b_sign == true)))
	{	
		*a_sign = false;
		return Sum(a,b);
	}
	else if(((*a_sign == false) && (*b_sign == false)))
		return Difference(b,a,a_sign);
	return Difference(b,a,a_sign);
}


vector<long> Multiply(vector<long> a, vector<long> b, bool *a_sign, bool *b_sign)
{
	unsigned long long temp = 0 ;
	long counter =0;

	vector<long> product(a.size()+ b.size(), 0);
	
	if(((*a_sign == true) && (*b_sign==true)) || ((*a_sign == false) && (*b_sign==false)))
		*a_sign = true;
	else
		*a_sign = false;


	stringstream out;
	string keep = "0";
	string carrier = "0";
	
	a.push_back(0);
	for(long j=0; j<(long)b.size(); j++)
	{
		for(long i=0; i<(long)a.size(); i++)
		{
			temp = ((long long)a[i] * (long long)b[j]) + atol(carrier.data()) + product.at(i+j);
			out.str("");
			carrier="0";
			keep ="0";
			if(temp >= 1E9)
			{
				out << temp;
				carrier = out.str();
				keep = carrier.substr(carrier.size()-9, 9);
				carrier.erase(carrier.size()-9, 9);
				product.at(i+j) = (atol(keep.data()));	
				temp=0;
			}
			else 
			{	
				product.at(i+j) = (long)temp;
				temp=0;
			}

		}
	}
	while (product.at(product.size()-1)==0)
		product.pop_back();
	return product;
}

vector<long> DivideTwo(vector<long> a)
{
	
	long math=0;
	long carrier=0;
	bool temp_sign;
	long temp_digit;
	stringstream out;
	out.str("");
	string temp="";
	string temp2="";
	
	out << a.at(a.size()-1);

	temp = out.str();

	out.str("");

	for(long i=a.size()-2; i>=0;i--)
	{
	out << a[i];
	temp2 = out.str();
	for(int j=temp2.size(); j<9; j++)
		temp = temp+"0";
	temp = temp+ out.str();
	out.str("");
	
	}


	out.str("");


	for(long i=0; i<(long)temp.size(); i++)
	{
		math = (atol(temp.substr(i,1).data())+(carrier*10)) / 2;
		carrier =  (atol(temp.substr(i,1).data())+(carrier*10)) %2;
		out<<math;
		
	}
	
	temp2 = out.str();

	
	
	vector<long> v_temp;
	v_temp = readInput(temp2, &temp_sign, &temp_digit);
	return v_temp;
}





vector<long> Division(vector<long> a, vector<long> b, bool *a_sign, bool *b_sign, long *a_digit, long *b_digit)
{
	unsigned long long temp = 0 ;
	vector<long> v_temp;
	bool temp_sign = true;
	long temp_digit = 0;

	if(((*a_sign == true) && (*b_sign==true)) || ((*a_sign == false) && (*b_sign==false)))
		*a_sign = true;
	else
		*a_sign = false;

	stringstream out;

	string Display;

	
	stringstream fix_digit;
	string accum_digit;
	*a_digit = 0;

	fix_digit << a[a.size()-1];
	accum_digit = fix_digit.str();
	*a_digit = accum_digit.size();

	fix_digit.str("");

	for(long i=a.size()-2; i>=0; i--)
	{
		fix_digit<< a[i];
		accum_digit =fix_digit.str();
				
		for(long j = accum_digit.size(); j<9; j++)
			accum_digit = "0" + accum_digit;

		*a_digit =*a_digit + accum_digit.size();
		
		fix_digit.str("");
	}
	

	switch(CompareV(a, b)) // Compares the ABSOLUTE value of the two 
	{
		case 2: 
			{
				*a_sign = true;
				v_temp.push_back(0);
				return v_temp;
				break;
			}
		case 0: 
			{
				v_temp.push_back(1);
				return v_temp;
				break;
			}
		
		case 1:
			{
				long n = *a_digit - *b_digit;
				string bound="";
				
				vector<long> v_upper;
				vector<long> v_lower;
				vector<long> v_mid;
				vector<long> v_temp;
				
				bound = "1";
				for(int j=1; j<n; j++)
				bound += "0";
				v_lower = readInput(bound, &temp_sign, &temp_digit);

				bound = "9";
				for(int j=1; j<=n; j++)
				bound +="9";	
				v_upper = readInput(bound, &temp_sign, &temp_digit);
				
				v_mid = Sum(v_upper,v_lower);
				v_mid = DivideTwo(v_mid);		

				while(1)
				{

				v_temp = Multiply(b,v_mid,&temp_sign,&temp_sign);
				switch(CompareV(a,v_temp))
				{
				case 1:
					{
					v_lower = v_mid;
					break;
					}
				case 2:
					{
					v_upper = v_mid;
					break;
					}
				case 0:
					{
					return v_mid;
					break;
					}
				default:
					break;
				}
				
				v_mid = DivideTwo(Sum(v_upper,v_lower));

				if(Difference(v_upper, v_lower, &temp_sign)[0] ==1)
				{
					while (v_lower.at(v_lower.size()-1)==0)
						v_lower.pop_back();
					return v_lower;
				}
				
			}


				}
			}

	






	
return a;
}

vector<long> readInput(string stringA, bool *sign, long *digit) //Takes stringA, and turn it into a vector
{
	vector<long> v_temp;

	if(stringA[0] == '-')
	{
		*sign = false;
		stringA.erase(0,1);
	}
	else
	{
		*sign = true;
	}
	
	*digit = stringA.size();

	for(long i=*digit; i>9; i=i-9)
	{
		v_temp.push_back (atol(stringA.substr(i-9, 9).data()));
		stringA.erase (i-9,9);
		

	}

	v_temp.push_back (atol(stringA.data()));
	stringA.clear();

	return v_temp;
}

void DisplayValue(vector<long> v_in, bool sign) //cout the values of the vector
{
	stringstream out;
	string Display;

	if(sign==false)
		cout<<'-';
	
	
	cout << v_in[v_in.size()-1];

	for(long i=v_in.size()-2; i>=0; i--)
	{
		out<< v_in[i];
		Display =out.str();
				
		for(long j = Display.size(); j<9; j++)
			Display = "0" + Display;

		cout<<Display;
		out.str("");

	}

	cout<<endl;
}


bool checkValid(string stringA) 
{
	
	int signal=0;
	if(stringA[0] == '-')
		stringA.erase(0,1);
	
	for(long i = 0; i<(long)stringA.size(); i++)
	{	

		switch(stringA[i])
		{
			case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8':case '9': case '0':
				break;
			default:
			{
				signal =1;
				break;
			}
		}	
		
	}
	
	
	if(signal!=1)
		return true;
	else
		cout << "Invalid input"<<endl;
		return false;

}







int main()
{
	string input_string;
	vector<long> accum(1,0); 
	bool accum_sign = true;
	long accum_digit = 0;

	vector<long> input(1,0); 
	bool input_sign = true;
	char input_operation = 0 ;
	long input_digit = 0;

	cout<<"Value: ";
	DisplayValue(accum, accum_sign);
	

	while(input_string[0]!='E')
	{
		cout << "Enter: ";
		cin >> input_string;
	
	switch(input_string[0])
	{
	case 'C':
		input_string.erase(0,1);
		if(checkValid(input_string))
			accum = readInput("0", &accum_sign, &accum_digit);
		break;
	case 'E':
		if(checkValid(input_string))
		exit(0);
		break;
	case '=': 
		input_string.erase(0,1);
		if(checkValid(input_string))
			accum = readInput(input_string, &accum_sign, &accum_digit);
		break;
	case '+':
		input_string.erase(0,1);
		if(checkValid(input_string))
		{
		input = readInput(input_string, &input_sign, &input_digit);
		accum = Add(accum,input,&accum_sign, &input_sign);
		}
		break;
	case '-':
		input_string.erase(0,1);
		if(checkValid(input_string))
		{
		input = readInput(input_string, &input_sign, &input_digit);
		accum = Subtract(accum,input,&accum_sign, &input_sign);
		}
		break;
	case '*':
		input_string.erase(0,1);
		if(checkValid(input_string))
		{
		input = readInput(input_string, &input_sign, &input_digit);
		accum = Multiply(accum,input,&accum_sign, &input_sign);
		}
		break;
	case '/':
		input_string.erase(0,1);
		if(checkValid(input_string))
		{
			
		input = readInput(input_string, &input_sign, &input_digit);
		
		accum = Division(accum, input, &accum_sign, &input_sign, &accum_digit, &input_digit);
		}
		break;
	default:
		cout<<"Invalid input"<<endl;
		break;
	}
	
	cout<<"Value: ";
	DisplayValue(accum, accum_sign);


	}
}