Compiler Explorer

Source code

#include <vector>
#include <array>
#include <fstream>
#include <stdexcept>
#include <optional>
#include <type_traits>
#include <random>
#include <chrono>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <execution>
#include <filesystem>
#include <memory>
#include <variant>
#include <functional>

#define ASSERT_MSG(cond, msg) { if (!(cond)) throw std::runtime_error("Assertion (" #cond ") failed at line " + std::to_string(__LINE__) + "! Msg: '" + std::string(msg) + "'"); }
#define ASSERT(cond) ASSERT_MSG(cond, "")
#define DASSERT_MSG(cond, msg) //ASSERT_MSG(cond, msg)
#define DASSERT(cond) DASSERT_MSG(cond, "")
#define OSTR(code) ([&]{ std::ostringstream ss; ss code; return ss.str(); }())
#define LN //{ std::cout << "LN " << __LINE__ << std::endl << std::flush; }
#define DUMP(var) //{ std::cout << #var << " = (" << (var) << ")" << std::endl << std::flush; }

#if defined(_MSC_VER)
    // https://stackoverflow.com/a/9504047/941531
    #define ATTR_PACKED
    #define PACKED_BEGIN __pragma(pack(push, 1))
    #define PACKED_END __pragma(pack(pop))
#else
    #define ATTR_PACKED __attribute__((packed))
    #define PACKED_BEGIN
    #define PACKED_END
#endif

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using u128 = unsigned __int128;

template <typename T>
class DiskRW {
public:
    DiskRW(size_t size, std::string const & fname, size_t rbuf_size = 64)
        : size_(size), fsize_(size), fname_(fname), rbuf_(rbuf_size),
          f_(fname_, std::ios::binary | std::ios::in | std::ios::out | std::ios::trunc /* | std::ios::ate*/) {
        ASSERT_MSG(f_ && f_.is_open(), "file name '" + fname_ + "'");
        // https://stackoverflow.com/a/16605541/941531
        //f_.rdbuf()->pubsetbuf((char*)buf_.data(), buf_.size());
        f_.rdbuf()->pubsetbuf(0, 0);
        if (size > 0) {
            f_.seekg(size * sizeof(T) - 1, f_.beg);
            char b = 0;
            f_.write(&b, 1);
            f_.clear();
        }
    }
    T Read(size_t pos) {
        if (!(rbuf_pos_ <= pos && pos < rbuf_pos_ + rbuf_.size())) {
            if (pos + rbuf_.size() > size_) {
                ASSERT_MSG(pos < size_, "pos " + std::to_string(pos) + " size " + std::to_string(size_));
                T obj{};
                f_.seekg(pos * sizeof(T), f_.beg);
                f_.read((char*)&obj, sizeof(T));
                i64 const gc = f_.gcount();
                ASSERT_MSG(gc >= 0 && gc == sizeof(T), "fname '" + fname_ + "' gc " + std::to_string(gc) +
                    " pos " + std::to_string(pos) + " size " + std::to_string(size_));
                rbuf_pos_ = (size_t(-1) >> 1);
                return obj;
            } else {
                ASSERT_MSG(pos + rbuf_.size() <= size_, "pos " + std::to_string(pos) + " size " + std::to_string(size_));
                f_.seekg(pos * sizeof(T), f_.beg);
                f_.read((char*)rbuf_.data(), rbuf_.size() * sizeof(T));
                rbuf_pos_ = pos;
                i64 const gc = f_.gcount();
                ASSERT_MSG(gc >= 0 && gc == rbuf_.size() * sizeof(T), "fname '" + fname_ + "' gc " + std::to_string(gc) +
                    " pos " + std::to_string(pos) + " size " + std::to_string(size_));
                ASSERT_MSG(f_ && f_.good(), fname_);
            }
        }
        return rbuf_.at(pos - rbuf_pos_);
    }
    void Write(size_t pos, T const & obj) {
        ASSERT_MSG(pos < size_, "pos " + std::to_string(pos) + " size " + std::to_string(size_));
        f_.seekg(pos * sizeof(T), f_.beg);
        f_.write((char*)&obj, sizeof(obj));
        ASSERT_MSG(f_ && f_.good(), fname_);
        if (rbuf_pos_ <= pos && pos < rbuf_pos_ + rbuf_.size())
            rbuf_pos_ = (size_t(-1) >> 1);
    }
    void Resize(size_t size) {
        if (size > size_ && size > fsize_) {
            size_ = size;
            fsize_ = size;
            Write(size - 1, {});
        }
        size_ = size;
    }
    size_t Size() const { return size_; }
    
private:
    size_t size_ = 0, rbuf_pos_ = (size_t(-1) >> 1), fsize_ = 0;
    std::string fname_;
    std::vector<T> rbuf_;
    std::fstream f_;
};

template <typename T>
class RamRW {
    static size_t constexpr block_size = 1 << 16;
    
public:
    RamRW(size_t size, std::string const & dummy = "", size_t dummy2 = 0) {
        Resize(size);
    }
    T const & Read(size_t pos) const {
        ASSERT_MSG(pos < Size(), "pos " + std::to_string(pos) +
            " size " + std::to_string(Size()));
        return entries_[pos / block_size][pos % block_size];
    }
    void Write(size_t pos, T obj) {
        ASSERT_MSG(pos < Size(), "pos " + std::to_string(pos) +
            " size " + std::to_string(Size()));
        entries_[pos / block_size][pos % block_size] = std::move(obj);
    }
    void Resize(size_t size) {
        size_ = size;
        static std::vector<T> const empty_block(block_size);
        entries_.resize((size + block_size - 1) / block_size, empty_block);
    }
    size_t Size() const { return size_; }
    
private:
    size_t size_ = 0;
    std::vector<std::vector<T>> entries_;
};

