BigInteger.cpp

// TODO
// Subtraction!

// Explanation
//
// unsigned long long int ranging from 18446744073709551615 (9 digit maximum)
// ...
// So, we choose to deal with base 1*10^9

// Uncomment this to turn off testing
#define TEST

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <cassert>
#include <stdexcept>
#include <algorithm>
#include <utility>

const int DIGIT_MAX = 9;
const unsigned long long int BASE = 1000000000;

std::pair<
    std::vector<unsigned long long int>,
    std::vector<unsigned long long int>
> vector_split(std::vector<unsigned long long int> vec, int middle)
{
    return std::pair(std::vector(vec.begin(), vec.begin() + middle), std::vector(vec.begin() + middle, vec.end()));
}

unsigned long long atoull(const char* number, char skipped_char)
{
    unsigned long long int result = 0;
    for (int i = 0; number[i] != '\0'; ++i) 
    {
        if (number[i] == skipped_char)
        {
            continue;
        }
        result = result * 10 + (number[i] - '0'); 
    }
    return result;
}

enum class Sign
{
    Positive,
    Negative
};

// Declaration
class BigInteger
{
private:
    std::vector<unsigned long long int> numbers;
    Sign sign;
public:
    BigInteger() = default;
    BigInteger(const char* c_string);
    BigInteger(std::vector<unsigned long long int> number_vec);

    // Naive multiplication
    BigInteger operator*(BigInteger other);
    BigInteger operator+(BigInteger other);
    BigInteger operator-(BigInteger other);
    bool operator<(BigInteger other);
    bool operator>(BigInteger other);
    bool operator==(BigInteger other);
    bool operator!=(BigInteger other);

    const char* c_str();
    const Sign getSign();
    const std::vector<unsigned long long int> numbersData();

    // BigInteger fastMul(BigInteger other);
#ifdef TEST
    void print_vector();
#endif
};

////////////////////////////////////////////////////////////////////////////////////////

class BigUnsignedInteger
{
private:
    std::vector<unsigned long long int> numbers;
public:
    BigUnsignedInteger() = default;
    BigUnsignedInteger(const char* c_string);
    BigUnsignedInteger(std::vector<unsigned long long int> number_vec);

    // Naive multiplication
    BigUnsignedInteger operator*(BigUnsignedInteger other);
    BigUnsignedInteger operator+(BigUnsignedInteger other);
    BigUnsignedInteger operator-(BigUnsignedInteger other);
    bool operator<(BigUnsignedInteger other);
    bool operator>(BigUnsignedInteger other);
    bool operator==(BigUnsignedInteger other);
    bool operator!=(BigUnsignedInteger other);

    const char* c_str();
    const std::vector<unsigned long long int> numbersData();

    // BigUnsignedInteger fastMul(BigInteger other);
#ifdef TEST
    void print_vector();
#endif
};
// End declaration ///////////////////////////////////////////////////////////////////

// Definition ////////////////////////////////////////////////////////////////////////
BigInteger::BigInteger(const char* c_string)
{
    // Check sign
    bool has_sign = false;
    if (c_string[0] == '+' || c_string[0] == '-')
    {
        has_sign = true;
        if (c_string[0] == '-')
        {
            sign = Sign::Negative;
        }
        else
        {
            sign = Sign::Positive;
        }
    }
    else
    {
        sign = Sign::Positive;
    }

    if (has_sign)
    {
        BigUnsignedInteger unsigned_calculation(c_string + 1);
        numbers = unsigned_calculation.numbersData();
    }
    else
    {
        BigUnsignedInteger unsigned_calculation(c_string);
        numbers = unsigned_calculation.numbersData();
    }
}

BigInteger::BigInteger(std::vector<unsigned long long int> number_vec) :
    numbers(number_vec)
{
}

BigInteger BigInteger::operator*(BigInteger other)
{
    
    return BigInteger("");
}

BigUnsignedInteger karatsuba(BigUnsignedInteger left, BigUnsignedInteger right)
{
    if (left.numbersData().size() == 1 || right.numbersData().size() == 1)
    {
        return BigUnsignedInteger(left.numbersData()) * BigUnsignedInteger(right.numbersData());
    }

    int middle_idx = std::min(left.numbersData().size(), right.numbersData().size());

    std::pair<std::vector<unsigned long long int>, std::vector<unsigned long long int>> left_split = vector_split(left.numbersData(), middle_idx);std::pair<std::vector<unsigned long long int>, std::vector<unsigned long long int>> right_split = vector_split(right.numbersData(), middle_idx);

    BigUnsignedInteger z0 = karatsuba(BigUnsignedInteger(left_split.first), BigUnsignedInteger(right_split.first));

    BigUnsignedInteger z1 = karatsuba(BigUnsignedInteger(left_split.first) + BigUnsignedInteger(left_split.second), BigUnsignedInteger(right_split.first) + BigUnsignedInteger(right_split.second));

    BigUnsignedInteger z2 = karatsuba(BigUnsignedInteger(right_split.second), BigUnsignedInteger(right_split.second));

    // TODO
}

