LAB 8

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <thread>
#include <functional>
#include <iomanip>
#include <atomic>
#include <algorithm>

/**
 * @brief Базовое исключение, содержащее строку
 */
class Exception: public std::exception
{
private:
    std::string text;                       ///< Текст исключения

public:
    /**
     * @brief Основной конструктор
     * @param string Текст исключения
     */
    explicit Exception(std::string string)
        : text(std::move(string))
    {}

    const char *what() const noexcept override
    {
        return text.c_str();
    }
};

/**
 * @brief Информация о потоках
 * Свойства public, так как их защите не ожидается
 */
struct ThreadInfo
{
    size_t threadMax;                                   ///< Максимальное количество потоков
    std::atomic<size_t> threadAmount{0};                ///< Текущее количество потоков

    /**
     * @brief Основной конструктор
     * @param maxThreads Максимальное количество потоков
     */
    explicit ThreadInfo(size_t maxThreads)
        : threadMax(maxThreads)
    {}
};

/**
 * @brief Обертка для типа, позволяющая создать пустой экземпляр
 * @tparam T Оборачиваемый тип
 */
template<class T>
struct TypeWrapper
{
    // Не ожидается защита полей

    T value;                    ///< Значение
    bool isEmpty = false;       ///< Пустое ли значение

    explicit TypeWrapper(T value)
        : value(value)
    {}

    TypeWrapper(T value, bool isEmpty)
        : value(value), isEmpty(isEmpty)
    {}

    // Не ожидается приведение типов => операторы перегружены внутри структуры\

    bool operator==(const TypeWrapper<T> &right) const noexcept
    {
        return TypeWrapper::value == right.value;
    }

    bool operator>=(const TypeWrapper<T> &right) const noexcept
    {
        return TypeWrapper::value >= right.value;
    }

    bool operator<=(const TypeWrapper<T> &right) const noexcept
    {
        return TypeWrapper::value <= right.value;
    }

    bool operator<(const TypeWrapper<T> &right) const noexcept
    {
        return TypeWrapper::value < right.value;
    }

    bool operator>(const TypeWrapper<T> &right) const noexcept
    {
        return TypeWrapper::value > right.value;
    }
};

/**
 * @brief Отображение вектора в std::cout
 * @tparam T Тип вектора
 * @param vector Вектор для отображения
 */
template<typename T>
void printVector(const std::vector<TypeWrapper<T>> &vector)
{
    const size_t ROW_SIZE = 20;                 ///< Максимальное количество элементов в векторе

    size_t index = 0;                           ///< Индекс текущего элемента в векторе
    for (const auto &it : vector) {
        std::cout << std::setw(5) << it.value << " ";

        if (index % ROW_SIZE == 0 && index != 0) {
            std::cout << std::endl;
        }
        index++;
    }

    std::cout << std::endl;
}

/**
 * @brief Определяет, является ли число степеньню 2
 * @param number Число
 * @return Пара (является ли степень 2, log_2(number))
 */
std::pair<bool, size_t> isTwoPower(uint64_t number)
{
    size_t result = 0;                  ///< Количество единиц в двоичной записи
    size_t index = 0;                   ///< Индекс последней единицы

    // Пока число существует
    while (number != 0) {
        // Определяем крайний бит
        result += number & 0x1u;

        index++;
        number >>= 1u;
    }

    return {result == 1, index - 1};
}

/**
 * @brief Применение алгоритма к блоку
 * @tparam T Тип вектора
 * @tparam Compare Функция сравнения
 * @param start Начальный итератор
 * @param end Конечный итератор
 * @param isOdd Четный ли блок
 * @param threadInfo Информация о доступных потоках
 */
