Fivt_4/task-A/07.12.2017

#ifndef FIVT_4_BIGINTEGER_H
#define FIVT_4_BIGINTEGER_H

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

const unsigned int BASE = 10;

class BigInteger {
public:
	BigInteger(const std::vector<int>& _numbers, bool _is_positive);
	BigInteger(int integer_value);
	BigInteger();
	void Print() const;
	bool GetIsPositive() const;
	size_t GetNumberOfDigits() const;
	std::vector<int> GetVectorOfDigits() const;
	void SetIsPositive(bool sign);
	void MultiplyOnBase();
	void DeleteLeadZeros();

	BigInteger operator + (const BigInteger& other) const;
	BigInteger operator - (const BigInteger& other) const;
	BigInteger operator - ();
	BigInteger operator * (const BigInteger& other) const;
	BigInteger operator / (const BigInteger& other) const;
	BigInteger operator % (const BigInteger& other) const;

	void operator += (const BigInteger& other);
	void operator -= (const BigInteger& other);
	void operator *= (const BigInteger& other);
	void operator /= (const BigInteger& other);

	BigInteger operator++() const; 				// prefix-form
	BigInteger operator++(int notused) const; // postfix-form
	BigInteger operator--() const; 				// prefix-form
	BigInteger operator--(int notused) const; // postfix-form

	bool operator==(const BigInteger& other) const;
	bool operator!=(const BigInteger& other) const;
	bool operator<=(const BigInteger& other) const;
	bool operator>=(const BigInteger& other) const;
	bool operator<(const BigInteger& other) const;
	bool operator>(const BigInteger& other) const;

	// input - output
	friend std::ostream &operator<<(std::ostream& stream, const BigInteger& big_integer);
	friend std::istream &operator>>(std::istream& stream, BigInteger& big_integer);

	// type conversion
	operator int();
	operator bool();

	std::string toString();
private:
	std::vector<int> vector_of_digits;
	bool is_positive;
	bool CompareByAbs(const BigInteger& other) const;
};




BigInteger::BigInteger(const std::vector<int>& _numbers, bool _is_positive) {
	vector_of_digits = _numbers;
	is_positive = _is_positive;
}



BigInteger::BigInteger(int integer_value) {
	std::vector<int> digits;
	is_positive = (integer_value >= 0);
	integer_value = ( integer_value < 0 )? -integer_value : integer_value;
	if ( integer_value == 0  ) {
		digits.push_back(0);
	} else {
		int current_rest = 0;
		int prev_rest = 0;
		unsigned long long charge = BASE;
		while (true) {
			prev_rest = current_rest;
			current_rest = integer_value % charge;
			digits.push_back((current_rest - prev_rest) / (charge / BASE));
			if (current_rest == integer_value) {
				break;
			}
			charge *= BASE;
		}
	}
	vector_of_digits = digits;
}




BigInteger::BigInteger() {
	std::vector<int> digits;
	vector_of_digits = digits;
	is_positive = true;
}



std::vector<int> BigInteger::GetVectorOfDigits() const {
	return vector_of_digits;
}



bool BigInteger::GetIsPositive() const {
	return is_positive;
}


BigInteger BigInteger::operator+(const BigInteger &other) const {

	// this is positive, other is negative
	if (this->GetIsPositive() && !other.GetIsPositive()) {						// (+a) + (-b)
		BigInteger other_positive = other;										// MEMORY!
		other_positive.SetIsPositive(true);
		return (*this - other_positive);

		// this is negative, other is positive
	} else if (!this->GetIsPositive() && other.GetIsPositive()) {				// (-a) + (+b)
		BigInteger this_positive = *this;										// MEMORY!
		this_positive.SetIsPositive(true);
		return (other - this_positive);

		// this & other are negative
	} else if (!this->GetIsPositive() && !other.GetIsPositive()) {
		BigInteger this_positive = *this;										// MEMORY!
		this_positive.SetIsPositive(true);
		BigInteger other_positive = other;										// MEMORY!
		other_positive.SetIsPositive(true);
		return -(this_positive + other_positive);

		// both operands are positive
	} else {

		auto other_vector_of_numbers = other.GetVectorOfDigits();
		std::vector<int> result;
		size_t n = vector_of_digits.size();
		size_t m = other_vector_of_numbers.size();

		int to_next_charge = 0;
		for (size_t i = 0; i < n || i < m; ++i) {
			int rest = 0;
			int number = 0;

			number = ((i < m)? other_vector_of_numbers[i]:0) + ((i < n)? vector_of_digits[i]:0) + to_next_charge;
			rest = number%BASE;
			if ( number >= BASE) {
				to_next_charge = 1;
				number = rest;
			} else {
				to_next_charge = 0;
			}

			result.push_back(number);
		}

		if (to_next_charge != 0) {
			result.push_back(to_next_charge);
		}

		return {result, true};
	}
}