u64 FnvHash64(void const * data, size_t size, u64 prev = u64(-1)) {
    // http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param
    u64 constexpr
        fnv_prime = 1099511628211ULL,
        fnv_offset_basis = 14695981039346656037ULL;
    
    u64 hash = prev == u64(-1) ? fnv_offset_basis : prev;
    
    for (size_t i = 0; i < size; ++i) {
        hash ^= ((u8*)data)[i];
        hash *= fnv_prime;
    }
    
    return hash;
}

u128 FnvHash128(void const * data, size_t size, u128 prev = u128(-1)) {
    // http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param
    u128 constexpr
        fnv_prime = (u128(0x1000000ULL) << 64) | u128(0x000000000000013BULL),
        fnv_offset_basis = (u128(0x6C62272E07BB0142ULL) << 64) | u128(0x62B821756295C58DULL);
    
    u128 hash = prev == u128(-1) ? fnv_offset_basis : prev;
    
    for (size_t i = 0; i < size; ++i) {
        hash ^= ((u8*)data)[i];
        hash *= fnv_prime;
    }
    
    return hash;
}

PACKED_BEGIN
template <typename A, typename B>
struct ATTR_PACKED PackedPair {
    A first{};
    B second{};

bool operator < (PackedPair const & o) const {
        return std::tie(first, second) < std::tie(o.first, o.second);
    }
    bool operator > (PackedPair const & o) const {
        return std::tie(first, second) > std::tie(o.first, o.second);
    }
};
PACKED_END

template <typename TInp = void, typename KeyDataInp = void, size_t ExtraHashBytes = 8, bool IsDisk = false>
class DiskHashSet {
    struct Null {};
    using T = std::conditional_t<std::is_same_v<std::decay_t<TInp>, void>, Null, std::decay_t<TInp>>;
    using KeyData = std::conditional_t<std::is_same_v<std::decay_t<KeyDataInp>, void>, Null, std::decay_t<KeyDataInp>>;
    using HashT = u128;
    static size_t constexpr hdr_bysize = ExtraHashBytes, hdr_bisize = hdr_bysize * 8, max_collisions = 256;
    static bool constexpr is_null_t = std::is_same_v<T, Null>, is_null_key_data = std::is_same_v<KeyData, Null>;
    
    PACKED_BEGIN
    struct ATTR_PACKED Entry {
        using HdrT = std::array<u8, hdr_bysize>;
        
        HdrT & Hdr() {
            if constexpr(is_null_t)
                return hdr_obj;
            else
                return *&hdr_obj.first;
        }
        HdrT const & Hdr() const { return const_cast<Entry &>(*this).Hdr(); }
        bool Empty() const { return (Hdr()[sizeof(HdrT) - 1] >> 6) == 0; }
        bool Deleted() const { return (Hdr()[sizeof(HdrT) - 1] >> 6) == 1; }
        bool EmptyOrDeleted() const { return (Hdr()[sizeof(HdrT) - 1] >> 7) == 0; }
        HashT HashHi() const {
            ASSERT(!EmptyOrDeleted());
            return (*(HashT*)Hdr().data()) & ((HashT(1) << (hdr_bisize - 1)) - 1);
        }
        void SetHdr(HashT h, bool full, bool del = false) {
            if (full)
                ASSERT(!del);
            if (full)
                h |= HashT(1) << (hdr_bisize - 1);
            else {
                h = 0;
                if (del)
                    h |= HashT(1) << (hdr_bisize - 2);
            }
            std::memcpy(&Hdr(), &h, sizeof(HdrT));
        }
        template <typename T0>
        void SetObj(T0 && obj) {
            if constexpr(!is_null_t)
                hdr_obj.second = std::forward<T0>(obj);
        }
        T & Obj() {
            if constexpr(is_null_t) {
                static auto null = Null{};
                return null;
            } else {
                return *&hdr_obj.second;
            }
        }
        
        std::conditional_t<is_null_t, HdrT, PackedPair<HdrT, T>> hdr_obj{};
    };
    PACKED_END
    
    using RW = std::conditional_t<IsDisk, DiskRW<Entry>, RamRW<Entry>>;
    
public:
    DiskHashSet(size_t size, std::string const & fname = "", KeyData const & key_data = Null{})
        : size_(size), rw_(size + max_collisions + 2, fname), key_data_(key_data) {}
    
    template <typename Key>
    void Set(Key const & key, T const & obj = Null{}) {
        auto const hash = Hash(key);
        auto const hash_hi = HashHi(hash);
        auto const bucket = Bucket(hash);
        size_t i = bucket;
        for (size_t cnt = 0;; ++i, ++cnt) {
            Entry e = rw_.Read(i);
            if (e.Empty() || !e.Deleted() && Equal(key, hash_hi, e.Obj(), e.HashHi()))
                break;
            ASSERT(cnt < max_collisions);
        }
        Entry entry{};
        entry.SetObj(obj);
        entry.SetHdr(hash_hi, true);
        rw_.Write(i, std::move(entry));
    }
    
    template <typename Key>
    std::optional<T> Get(Key const & key) {
        auto const hash = Hash(key);
        auto const hash_hi = HashHi(hash);
        auto const bucket = Bucket(hash);
        for (size_t i = bucket, cnt = 0;; ++i, ++cnt) {
            Entry e = rw_.Read(i);
            if (e.Empty())
                return std::nullopt;
            if (!e.Deleted() && Equal(key, hash_hi, e.Obj(), e.HashHi()))
                return e.Obj();
            ASSERT(cnt < max_collisions);
        }
    }
    