template<typename T, typename Compare>
void bitonicSortStep(typename std::vector<T>::iterator start,
                     typename std::vector<T>::iterator end,
                     bool isOdd,
                     ThreadInfo &threadInfo)
{
    Compare comparator;                 ///< Функция сравнения
    size_t size = end - start;          ///< Размер блока
    auto sizeInfo = isTwoPower(size);   ///< Получение информации о размере
    if (!sizeInfo.first) {
        // Выход, если размер не степень 2
        throw Exception("log_2(size) is bad");
    }

    size_t step = size >> 1u;           ///< Расстояние от начального до конечного элемента сравнения
    // (Длина стрелки в алгоритме сравенения) size / 2

    // Обход первой половины блока
    for (auto it = start; it != start + (size >> 1u); it++) {
        auto secondIterator = it + step;            ///< Сравниваемый элемент (из второй половины)
        if (isOdd) {
            // Если четное, то максимум во второй половине в случае сортировки по возрастанию
            if (comparator(*it, *secondIterator)) {
                // Если максимум в первой половине - делаем swap
                std::swap(*it, *secondIterator);
            }
        } else {
            // Если нечетное, то минимум во второй половине в случае сортировки по возрастанию
            if (!comparator(*it, *secondIterator)) {
                // Если минимум в первой половине - делаем swap
                std::swap(*it, *secondIterator);
            }
        }
    }

    // Если блок делится на подблоки
    if (step > 1) {
        auto executable = [start, size, isOdd, &threadInfo]() {
            bitonicSortStep<T, Compare>(start, start + (size >> 1u), isOdd, std::ref(threadInfo));
        };
        ///< Анонимная функция void (*)(), вызывающая функцию сортировки подблока

        // ветвление бинарное => поток единственный
        std::thread *thread = nullptr;                      ///< Указатель на подпоток
        if (threadInfo.threadAmount < threadInfo.threadMax) {
            // Есть доступные подпотоки
            threadInfo.threadAmount++;
            thread = new std::thread(executable);
        } else {
            // Нет доступных потоков. Выполнение параллельное
            executable();
        }

        // Вторая ветвь продолжается в текущем потоке
        bitonicSortStep<T, Compare>(start + (size >> 1u), end, isOdd, std::ref(threadInfo));

        if (thread) {
            // Если существует подпоток - присоединить
            thread->join();
            threadInfo.threadAmount--;
            delete thread;
        }
    }
}

/**
 * @brief Функция битонической сортировки
 * @tparam T Тип вектора
 * @tparam Compare Функция сравнения
 * @param vector Сортируемый вектор
 * @param threadAmount Количество доступных потоков
 */
template<typename T, typename Compare = std::greater_equal<T>>
void bitonicSort(std::vector<T> &vector, size_t threadAmount)
{
    auto sizeInfo = isTwoPower(vector.size());              ///< Информация о размере
    if (!sizeInfo.first) {
        throw Exception("Bad vector size (expected power of 2)");
    }

    const size_t MIN_BLOCK_SIZE = 8;        ///< Минимальный размер блока, для обработки которого создается новый поток

    for (size_t i = 0; i < sizeInfo.second; i++) {
        const size_t step = 0b10u << i;                     ///< Размер блока 2**i

        size_t subThreadAmount = threadAmount;                             ///< Количество подпотоков
        if (step >= MIN_BLOCK_SIZE) {
            size_t exceptedThreadAmount = vector.size() / step;            ///< Количество основных потоков
            if (exceptedThreadAmount >= threadAmount) {
                subThreadAmount = 0;
            } else {
                subThreadAmount = threadAmount - exceptedThreadAmount;
            }
        }

        std::vector<std::thread *> threads;                ///< Вектор, содержащий указатели на основные потоки
        ThreadInfo threadInfo(subThreadAmount);                            ///< Информация о подпотоках

        for (size_t j = 0; j < vector.size(); j += step) {
            auto executable = [&vector, j, step, &threadInfo]() {
                bitonicSortStep<T, Compare>(
                    vector.begin() + j,
                    vector.begin() + j + step,
                    (j / step) % 2 == 0,
                    std::ref(threadInfo)
                );
            };
            ///< Анонимная функция void (*)(), вызывающая сортировку блока

            if (step >= MIN_BLOCK_SIZE && j / step <= threadAmount && j + step < vector.size()) {
                // Размер блока не менее MIN_BLOCK_SIZE, достаточно потоков и блок не последний
                // => Параллельный вызов
                threads.push_back(new std::thread(executable));
            } else {
                // В другом случае вызываем функцию последовательно
                executable();
            }
        }

        // Перед переходом к следуюшему шагу текущий должен быть полностью выполнен
        if (!threads.empty()) {
            for (std::thread *thread: threads) {
                thread->join();
                delete thread;
            }
        }
    }
}