BigInteger BigInteger::operator-(const BigInteger &other) const {

	// this is positive, other is negative
	if (this->GetIsPositive() && !other.GetIsPositive()) {
		BigInteger other_positive = other;										// (+a) - (-b)
		other_positive.SetIsPositive(true);
		return (*this + other_positive);

		// this is negative, other is positive
	} else if (!this->GetIsPositive() && other.GetIsPositive()) {			// (-a) - (+b)
		BigInteger this_positive = *this;										// MEMORY!
		this_positive.SetIsPositive(true);
		BigInteger other_positive = other;										// MEMORY!
		other_positive.SetIsPositive(true);
		return -(this_positive + other_positive);									// -((+a) + (+b))

		// this & other are negative
	} else if (!this->GetIsPositive() && !other.GetIsPositive()) {			//(-a) - (-b)
		BigInteger this_positive = *this;										// MEMORY!
		this_positive.SetIsPositive(true);
		BigInteger other_positive = other;										// MEMORY!
		other_positive.SetIsPositive(true);
		return (other_positive - this_positive);

		// both operands are positive
	} else {																//(+a) - (+b)
		std::vector<int> result;
		// из большего - меньшее
		if ( *this > other ) {

			auto other_vector_of_numbers = other.GetVectorOfDigits();

			size_t n = vector_of_digits.size();
			size_t m = other_vector_of_numbers.size();

			int to_next_charge = 0;
			int number = 0;

			for (size_t i = 0; i < n || i < m; ++i) {
				number = vector_of_digits[i] - ((i < m)? other_vector_of_numbers[i]:0) - to_next_charge;
				if (number < 0) {
					result.push_back(number + BASE);
					to_next_charge = 1;
				} else {
					result.push_back(number);
					to_next_charge = 0;
				}
			}

			// убираем нули в конце
			while (result.back() == 0) {
				result.pop_back();
			}

			return {result, true};

			// сводим к вычитанию из большего меньшее
		} else if (*this == other) {
			result.push_back(0);
			return {result, true};
		} else {
			return -(other - *this);
		}
	}
}



BigInteger BigInteger::operator-() {
	this->is_positive = false;
	return *this;
}



BigInteger BigInteger::operator*(const BigInteger &other) const {

	size_t n = this->GetNumberOfDigits();
	size_t m = other.GetNumberOfDigits();

	// умножение длинного на короткое
	if ( n >= m ) {

		std::vector<int> this_vector = this->GetVectorOfDigits();
		std::vector<int> other_vector = other.GetVectorOfDigits();

		bool result_sign = this->GetIsPositive() & other.GetIsPositive();

		std::vector<BigInteger> parts;
		for (int j = 0; j < m; ++j) { // идем по короткому
			int to_next_charge = 0;
			std::vector<int> new_part(n + j);
			for (int i = 0; i < n; ++i) { // по длинному

				int value = (other_vector[j] * this_vector[i]) + to_next_charge;
				int rest = value % BASE;

				if ( rest < value ) { //число больше 10
					to_next_charge = (value - rest)/BASE;
				} else {
					to_next_charge = 0;
				}
				new_part[i + j] = rest;

			}

			if ( to_next_charge > 0 ) {
				new_part.push_back(to_next_charge);
			}

			parts.push_back({new_part,true});
		}

		BigInteger result = parts[0];
		for(int i = 1; i < parts.size(); ++i) {
			result += parts[i];
		}

		result.DeleteLeadZeros();

		return result;

	} else {
		return (other * (*this));
	}

}


