tests/compressor.test.cpp

View this file on GitHub
Last update: 2025-07-13 12:55:38+09:00

Depends on

Code

// competitive-verifier: STANDALONE

#include <iostream>
#include <ranges>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/compressor.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  {
    tools::compressor<int> cp(std::vector<int>{3, -1, 2, 2});
    assert_that(cp.size() == 3);
    assert_that(cp.compress(-1) == 0);
    assert_that(cp.compress(2) == 1);
    assert_that(cp.compress(3) == 2);
    assert_that(cp.decompress(0) == -1);
    assert_that(cp.decompress(1) == 2);
    assert_that(cp.decompress(2) == 3);
    assert_that(cp.contains(-1));
    assert_that(!cp.contains(0));
    assert_that(!cp.contains(1));
    assert_that(cp.contains(2));
    assert_that(cp.contains(3));
    assert_that(!cp.contains(4));
    assert_that(std::distance(cp.begin(), cp.end()) == 3);
    assert_that(cp.begin()[0] == -1);
    assert_that(cp.begin()[1] == 2);
    assert_that(cp.begin()[2] == 3);
  }
  {
    tools::compressor<int> cp(std::vector<int>{});
    assert_that(cp.size() == 0);
    assert_that(!cp.contains(0));
    assert_that(!cp.contains(1));
    assert_that(std::distance(cp.begin(), cp.end()) == 0);
  }
  {
    tools::compressor<int> cp(std::views::iota(0, 200000));
    assert_that(cp.size() == 200000);
    for (int i = 0; i < 200000; ++i) {
      assert_that(cp.compress(i) == i);
      assert_that(cp.decompress(i) == i);
      assert_that(cp.contains(i));
    }
  }

  return 0;
}

#line 1 "tests/compressor.test.cpp"
// competitive-verifier: STANDALONE

#include <iostream>
#include <ranges>
#include <vector>
#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    ::std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    ::std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/compressor.hpp"



#include <algorithm>
#include <cassert>
#line 1 "tools/lower_bound.hpp"



#line 5 "tools/lower_bound.hpp"
#include <functional>
#include <iterator>
#line 8 "tools/lower_bound.hpp"

namespace tools {

  template <
    ::std::random_access_iterator I,
    ::std::sentinel_for<I> S,
    typename Proj = ::std::identity,
    typename T = ::std::remove_cvref_t<::std::invoke_result_t<Proj&, ::std::iter_value_t<I>&>>,
    ::std::indirect_strict_weak_order<const T*, ::std::projected<I, Proj>> Comp = ::std::ranges::less
  >
  constexpr ::std::iter_difference_t<I> lower_bound(const I first, const S last, const T& value, const Comp comp = {}, const Proj proj = {}) {
    return ::std::ranges::distance(first, ::std::ranges::lower_bound(first, last, value, comp, proj));
  }

  template <
    ::std::ranges::random_access_range R,
    typename Proj = ::std::identity,
    typename T = ::std::remove_cvref_t<::std::invoke_result_t<Proj&, ::std::ranges::range_value_t<R>&>>,
    ::std::indirect_strict_weak_order<const T*, ::std::projected<::std::ranges::iterator_t<R>, Proj>> Comp = ::std::ranges::less
  >
  constexpr ::std::ranges::range_difference_t<R> lower_bound(R&& r, const T& value, const Comp comp = {}, const Proj proj = {}) {
    return ::std::ranges::distance(::std::ranges::begin(r), ::std::ranges::lower_bound(r, value, comp, proj));
  }
}


#line 9 "tools/compressor.hpp"

namespace tools {
  template <typename T>
  class compressor {
    ::std::vector<T> m_sorted;

  public:
    compressor() = default;
    template <typename InputIterator>
    compressor(const InputIterator begin, const InputIterator end) : m_sorted(begin, end) {
      ::std::ranges::sort(this->m_sorted);
      this->m_sorted.erase(::std::unique(this->m_sorted.begin(), this->m_sorted.end()), this->m_sorted.end());
    }
    template <::std::ranges::range R>
    explicit compressor(R&& range) : compressor(::std::ranges::begin(range), ::std::ranges::end(range)) {
    }

    T size() const {
      return this->m_sorted.size();
    }
    T compress(const T& x) const {
      const T i = ::tools::lower_bound(this->m_sorted, x);
      assert(i < this->size());
      assert(this->m_sorted[i] == x);
      return i;
    }
    T decompress(const T& i) const {
      assert(0 <= i && i < this->size());
      return this->m_sorted[i];
    }
    bool contains(const T& x) const {
      const auto it = ::std::ranges::lower_bound(this->m_sorted, x);
      return it != this->m_sorted.end() && *it == x;
    }

    typename ::std::vector<T>::const_iterator begin() const {
      return this->m_sorted.begin();
    }
    typename ::std::vector<T>::const_iterator end() const {
      return this->m_sorted.end();
    }
  };
}


#line 8 "tests/compressor.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  {
    tools::compressor<int> cp(std::vector<int>{3, -1, 2, 2});
    assert_that(cp.size() == 3);
    assert_that(cp.compress(-1) == 0);
    assert_that(cp.compress(2) == 1);
    assert_that(cp.compress(3) == 2);
    assert_that(cp.decompress(0) == -1);
    assert_that(cp.decompress(1) == 2);
    assert_that(cp.decompress(2) == 3);
    assert_that(cp.contains(-1));
    assert_that(!cp.contains(0));
    assert_that(!cp.contains(1));
    assert_that(cp.contains(2));
    assert_that(cp.contains(3));
    assert_that(!cp.contains(4));
    assert_that(std::distance(cp.begin(), cp.end()) == 3);
    assert_that(cp.begin()[0] == -1);
    assert_that(cp.begin()[1] == 2);
    assert_that(cp.begin()[2] == 3);
  }
  {
    tools::compressor<int> cp(std::vector<int>{});
    assert_that(cp.size() == 0);
    assert_that(!cp.contains(0));
    assert_that(!cp.contains(1));
    assert_that(std::distance(cp.begin(), cp.end()) == 0);
  }
  {
    tools::compressor<int> cp(std::views::iota(0, 200000));
    assert_that(cp.size() == 200000);
    for (int i = 0; i < 200000; ++i) {
      assert_that(cp.compress(i) == i);
      assert_that(cp.decompress(i) == i);
      assert_that(cp.contains(i));
    }
  }

  return 0;
}