    template <typename Key>
    bool Del(Key const & key) {
        auto const hash = Hash(key);
        auto const hash_hi = HashHi(hash);
        auto const bucket = Bucket(hash);
        for (size_t i = bucket, cnt = 0;; ++i, ++cnt) {
            Entry e = rw_.Read(i);
            if (e.Empty())
                return false;
            if (!e.Deleted() && Equal(key, hash_hi, e.Obj(), e.HashHi())) {
                if constexpr(!is_null_t)
                    e.SetObj(T());
                if (rw_.Read(i + 1).Empty()) {
                    e.SetHdr(0, false);
                    rw_.Write(i, e);
                    for (ptrdiff_t j = ptrdiff_t(i) - 1; j >= ptrdiff_t(bucket); --j) {
                        if (rw_.Read(j).Deleted())
                            rw_.Write(j, e);
                        else
                            break;
                    }
                } else {
                    e.SetHdr(0, false, true);
                    rw_.Write(i, std::move(e));
                }
                return true;
            }
            ASSERT(cnt < max_collisions - 1);
        }
    }
    
private:
    size_t Bucket(HashT const & hash) const {
        return u64(hash) % size_;
    }
    template <typename Key>
    bool Equal(Key const & keya, HashT const ha, T const & b, HashT const hb) const {
        return ha == hb;
    }
    template <typename Key>
    HashT Hash(Key const & key) {
        if constexpr(is_null_key_data)
            return FnvHash128(&key, sizeof(key));
        else {
            auto const [ptr, size] = key_data_(key);
            return FnvHash128(ptr, size);
        }
    }
    HashT HashHi(HashT const & h) {
        return (h >> (sizeof(h) * 8 - hdr_bisize)) & ((HashT(1) << (hdr_bisize - 1)) - 1);
    }
    
    size_t size_ = 0;
    RW rw_;
    KeyData key_data_;
};

double Time() {
    static auto const gtb = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::duration<double>>(
        std::chrono::high_resolution_clock::now() - gtb).count();
}

void Algo_HashSet(std::string const & fname) {
    auto tim = Time();
    
    size_t constexpr extra_hash_bytes = 8;
    size_t cnt_lines = 0;
    {
        std::ifstream f(fname);
        std::string line;
        while (std::getline(f, line))
            ++cnt_lines;
    }
    auto KeyData = [](auto const & s){ return std::pair{s.data(), s.size()}; };
    DiskHashSet<void, decltype(KeyData), extra_hash_bytes, true> hset(
        std::llround(cnt_lines * 1.25), fname + ".hset", KeyData);
    {
        std::ofstream fout(fname + ".out.algo_hash_set");
        std::ifstream f(fname);
        std::string line;
        while (std::getline(f, line)) {
            if (hset.Get(line))
                continue;
            fout << line << std::endl;
            hset.Set(line);
        }
    }
    
    std::cout << "Algo HashSet "  << std::setprecision(2) << (Time() - tim) << " sec" << std::endl;
}

template <typename It>
void MultiMergeSort(std::vector<std::pair<It, It>> const & ranges, std::string const & out_fname) {
    std::ofstream fout(out_fname, std::ios::binary);
    using T = std::decay_t<decltype(*std::declval<It>())>;
    std::vector<It> ptrs;
    for (auto const & [a, b]: ranges)
        ptrs.push_back(a);
    std::vector<std::pair<T, u16>> heap;
    for (u16 i = 0; i < ptrs.size(); ++i)
        heap.push_back({*ptrs[i], i});
    auto Cmp = [](auto const & a, auto const & b){ return a > b; };
    std::make_heap(heap.begin(), heap.end(), Cmp);
    std::vector<T> buf;
    while (!heap.empty()) {
        std::pop_heap(heap.data(), heap.data() + heap.size(), Cmp);
        auto const [val, i] = heap.back();
        buf.push_back(val);
        heap.pop_back();
        if (buf.size() >= (1ULL << 22) || heap.empty()) {
            fout.write((char*)buf.data(), buf.size() * sizeof(buf[0]));
            buf.clear();
        }
        ++ptrs[i];
        if (ptrs[i] != ranges[i].second) {
            heap.push_back({*ptrs[i], i});
            std::push_heap(heap.data(), heap.data() + heap.size(), Cmp);
        }
    }
}

// https://stackoverflow.com/a/2513561/941531
#if _WIN32
    #include <windows.h>
    #undef min
    #undef max
    
    unsigned long long TotalMemory() {
        MEMORYSTATUSEX status;
        status.dwLength = sizeof(status);
        GlobalMemoryStatusEx(&status);
        return status.ullTotalPhys;
    }
#else
    #include <unistd.h>

unsigned long long TotalMemory() {
        long pages = sysconf(_SC_PHYS_PAGES);
        long page_size = sysconf(_SC_PAGE_SIZE);
        return pages * page_size;
    }
#endif

template <typename T, typename CmpIn>
class DiskSorter {
    using Cmp = std::decay_t<CmpIn>;
    inline static size_t const mem_size = size_t(TotalMemory() * 0.5);
    
public:
    class It {
    public:
        It() {}
        It(std::string const & fname)
            : empty_(false), fname_(fname),
              f_(std::make_shared<std::ifstream>(fname_, std::ios::binary)) {
            fsize_ = std::filesystem::file_size(fname_);
            ReFill();
        }
        It & operator ++ () {
            ++pos_;
            ++tpos_;
            ASSERT(tpos_ <= fsize_);
            if (pos_ >= buf_.size())
                ReFill();
            return *this;
        }
        auto const & operator * () const {
            ASSERT_MSG(tpos_ * sizeof(T) < fsize_ && pos_ < buf_.size(), "tpos " + std::to_string(tpos_) + " tpos * sizeof(T) " + std::to_string(tpos_ * sizeof(T)) +
                " fsize " + std::to_string(fsize_) + " pos " + std::to_string(pos_) + " buf_.size() " + std::to_string(buf_.size()));
            return buf_[pos_];
        }
        bool operator == (It const & o) const {
            if (o.empty_)
                return empty_ || tpos_ * sizeof(T) >= fsize_;
            else if (empty_)
                return o.empty_ || o.tpos_ * sizeof(T) >= o.fsize_;
            return fname_ == o.fname_ && tpos_ == o.tpos_;
        }
        bool operator != (It const & o) const {
            return !(*this == o);
        }
    private:
        void ReFill() {
            ASSERT(pos_ == buf_.size());
            buf_.clear();
            if (!f_->eof()) {
                buf_.resize(1ULL << 20);
                ASSERT_MSG(fpos_ == f_->tellg(), "fpos " + std::to_string(fpos_) + " tell " + std::to_string(f_->tellg()));
                f_->read((char*)buf_.data(), buf_.size() * sizeof(buf_[0]));
                i64 const gc = f_->gcount();
                ASSERT(gc % sizeof(buf_[0]) == 0);
                buf_.resize(gc / sizeof(buf_[0]));
                fpos_ += gc;
            }
            pos_ = 0;
        }
        