const Sign BigInteger::getSign()
{
    return sign;
}

BigInteger BigInteger::operator-(BigInteger other)
{
    BigInteger* bigger_integer_ptr = &other;
    BigInteger* smaller_integer_ptr = this;

    bool swapped = false;

    if (*bigger_integer_ptr < *smaller_integer_ptr)
    {
        swapped = true;
        std::swap(bigger_integer_ptr, smaller_integer_ptr);
    }

    BigInteger output;

    // (1+) - (2+)
    if (sign == Sign::Positive && other.sign == Sign::Positive)
    {
        output.sign = (!swapped)? Sign::Positive : Sign::Negative;
        output.numbers = (BigUnsignedInteger(bigger_integer_ptr->numbers) - BigUnsignedInteger(smaller_integer_ptr->numbers)).numbersData();
    }
    // (1-) - (2-) == -((1+) - (2+))
    else if (sign == Sign::Negative && other.sign == Sign::Negative)
    {
        output.sign = (swapped)? Sign::Positive : Sign::Negative;
        output.numbers = (BigUnsignedInteger(bigger_integer_ptr->numbers) - BigUnsignedInteger(smaller_integer_ptr->numbers)).numbersData();
    }
    // (1-) - (2+) == -((1+) + (2+))
    else if (sign == Sign::Negative && other.sign == Sign::Positive)
    {
        output.sign = (swapped)? Sign::Positive : Sign::Negative;
        output.numbers = (BigUnsignedInteger(bigger_integer_ptr->numbers) + BigUnsignedInteger(smaller_integer_ptr->numbers)).numbersData();
    }
    // (1+) - (2-) == (1+) + (2+)
    else
    {
        output.sign = (!swapped)? Sign::Positive : Sign::Negative;
        output.numbers = (BigUnsignedInteger(bigger_integer_ptr->numbers) + BigUnsignedInteger(smaller_integer_ptr->numbers)).numbersData();
    }

    return output;
}

BigInteger BigInteger::operator+(BigInteger other)
{
    // (+) + (+) | (-) + (-)
    if (sign == other.sign)
    {
        // Actually can use friend class feature
        BigInteger output(
            (BigUnsignedInteger(numbers) + BigUnsignedInteger(other.numbers)).numbersData()
        );
        output.sign = sign;
        return output;
    }
    else
    {
        BigInteger* bigger_integer = &other;
        BigInteger* smaller_integer = this;

        if (*bigger_integer < *smaller_integer)
        {
            std::swap(bigger_integer, smaller_integer);
        }

        BigInteger output(
            (BigUnsignedInteger(bigger_integer->numbers) - BigUnsignedInteger(smaller_integer->numbers)).numbersData()
        );

        // (1+) +  (2-) == (1+) - (2+)
        if (bigger_integer->sign == Sign::Positive && smaller_integer->sign == Sign::Negative)
        {
            output.sign = Sign::Positive;
        }
        // (1-) + (2+) == -((1+) - (2+))
        else
        {
            output.sign = Sign::Negative;
        }
        return output;
    }
}

bool BigInteger::operator==(BigInteger other)
{
    return numbers == other.numbers && sign == other.sign;
}

bool BigInteger::operator!=(BigInteger other)
{
    return numbers != other.numbers || sign != other.sign;
}

bool BigInteger::operator>(BigInteger other)
{
    if (sign == Sign::Positive && other.sign == Sign::Positive)
    {
        return BigUnsignedInteger(numbers) > BigUnsignedInteger(other.numbers);
    }
    else if (sign == Sign::Negative && other.sign == Sign::Negative)
    {
        return BigUnsignedInteger(numbers) < BigUnsignedInteger(other.numbers);
    }
    else if (sign == Sign::Positive && other.sign == Sign::Negative)
    {
        return true;
    }
    else if (sign == Sign::Negative && other.sign == Sign::Positive)
    {
        return false;
    }
    return false;
}

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

#ifdef TEST
void BigInteger::print_vector()
{
    for (auto number = numbers.rbegin(); number != numbers.rend(); ++number)
    {
        printf("%llu ", *number);
    }
    printf("\n");
}
#endif

