coordinate_compression.hpp¶

SECTIONUtility INCLUDEnoya/coordinate_compression.hpp

把任意可排序坐标映射到连续排名，并支持 lower/upper rank 与批量编码解码。

Complexity: Time: O(n log n) build and O(log n) rank queries. Space: O(n).

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n log n) build and O(log n) rank queries.
/// Space: O(n).

#include <algorithm>
#include <cassert>
#include <vector>

namespace noya {

/// @brief Sorted unique coordinates with exact rank and lower/upper-rank
/// queries, plus bulk encoding and decoding.
template <class T> struct coordinate_compression {
  std::vector<T> a;

  coordinate_compression() = default;
  explicit coordinate_compression(std::vector<T> arr) { build(std::move(arr)); }

  void build(std::vector<T> arr) {
    a = std::move(arr);
    std::sort(a.begin(), a.end());
    a.erase(std::unique(a.begin(), a.end()), a.end());
  }

  int size() const { return int(a.size()); }
  int lower_rank(const T &val) const {
    return int(std::lower_bound(a.begin(), a.end(), val) - a.begin());
  }
  int upper_rank(const T &val) const {
    return int(std::upper_bound(a.begin(), a.end(), val) - a.begin());
  }
  int rank(const T &val) const {
    int res = lower_rank(val);
    assert(res < size() && a[res] == val);
    return res;
  }
  const T &operator[](int idx) const {
    assert(0 <= idx && idx < size());
    return a[idx];
  }
  std::vector<int> encode(const std::vector<T> &arr) const {
    std::vector<int> res(arr.size());
    for (int idx = 0; idx < int(arr.size()); idx++) {
      res[idx] = rank(arr[idx]);
    }
    return res;
  }
};

} // namespace noya

#ifndef NOYA_COORDINATE_COMPRESSION_HPP
#define NOYA_COORDINATE_COMPRESSION_HPP 1

/// @complexity Time: O(n log n) build and O(log n) rank queries.
/// Space: O(n).

#include <algorithm>
#include <cassert>
#include <vector>

namespace noya {

/// @brief Sorted unique coordinates with exact rank and lower/upper-rank
/// queries, plus bulk encoding and decoding.
template <class T> struct coordinate_compression {
  std::vector<T> a;

  coordinate_compression() = default;
  explicit coordinate_compression(std::vector<T> arr) { build(std::move(arr)); }

  void build(std::vector<T> arr) {
    a = std::move(arr);
    std::sort(a.begin(), a.end());
    a.erase(std::unique(a.begin(), a.end()), a.end());
  }

  int size() const { return int(a.size()); }
  int lower_rank(const T &val) const {
    return int(std::lower_bound(a.begin(), a.end(), val) - a.begin());
  }
  int upper_rank(const T &val) const {
    return int(std::upper_bound(a.begin(), a.end(), val) - a.begin());
  }
  int rank(const T &val) const {
    int res = lower_rank(val);
    assert(res < size() && a[res] == val);
    return res;
  }
  const T &operator[](int idx) const {
    assert(0 <= idx && idx < size());
    return a[idx];
  }
  std::vector<int> encode(const std::vector<T> &arr) const {
    std::vector<int> res(arr.size());
    for (int idx = 0; idx < int(arr.size()); idx++) {
      res[idx] = rank(arr[idx]);
    }
    return res;
  }
};

} // namespace noya

#endif // NOYA_COORDINATE_COMPRESSION_HPP

#include <algorithm>
#include <cassert>
#include <vector>

/// @complexity Time: O(n log n) build and O(log n) rank queries.
/// Space: O(n).

namespace noya {

/// @brief Sorted unique coordinates with exact rank and lower/upper-rank
/// queries, plus bulk encoding and decoding.
template <class T> struct coordinate_compression {
  std::vector<T> a;

  coordinate_compression() = default;
  explicit coordinate_compression(std::vector<T> arr) { build(std::move(arr)); }

  void build(std::vector<T> arr) {
    a = std::move(arr);
    std::sort(a.begin(), a.end());
    a.erase(std::unique(a.begin(), a.end()), a.end());
  }

  int size() const { return int(a.size()); }
  int lower_rank(const T &val) const {
    return int(std::lower_bound(a.begin(), a.end(), val) - a.begin());
  }
  int upper_rank(const T &val) const {
    return int(std::upper_bound(a.begin(), a.end(), val) - a.begin());
  }
  int rank(const T &val) const {
    int res = lower_rank(val);
    assert(res < size() && a[res] == val);
    return res;
  }
  const T &operator[](int idx) const {
    assert(0 <= idx && idx < size());
    return a[idx];
  }
  std::vector<int> encode(const std::vector<T> &arr) const {
    std::vector<int> res(arr.size());
    for (int idx = 0; idx < int(arr.size()); idx++) {
      res[idx] = rank(arr[idx]);
    }
    return res;
  }
};

} // namespace noya