        bool empty_ = true;
        std::string fname_;
        std::shared_ptr<std::ifstream> f_;
        std::vector<T> buf_;
        size_t fsize_ = 0, pos_ = 0, tpos_ = 0, fpos_ = 0;
    };
    DiskSorter(std::string const & fname, Cmp const & cmp)
        : fname_(fname), cmp_(cmp) {}
    void Flush() {
        if (to_sort_.empty())
            return;
        std::sort(std::execution::par_unseq, to_sort_.data(), to_sort_.data() + to_sort_.size(), cmp_);
        std::ofstream fw(SortFName(nblocks_), std::ios::binary);
        fw.write((char*)to_sort_.data(), to_sort_.size() * sizeof(to_sort_[0]));
        to_sort_.clear();
        ++nblocks_;
    }
    void Add(T const & obj) {
        to_sort_.push_back(obj);
        if (to_sort_.size() * sizeof(to_sort_[0]) >= mem_size)
            Flush();
    }
    std::string SortAllFName() const {
        return fname_ + ".sort_all";
    }
    void Sort() {
        Flush();
        std::vector<std::pair<It, It>> ranges;
        for (size_t i = 0; i < nblocks_; ++i)
            ranges.push_back({It(SortFName(i)), It()});
        MultiMergeSort(ranges, SortAllFName());
    }
private:
    std::string SortFName(size_t iblock) const {
        return fname_ + ".sort." + OSTR(<< std::setfill('0') << std::setw(3) << iblock);
    }
    
    std::string const fname_;
    Cmp cmp_;
    size_t nblocks_ = 0;
    std::vector<T> to_sort_;
};

void Algo_Sort(std::string const & fname) {
    using Pair = PackedPair<u128, u64>;
    
    auto tim = Time();
    auto Cmp = [](auto const & a, auto const & b){ return a < b; };
    
    {
        DiskSorter<Pair, decltype(Cmp)> sorter(fname + ".stage_a", Cmp);
        std::ifstream f(fname);
        std::string line;
        size_t i = 0;
        while (std::getline(f, line)) {
            sorter.Add({FnvHash128(line.data(), line.size()), i});
            ++i;
        }
        
        sorter.Sort();
        
        {
            std::ofstream fw(fname + ".stage_a.unique_all", std::ios::binary);
            DiskSorter<Pair, decltype(Cmp)>::It it(sorter.SortAllFName()), end;
            std::vector<Pair> buf;
            for (; it != end;) {
                buf.push_back(*it);
                ++it;
                while (buf.size() >= 2 && buf[buf.size() - 1].first == buf[buf.size() - 2].first)
                    buf.pop_back();
                if (buf.size() >= (1ULL << 20) || it == end) {
                    fw.write((char*)buf.data(), buf.size() * sizeof(buf[0]));
                    buf.clear();
                }
            }
        }
    }
    
    {
        DiskSorter<u64, decltype(Cmp)> sorter2(fname + ".stage_b", Cmp);
        std::ifstream fr(fname + ".stage_a.unique_all", std::ios::binary);
        std::vector<Pair> buf;
        while (true) {
            buf.clear();
            buf.resize(1ULL << 20);
            fr.read((char*)buf.data(), buf.size() * sizeof(buf[0]));
            i64 const gc = fr.gcount();
            ASSERT(gc >= 0 && (gc % sizeof(buf[0]) == 0));
            if (gc == 0)
                break;
            fr.clear();
            buf.resize(gc / sizeof(buf[0]));
            for (auto const & p: buf)
                sorter2.Add(p.second);
        }
        
        sorter2.Sort();
        
        {
            DiskSorter<u64, decltype(Cmp)>::It it(sorter2.SortAllFName()), end;
            std::ifstream f(fname);
            std::ofstream fw(fname + ".out.algo_sort");
            std::string line;
            size_t i = 0;
            while (std::getline(f, line) && it != end) {
                if (i >= *it) {
                    ASSERT(i == *it);
                    fw << line << std::endl;
                    ++it;
                }
                ++i;
            }
        }
    }
    
    std::cout << "Algo Sort "  << std::setprecision(1) << (Time() - tim) << " sec" << std::endl;
}

std::string RepeatStr(std::string const & s, size_t cnt) {
    std::string r;
    for (size_t i = 0; i < cnt; ++i)
        r += s;
    return r;
}

std::string IntToStr(u128 n, size_t zero_pad = size_t(-1)) {
    if (n == 0)
        return "0";
    std::string r;
    bool sign = false;
    if (n < 0) {
        sign = true;
        n = -n;
    }
    while (n != 0) {
        u32 constexpr mod = 1'000'000'000U;
        std::ostringstream ss;
        auto const nm = u32(n % mod);
        n /= mod;
        if (n != 0)
            ss << std::setw(9) << std::setfill('0');
        ss << nm;
        r = ss.str() + r;
    }
    if (zero_pad != size_t(-1))
        r = RepeatStr("0", std::max<size_t>(zero_pad, r.size()) - r.size()) + r;
    return (sign ? "-" : "") + r;
}