const char* BigInteger::c_str()
{
    // std::string output;
    // for (auto number = numbers.rbegin(); number != numbers.rend(); ++number)
    // {
        
    // }
    return "";
}

const std::vector<unsigned long long int> BigInteger::numbersData()
{
    return numbers;
}

///////////////////////////////////////////////////////////////////////////////////////////////////

BigUnsignedInteger::BigUnsignedInteger(const char* c_string)
{
    int index_current = strlen(c_string) - 1;

    // Parse string to vector of number
    char number_buffer_string[DIGIT_MAX + 1];
    number_buffer_string[DIGIT_MAX] = '\0';
    memset(number_buffer_string, ' ', DIGIT_MAX - 1);
    int current_number_digit_index = DIGIT_MAX - 1;
    for (; index_current >= 0; --index_current)
    {
        number_buffer_string[current_number_digit_index] = c_string[index_current];
        current_number_digit_index--;
        
        if (current_number_digit_index == 0)
        {
            numbers.push_back(atoull(number_buffer_string, ' '));
            // printf("->%s\n", number_buffer_string);
            current_number_digit_index = DIGIT_MAX - 1;
            memset(number_buffer_string, ' ', DIGIT_MAX - 1);
        }
    }

    numbers.push_back(atoull(number_buffer_string, ' '));
}

BigUnsignedInteger::BigUnsignedInteger(std::vector<unsigned long long int> number_vec) :
    numbers(number_vec)
{
}

BigUnsignedInteger BigUnsignedInteger::operator+(BigUnsignedInteger other)
{
    BigUnsignedInteger *smaller_digit_ptr = &other;
    BigUnsignedInteger *bigger_digit_ptr = this;
    
    if (bigger_digit_ptr->numbers.size() < smaller_digit_ptr->numbers.size())
    {
        std::swap(bigger_digit_ptr, smaller_digit_ptr);
    }

    std::vector<unsigned long long int> number_output;

    int digit_length_diff = bigger_digit_ptr->numbers.size() - smaller_digit_ptr->numbers.size();
    unsigned long long int carry = 0;
    for (int i = 0; i < smaller_digit_ptr->numbers.size(); ++i)
    {
        unsigned long long int sum = smaller_digit_ptr->numbers[i] + bigger_digit_ptr->numbers[i + digit_length_diff] + carry;
        number_output.push_back(sum % BASE);
        carry = sum / BASE;
    }

    for (int i = digit_length_diff - 1; i >= 0; --i)
    {
        unsigned long long int sum = bigger_digit_ptr->numbers[i] + carry;
        number_output.push_back(sum % BASE);
        carry = sum / BASE;
    }

    if (carry != 0)
    {
        number_output.push_back(carry);
    }

    return BigUnsignedInteger(number_output);
}

BigUnsignedInteger BigUnsignedInteger::operator-(BigUnsignedInteger other)
{
    if (*this < other)
    {
        std::runtime_error("Left operand is smaller than right operand!");
    }

    std::vector<unsigned long long int> number_output;
    int carry = 0;
    int digit_length_diff = numbers.size() - other.numbers.size();
    unsigned long long int sub;
    
    for (int i = other.numbers.size() - 1; i >= 0; --i)
    {
        sub = numbers[i + digit_length_diff] - other.numbers[i] - carry;
        if (sub < 0)
        {
            sub += BASE;
            carry = 1;
        }
        else
        {
            carry = 0;
        }
        number_output.push_back(sub);
    }

    for (int i = digit_length_diff - 1; i >= 0; --i)
    {
        if (numbers[i] == 0 && carry != 0)
        {
            number_output.push_back(BASE - 1);
            continue;
        }
        
        sub = numbers[i] - carry;

        if (i > 0 || sub > 0)
        {
            number_output.push_back(sub);
        }
    }

    std::reverse(number_output.begin(), number_output.end());

    return BigUnsignedInteger(number_output);
}

void BigUnsignedInteger::print_vector()
{
    for (auto number = numbers.rbegin(); number != numbers.rend(); ++number)
    {
        printf("%llu ", *number);
    }
    printf("\n");
}

const std::vector<unsigned long long int> BigUnsignedInteger::numbersData()
{
    return numbers;
}

bool BigUnsignedInteger::operator==(BigUnsignedInteger other)
{
    return numbers == other.numbers;
}

bool BigUnsignedInteger::operator!=(BigUnsignedInteger other)
{
    return numbers != other.numbers;
}

