lab8 (final (i guess))

#include <iostream>
#include <iomanip>
#include <vector>
#include <cstring>              // Для std::memset, std::memcpy
#include <cassert>              // Для assert
#include <map>                  // Для std::map
#include <functional>           // Для std::bit_and, std::bit_xor, и т.п.
#include <type_traits>          // Для проверки типов

/*
 * Использована структура
 * Использованы assert'ы для выброса исключений
   (т.к. мы еще не умеем пользоваться классами => наследоваться => создавать свои исключения)
 * Использованы шаблоны функций (и их спецификация)
 * Использованы методы структур
 * Использована перегрузка функций операторов
 * Использована работа с памятью в стиле Си
 * Использованы функторы (объект с перегруженным operator() ) из <functional>
*/

// unsigned number (24 Байта)
struct BigUInt192
{
    using baseType = uint16_t;          // Базовый тип (для хранения)
    using oversizedType = uint32_t;     // Тип для вычислений

    static_assert(sizeof(baseType) < sizeof(oversizedType), "Size of oversizedType must be greater");
    static_assert(std::is_arithmetic<baseType>::value, "baseType must be arithmetic");
    static_assert(std::is_unsigned<baseType>::value, "baseType must be unsigned");
    static_assert(std::is_arithmetic<oversizedType>::value, "oversizedType must be arithmetic");
    static_assert(std::is_unsigned<oversizedType>::value, "oversizedType must be unsigned");

    // Стандартный конструктор
    // Созданное число - 0
    BigUInt192()
    {
        parts = new baseType[arraySize];            // Выделяем память
        this->erase();                              // Инициализируем 0
    }

    // Конструктор копирования
    BigUInt192(const BigUInt192 &original)
        : BigUInt192()
    {
        // Копируем область памяти
        std::memcpy(parts, original.parts, sizeof(baseType) * arraySize);
    }

    // Конструктор, инициализирующий 0ю ячейку
    explicit BigUInt192(const baseType &original)
        : BigUInt192()
    {
        parts[0] = original;
    }

    // Шаблонная функция (шаблон задает систему счисления)
    // Парсит строку в себя
    template<int T>
    void fromString(const std::string &str)
    {
        // Управление сюда передаваться не должно
        assert(false);  // Выкидываем ошибку
    }

    // Очистка памяти, выделенной под данные
    void erase()
    {
        std::memset(parts, 0, sizeof(baseType) * arraySize);
    }

    // Шаблонная функция
    // Применяет функтор к каждому блоку данных
    template<template<class> class F, class T>
    BigUInt192 applyBlock(F<T> functor) const
    {
        BigUInt192 result;
        for (size_t i = 0; i < arraySize; i++) {
            result.parts[i] = functor(parts[i]);
        }
        return result;
    }

    // Шаблонная функция
    // Применяет функтор к каждому блоку данных попарно
    // Вообще говоря, не коммутативна
    template<template<class> class F, class T>
    BigUInt192 applyBlock(const BigUInt192 &right, F<T> functor) const
    {
        BigUInt192 result;
        for (size_t i = 0; i < BigUInt192::arraySize; i++) {
            result.parts[i] = functor(parts[i], right.parts[i]);
        }
        return result;
    }

    // Сдвиг
    // Вынесено в отдельную функцию из-за некоторых повторяющихся блоков кода
    // Например: генерация маски и процесс сдвига для циклического сдвига
    BigUInt192 shift(char way, size_t amount, bool circled) const
    {
        // Маска
        baseType mask = 0x0;
        for (size_t i = 0; i < amount; i++) {
            mask = static_cast<BigUInt192::baseType>(mask << 1 | 1);
        }

        BigUInt192 result;                  // Результат
        baseType last = 0;                  // Биты для переноса в другой блок
        if (way == 0) {                     // <<
            for (size_t i = 0; i < arraySize; i++) {
                result.parts[i] = (parts[i] << amount) | last;
                last = (parts[i] >> (8 * sizeof(baseType) - amount)) & mask;
            }
        } else {                            // >>
            for (size_t i = 0; i < arraySize; i++) {
                const size_t index = arraySize - i - 1;
                result.parts[index] = (parts[index] >> amount);
                result.parts[index] |= last << (8 * sizeof(baseType) - amount);
                last = parts[index] & mask;
            }
        }

        // Для циклического сдвига
        if (circled) {
            if (way == 0)                   // <<
                result.parts[0] |= last;
            else                            // >>
                result.parts[arraySize - 1] |= last << (8 * sizeof(baseType) - amount);
        }

        return result;
    }

