#include <algorithm>
#include <array>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
// ----------------------------------------------------------------------------
using series = uint64_t;
using decimal = uint64_t;
// ----------------------------------------------------------------------------
// Сохраняем все элементы строки последовательно в памяти
struct Employee {
    series id;
    decimal salary;
    std::array<char, 16> firstname;
};
// Вектор - это наращиваемый массив данных, каждый элемент которого — полная строка
struct ArrayOfStruct {
    std::vector<Employee> table;
};
// ----------------------------------------------------------------------------
// Сохраняем один и тот же столбец последовательно в памяти
struct StructOfArrays {
    std::vector<series> id;
    std::vector<decimal> salary;
    std::vector<std::array<char, 16>> firstname;
};
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const ArrayOfStruct& store)
// Вычисляем зарплату из массива структур
{
    decimal salary = 0;
    // Итеративно обходим строки и выбираем зарплату
    for (const auto& r : store.table)
        salary += r.salary;
    return salary;
}
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const StructOfArrays& store)
// Вычисляем зарплату из структуры массивов
{
    decimal salary = 0;
    // Итеративно обходим столбец
    for (auto s : store.salary)
        salary += s;
    return salary;
}
// ----------------------------------------------------------------------------
static void updateEntry(ArrayOfStruct& store, std::vector<series> ids, std::array<char, 16>& newName)
// Обновляем элементы хранилища AoS
{
    for (auto id : ids) {
        auto& record = store.table[id];
        record.firstname = newName;
        record.salary *= 2;
    }
}
// ----------------------------------------------------------------------------
static void updateEntry(StructOfArrays& store, std::vector<series> ids, std::array<char, 16>& newName)
// Обновляем элементы хранилища SoA
{
    for (auto id : ids) {
        store.firstname[id] = newName;
        store.salary[id] = 2 * store.salary[id];
    }
}
// ----------------------------------------------------------------------------
int main() {
    // Создаём 100 миллионов пользователей
    auto users = 100 * 1000 * 1000ull;
    std::array<char, 16> name = {"Moritz - Felipe"};
    // Для обеих версий
    ArrayOfStruct aos;
    StructOfArrays soa;
    // Заполняем хранилища
    for (auto i = 0ull; i < users; i++) {
        aos.table.emplace_back(static_cast<series>(i), static_cast<decimal>(i * 100) , name);
        soa.id.push_back(static_cast<series>(i));
        soa.salary.push_back(static_cast<decimal>(i) * 100);
        soa.firstname.emplace_back(name);
    }

    // Вычисляем зарплату
    auto measureSalary = []<typename T>(const T& store) {
        // Запускаем таймер
        std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
        auto salary = getTotalSalary(store);
        // Останавливаем таймер
        std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
        // Определяем тип хранилища
        auto storeName = "SoA";
        if constexpr (std::is_same_v<ArrayOfStruct, T>)
            storeName = "AoS";
        // Выводим результаты
        std::cout << "Workload: Analyze; Store: " << storeName << "; Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << " [μs]" << std::endl;
        return salary;
    };

    // Проверяем корректность
    if (measureSalary(aos) != measureSalary(soa))
        return -1;

    // -------------

    std::random_device rnd_device;
    std::mt19937 mt{rnd_device()}; // Генерирует случайные целые числа
    std::uniform_int_distribution<uint64_t> dist{0, users - 1};

    auto gen = [&]() {
        return dist(mt);
    };

    std::vector<series> ids(0.1 * users);
    std::generate(ids.begin(), ids.end(), gen);

    // Обновляем столбец
    auto measureUpdate = []<typename T>(T& store, std::vector<series> ids) {
        // Обновляем имя и зарплату
        std::array<char, 16> name = {"Dr. Moritz - F."};

        // Запускаем таймер
        std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
        updateEntry(store, ids, name);
        // Останавливаем таймер
        std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
        // Определяем тип хранилища
        auto storeName = "SoA";
        if constexpr (std::is_same_v<ArrayOfStruct, T>)
            storeName = "AoS";
        // Выводим результаты
        std::cout << "Workload: Update; Store: " << storeName << "; Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << " [μs]" << std::endl;
    };

    measureUpdate(aos, ids);
    measureUpdate(soa, ids);

    return 0;
}
// ----------------------------------------------------------------------------