bool BigUnsignedInteger::operator<(BigUnsignedInteger other)
{
    if (numbers == other.numbers)
    {
        return false;
    }
    else if (numbers.size() < other.numbers.size())
    {
        return true;
    }
    else
    {
        for (int i = 0; i < numbers.size(); ++i)
        {
            if (numbers[i] < other.numbers[i])
            {
                return true;
            }
            else if (numbers[i] > other.numbers[i])
            {
                return false;
            }
        }
        return false;
    }
}

bool BigUnsignedInteger::operator>(BigUnsignedInteger other)
{
    return !(*this < other);
}

// End definition ////////////////////////////////////////////////////////////////////////

void test()
{
    printf("======================\n");
    printf("TEST\n");
    printf("======================\n");

    printf("======================\n");
    printf("Manual Test\n");
    printf("======================\n");

    {
        auto number = BigInteger("123");
        number.print_vector();
        printf("[?] — Print BigInteger 123\n");
    }

    {
        auto number = BigInteger("12345678901234567890");
        number.print_vector();
        printf("[?] — Print BigInteger 12345678901234567890\n");
    }

    {
        auto number = BigInteger("99") + BigInteger("33");
        number.print_vector();
        printf("[?] — Print BigInteger 99 + 33 = 132\n");
    }

    {
        auto number = BigInteger("1234567890") + BigInteger("1234567890");
        number.print_vector();
        printf("[?] — Print BigInteger 1234567890 + 1234567890 = 2469135780\n");
    }

    {
        auto number = BigInteger("987654321") - BigInteger("123456789");
        number.print_vector();
        printf("[?] — Print BigInteger 987654321 - 123456789 = 864197532\n");
    }

    printf("======================\n");
    printf("Automatic Test\n");
    printf("======================\n");

    {
        bool result = BigInteger("1") == BigInteger("1");
        assert(result && "[ ] — 1 compared to 1 must be true");
        printf("[x] — 1 compared to 1 must be true — PASSED\n");
    }

    {
        bool result = BigInteger("-1") == BigInteger("-1");
        assert(result && "[ ] — -1 compared to -1 must be true");
        printf("[x] — -1 compared to -1 must be true — PASSED\n");
    }

    {
        bool result = BigInteger("1") != BigInteger("-1");
        assert(result && "[ ] — 1 compared to -1 must not be true");
        printf("[x] — 1 compared to -1 must be true — PASSED\n");
    }

    {
        bool result = BigInteger("12345678901234567890") == BigInteger("12345678901234567890");
        assert(result && "[ ] — 12345678901234567890 compared to 12345678901234567890 must be true");
        printf("[x] — 12345678901234567890 compared to 12345678901234567890 must be true — PASSED\n");
    }

    {
        bool result = BigInteger("123456789") - BigInteger("987654321") == BigInteger("-864197532");
        
        auto a = BigInteger("123456789") - BigInteger("987654321");
        a.print_vector();

        auto b = BigInteger("-864197532");
        b.print_vector();

        printf("Sign equality %d %d\n", a.getSign(), b.getSign());

        assert(result && "[ ] — 123456789 - 987654321 equal -864197532");
        printf("[x] — 123456789 - 987654321 equal -864197532 must be true — PASSED\n");
    }

    {
        bool result = BigInteger("-12345678901234567890") == BigInteger("-12345678901234567890");
        assert(result && "[ ] — -12345678901234567890 compared to -12345678901234567890 must be true");
        printf("[x] — -12345678901234567890 compared to -12345678901234567890 must be true — PASSED\n");
    }

    {
        bool result = BigUnsignedInteger("100") + BigUnsignedInteger("100") == BigUnsignedInteger("200");
        assert(result && "[ ] — 100U add 100U must be 200U");
        printf("[x] — 100U add 100U must be 200U — PASSED\n");
    }

    {
        bool result = BigInteger("100") + BigInteger("100") == BigInteger("200");
        assert(result && "[ ] — 100 add 100 must be 200");
        printf("[x] — -100 add 100 must be 200 — PASSED\n");
    }

    {
        bool result = (BigInteger("1") * BigInteger("1")) == BigInteger("1");
        assert(result && "[ ] — 1 * 1 must be 1");
        printf("[x] — 1 * 1 must be 1 — PASSED\n");
    }

    {
        bool result = (BigInteger("1") * BigInteger("0")) == BigInteger("0");
        assert(result && "[ ] — 1 * 0 must be 0");
        printf("[x] — 1 * 0 must be 0 — PASSED\n");
    }

    // Add more test case
}

int main() {
#ifdef TEST
    test();
#endif

    return 0;
}