void BigInteger::MultiplyOnBase() {
	vector_of_digits.insert(vector_of_digits.begin(),0);
}



void BigInteger::DeleteLeadZeros() {
	while (vector_of_digits.back() == 0 && vector_of_digits.size() > 1) {
		vector_of_digits.pop_back();
	}
}


BigInteger BigInteger::operator/(const BigInteger& other) const {

	bool result_sign = this->GetIsPositive() & other.GetIsPositive();
	BigInteger other_positive = {other.GetVectorOfDigits(), true};
	BigInteger this_positive = {this->GetVectorOfDigits(), true};


	std::vector<int> result_vector;

	if (other_positive > this_positive) {
		result_vector.push_back(0);
		return {result_vector, true};

	} else if (other_positive == this_positive) {
		result_vector.push_back(1);
		return {result_vector, result_sign};

	} else { //this > other		// what if this == {0}

		size_t n = this->GetNumberOfDigits();
		result_vector.resize(n);	// число разрядов в частном не больше чем в делимом
		std::vector<int> this_vector = this->GetVectorOfDigits();
		BigInteger current_value;

		for (int i = n - 1; i >= 0; i--) {

			current_value.MultiplyOnBase();
			current_value.vector_of_digits[0] = this_vector[i]; //?? private

			// подбираем максимальное число x, такое что other * attempt <= curent_value
			for (int l = 0; l <= BASE; ++l) {

				BigInteger attempt({l}, true);
				BigInteger cur = other_positive * attempt;

				if (cur > current_value) {
					result_vector[i] = l - 1;
					current_value = current_value - other_positive * BigInteger({l - 1}, true);
					current_value.DeleteLeadZeros();
					break;
				}
			}
		}

		BigInteger result {result_vector, result_sign};
		result.DeleteLeadZeros();

		return result;
	}
}



BigInteger BigInteger::operator%(const BigInteger &other) const {

	bool result_sign = this->GetIsPositive() & other.GetIsPositive();
	BigInteger other_positive = {other.GetVectorOfDigits(), true};
	BigInteger this_positive = {this->GetVectorOfDigits(), true};


	std::vector<int> result_vector;

	if (other_positive > this_positive) {
		result_vector.push_back(0);
		return {result_vector, true};

	} else if (other_positive == this_positive) {
		result_vector.push_back(1);
		return {result_vector, result_sign};

	} else {

		size_t n = this->GetNumberOfDigits();
		result_vector.resize(n);	// число разрядов в частном не больше чем в делимом
		std::vector<int> this_vector = this->GetVectorOfDigits();
		BigInteger current_value;

		for (int i = n - 1; i >= 0; i--) {

			current_value.MultiplyOnBase();
			current_value.vector_of_digits[0] = this_vector[i];

			// подбираем максимальное число x, такое что b * x <= curValue
			for (int l = 0; l <= BASE; ++l) {

				BigInteger attempt({l}, true);
				BigInteger cur = other_positive * attempt;

				if (cur > current_value) {
					result_vector[i] = l - 1;
					current_value = current_value - other_positive * BigInteger({l-1}, true);
					current_value.DeleteLeadZeros();
					break;
				}
			}
		}
		current_value.SetIsPositive( result_sign );
		return current_value;
	}
}



void BigInteger::operator+=(const BigInteger &other) {
	*this = (*this + other);
}



void BigInteger::operator-=(const BigInteger &other) {
	*this = (*this - other);
}

void BigInteger::operator*=(const BigInteger &other) {
	*this = (*this * other);
}



void BigInteger::operator/=(const BigInteger &other) {
	*this = (*this / other);
}




bool BigInteger::operator==(const BigInteger &other) const {
	size_t  n = this->GetNumberOfDigits();
	if ( n != other.GetNumberOfDigits() ) {
		return  false;
	} else {
		if ( this->GetIsPositive() != other.GetIsPositive() ) {
			return  false;
		} else {
			auto this_vector = this->GetVectorOfDigits();
			auto other_vector = other.GetVectorOfDigits();
			for (size_t i = 0; i < n; ++i) {
				if (this_vector[i] != other_vector[i]) { // there isn't matter where we are starting
					return false;
				}
			}
			return true;
		}
	}
}