PACKED_BEGIN
template <size_t Bytes, typename NumT = std::conditional_t<Bytes <= 8, u64, u128>>
class ATTR_PACKED CutNum {
public:
    CutNum() {}
    CutNum(NumT const & n) {
        Set(n);
    }
    CutNum & operator = (NumT const & n) {
        Set(n);
        return *this;
    }
    operator NumT() const {
        return Get();
    }
    void Set(NumT const & n) {
        /*
        *(u64*)&n_ = ((*(u64*)&n_) & (u64(-1) << (Bytes * 8))) |
            (n & (u64(-1) >> (64 - Bytes * 8)));
        */
        std::memcpy(&n_, &n, Bytes);
    }
    NumT Get() const {
        //return (*(u64*)&n_) & (u64(-1) >> (64 - Bytes * 8));
        NumT n = 0;
        std::memcpy(&n, &n_, Bytes);
        return n;
    }
    std::strong_ordering operator <=> (CutNum const & o) const {
        return Get() <=> o.Get();
    }
    
private:
    static_assert(Bytes <= sizeof(NumT));
    
    std::array<u8, Bytes> n_{};
};
PACKED_END

template <typename T, typename Key = T, template <typename> class RW = RamRW>
class BTree {
    static bool constexpr verbose = 0;
    static size_t constexpr degree = 10, nidx_bysize = 5;
    
    using NodeIdx = CutNum<nidx_bysize>;
    using NodeArrIdx = u8;
    using ValToKeyT = std::function<Key(T const & Val)>;
    
    static_assert(degree + 1 < (1ULL << (sizeof(NodeArrIdx) * 8)));
    
    PACKED_BEGIN
    struct ATTR_PACKED IntermNode {
        NodeArrIdx size = 0;
        std::array<PackedPair<NodeIdx, Key>, degree> children{};
    };
    struct ATTR_PACKED LeafNode {
        NodeArrIdx size = 0;
        std::array<T, degree> vals{};
    };
    PACKED_END
    
    struct PathEntry {
        LeafNode & Leaf() { return std::get<LeafNode>(node); }
        LeafNode const & Leaf() const { return std::get<LeafNode>(node); }
        IntermNode & Interm() { return std::get<IntermNode>(node); }
        IntermNode const & Interm() const { return std::get<IntermNode>(node); }
        
        std::variant<IntermNode, LeafNode> node;
        u64 nidx = 0;
        NodeArrIdx aidx = 0;
    };
    
public:
    BTree(std::string const & fname = "", ValToKeyT const & val_to_key = ValToKeyT{})
        : interms_(0, fname + ".interms", 1), leafs_(0, fname + ".leafs", 1) {
        if (val_to_key)
            ValToKey = val_to_key;
        else {
            if constexpr(std::is_same_v<T, Key>)
                ValToKey = [](auto const & val){ return val; };
        }
        ASSERT(ValToKey);
    }
    
    void Set(T const & val) {
        if constexpr(verbose)
            std::cout << "Set:" << std::endl;
        if (height_ == 0) {
            CreateFirstRoot(val);
            return;
        }
        auto const key = ValToKey(val);
        auto & path = Find(key);
        if constexpr(verbose) {
            std::cout << "Key: " << IntToStr(key) << std::endl;
            std::cout << "Path: ";
            size_t i = 0;
            for (auto const & e: path) {
                std::cout << "nidx " << e.nidx << " aidx " << size_t(e.aidx) << " key "
                    << IntToStr(i + 1 == path.size() ? e.Leaf().vals[e.aidx] : e.Interm().children[e.aidx].second, 20) << ",   ";
                ++i;
            }
            std::cout << std::endl << std::endl;
            std::cout << "Before:" << std::endl << Dump() << std::endl << std::endl;
        }
        auto const leaf_inode = path.back().nidx;
        auto leaf = path.back().Leaf();
        auto const leaf_idx = path.back().aidx;
        auto const leaf_key = ValToKey(leaf.vals.at(leaf_idx));
        if (leaf_key != key) {
            if (leaf.size < leaf.vals.size()) {
                if (leaf_idx == 0 && key < leaf_key) {
                    std::move_backward(leaf.vals.data(), leaf.vals.data() + leaf.size, leaf.vals.data() + leaf.size + 1);
                    leaf.vals.at(0) = val;
                    for (ptrdiff_t i = ptrdiff_t(path.size()) - 2; i >= 0; --i) {
                        auto interm = path[i].Interm();
                        if (interm.children[path[i].aidx].second != key) {
                            interm.children[path[i].aidx].second = key;
                            WriteInterm(path[i].nidx, interm);
                        }
                        if (path[i].aidx > 0)
                            break;
                    }
                } else {
                    std::move_backward(leaf.vals.data() + leaf_idx + 1, leaf.vals.data() + leaf.size, leaf.vals.data() + leaf.size + 1);
                    leaf.vals.at(leaf_idx + 1) = val;
                }
                ++leaf.size;
                WriteLeaf(leaf_inode, leaf);
            } else {
                auto const new_leaf_inode = AddLeaf();
                LeafNode new_leaf;
                size_t const size_left = (leaf.size + 1) / 2, size_right = leaf.size - size_left;
                DASSERT(size_left > 0 && size_right > 0);
                DASSERT(leaf.size <= leaf.vals.size());
                DASSERT(size_left <= leaf.size);
                std::move(leaf.vals.data() + size_left, leaf.vals.data() + leaf.size, new_leaf.vals.data());
                std::fill(leaf.vals.data() + size_left, leaf.vals.data() + leaf.size, std::decay_t<decltype(leaf.vals[0])>());
                leaf.size = size_left;
                new_leaf.size = size_right;
                
                if (leaf_idx < leaf.size) {
                    if (leaf_idx == 0 && key < leaf_key) {
                        std::move_backward(leaf.vals.data(), leaf.vals.data() + leaf.size, leaf.vals.data() + leaf.size + 1);
                        leaf.vals.at(0) = val;
                    } else {
                        std::move_backward(leaf.vals.data() + leaf_idx + 1, leaf.vals.data() + leaf.size, leaf.vals.data() + leaf.size + 1);
                        leaf.vals.at(leaf_idx + 1) = val;
                    }
                    ++leaf.size;
                } else {
                    std::move_backward(new_leaf.vals.data() + leaf_idx + 1 - leaf.size, new_leaf.vals.data() + new_leaf.size, new_leaf.vals.data() + new_leaf.size + 1);
                    new_leaf.vals.at(leaf_idx + 1 - leaf.size) = val;
                    ++new_leaf.size;
                }
                
                WriteLeaf(leaf_inode, leaf);
                WriteLeaf(new_leaf_inode, new_leaf);
                path.pop_back();
                if constexpr(verbose)
                    std::cout << "SplitInterm " << leaf_inode << "|" << IntToStr(ValToKey(leaf.vals.front())) << ",    "
                        << new_leaf_inode << "|" << IntToStr(ValToKey(new_leaf.vals.front())) << std::endl;
                SplitInterm(path, leaf_inode, ValToKey(leaf.vals.front()), new_leaf_inode, ValToKey(new_leaf.vals.front()));
            }
        } else {
            leaf.vals.at(leaf_idx) = val;
            WriteLeaf(leaf_inode, leaf);
        }

if constexpr(verbose)        
            std::cout << "After:" << std::endl << Dump() << std::endl << std::endl;
    }
    