    // Циклический <<
    BigUInt192 shiftCircleL(size_t amount)
    {
        return shift(0, amount, true);
    }

    // Циклический >>
    BigUInt192 shiftCircleR(size_t amount)
    {
        return shift(1, amount, true);
    }

    // friend функции, имеющие доступ к private членам структуры
    // Однако, мы не знаем, что такое модификаторы доступа
    // В контексте этого кода используются как описания функций, объявленных после структуры

    friend BigUInt192 &operator+=(BigUInt192 &, const BigUInt192 &);
    friend BigUInt192 operator+(const BigUInt192 &, const BigUInt192 &);
    friend BigUInt192 &operator-=(BigUInt192 &, const BigUInt192 &);
    friend BigUInt192 operator-(const BigUInt192 &, const BigUInt192 &);
    friend bool operator>(const BigUInt192 &, const BigUInt192 &);
    friend bool operator==(const BigUInt192 &, const BigUInt192 &);
    friend bool operator!=(const BigUInt192 &, const BigUInt192 &);
    friend bool operator<(const BigUInt192 &, const BigUInt192 &);
    friend bool operator<=(const BigUInt192 &, const BigUInt192 &);
    friend bool operator>=(const BigUInt192 &, const BigUInt192 &);
    friend BigUInt192 operator&(const BigUInt192 &, const BigUInt192 &);
    friend BigUInt192 operator|(const BigUInt192 &, const BigUInt192 &);
    friend BigUInt192 operator^(const BigUInt192 &, const BigUInt192 &);
    friend BigUInt192 operator~(const BigUInt192 &);
    friend BigUInt192 operator<<(const BigUInt192 &, size_t);
    friend BigUInt192 operator>>(const BigUInt192 &, size_t);
    friend std::istream &operator>>(std::istream &, BigUInt192 &);
    friend std::ostream &operator<<(std::ostream &, const BigUInt192 &);

    // Умножение через сложение
    // Замечание: такое умножение не коммутативно относительно времени выполнения
    BigUInt192 &multiplySlow(const BigUInt192 &right)
    {
        // Умножение на 0 ожидаемо дает 0
        if (right == BigUInt192(0)) {
            erase();
            return *this;
        }

        BigUInt192 original(*this);     // Копия себя
        BigUInt192 one(1);              // Единица (чтобы постоянно 24 Байта не выделять)
        for (BigUInt192 i; i < right - one; i += one) {
            *this += original;
        }
        return *this;
    }

    // Шаблонная функция (шаблон задает систему счисления)
    // Преобразует число в строку
    template<int T>
    std::string toString() const
    {
        // Управление сюда передаваться не должно
        assert(false);  // Выкидываем ошибку
    }

    // Деструктор
    ~BigUInt192()
    {
        delete[] parts;     // Очистка памяти
    }

    // Количество байт (размер типа)
    static const size_t bytes = 24;
    // Размер массива (для выделения памяти)
    static const size_t arraySize = bytes / sizeof(baseType) + (bytes % sizeof(baseType) > 0);

    // Хранит данные о числе
    baseType *parts;
};

// Преобразование из строки 10-чной системы
template<>
void BigUInt192::fromString<10>(const std::string &str)
{
    // Подготовка
    erase();

    // Множитель
    BigUInt192 multiplier(1);
    BigUInt192 multiplierCoeff(10);         // Коэффициент умножения

    for (auto it = str.crbegin(); it != str.crend(); it++) {
        // Цифра в 10й системе
        const BigUInt192 numeral = BigUInt192(static_cast<baseType>(*it - '0'));

        // Копирование
        // Необходимо для умножения 10**k * n
        // Т.е. n раз прибавим 10**k , где 0 <= n <= 9
        BigUInt192 multiplierCopy = multiplier;

        // Операции
        *this += multiplierCopy.multiplySlow(numeral);
        multiplier.multiplySlow(multiplierCoeff);       // Увеличиваем множитель
    }
}

