compression
(misc/compression.cpp)

• View this file on GitHub
• Last update: 2024-04-05 18:02:52+08:00

An std-like coordinate compression template

about some usage cases of projection, see misc/rectangleSum.cpp

usage

constructors

• compression(vector<T> &init) initialize with coordinates in init
• compression(int size = 0) reserve space for later addition of coordinates, after finishing inserting coordinate, call precompute()

member functions

• void precompute() do coordinate compression and store result in ord and val
• int lower_bound(T x) find # of coordinates less than $x$
• int size() return # of coordinates
• void mapping(rng &v, proj p = {}) replace coordinates in a range v with its compressed coordinates, projection is allowed to used so you can do e.g. mapping a certain entry of a vector<array<T, sz>>
• void insert(rng &v, proj p = {}) insert coordinates in a range v, projection is allowed to used so you can do e.g. inserting certain entry of a vector<array<T, sz>>

Verified with

• test/point_add_rectangle_sum.test.cpp
• test/range_kth_smallest.test.cpp
• test/range_kth_smallest2.test.cpp
• test/rectangle_add_point_get.test.cpp
• test/rectangle_sum.test.cpp
• test/static_range_count_distinct.test.cpp
• test/static_range_frequency.test.cpp

Code

template<class T, bool duplicate = false>
struct compression {
  vector<int> ord;
  vector<T> val;

  compression(vector<T> &init) : val(init) { precompute(); }
  compression(int size = 0) { val.reserve(size); }

  void precompute() {
    vector<T> init = val;
    ord.resize(ssize(val));
    ranges::sort(val);
    if constexpr (duplicate) {
      vector<int> cnt(ssize(init));
      iota(cnt.begin(), cnt.end(), 0);
      for(int i = 0; i < ssize(ord); i++)
        ord[i] = cnt[lower_bound(init[i])]++;
    } else {
      val.resize(unique(val.begin(), val.end()) - val.begin());
      for(int i = 0; i < ssize(ord); i++)
        ord[i] = lower_bound(init[i]);
    }
  }

  int lower_bound(T x) { return ranges::lower_bound(val, x) - val.begin(); }
  int size() { return ssize(val); }
  template<ranges::range rng, class proj = identity>
  void mapping(rng &v, proj p = {}) { for(auto &x : v) p(x) = lower_bound(p(x)); }
  template<ranges::range rng, class proj = identity>
  void insert(rng &v, proj p = {}) { for(auto &x : v) val.emplace_back(p(x)); }
};

#line 1 "misc/compression.cpp"
template<class T, bool duplicate = false>
struct compression {
  vector<int> ord;
  vector<T> val;

  compression(vector<T> &init) : val(init) { precompute(); }
  compression(int size = 0) { val.reserve(size); }

  void precompute() {
    vector<T> init = val;
    ord.resize(ssize(val));
    ranges::sort(val);
    if constexpr (duplicate) {
      vector<int> cnt(ssize(init));
      iota(cnt.begin(), cnt.end(), 0);
      for(int i = 0; i < ssize(ord); i++)
        ord[i] = cnt[lower_bound(init[i])]++;
    } else {
      val.resize(unique(val.begin(), val.end()) - val.begin());
      for(int i = 0; i < ssize(ord); i++)
        ord[i] = lower_bound(init[i]);
    }
  }

  int lower_bound(T x) { return ranges::lower_bound(val, x) - val.begin(); }
  int size() { return ssize(val); }
  template<ranges::range rng, class proj = identity>
  void mapping(rng &v, proj p = {}) { for(auto &x : v) p(x) = lower_bound(p(x)); }
  template<ranges::range rng, class proj = identity>
  void insert(rng &v, proj p = {}) { for(auto &x : v) val.emplace_back(p(x)); }
};

Back to top page