vlong.cpp

very long 整数类

/* -------------- constructor start ----------------*/
// default constructor, which demand user to input the num
// need to catch input error exception
vlong::vlong()
{
	try
	{
		input();
		str_to_vec();
	}
	catch(domain_error) // if input is error, set vlong num to zero
	{
		cout << "INPUT ERROR!!!\n";
		cout << "num reset to ZERO\n";
		num_str = "0";
		str_to_vec();
	}
}

// constructor that takes another vlong type as parameter to copy constructor
// no mistake here if init num is a vlong num already
vlong::vlong(const vlong& in) : is_positive (in.is_positive), num_str (in.num_str)
{	str_to_vec();	}

// constructor that takes string type as parameter to copy constructor
// need to catch input error exception
vlong::vlong(const string& in) 
{
	try
	{
		num_str = in;
		is_positive = check_positive(num_str);	
		check_input(); // check if there is no-digit num in string, if so, throw error
		str_to_vec();
	}
	catch(domain_error) // if input is error, set vlong num to zero
	{
		cout << "INPUT ERROR!!!\n";
		cout << "num reset to ZERO\n";
		num_str = "0";
		str_to_vec();		
	}
}

// constructor that takes int type as parameter to copy constructor
// no mistake here if init num is a int type already
vlong::vlong(const int& in)
{
	is_positive = (in >= 0 ? true : false);

	// using fstream to transform int into string
	stringstream tran;
	tran << in;
	tran >>	num_str;
	
	str_to_vec();
}

// constructor that takes classical c char* string type as parameter to copy constructor
// need to catch input error exception
vlong::vlong(const char* in)
{
	try
	{
		string t(in);
		is_positive = check_positive(t);
		num_str = t;
		check_input(); // check if there is no-digit num in string, if so, throw error
		str_to_vec();
	}
	catch(domain_error) // if input is error, set vlong num to zero
	{
		cout << "INPUT ERROR!!!\n";
		cout << "num reset to ZERO\n";
		num_str = "0";
		str_to_vec();
	}
}

// constructor that takes std::vector type as parameter to copy constructor
vlong::vlong(const vector<long>& in, bool sig = true)
{
	is_positive = sig;
	num_vector = in;
	
	// clear the 0-start element so diminish the size of the vector
	while (!*num_vector.begin() && num_vector.size() > 1)
		num_vector.erase(num_vector.begin());
	vec_to_str();
}
/* -------------- constructor end ----------------*/


/* -------------- copy pass value overload start----------------*/
vlong& vlong::operator=(const vlong& v)
{
	num_str = v.num_str;
	is_positive = v.is_positive;
	str_to_vec();
	return *this;
}

vlong& vlong::operator=(const string& v)
{
	num_str = v;
	is_positive = check_positive(num_str);
	try
	{	
		check_input();
		str_to_vec();
	}
	catch (domain_error)
	{
		cout << "INPUT ERROR!!!\n";
		cout << "num reset to ZERO\n";
		num_str = "0";
		str_to_vec();
	}

	return *this;
}

vlong& vlong::operator=(const int& v)
{
	is_positive = (v >= 0 ? true : false);	
	stringstream tran;
	tran << v;
	tran >>	num_str;
	str_to_vec();
	return *this;
}

vlong& vlong::operator=(const char* v)
{
	string t(v);
	is_positive = check_positive(t);	
	num_str = t;
	try
	{
		check_input();
		str_to_vec();
	}
	catch(domain_error)
	{
		cout << "INPUT ERROR!!!\n";
		cout << "num reset to ZERO\n";
		num_str = "0";
		str_to_vec();
	}

	return *this;		
}

vlong& vlong::operator=(const vector<long>& v)
{
	is_positive = true;
	num_vector = v;
	vec_to_str();
	return *this;	
}
/* -------------- copy pass value overload ----------------*/


/* -------------- comparision overload ----------------*/
bool operator==(const vlong& l, const vlong& v)
{	return (l.get_str() == v.get_str() && l.get_sig() == v.get_sig());	}

bool operator!=(const vlong& l, const vlong& v)
{	return !(l == v);	}

bool operator>(const vlong& l, const vlong& r)
{
	bool tag;
	if (l.get_sig() && !r.get_sig())
		return true;
	if (!l.get_sig() && r.get_sig())
		return false;

	if (l.length() > r.length())
			tag = true;
	else
		if (l.length() < r.length())
			tag = false;
		else
			tag = l.get_str() > r.get_str();
	if (l.get_sig())
		return tag;
	return !tag;
}

bool operator>=(const vlong& l, const vlong& r)
{	return (l == r || l > r);	}

bool operator<(const vlong& l, const vlong& r)
{	return !(l >= r);	}

bool operator<=(const vlong& l, const vlong& r)
{	return !(l > r);	}
/* -------------- comparision overload ----------------*/


