cp-algo/util/compress_coords.hpp

View this file on GitHub
Last update: 2024-11-15 00:01:35+01:00
Include: #include "cp-algo/util/compress_coords.hpp"

Depends on

Verified with

Ordered Set (verify/structures/fenwick/ordered_set.test.cpp)

Code

#ifndef CP_ALGO_UTIL_COMPRESS_COORDS_HPP
#define CP_ALGO_UTIL_COMPRESS_COORDS_HPP
#include "sort.hpp"
#include <vector>
namespace cp_algo {
    // coords is a range of reference_wrapper<T>
    auto compress_coords(auto &coords) {
        using T = std::decay_t<std::unwrap_reference_t<
            std::ranges::range_value_t<decltype(coords)>
        >>;
        std::vector<T> original;
        if(empty(coords)) {
            return original;
        }
        original.reserve(size(coords));
        radix_sort(coords);
        size_t idx = -1;
        T prev = ~coords.front();
        for(auto &x: coords) {
            if(x != prev) {
                idx++;
                prev = x;
                original.push_back(x);
            }
            x.get() = idx;
        }
        return original;
    }
}
#endif // CP_ALGO_UTIL_COMPRESS_COORDS_HPP

#line 1 "cp-algo/util/compress_coords.hpp"


#line 1 "cp-algo/util/sort.hpp"


#line 1 "cp-algo/util/bit.hpp"


#include <immintrin.h>
#include <cstdint>
#include <array>
#include <bit>
namespace cp_algo {
    template<typename Uint>
    constexpr size_t bit_width = sizeof(Uint) * 8;

    size_t order_of_bit(auto x, size_t k) {
        return k ? std::popcount(x << (bit_width<decltype(x)> - k)) : 0;
    }
    [[gnu::target("bmi2")]]
    size_t kth_set_bit(uint64_t x, size_t k) {
        return std::countr_zero(_pdep_u64(1ULL << k, x));
    }
    template<int fl = 0>
    void with_bit_floor(size_t n, auto &&callback) {
        if constexpr (fl >= 63) {
            return;
        } else if (n >> (fl + 1)) {
            with_bit_floor<fl + 1>(n, callback);
        } else {
            callback.template operator()<1ULL << fl>();
        }
    }
}

#line 4 "cp-algo/util/sort.hpp"
#include <algorithm>
#include <numeric>
#include <ranges>
#include <vector>
namespace cp_algo {
    template<size_t maxc>
    void count_sort(auto &a, auto &&proj = std::identity{}) {
        std::array<int, maxc> cnt = {};
        for(auto &x: a) {
            cnt[proj(x)]++;
        }
        std::partial_sum(begin(cnt), end(cnt), begin(cnt));
        auto res = a;
        for(auto const& it: a | std::views::reverse) {
            res[--cnt[proj(it)]] = it;
        }
        a = std::move(res);
    }

    void radix_sort(auto &a) {
        if(empty(a)) {
            return;
        }
        auto [mn, mx] = std::ranges::minmax(a);
        with_bit_floor<1>(size(a), [&]<size_t floor>() {
            constexpr int base = std::min<size_t>(floor, 1 << 16);
            for(int64_t i = 1; i <= mx - mn; i *= base) {
                count_sort<base>(a, [&](auto x) {
                    return (x - mn) / i % base;
                });
            }
        });
    }
}

#line 5 "cp-algo/util/compress_coords.hpp"
namespace cp_algo {
    // coords is a range of reference_wrapper<T>
    auto compress_coords(auto &coords) {
        using T = std::decay_t<std::unwrap_reference_t<
            std::ranges::range_value_t<decltype(coords)>
        >>;
        std::vector<T> original;
        if(empty(coords)) {
            return original;
        }
        original.reserve(size(coords));
        radix_sort(coords);
        size_t idx = -1;
        T prev = ~coords.front();
        for(auto &x: coords) {
            if(x != prev) {
                idx++;
                prev = x;
                original.push_back(x);
            }
            x.get() = idx;
        }
        return original;
    }
}