Compress values (for more complicated cases) (tools/compressor.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-02-18 13:45:51+09:00
• Include: #include "tools/compressor.hpp"

It provides the mapping which maps the $i$-th ($0$-indexed) least integer in a given integer set to $i$, and the inverse mapping of it.

License

• CC0

Author

• anqooqie

Constructor

(1)
template <typename InputIterator>
compressor<T> cp(InputIterator begin, InputIterator end);

(2)
compressor<T> cp(std::vector<T> v);

It creates an integer set initialized with a given integer container.

Constraints

• (1)
  • begin $\leq$ end

Time Complexity

• (1)
  • $O(n \log n)$ where $n$ is end $-$ begin
• (2)
  • $O(n \log n)$ where $n$ is v.size()

size

T cp.size();

It returns the number of distinct integers in the set.

Constraints

• None

Time Complexity

• $O(1)$

compress

T cp.compress(T x);

It returns $i$ such that the $i$-th ($0$-indexed) least integer in the set is $x$.

Constraints

• The set contains $x$.

Time Complexity

• $O(\log n)$ where $n$ is cp.size()

decompress

T cp.decompress(T i);

It returns the $i$-th ($0$-indexed) least integer in the set.

Constraints

• $0 \leq i < $ cp.size()

Time Complexity

• $O(1)$

begin

typename std::vector<T>::const_iterator cp.begin();

It returns the iterator pointing to the least integer in the set.

Constraints

• None

Time Complexity

• $O(1)$

end

typename std::vector<T>::const_iterator cp.end();

It returns the iterator pointing to the integer which would follow the largest integer in the set.

Constraints

• None

Time Complexity

• $O(1)$

Depends on

• std::lower_bound, but returns index (tools/lower_bound.hpp)

Required by

• Area of union of rectangles (tools/rectangle_union_area.hpp)

Verified with

• tests/rectangle_union_area.test.cpp

Code

#ifndef TOOLS_COMPRESSOR_HPP
#define TOOLS_COMPRESSOR_HPP

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

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

  public:
    compressor() = default;
    compressor(const ::tools::compressor<T>&) = default;
    compressor(::tools::compressor<T>&&) = default;
    ~compressor() = default;
    ::tools::compressor<T>& operator=(const ::tools::compressor<T>&) = default;
    ::tools::compressor<T>& operator=(::tools::compressor<T>&&) = default;

    template <typename InputIterator>
    compressor(InputIterator begin, InputIterator end) : m_sorted(begin, end) {
      ::std::sort(this->m_sorted.begin(), this->m_sorted.end());
      this->m_sorted.erase(::std::unique(this->m_sorted.begin(), this->m_sorted.end()), this->m_sorted.end());
    }
    explicit compressor(const ::std::vector<T>& v) : compressor(v.begin(), v.end()) {
    }

    T size() const {
      return this->m_sorted.size();
    }
    T compress(const T& x) const {
      const T i = ::tools::lower_bound(this->m_sorted.begin(), this->m_sorted.end(), 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];
    }

    auto begin() {
      return this->m_sorted.cbegin();
    }
    auto begin() const {
      return this->m_sorted.cbegin();
    }
    auto end() {
      return this->m_sorted.cend();
    }
    auto end() const {
      return this->m_sorted.cend();
    }
  };
}

#endif

#line 1 "tools/compressor.hpp"



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



#include <iterator>
#line 6 "tools/lower_bound.hpp"

namespace tools {

  template <class ForwardIterator, class T>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value) {
    return ::std::distance(first, ::std::lower_bound(first, last, value));
  }

  template <class ForwardIterator, class T, class Compare>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) {
    return ::std::distance(first, ::std::lower_bound(first, last, value, comp));
  }
}


#line 8 "tools/compressor.hpp"

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

  public:
    compressor() = default;
    compressor(const ::tools::compressor<T>&) = default;
    compressor(::tools::compressor<T>&&) = default;
    ~compressor() = default;
    ::tools::compressor<T>& operator=(const ::tools::compressor<T>&) = default;
    ::tools::compressor<T>& operator=(::tools::compressor<T>&&) = default;

    template <typename InputIterator>
    compressor(InputIterator begin, InputIterator end) : m_sorted(begin, end) {
      ::std::sort(this->m_sorted.begin(), this->m_sorted.end());
      this->m_sorted.erase(::std::unique(this->m_sorted.begin(), this->m_sorted.end()), this->m_sorted.end());
    }
    explicit compressor(const ::std::vector<T>& v) : compressor(v.begin(), v.end()) {
    }

    T size() const {
      return this->m_sorted.size();
    }
    T compress(const T& x) const {
      const T i = ::tools::lower_bound(this->m_sorted.begin(), this->m_sorted.end(), 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];
    }

    auto begin() {
      return this->m_sorted.cbegin();
    }
    auto begin() const {
      return this->m_sorted.cbegin();
    }
    auto end() {
      return this->m_sorted.cend();
    }
    auto end() const {
      return this->m_sorted.cend();
    }
  };
}

Back to top page