// Преобразование из строки 16-чной системы
template<>
void BigUInt192::fromString<16>(const std::string &str)
{
    erase();
    for (auto it = str.crbegin(); it != str.crend(); it++) {
        if (*it == '0')
            continue;
        const size_t i = static_cast<size_t>(it - str.crbegin());       // Индекс символа через итераторы

        // Преобразуем цифру/букву из символа в число
        std::stringstream stream;
        baseType numeral;               // Для числа
        stream << std::nouppercase << *it;
        stream >> std::hex >> numeral;

        const size_t index = i / (sizeof(baseType) * 2);                // Индекс в массиве
        assert(index < arraySize);          // Отлавливаем переполнение
        const size_t shift = (i % (sizeof(baseType) * 2)) * 4;          // Величина сдвига

        parts[index] |= numeral << shift;
    }
}

// Преобразование в строку 2-чной системы
template<>
std::string BigUInt192::toString<2>() const
{
    std::stringstream stream;           // Поток, преобразуемый в строку
    bool numberStarted = false;         // Убирает ведущие нули

    for (size_t i = 0; i < arraySize; i++) {
        const size_t index = arraySize - i - 1;         // Индекс с конца
        const size_t bits = sizeof(baseType) * 8;       // Количество бит

        for (int j = 0; j < bits; j++) {
            const size_t shift = bits - j - 1;          // Величина сдвига

            // Цифра (в 2й системе)
            const auto numeral = static_cast<uint16_t>((parts[index] >> shift) & 0b1);

            if ((numeral == 0 && numberStarted) || numeral == 1)
                stream << numeral;
            if (numeral == 1 && !numberStarted)
                // Каждая следующая цифра (в т.ч. ноль) будет записана
                numberStarted = true;
        }
    }

    // Ничего не было записано => Число 0
    if (!numberStarted)
        return "0";

    return stream.str();
}

// Преобразование в строку 16-чной системы
// Алгоритм аналогичен шаблону для 2й системы
template<>
std::string BigUInt192::toString<16>() const
{
    std::stringstream stream;
    bool numberStarted = false;

    for (size_t i = 0; i < BigUInt192::arraySize; i++) {
        const size_t index = BigUInt192::arraySize - i - 1;
        const size_t steps = sizeof(BigUInt192::baseType) * 2;

        for (int j = 0; j < steps; j++) {
            const size_t shift = (steps - j - 1) * 4;
            const auto numeral = static_cast<uint16_t>((parts[index] >> shift) & 0b1111);

            if ((numeral == 0 && numberStarted) || numeral != 0)
                stream << std::hex << std::uppercase << numeral;
            if (numeral != 0 && !numberStarted)
                numberStarted = true;
        }
    }

    if (!numberStarted)
        return "0";

    return stream.str();
}

// Алгоритм похож на сложение в столбик
BigUInt192 &operator+=(BigUInt192 &left, const BigUInt192 &right)
{
    // Перенесенный из предыдущего блока бит
    BigUInt192::oversizedType last = 0;

    for (size_t i = 0; i < BigUInt192::arraySize; i++) {
        // Парная сумма + предыдущий бит
        BigUInt192::oversizedType partSum = left.parts[i] + right.parts[i] + last;

        if (partSum >> (sizeof(BigUInt192::baseType) * 8) != 0) {
            last = 1;           // Переносим бит из последнего разряда (17й)
        } else {
            last = 0;
        }

        // Запоминаем сумму
        left.parts[i] = static_cast<BigUInt192::baseType>(partSum);
    }

    assert(last == 0);              // Отлавливаем переполнение

    return left;
}

BigUInt192 operator+(const BigUInt192 &left, const BigUInt192 &right)
{
    BigUInt192 result(left);        // Копируем константный left
    result += right;                // Применяем +=
    return result;
}

// Алгоритм похож на вычитание в столбик
BigUInt192 &operator-=(BigUInt192 &left, const BigUInt192 &right)
{
    // Перенесенный из предыдущего блока бит (необходимо вычесть)
    BigUInt192::oversizedType last = 0;

    for (size_t i = 0; i < BigUInt192::arraySize; i++) {
        // То, что будем вычитать
        const BigUInt192::oversizedType toSub = right.parts[i] + last;
        BigUInt192::oversizedType partSub;  // Результат

        if (left.parts[i] >= toSub) {
            partSub = left.parts[i] - toSub;
            last = 0;
        } else {
            // Если правая часть больше левой, "занимаем" бит из следующего блока
            partSub = (1 << 8 * sizeof(BigUInt192::baseType)) + left.parts[i];
            partSub -= toSub;
            last = 1;
        }

        // Сохраняем результат
        left.parts[i] = static_cast<BigUInt192::baseType>(partSub);
    }

    return left;
}

