other/coordinate_compression.hpp

• View this file on GitHub
• Last update: 2022-07-17 14:27:07+09:00
• Include: #include "other/coordinate_compression.hpp"

Verified with

• data_structure/test/range_kth_smallest.test.cpp

Code

#pragma once

#include <algorithm>
#include <vector>

template <typename T>
class CoordinateCompression {
    std::vector<T> data;

    int size_sum() {
        return 0;
    }

    template <typename... Tail>
    int size_sum(const std::vector<T> &head, const Tail &...tail) {
        return (int) head.size() + size_sum(tail...);
    }

    void push() {}

    template <typename... Tail>
    void push(const std::vector<T> &head, const Tail &...tail) {
        for (const T &ele : head) {
            data.emplace_back(ele);
        }
        push(tail...);
    }

    void compress() {}

    template <typename... Tail>
    void compress(std::vector<T> &head, Tail &...tail) {
        for (T &ele : head) {
            ele = (T) (std::lower_bound(data.begin(), data.end(), ele) - data.begin());
        }
        compress(tail...);
    }

public:
    template <typename... V>
    CoordinateCompression(V &...v) {
        data.reserve(size_sum(v...));
        push(v...);
        std::sort(data.begin(), data.end());
        data.erase(std::unique(data.begin(), data.end()), data.end());
        compress(v...);
    }

    const T &operator[](const T &ele) const {
        return data[ele];
    }

    int size() const {
        return data.size();
    }
    
    bool contains(const T &ele) const {
        auto it = std::lower_bound(data.begin(), data.end(), ele);
        return it != data.end() && *it == ele;
    }
    
    T cc(const T &ele) const {
        return (T) (std::lower_bound(data.begin(), data.end(), ele) - data.begin());
    }
};

#line 2 "other/coordinate_compression.hpp"

#include <algorithm>
#include <vector>

template <typename T>
class CoordinateCompression {
    std::vector<T> data;

    int size_sum() {
        return 0;
    }

    template <typename... Tail>
    int size_sum(const std::vector<T> &head, const Tail &...tail) {
        return (int) head.size() + size_sum(tail...);
    }

    void push() {}

    template <typename... Tail>
    void push(const std::vector<T> &head, const Tail &...tail) {
        for (const T &ele : head) {
            data.emplace_back(ele);
        }
        push(tail...);
    }

    void compress() {}

    template <typename... Tail>
    void compress(std::vector<T> &head, Tail &...tail) {
        for (T &ele : head) {
            ele = (T) (std::lower_bound(data.begin(), data.end(), ele) - data.begin());
        }
        compress(tail...);
    }

public:
    template <typename... V>
    CoordinateCompression(V &...v) {
        data.reserve(size_sum(v...));
        push(v...);
        std::sort(data.begin(), data.end());
        data.erase(std::unique(data.begin(), data.end()), data.end());
        compress(v...);
    }

    const T &operator[](const T &ele) const {
        return data[ele];
    }

    int size() const {
        return data.size();
    }
    
    bool contains(const T &ele) const {
        auto it = std::lower_bound(data.begin(), data.end(), ele);
        return it != data.end() && *it == ele;
    }
    
    T cc(const T &ele) const {
        return (T) (std::lower_bound(data.begin(), data.end(), ele) - data.begin());
    }
};

Back to top page