coordinate_compression.hpp¶

SECTIONUtility INCLUDEnoya/coordinate_compression.hpp

Sorted unique coordinates with exact rank and lower/upper-rank queries, plus bulk encoding and decoding.

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

Implementation¶

SourceExpanded

#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> values;

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

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

  int size() const { return int(values.size()); }
  int lower_rank(const T &value) const {
    return int(std::lower_bound(values.begin(), values.end(), value) -
               values.begin());
  }
  int upper_rank(const T &value) const {
    return int(std::upper_bound(values.begin(), values.end(), value) -
               values.begin());
  }
  int rank(const T &value) const {
    int result = lower_rank(value);
    assert(result < size() && values[result] == value);
    return result;
  }
  const T &operator[](int index) const {
    assert(0 <= index && index < size());
    return values[index];
  }
  std::vector<int> encode(const std::vector<T> &input) const {
    std::vector<int> result(input.size());
    for (int index = 0; index < int(input.size()); index++) {
      result[index] = rank(input[index]);
    }
    return result;
  }
};

} // 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> values;

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

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

  int size() const { return int(values.size()); }
  int lower_rank(const T &value) const {
    return int(std::lower_bound(values.begin(), values.end(), value) -
               values.begin());
  }
  int upper_rank(const T &value) const {
    return int(std::upper_bound(values.begin(), values.end(), value) -
               values.begin());
  }
  int rank(const T &value) const {
    int result = lower_rank(value);
    assert(result < size() && values[result] == value);
    return result;
  }
  const T &operator[](int index) const {
    assert(0 <= index && index < size());
    return values[index];
  }
  std::vector<int> encode(const std::vector<T> &input) const {
    std::vector<int> result(input.size());
    for (int index = 0; index < int(input.size()); index++) {
      result[index] = rank(input[index]);
    }
    return result;
  }
};

} // namespace noya