BigUInt192 operator-(const BigUInt192 &left, const BigUInt192 &right)
{
    BigUInt192 result(left);        // Копируем константный left
    result -= right;                // Применяем +=
    return result;
}

bool operator>(const BigUInt192 &left, const BigUInt192 &right)
{
    // Сравниваем каждый блок слева направо
    for (size_t i = 0; i < BigUInt192::arraySize; i++) {
        const size_t index = BigUInt192::arraySize - i - 1;     // Индекс с конца

        if (left.parts[index] == right.parts[index])
            continue;
        return left.parts[index] > right.parts[index];
    }

    return false;       // Если left == right
}

bool operator==(const BigUInt192 &left, const BigUInt192 &right)
{
    // Сравниваем каждый блок слева направо
    for (size_t i = 0; i < BigUInt192::arraySize; i++) {
        if (left.parts[i] != right.parts[i])
            return false;
    }
    return true;
}

/* Следующие 4 операции будут выведены из уже существующих */

bool operator!=(const BigUInt192 &left, const BigUInt192 &right)
{
    return !(left == right);
}

bool operator<(const BigUInt192 &left, const BigUInt192 &right)
{
    return !(left > right) && left != right;
}

bool operator<=(const BigUInt192 &left, const BigUInt192 &right)
{
    return left < right || left == right;
}

bool operator>=(const BigUInt192 &left, const BigUInt192 &right)
{
    return left > right || left == right;
}

/* Следующие 4 операции будут выведены через метод applyBlock и функтор */

BigUInt192 operator&(const BigUInt192 &left, const BigUInt192 &right)
{
    return left.applyBlock(right, std::bit_and<>());
}

BigUInt192 operator|(const BigUInt192 &left, const BigUInt192 &right)
{
    return left.applyBlock(right, std::bit_or<>());
}

BigUInt192 operator^(const BigUInt192 &left, const BigUInt192 &right)
{
    return left.applyBlock(right, std::bit_xor<>());
}

BigUInt192 operator~(const BigUInt192 &left)
{
    return left.applyBlock(std::bit_not<>());
}

/* Следующие 2 операции будут выведены через метод shift */

BigUInt192 operator<<(const BigUInt192 &left, size_t shift)
{
    return left.shift(0, shift, false);
}

BigUInt192 operator>>(const BigUInt192 &left, size_t shift)
{
    return left.shift(1, shift, false);
}

// Чтение из потока
std::istream &operator>>(std::istream &istream, BigUInt192 &value)
{
    // Читаем в строку
    std::string input;
    istream >> input;

    // Получаем систему счисления
    std::ios_base::fmtflags base = istream.flags() & std::istream::basefield;

    switch (base) {
        case std::ios_base::hex: {
            value.fromString<16>(input);
            break;
        }
        default: {
            value.fromString<10>(input);
            break;
        }
    }

    return istream;
}

std::ostream &operator<<(std::ostream &ostream, const BigUInt192 &value)
{
    // Получаем систему счисления
    std::ios_base::fmtflags base = ostream.flags() & std::istream::basefield;

    switch (base) {
        case std::ios_base::hex: {
            ostream << value.toString<16>();
            break;
        }
        default: {
            ostream << value.toString<2>();
            break;
        }
    }

    return ostream;
}

//** Tester (не будет вставлен в отчет) //

#define TESTER
#define BOOL_TO_STRING(x) ((x) ? "Correct" : "Wrong")

