座標圧縮
(src/sequence/compression.hpp)

View this file on GitHub
Last update: 2023-07-30 00:54:52+09:00
Include: #include "src/sequence/compression.hpp"

コンストラクタ

Compressor<T, Compare>(std::vector<T> vs)

引数で与えられた vector を 0-indexed で座標圧縮する。

簡単のため、以下では与えられた vector のサイズを $n$ とし、重複を除いた要素数を $m$ とする。

Compare について

Compare にはデフォルトで std::less が与えられている。

内部的に std::sort を用いているため、Compare は狭義の弱順序を満たす必要がある。狭義の弱順序とは以下の性質をすべて満たすものである。

任意の a について not (a < a)
a < b ならば not (b < a)
a < b かつ b < c ならば a < c

座標圧縮後の要素 a, b の a < b の結果と Compare()(a, b) の結果は一致するようになっている。

計算量

Compare() を $O(1)$ として $O(n \log n)$

compressed_vector

std::vector< usize > compressed_vector() const

コンストラクタに与えられた vector を座標圧縮した結果を返す。

計算量

$O(n)$

compress

usize compress(T v) const

座標圧縮の結果、$v$ がどこに mapping されたかを再計算して返す。

制約

$v$ はコンストラクタに与えられた vector の要素である。

計算量

$O(\log n)$

expand

T expand(usize i) const

$i$ に対応する座標圧縮前の要素を返す。

制約

$0 \leq i \lt m$

計算量

$O(1)$

Depends on

Required by

src/geometry/Z2/segment-function/counterbalance-segments.hpp

Verified with

Code

#pragma once

#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"

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

namespace luz {

  template < class T, class Compare = std::less< T > >
  class Compressor {
    std::vector< T > vs;
    std::vector< T > zip;
    std::vector< usize > ziped_vs;

   public:
    explicit Compressor(std::vector< T > vs)
        : vs(vs),
          zip(vs),
          ziped_vs(vs.size()) {
      std::sort(zip.begin(), zip.end(), Compare());
      zip.erase(std::unique(zip.begin(), zip.end()), zip.end());
      for (usize i: rep(0, vs.size())) {
        ziped_vs[i] = compress(vs[i]);
      }
    }

    std::vector< usize > compressed_vector() const {
      return ziped_vs;
    }

    usize compress(T v) const {
      auto iter = std::lower_bound(zip.begin(), zip.end(), v);
      assert(*iter == v);
      return iter - zip.begin();
    }

    T expand(usize i) const {
      assert(i < zip.size());
      return zip[i];
    }
  };

} // namespace luz

#line 2 "src/sequence/compression.hpp"

#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 5 "src/sequence/compression.hpp"

#line 7 "src/sequence/compression.hpp"
#include <cassert>
#include <functional>
#include <vector>

namespace luz {

  template < class T, class Compare = std::less< T > >
  class Compressor {
    std::vector< T > vs;
    std::vector< T > zip;
    std::vector< usize > ziped_vs;

   public:
    explicit Compressor(std::vector< T > vs)
        : vs(vs),
          zip(vs),
          ziped_vs(vs.size()) {
      std::sort(zip.begin(), zip.end(), Compare());
      zip.erase(std::unique(zip.begin(), zip.end()), zip.end());
      for (usize i: rep(0, vs.size())) {
        ziped_vs[i] = compress(vs[i]);
      }
    }

    std::vector< usize > compressed_vector() const {
      return ziped_vs;
    }

    usize compress(T v) const {
      auto iter = std::lower_bound(zip.begin(), zip.end(), v);
      assert(*iter == v);
      return iter - zip.begin();
    }

    T expand(usize i) const {
      assert(i < zip.size());
      return zip[i];
    }
  };

} // namespace luz

座標圧縮 (src/sequence/compression.hpp)