#include <algorithm>
#include <array>
#include <chrono>
#include <iostream>
#include <random>
#include <thread>
#include <vector>
// ----------------------------------------------------------------------------
using series = uint64_t;
using decimal = uint64_t;
// ----------------------------------------------------------------------------
// Сохраняем все элементы строки последовательно в памяти
struct Employee {
    series id;
    decimal salary;
    std::array<char, 16> firstname;
};
// Вектор — это наращиваемый массив данных, каждый элемент которого — полная строка
struct ArrayOfStruct {
    // The rows
    std::vector<Employee> table;

    // Вычисляем размер
    size_t getSize() const {
        return table.size() * sizeof(decltype(table)::value_type) + sizeof(ArrayOfStruct);
    }
};
// ----------------------------------------------------------------------------
// Сохраняем один столбец последовательно в памяти
// Для упрощения мы игнорируем, что векторы помещают данные в разные области памяти.
// Скорее всего, база данных будет использовать специальную структуру данных, упаковывающую все столбцы.
struct StructOfArrays {
    // Столбцы
    std::vector<series> id;
    std::vector<decimal> salary;
    std::vector<std::array<char, 16>> firstname;

    // Вычисляем размер
    size_t getSize() const {
        size_t size = id.size() * sizeof(decltype(id)::value_type);
        size += salary.size() * sizeof(decltype(salary)::value_type);
        size += firstname.size() * sizeof(decltype(firstname)::value_type);
        return size + sizeof(StructOfArrays);
    }
};
// ----------------------------------------------------------------------------
// Разные алгоритмы сжатия
enum class CompressionType : uint8_t {
    RAW,
    FOR1,
    FOR2,
    FOR4
};
// ----------------------------------------------------------------------------
// Базовый класс для сырых и несжатых столбцов
template <typename T>
struct Column {
    using value_type = T;
    // Схема сжатия
    CompressionType type;
    // Деструктор
    virtual ~Column() {}
    // Конструктор
    Column(CompressionType type) : type(type) {}
    // Вычисляем размер (virtual)
    virtual size_t getSize() const = 0;
};
// ---------------------------------------------------------------------------
// Столбец хранится в сыром формате, например, vector<type>
template <typename T>
struct RawColumn : public Column<T> {
    // Сырые значения
    std::vector<T> column;

    // Конструктор
    RawColumn(auto begin, auto end) : Column<T>(CompressionType::RAW) {
        column.reserve(end - begin);
        for (auto it = begin; it != end; ++it)
            column.emplace_back(*it);
    }
    // Деструктор
    ~RawColumn() override = default;
    // Вычисляем размер
    size_t getSize() const override {
        return column.size() * sizeof(typename decltype(column)::value_type) + sizeof(RawColumn<T>);
    }
};
// ----------------------------------------------------------------------------
// Столбец сжимается кодированием frame-of-reference
template <typename T, typename C>
requires std::is_unsigned_v<T>
struct FORCompressedColumn : public Column<T> {
    // Минимальное значение столбца
    T minValue;
    // Максимальное значение столбца (для frame-of-reference необязательно, но пригодится в дальнейшем)
    T maxValue;
    // Значения, сжатые frame-of-reference
    std::vector<C> compressed;

    // Конструктор
    FORCompressedColumn(auto begin, auto end, T minValue, T maxValue, CompressionType type) : Column<T>(type), minValue(minValue), maxValue(maxValue) {
        compressed.reserve(end - begin);
        for (auto it = begin; it != end; ++it)
            compressed.emplace_back(*it - minValue);
    }
    // Деструктор
    ~FORCompressedColumn() override = default;
    // Вычисляем размер
    size_t getSize() const override {
        return compressed.size() * sizeof(typename decltype(compressed)::value_type) + sizeof(FORCompressedColumn<T, C>);
    }
};
// ----------------------------------------------------------------------------
// Сохраняем тот же столбец со сжатием
struct CompressedStructOfArrays {
    // Потенциально сжатые столбцы
    std::unique_ptr<Column<series>> id;
    std::unique_ptr<Column<decimal>> salary;
    std::unique_ptr<Column<std::array<char, 16>>> firstname;