void BigInteger::Print() const {
	std::vector<int> vector = GetVectorOfDigits();
	for (int i = vector.size() - 1; i >= 0; --i) {
		std::cout<<vector[i];
	}
	std::cout<<'\n';
}



size_t BigInteger::GetNumberOfDigits() const {
	return vector_of_digits.size();
}

bool BigInteger::operator!=(const BigInteger &other) const {
	return !( *this == other );
}

bool BigInteger::operator<=(const BigInteger &other) const {
	bool is_equal = ( *this == other );
	bool is_less = (*this < other);
	return is_equal || is_less;
}



bool BigInteger::operator>=(const BigInteger &other) const {
	bool is_equal = ( *this == other );
	bool is_more = (*this > other);
	return is_equal || is_more;
}



bool BigInteger::CompareByAbs(const BigInteger &other) const { // is this < other by abs?
	size_t  n = this->GetNumberOfDigits();
	size_t m = other.GetNumberOfDigits();

	if ( n < m ) {
		return  true;
	} else if ( m == n ) {

		auto this_vector = this->GetVectorOfDigits();
		auto other_vector = other.GetVectorOfDigits();
		for (size_t i = n - 1; i >= 0; --i) {  // start from the end
			if (this_vector[i] < other_vector[i]) {
				return true;
			} else if (this_vector[i] > other_vector[i]) {
				return  false;
			}
		}
		return  false;
	} else {
		return false;
	}
}

bool BigInteger::operator<(const BigInteger &other) const {
	bool is_less = false;
	// this - negative , other - positive
	if ( !this->GetIsPositive() && other.GetIsPositive() ) {
		is_less = true;

		// this - positive , other - negative
	} else if ( this->GetIsPositive() && !other.GetIsPositive() ) {
		is_less = false;

		// this & other have similar sign
	} else {
		// this & other negative
		if ( !this->GetIsPositive() && !other.GetIsPositive() ) {
			is_less = !(this->CompareByAbs(other));
		}
		// this & other positive
		if ( this->GetIsPositive() && other.GetIsPositive() ){
			is_less = this->CompareByAbs(other);
		}
	}
	return  is_less && (*this != other);
}



bool BigInteger::operator>(const BigInteger &other) const {
	return (!(*this < other)) && (*this != other);
}


std::ostream& operator<<(std::ostream &stream, const BigInteger& big_integer) {

	std::vector<int> vector_of_digits = big_integer.GetVectorOfDigits();
	if ( !big_integer.is_positive ) {
		stream << '-';
	}
	for (int i = big_integer.GetNumberOfDigits() - 1; i >= 0; --i) {
		stream << vector_of_digits[i];
	}
	return stream;
}


std::istream& operator>>(std::istream &stream, BigInteger& big_integer) {

	std::string str;

	stream.setf(std::ios::skipws);

	stream >> str;

	int first_position_of_number = 0;
	if (str[0] == '-') {
		big_integer.is_positive = false;
		first_position_of_number = 1;
		if ( str.size() == 1 ) {
			std::string rest_of_str;
			stream >> rest_of_str;
			str.append(rest_of_str);
		}
	} else {
		big_integer.is_positive = true;
	}

	for (int i = str.size() - 1; i >= first_position_of_number; --i) {
		std::string digit = {str[i]};
		big_integer.vector_of_digits.push_back(std::stoi(digit,nullptr,BASE));
	}
	return stream;
}



BigInteger::operator int() {

	int int_value = 0;

	unsigned long long charge = 1;
	for (auto digit : this->GetVectorOfDigits()) {
		int_value += digit*charge;
		charge *= BASE;
	}

	return int_value;
}



BigInteger::operator bool() {
	for (auto digit : this->GetVectorOfDigits()) {
		if ( digit != 0 ) {
			return true;
		}
	}
	return  false;
}


void BigInteger::SetIsPositive(bool sign) {
	this->is_positive = sign;
}



std::string BigInteger::toString() {
	std::string string_number;
	for (int i = GetNumberOfDigits() - 1; i >= 0; --i) {
		std::string digit = std::to_string(vector_of_digits[i]);
		string_number.append(digit);
	}
	return string_number;
}

#endif //FIVT_4_BIGINTEGER_H