Coordinate Compression
(misc/compress.hpp)

• View this file on GitHub
• Last update: 2024-01-08 16:33:05+09:00
• Include: #include "misc/compress.hpp"

Verified with

• test/yosupo/point_add_rectangle_sum.quadtree.test.cpp
• test/yosupo/rectangle_sum.persistent_segment_tree.test.cpp
• test/yosupo/rooted_tree_isomorphism_classification.hash.test.cpp
• test/yosupo/static_range_inversions_query.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>

/**
 * @brief Coordinate Compression
 */
template <typename T>
class Compress {
   public:
    Compress() = default;
    explicit Compress(const std::vector<T>& vs) : xs(vs) {
        std::ranges::sort(xs);
        xs.erase(std::ranges::unique(xs).begin(), xs.end());
    }

    int compress(const T& x) const {
        return std::ranges::lower_bound(xs, x) - xs.begin();
    }

    std::vector<int> compress(const std::vector<T>& vs) const {
        std::vector<int> res(vs.size());
        std::ranges::transform(vs, res.begin(),
                               [&](const T& x) { return compress(x); });
        return res;
    }

    T decompress(int i) const { return xs[i]; }

    int size() const { return xs.size(); }

   private:
    std::vector<T> xs;
};

#line 2 "misc/compress.hpp"
#include <algorithm>
#include <vector>

/**
 * @brief Coordinate Compression
 */
template <typename T>
class Compress {
   public:
    Compress() = default;
    explicit Compress(const std::vector<T>& vs) : xs(vs) {
        std::ranges::sort(xs);
        xs.erase(std::ranges::unique(xs).begin(), xs.end());
    }

    int compress(const T& x) const {
        return std::ranges::lower_bound(xs, x) - xs.begin();
    }

    std::vector<int> compress(const std::vector<T>& vs) const {
        std::vector<int> res(vs.size());
        std::ranges::transform(vs, res.begin(),
                               [&](const T& x) { return compress(x); });
        return res;
    }

    T decompress(int i) const { return xs[i]; }

    int size() const { return xs.size(); }

   private:
    std::vector<T> xs;
};

Back to top page