    std::optional<T> Get(Key const & key) {
        if (height_ == 0)
            return std::nullopt;
        auto const & path = Find(key);
        auto const & leaf = path.back().Leaf();
        auto const leaf_idx = path.back().aidx;
        auto const leaf_key = ValToKey(leaf.vals.at(leaf_idx));
        if (leaf_key != key)
            return std::nullopt;
        else
            return leaf.vals.at(leaf_idx);
    }
    
    std::string Dump(size_t inode = size_t(-1), size_t depth = 0, std::string const & indent = "") const {
        std::string r;
        if (inode == size_t(-1)) {
            ASSERT(depth == 0);
            inode = root_idx_;
            r += "(" + std::to_string(inode) + ")\n";
        }
        if (depth + 1 < height_) {
            auto const interm = IntermAt(inode);
            for (size_t i = 0; i < interm.size; ++i) {
                r += indent + "* " + IntToStr(interm.children[i].second, 20) +
                    " (" + std::to_string(interm.children[i].first) + ")\n";
                r += Dump(interm.children[i].first, depth + 1,
                    indent + (i + 1 >= interm.size ? "  " : "| "));
            }
        } else {
            auto const leaf = LeafAt(inode);
            for (size_t i = 0; i < leaf.size; ++i)
                r += indent + "* " + IntToStr(leaf.vals[i], 20) + "\n";
        }
        return r;
    }
    
private:
    void CreateFirstRoot(T const & val) {
        DASSERT(height_ == 0);
        DASSERT(root_idx_ == u64(-1));
        auto const root_inode = AddInterm();
        IntermNode root;
        auto const leaf_inode = AddLeaf();
        LeafNode leaf;
        leaf.vals.at(0) = val;
        leaf.size = 1;
        root.children.at(0).first = leaf_inode;
        root.children.at(0).second = ValToKey(val);
        root.size = 1;
        WriteInterm(root_inode, root);
        WriteLeaf(leaf_inode, leaf);
        root_idx_ = root_inode;
        height_ = 2;
        return;
    }
    
    void SplitInterm(std::vector<PathEntry> & path,
            u64 child_inode_left, Key const & child_key_first_left,
            u64 child_inode_right, Key const & child_key_first_right) {
        if (path.empty()) {
            auto const root_inode = AddInterm();
            IntermNode root;
            root.children.at(0).first = child_inode_left;
            root.children.at(0).second = child_key_first_left;
            root.children.at(1).first = child_inode_right;
            root.children.at(1).second = child_key_first_right;
            root.size = 2;
            WriteInterm(root_inode, root);
            root_idx_ = root_inode;
            ++height_;
            return;
        }
        auto interm = path.back().Interm();
        auto const interm_inode = path.back().nidx;
        auto const interm_idx = path.back().aidx;
        if (interm.size < interm.children.size()) {
            DASSERT(interm_idx + 1 <= interm.size);
            std::move_backward(interm.children.data() + interm_idx + 1, interm.children.data() + interm.size, interm.children.data() + interm.size + 1);
            interm.children.at(interm_idx).first = child_inode_left;
            interm.children[interm_idx].second = child_key_first_left;
            interm.children.at(interm_idx + 1).first = child_inode_right;
            interm.children[interm_idx + 1].second = child_key_first_right;
            ++interm.size;
            WriteInterm(interm_inode, interm);
            
            if (interm_idx == 0)
                for (ptrdiff_t i = ptrdiff_t(path.size()) - 2; i >= 0; --i) {
                    auto cur = path[i].Interm();
                    if (cur.children[path[i].aidx].second != child_key_first_left) {
                        cur.children[path[i].aidx].second = child_key_first_left;
                        WriteInterm(path[i].nidx, cur);
                    }
                    if (path[i].aidx > 0)
                        break;
                }
        } else {
            auto const new_interm_inode = AddInterm();
            IntermNode new_interm;
            size_t const size_left = (interm.size + 1) / 2, size_right = interm.size - size_left;
            std::move(interm.children.data() + size_left, interm.children.data() + interm.size, new_interm.children.data());
            std::fill(interm.children.data() + size_left, interm.children.data() + interm.size, std::decay_t<decltype(interm.children[0])>());
            interm.size = size_left;
            new_interm.size = size_right;
            
            if (interm_idx < interm.size) {
                interm.children[interm_idx].first = child_inode_left;
                interm.children[interm_idx].second = child_key_first_left;
            } else {
                new_interm.children[interm_idx - interm.size].first = child_inode_left;
                new_interm.children[interm_idx - interm.size].second = child_key_first_left;
            }
            if (interm_idx + 1 <= interm.size) {
                std::move_backward(interm.children.data() + interm_idx + 1, interm.children.data() + interm.size, interm.children.data() + interm.size + 1);
                interm.children[interm_idx + 1].first = child_inode_right;
                interm.children[interm_idx + 1].second = child_key_first_right;
                ++interm.size;
            } else {
                std::move_backward(new_interm.children.data() + interm_idx + 1 - interm.size, new_interm.children.data() + new_interm.size,
                    new_interm.children.data() + new_interm.size + 1);
                new_interm.children[interm_idx + 1 - interm.size].first = child_inode_right;
                new_interm.children[interm_idx + 1 - interm.size].second = child_key_first_right;
                ++new_interm.size;
            }
            
            WriteInterm(interm_inode, interm);
            WriteInterm(new_interm_inode, new_interm);
            path.pop_back();
            SplitInterm(path, interm_inode, interm.children.front().second, new_interm_inode, new_interm.children.front().second);
        }
    }
    