// Функция для тестирования корректной работы перегруженных операций
void tester()
{
    using keyType = std::pair<std::string, std::string>;
    using valueType = std::vector<std::string>;

    std::map<keyType, valueType> tests = {
        {
            {
                "FF",
                "AA"
            },
            {
                "1A9",                                              // +
                "55",                                               // -
                "1FE0",                                             // << 5
                "F80000000000000000000000000000000000000000000007", // circle >> 5
                "AA",                                               // &
                "FF",                                               // |
                "55",                                               // ^
                "1",                                                // >
                "1",                                                // !=
            }
        },
        {
            {
                "AA5F601",
                "8D9A34"
            },
            {
                "B339035",                                          // +
                "A185BCD",                                          // -
                "154BEC020",                                        // << 5
                "80000000000000000000000000000000000000000552FB0",  // circle >> 5
                "859200",                                           // &
                "AADFE35",                                          // |
                "A286C35",                                          // ^
                "1",                                                // >
                "1",                                                // !=
            }
        },
        {
            {
                "135",
                "135"
            },
            {
                "26A",                                              // +
                "0",                                                // -
                "26A0",                                             // << 5
                "A80000000000000000000000000000000000000000000009", // circle >> 5
                "135",                                              // &
                "135",                                              // |
                "0",                                                // ^
                "0",                                                // >
                "0",                                                // !=
            }
        },
    };

    // Проверка
    for (const auto &it : tests) {
        BigUInt192 left;
        left.fromString<16>(it.first.first);
        BigUInt192 right;
        right.fromString<16>(it.first.second);
        std::cout << "A = " << std::hex << left << std::endl;
        std::cout << "B = " << std::hex << right << std::endl;

        const valueType &results = it.second;
        BigUInt192 tempResult;
        tempResult.fromString<16>(results[0]);
        std::cout << "A + B   " << BOOL_TO_STRING((left + right) == tempResult) << std::endl;
        tempResult.fromString<16>(results[1]);
        std::cout << "A - B   " << BOOL_TO_STRING((left - right) == tempResult) << std::endl;
        tempResult.fromString<16>(results[2]);
        std::cout << "A << 5  " << BOOL_TO_STRING((left << 5) == tempResult) << std::endl;
        tempResult.fromString<16>(results[3]);
        std::cout << "A c>> 5 " << BOOL_TO_STRING(left.shiftCircleR(5) == tempResult) << std::endl;
        tempResult.fromString<16>(results[4]);
        std::cout << "A & B   " << BOOL_TO_STRING((left & right) == tempResult) << std::endl;
        tempResult.fromString<16>(results[5]);
        std::cout << "A | B   " << BOOL_TO_STRING((left | right) == tempResult) << std::endl;
        tempResult.fromString<16>(results[6]);
        std::cout << "A ^ B   " << BOOL_TO_STRING((left ^ right) == tempResult) << std::endl;
        std::cout << "A > B   " << BOOL_TO_STRING((left > right) == (results[7] == "1")) << std::endl;
        std::cout << "A != B  " << BOOL_TO_STRING((left != right) == (results[8] == "1")) << std::endl;
    }
}

// Tester **//

int main()
{

#ifdef TESTER
    tester();
#endif

    // Ввод типов
    size_t inputType;       // Тип ввода
    size_t outputType;      // Тип вывода
    std::cout << "Choose input type ( HEX(0) or DEC(1) ): ";
    std::cin >> inputType;
    std::cout << "Choose output type ( HEX(0) or BIN(1) ): ";
    std::cin >> outputType;

    // Ввод больших чисел и размера сдвига
    BigUInt192 left;
    BigUInt192 right;
    size_t shiftSize;
    std::cout << "A = ";
    std::cin >> ((inputType == 1) ? std::dec : std::hex) >> left;
    std::cout << "B = ";
    std::cin >> ((inputType == 1) ? std::dec : std::hex) >> right;
    std::cout << "Enter shift size (DEC): ";
    std::cin >> shiftSize;

    // Вывод результатов операций над данными числами
    auto flag = ((outputType == 0) ? std::hex : std::dec);
    std::cout << "A       = " << left << std::endl;
    std::cout << "B       = " << right << std::endl;
    std::cout << "A + B   = " << flag << (left + right) << std::endl;
    std::cout << "A - B   = " << flag << (left - right) << std::endl;
    std::cout << "A << s  = " << flag << (left << shiftSize) << std::endl;
    std::cout << "A >> s  = " << flag << (left >> shiftSize) << std::endl;
    std::cout << "A c<< s = " << flag << left.shiftCircleL(shiftSize) << std::endl;
    std::cout << "A c>> s = " << flag << left.shiftCircleR(shiftSize) << std::endl;
    std::cout << "A & B   = " << flag << (left & right) << std::endl;
    std::cout << "A | B   = " << flag << (left | right) << std::endl;
    std::cout << "A ^ B   = " << flag << (left ^ right) << std::endl;
    std::cout << "A > B   = " << flag << (left > right) << std::endl;
    std::cout << "A < B   = " << flag << (left < right) << std::endl;
    std::cout << "A == B  = " << flag << (left == right) << std::endl;

    return 0;
}