/* -------------- arithmetic overload ----------------*/
const vlong operator+(const vlong& l, const vlong& r)
{
	vector<long> shorter = l.length() <= r.length() ? l.get_vec() : r.get_vec();
	vector<long> longer = l.length() > r.length() ? l.get_vec() : r.get_vec();
	
	if (!l.get_sig() && r.get_sig())
		return r - -l;
	if (l.get_sig() && !r.get_sig())
		return l - -r;
	
	int cp = 0;
	
	vector<long> result(longer.size() + 1);

	vector<long>::iterator i = shorter.end() - 1;
	vector<long>::iterator j = longer.end() - 1;
	vector<long>::iterator k = result.end() - 1;

	for (vector<long>::size_type counter = 0; counter < shorter.size(); ++counter)
	{
		*k = *i-- + *j-- + cp;
		cp = *k-- / seg_num;
		cp ? *(k + 1) %= seg_num : 0;
	}

	if (cp != 0 && longer.size() == shorter.size())
		*k = 1;
	else if (longer.size() > shorter.size())
		*k-- = *j-- + cp;

	if (*(k + 1) / seg_num)
	{
		*(k + 1) %= seg_num;
		++(*k);
	}		

	for (vector<long>::size_type counter = shorter.size(); counter < longer.size() - 1; ++counter)
		*k-- = *j--; 

	vlong rst(result, l.get_sig());
	return rst;
}

const vlong operator-(const vlong& v) 
{
	vlong t(v);
	t.set_sig(!t.get_sig());
	return t;
}


const vlong operator-(const vlong& l, const vlong& r)
{
	if (!(l.get_sig() == r.get_sig()))
		return  l + -r;

	bool sign = (l >= r);

	if (l == r)
	{
		vlong r(0);
		return r;
	}

	vector<long> shorter = l < r ? l.get_vec() : r.get_vec();
	vector<long> longer = l < r ? r.get_vec() : l.get_vec();
	vector<long> result(longer.size() + 1);	
	
	int cp = 0;
	

	vector<long>::iterator i = shorter.end() - 1;
	vector<long>::iterator j = longer.end() - 1;
	vector<long>::iterator k = result.end() - 1;

	for (vector<long>::size_type counter = 0 ; counter < shorter.size(); ++counter)
	{
		*k = *j-- - *i-- - cp;
		if (*k < 0)
		{
			cp = 1;
			*k += seg_num;
		}
		else
			cp = 0;
		--k;
	}
	
	if (longer.size() > shorter.size())
		*k-- = *j-- - cp;

	for (vector<long>::size_type counter = shorter.size() + 1; counter < longer.size(); ++counter)
		*k-- = *j--;

	vlong rst(result, sign);
	return rst;
}

const vlong operator*(const vlong& l, const vlong& r)
{
	vector<long> result((l.length() + r.length()) / seg_length + 1 );
	
	bool sign = (l.get_sig() == r.get_sig());

	vector<long> shorter = l.length() <= r.length() ? l.get_vec() : r.get_vec();
	vector<long> longer = l.length() > r.length() ? l.get_vec() : r.get_vec();
	
	int cp = 0;
	
	vector<long>::iterator i = shorter.end() - 1;
	vector<long>::iterator j = longer.end() - 1;
	vector<long>::iterator k = result.end() - 1;
	
	// use to extend multiply result
	long low = 0;
	long high = 0;
	
	for (vector<long>::size_type m = 0 ; m < shorter.size(); ++m)
	{
		for (vector<long>::size_type n = 0; n < longer.size(); ++n)
		{
			low = (*i % divide) * (*j % divide);
			low += (*i / divide) * (*j % divide) % divide * divide;
			low += (*i % divide) * (*j / divide) % divide * divide;
			high = low / seg_num; // to high extend
			low %= seg_num;
			high += (*i / divide) * (*j % divide) / divide;
			high += (*i % divide) * (*j / divide) / divide;
			high += (*i / divide) * (*j / divide);

			*k += low;
			cp = *k / seg_num;
			*k-- %= seg_num;
			*k += high + cp;
			low = high = 0;
			--j;
		}
		k += longer.size();
		j += longer.size();
		--i;
		--k;
	}

	vlong rst(result, sign);
	return rst;
}

const vlong operator/(const vlong& lhs, const vlong& rhs)
{
	bool sign = (lhs.get_sig() == rhs.get_sig());
	string origin = lhs.get_str();
	string rst;
	int div_dig = 0;
	stringstream transfer;
	
	
	if (rhs == 0)
		throw domain_error("divide by zero");
	
	if (lhs < rhs)
		return *new vlong(0);
	
	vlong source = origin.substr(0, rhs.length() < origin.size() ? rhs.length() : origin.size());
	origin = origin.substr(source.length(), origin.size() - source.length());
	
	string tmp;
	while (origin.size() || source >= rhs)
	{
		while (source >= rhs)
		{ 
			source-=rhs;
			++div_dig;
		}
		if (div_dig)
		{
			transfer.clear();
			transfer << div_dig;
			transfer >> tmp;
			rst = rst + tmp ;
			div_dig = 0;
		}
		
		if (origin.size())
		{
			tmp = source.get_str() + origin.substr(0, 1);
			source = tmp;
			origin.erase(origin.begin());
		}
	}
	
	vlong r(rst);
	r.set_sig(sign);
	
	return r;
}

const vlong operator%(const vlong& lhs, const vlong& rhs)
{
	string origin = lhs.get_str();
	string rst;
	stringstream transfer;