/**
 * @brief Случайная генерация вектора указанной длины
 * @param size Размер вектора
 * @tparam T Тип результирующего вектора
 * @return Сгенерированный вектор
 */
template<typename T>
std::vector<T> generateVector(size_t size)
{
    std::vector<T> result(size);

    // Инициализация рандома
    std::random_device randomDevice;
    std::mt19937 mt(randomDevice());
    std::uniform_int_distribution<T> rand(-1000, 1000);

    for (size_t i = 0; i < size; i++) {
        result[i] = rand(mt);
    }
    return result;
}

/**
 * @brief Удобная функция для ввода
 * @tparam T Приводимый тип
 * @param string Вывод перед вводом
 * @return Значение из потока, приведенное к типу T
 */
template<typename T>
T input(const std::string &string)
{
    T value;
    std::cout << string;
    std::cin >> value;
    return value;
}

/**
 * @brief Проверка на отсортированный вектор
 * @tparam T Тип вектора
 * @tparam Compare Функция сравнения
 * @param vector Исследуемый вектор
 * @return Отсортирован ли вектор
 */
template<typename T, typename Compare = std::greater_equal<TypeWrapper<T>>>
bool isSorted(const std::vector<TypeWrapper<T>> &vector)
{
    Compare comparator;
    for (auto it = vector.cbegin() + 1; it != vector.cend(); it++) {
        if (!comparator(*it, *(it - 1))) {
            return false;
        }
    }

    return true;
}

int main()
{
    std::cout << "Works for 10 seconds with 1048576 elements" << std::endl;

    auto vectorSize = input<size_t>("Enter vector size: ");    ///< Размер вектора
    auto threadAmount = input<size_t>("Enter thread amount: ");     ///< Количество потоков

    using Type = TypeWrapper<int>;
    std::vector<int> originalVector = generateVector<int>(vectorSize);      ///< Вектор из случайных значений
    std::vector<Type> vector(originalVector.cbegin(), originalVector.cend());                ///< Вектор длины 2**K

    // Вывод вектора
    std::cout << "Source vector: " << std::endl;
    if (vectorSize <= 1024) {
        printVector(vector);
    } else {
        std::cout << "\tIs large..." << std::endl;
    }

    size_t additionalElementAmount = (0x1u << (isTwoPower(vectorSize).second + 1)) - vectorSize;
    ///< Количество элементов, которые необходимо добавить, для приведения вектора к длине 2**K

    // Добавление заглушек
    std::cout << "Additional empty elements amount: " << additionalElementAmount << std::endl;
    for (size_t i = 0; i < additionalElementAmount; i++) {
        vector.emplace_back(TypeWrapper<int>(0, true));
    }

    std::chrono::time_point<std::chrono::high_resolution_clock> startTime, endTime;     ///< Тайминг

    // Замер времени и выполнение сортировки
    startTime = std::chrono::high_resolution_clock::now();
    bitonicSort<Type>(vector, threadAmount);                    // Сортировка
    endTime = std::chrono::high_resolution_clock::now();

    // После сортировки необходимо удалить "заглушки"
    vector.erase(
        std::remove_if(
            vector.begin(),
            vector.end(),
            [](Type value) {
                return value.isEmpty;
            }
        ),
        vector.end()
    );

    // Вывод тайминга
    std::cout << std::endl
              << "Time elapsed: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count()
              << " ms"
              << std::endl;

    // Вывод вектора
    std::cout << "Result vector: " << std::endl;
    if (vectorSize <= 1024) {
        printVector(vector);
    } else {
        std::cout << "\tIs large..." << std::endl;
    }

    // Проверка сортировки
    std::cout << std::endl << "Is sorted: " << (isSorted(vector) ? "True" : "False") << std::endl;

    return 0;
}