    // Вычисляем размер
    size_t getSize() const {
        return id->getSize() + salary->getSize() + firstname->getSize() + sizeof(CompressedStructOfArrays);
    }
};
// ---------------------------------------------------------------------------
static constexpr auto createColumn(auto begin, auto end) -> std::unique_ptr<Column<typename decltype(begin)::value_type>>
// Вычисляем идеальную схему сжатия на основании значений
{
    using T = decltype(begin)::value_type;
    if constexpr (!std::is_unsigned_v<T>) {
        return std::make_unique<RawColumn<T>>(begin, end);
    } else {
        auto [minValue, maxValue] = std::ranges::minmax_element(begin, end);
        if (*maxValue - *minValue > std::numeric_limits<uint32_t>::max())
            return std::make_unique<RawColumn<T>>(begin, end);

        if (*maxValue - *minValue <= std::numeric_limits<uint8_t>::max()) {
            return std::make_unique<FORCompressedColumn<T, uint8_t>>(begin, end, *minValue, *maxValue, CompressionType::FOR1);
        } else if (maxValue - minValue <= std::numeric_limits<uint16_t>::max()) {
            return std::make_unique<FORCompressedColumn<T, uint16_t>>(begin, end, *minValue, *maxValue, CompressionType::FOR2);
        } else {
            return std::make_unique<FORCompressedColumn<T, uint32_t>>(begin, end, *minValue, *maxValue, CompressionType::FOR4);
        }
    }
}
// ----------------------------------------------------------------------------
// Сохраняем те же столбцы в формате PAX
struct PaxStore {
    // Блоки сжатых столбцов
    std::vector<CompressedStructOfArrays> pax;