    std::vector<PathEntry> & Find(Key const & key) const {
        thread_local std::vector<PathEntry> path;
        path.clear();
        u64 inode = root_idx_;
        size_t ifind = 0;
        while (path.size() + 1 < height_) {
            auto const * pnode = &IntermAt(inode);
            size_t i = 1;
            for (; i < pnode->size; ++i)
                if (key < pnode->children.at(i).second)
                    break;
            if constexpr(verbose)
                std::cout << "Find i " << ifind << ", aidx " << (i - 1) << ", key " << IntToStr(pnode->children.at(i - 1).second, 20) << ", inode " << inode << std::endl;
            path.push_back({.node = *pnode, .nidx = inode, .aidx = NodeArrIdx(i - 1)});
            inode = pnode->children.at(i - 1).first;
            ++ifind;
        }
        {
            auto const * pnode = &LeafAt(inode);
            size_t i = 1;
            for (; i < pnode->size; ++i)
                if (key < ValToKey(pnode->vals.at(i)))
                    break;
            if constexpr(verbose)
                std::cout << "Find i " << ifind << ", aidx " << (i - 1) << ", key " << IntToStr(pnode->vals.at(i - 1), 20) << ", inode " << inode << std::endl;
            path.push_back({.node = *pnode, .nidx = inode, .aidx = NodeArrIdx(i - 1)});
            ++ifind;
        }
        DASSERT(path.size() == height_);
        return path;
    }
    
    IntermNode & IntermAt(size_t i) {
        thread_local IntermNode node{};
        node = interms_.Read(i);
        return node;
    }
    IntermNode const & IntermAt(size_t i) const {
        return const_cast<BTree &>(*this).IntermAt(i);
    }
    u64 AddInterm() {
        u64 const add_interm_size = interms_.Size();
        interms_.Resize(add_interm_size + 1);
        return add_interm_size;
    }
    void WriteInterm(size_t i, IntermNode const & node) {
        DASSERT_MSG(i < interms_.Size(), "i " + std::to_string(i) + " Size() " + std::to_string(interms_.Size()));
        interms_.Write(i, node);
    }
    LeafNode & LeafAt(size_t i) {
        thread_local LeafNode node{};
        node = leafs_.Read(i);
        return node;
    }
    LeafNode const & LeafAt(size_t i) const {
        return const_cast<BTree &>(*this).LeafAt(i);
    }
    u64 AddLeaf() {
        u64 const add_leaf_size = leafs_.Size();
        leafs_.Resize(add_leaf_size + 1);
        return add_leaf_size;
    }
    void WriteLeaf(size_t i, LeafNode const & node) {
        DASSERT_MSG(i < leafs_.Size(), "i " + std::to_string(i) + " Size() " + std::to_string(leafs_.Size()));
        leafs_.Write(i, node);
    }
    
    u64 root_idx_ = u64(-1);
    size_t height_ = 0;
    RW<IntermNode> interms_;
    RW<LeafNode> leafs_;
    ValToKeyT ValToKey{};
};

void Algo_BTree(std::string const & fname) {
    auto tim = Time();
    
    size_t constexpr extra_hash_bytes = 8;
    size_t cnt_lines = 0;
    {
        std::ifstream f(fname);
        std::string line;
        while (std::getline(f, line))
            ++cnt_lines;
    }
    auto Hash = [](auto const & s){ return FnvHash128(s.data(), s.size()); };
    BTree<CutNum<12>, CutNum<12>, DiskRW> btree(fname + ".btree");
    {
        std::ofstream fout(fname + ".out.algo_btree");
        std::ifstream f(fname);
        std::string line;
        while (std::getline(f, line)) {
            auto const line_hash = Hash(line);
            if (btree.Get(line_hash))
                continue;
            fout << line << std::endl;
            btree.Set(line_hash);
            DASSERT_MSG(btree.Get(line_hash), "line '" + line + "' line_hash " + IntToStr(line_hash) + "\n" + btree.Dump());
        }
    }
    
    std::cout << "Algo BTree " << std::setprecision(1) << (Time() - tim) << " sec" << std::endl;
}