    // Вычисляем размер
    size_t getSize() const {
        size_t size = sizeof(PaxStore);
        for (const auto& elem : pax)
            size += elem.getSize();
        return size;
    }
};
// ---------------------------------------------------------------------------
static PaxStore createPaxColumn(StructOfArrays& store, size_t paxSize)
// Вычисляем идеальную схему сжатия на основании значений
{
    PaxStore pax;
    pax.pax.reserve(store.id.size() / paxSize + 1);
    for (size_t i = 0; i < store.id.size(); i += paxSize) {
        CompressedStructOfArrays c;
        if (i + paxSize > store.id.size()) {
            c.id = createColumn(store.id.begin() + i, store.id.end());
            c.salary = createColumn(store.salary.begin() + i, store.salary.end());
            c.firstname = createColumn(store.firstname.begin() + i, store.firstname.end());
        } else {
            c.id = createColumn(store.id.begin() + i, store.id.begin() + i + paxSize);
            c.salary = createColumn(store.salary.begin() + i, store.salary.begin() + i + paxSize);
            c.firstname = createColumn(store.firstname.begin() + i, store.firstname.begin() + i + paxSize);
        }
        pax.pax.emplace_back(std::move(c));
    }
    return pax;
}
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const ArrayOfStruct& store)
// Вычисляем зарплату
{
    decimal salary = 0;
    // Итеративно обходим строки и выбираем зарплату
    for (const auto& r : store.table)
        salary += r.salary;
    return salary;
}
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const StructOfArrays& store)
// Вычисляем зарплату
{
    decimal salary = 0;
    // Итеративно обходим столбец
    for (auto s : store.salary)
        salary += s;
    return salary;
}
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const CompressedStructOfArrays& store)
// Вычисляем зарплату
{
    auto forComputation = []<typename T>(const T& column) {
        decimal salary = 0;
        for (auto s : column.compressed) {
            salary += s + column.minValue;
        }
        return salary;
    };

    using T = decltype(store.salary)::element_type::value_type;
    decimal salary = 0;
    // Итеративно обходим столбец
    switch (store.salary->type) {
        case CompressionType::RAW:
            {
                auto column = static_cast<RawColumn<T>*>(store.salary.get());
                for (auto s : column->column) {
                    salary += s;
                }
                break;
            }
        case CompressionType::FOR1:
            return forComputation(*static_cast<FORCompressedColumn<T, uint8_t>*>(store.salary.get()));
        case CompressionType::FOR2:
            return forComputation(*static_cast<FORCompressedColumn<T, uint16_t>*>(store.salary.get()));
        case CompressionType::FOR4:
            return forComputation(*static_cast<FORCompressedColumn<T, uint32_t>*>(store.salary.get()));
    }
    return salary;
}
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const PaxStore& store)
// Вычисляем зарплату
{
    decimal salary = 0;
    // Итеративно обходим столбец
    for (const auto& p : store.pax)
        salary += getTotalSalary(p);
    return salary;
}
// ----------------------------------------------------------------------------
static void updateEntry(ArrayOfStruct& store, std::vector<size_t> ids, std::array<char, 16>& newName)
// Обновляем элементы
{
    for (auto id : ids) {
        auto& record = store.table[id];
        record.firstname = newName;
        record.salary *= 2;
    }
}
// ----------------------------------------------------------------------------
static void updateEntry(StructOfArrays& store, std::vector<size_t> ids, std::array<char, 16>& newName)
// Обновляем элементы
{
    for (auto id : ids) {
        store.firstname[id] = newName;
        store.salary[id] = 2 * store.salary[id];
    }
}
// ----------------------------------------------------------------------------
int main() {
    // Создаём 100 миллионов пользователей
    auto users = 100 * 1000 * 1000ull;
    std::array<char, 16> name = {"Moritz - Felipe"};
    // Для обеих версий
    ArrayOfStruct aos;
    StructOfArrays soa;
    CompressedStructOfArrays compressed;
    PaxStore pax;
    // Заполняем хранилища
    for (auto i = 0ull; i < users; i++) {
        aos.table.emplace_back(static_cast<unsigned>(i), (1000 + (static_cast<decimal>(i) % 500)) * 100, name);

        soa.id.push_back(static_cast<unsigned>(i));
        soa.salary.push_back((1000 + (static_cast<decimal>(i) % 500)) * 100);
        soa.firstname.emplace_back(name);
    }

    compressed.id = createColumn(soa.id.cbegin(), soa.id.cend());
    compressed.salary = createColumn(soa.salary.cbegin(), soa.salary.cend());
    compressed.firstname = createColumn(soa.firstname.cbegin(), soa.firstname.cend());

    pax = createPaxColumn(soa, std::numeric_limits<uint16_t>::max());

    // Вычисляем зарплату
    auto measureSalary = []<typename T>(const T& store) {
        // Запускаем таймер
        std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
        auto salary = getTotalSalary(store);
        // Останавливаем таймер
        std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
        // Определяем тип хранилища
        auto storeName = "compressed";
        if constexpr (std::is_same_v<ArrayOfStruct, T>)
            storeName = "aos";
        if constexpr (std::is_same_v<StructOfArrays, T>)
            storeName = "soa";
        if constexpr (std::is_same_v<PaxStore, T>)
            storeName = "pax";
        // Выводим результаты
        std::cout << "Workload: Analyze; Store: " << storeName << "; Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << " [μs]; Size: " << store.getSize() / (1024 * 1024) << " [MB]" << std::endl;
        std::this_thread::sleep_for(std::chrono::milliseconds(1000));
        return salary;
    };

    // Проверяем корректность
    decimal salary = 0;
    if (salary = measureSalary(soa); salary != measureSalary(compressed))
        return -1;

    // Проверяем корректность
    if (salary != measureSalary(pax))
        return -1;

    // Проверяем корректность
    if (salary != measureSalary(aos))
        return -1;

    // -------------

    std::random_device rnd_device;
    std::mt19937 mt{rnd_device()}; // Генерирует случайные целые числа
    std::uniform_int_distribution<uint64_t> dist{0, users - 1};

    auto gen = [&]() {
        return dist(mt);
    };

    std::vector<uint64_t> ids(0.1 * users);
    std::generate(ids.begin(), ids.end(), gen);

    // Обновляем столбец
    auto measureUpdate = []<typename T>(T& store, std::vector<uint64_t> ids) {
        // Обновляем имя и зарплату
        std::array<char, 16> name = {"Dr. Moritz - F."};

        // Запускаем таймер
        std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
        updateEntry(store, ids, name);
        // Останавливаем таймер
        std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
        // Определяем тип хранилища
        auto storeName = "soa";
        if constexpr (std::is_same_v<ArrayOfStruct, T>)
            storeName = "aos";
        // Выводим результаты
        std::cout << "Workload: Update; Store: " << storeName << "; Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << " [μs]" << std::endl;
    };

    measureUpdate(aos, ids);
    measureUpdate(soa, ids);

    return 0;
}
// ----------------------------------------------------------------------------