void Test() {
    using BTreeT = BTree<PackedPair<u64, u64>, u64, RamRW>;
    size_t constexpr ntests = 16, size = 1ULL << 14;
    std::mt19937_64 rng{std::random_device{}()};
    std::vector<std::pair<u64, u64>> nums(std::llround(size * 0.75));
    auto CreateBTree = []{
        return std::make_shared<BTreeT>("", [](auto const & v){ return v.first; });
    };
    {
        std::unordered_set<u64> exists;
        for (auto & n: nums) {
            u64 x = rng();
            while (exists.count(x))
                x = rng();
            n = {x, rng()};
        }
    }
    {
        double ta = 1000, tb = 1000, tc = 1000;
        for (size_t it = 0; it < ntests; ++it) {
            std::unordered_map<u64, u64> a;
            a.rehash(size);
            auto tim = Time();
            for (auto const & [x, y]: nums)
                a[x] = y;
            ta = std::min(ta, Time() - tim);
        }
        for (size_t it = 0; it < ntests; ++it) {
            DiskHashSet<u64> b(size);
            auto tim = Time();
            for (auto const & [x, y]: nums)
                b.Set(x, y);
            tb = std::min(tb, Time() - tim);
        }
        for (size_t it = 0; it < ntests; ++it) {
            auto b = CreateBTree();
            auto tim = Time();
            for (auto const & [x, y]: nums)
                b->Set({x, y});
            tc = std::min(tc, Time() - tim);
        }
        std::cout << std::fixed << "Insert Time HS " << std::setprecision(1) << std::setw(6) << (tb * 1'000'000'000 / nums.size())
            << " ns/num, BT " << std::setw(6) << (tc * 1000000000 / nums.size()) << " ns/num, UM " << std::setw(6)
            << (ta * 1'000'000'000 / nums.size()) << " ns/num, Boost HS " << std::setprecision(3) << (ta / tb)
            << "x, Boost BT " << std::setprecision(3) << (ta / tc) << "x" << std::endl;
    }
    {
        double ta = 1000, tb = 1000, tc = 1000;
        {
            for (size_t it = 0; it < ntests; ++it) {
                std::unordered_map<u64, u64> a;
                a.rehash(size);
                for (auto const & [x, y]: nums)
                    a[x] = y;
                auto tim = Time();
                for (auto const & [x, y]: nums)
                    a.erase(x);
                ta = std::min(ta, Time() - tim);
            }
        }
        {
            for (size_t it = 0; it < ntests; ++it) {
                DiskHashSet<u64> b(size);
                for (auto const & [x, y]: nums)
                    b.Set(x, y);
                auto tim = Time();
                size_t i = 0;
                for (auto const & [x, y]: nums) {
                    ASSERT_MSG(b.Del(x), "i " + std::to_string(i) + " x " + std::to_string(x) + " y " + std::to_string(y));
                    ++i;
                }
                tb = std::min(tb, Time() - tim);
            }
        }
        std::cout << std::fixed << "Erase  Time HS " << std::setprecision(1) << std::setw(6) << (tb * 1'000'000'000 / nums.size())
            << " ns/num,                   UM " << std::setw(6) << (ta * 1'000'000'000 / nums.size()) << " ns/num, Boost HS " << std::setprecision(3)
            << (ta / tb) << "x" << std::endl;
    }
    {
        double ta = 1000, tb = 1000, tc = 1000;
        {
            std::unordered_map<u64, u64> a;
            a.rehash(size);
            for (auto const & [x, y]: nums)
                a[x] = y;
            for (size_t it = 0; it < ntests; ++it) {
                auto tim = Time();
                for (auto const & [x, y]: nums)
                    ASSERT(a.at(x) == y);
                ta = std::min(ta, Time() - tim);
            }
        }
        {
            DiskHashSet<u64> b(size);
            for (auto const & [x, y]: nums)
                b.Set(x, y);
            for (size_t it = 0; it < ntests; ++it) {
                auto tim = Time();
                for (auto const & [x, y]: nums) {
                    auto volatile res = b.Get(x);
                }
                tb = std::min(tb, Time() - tim);
                if (it == 0) {
                    size_t i = 0;
                    for (auto const & [x, y]: nums) {
                        auto const res = b.Get(x);
                        ASSERT_MSG(res && *res == y, "i " + std::to_string(i) + " x " + std::to_string(x) + " y " + std::to_string(y) + " res " + (res ? std::to_string(*res) : "null"));
                        ++i;
                    }
                }
            }
        }
        {
            auto b = CreateBTree();
            for (auto const & [x, y]: nums)
                b->Set({x, y});
            for (size_t it = 0; it < ntests; ++it) {
                auto tim = Time();
                for (auto const & [x, y]: nums) {
                    auto volatile res = b->Get(x);
                }
                tc = std::min(tc, Time() - tim);
                if (it == 0) {
                    size_t i = 0;
                    for (auto const & [x, y]: nums) {
                        auto const res = b->Get(x);
                        ASSERT_MSG(res && res->first == x && res->second == y,
                            "i " + std::to_string(i) + " x " + std::to_string(x) + " y " +
                            std::to_string(y) + " res.x " + (res ? std::to_string(res->second) : "null") +
                            " res.y " + (res ? std::to_string(res->second) : "null"));
                        ++i;
                    }
                }
            }
        }
        std::cout << std::fixed << "Find   Time HS " << std::setprecision(1) << std::setw(6) << (tb * 1'000'000'000 / nums.size())
            << " ns/num, BT " << std::setw(6) << (tc * 1000000000 / nums.size()) << " ns/num, UM " << std::setw(6)
            << (ta * 1'000'000'000 / nums.size()) << " ns/num, Boost HS " << std::setprecision(3) << (ta / tb)
            << "x, Boost BT " << std::setprecision(3) << (ta / tc) << "x " << std::endl;
    }
}

void GenData(std::string const & fname) {
    size_t constexpr nums_cnt = 1ULL << 14;
    std::ofstream f(fname);
    std::mt19937_64 rng{123}; //{std::random_device{}()};
    for (size_t i = 0; i < nums_cnt; ++i)
        f << (rng() % nums_cnt) << std::endl;
}

int main() {
    try {
        Test();
        
        std::string const fname = "test.txt";
        GenData(fname);
        Algo_HashSet(fname);
        Algo_Sort(fname);
        Algo_BTree(fname);
        
        return 0;
    } catch (std::exception const & ex) {
        std::cout << "Exception: " << ex.what() << std::endl;
        return -1;
    }
}