One-to-one mapping from a triangular array to a one-dimensional array (tools/triangular_array_compressor.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-06-08 00:56:00+09:00
• Include: #include "tools/triangular_array_compressor.hpp"

It is a one-to-one mapping $f: S \to T$ where $(S, T)$ is one of the following pairs.

• $S = \lbrace (i, j) \in \mathbb{N}^2 \mid 0 \leq i < j < n \rbrace, T = \left\lbrace k \in \mathbb{N} \mid 0 \leq k < \frac{n (n - 1)}{2} \right\rbrace$
• $S = \lbrace (i, j) \in \mathbb{N}^2 \mid 0 \leq i \leq j < n \rbrace, T = \left\lbrace k \in \mathbb{N} \mid 0 \leq k < \frac{n (n + 1)}{2} \right\rbrace$
• $S = \lbrace (i, j) \in \mathbb{N}^2 \mid 0 \leq j < i < n \rbrace, T = \left\lbrace k \in \mathbb{N} \mid 0 \leq k < \frac{n (n - 1)}{2} \right\rbrace$
• $S = \lbrace (i, j) \in \mathbb{N}^2 \mid 0 \leq j \leq i < n \rbrace, T = \left\lbrace k \in \mathbb{N} \mid 0 \leq k < \frac{n (n + 1)}{2} \right\rbrace$

License

• CC0

Author

• anqooqie

Constructor

triangular_array_compressor<Compare> f(int n);

It is a one-to-one mapping $f: S \to T$ where $S$ is $\lbrace (i, j) \in \mathbb{N}^2 \mid 0 \leq i < n \land 0 \leq j < n \land \mathrm{Compare}()(i, j) \rbrace$ and $T$ is $\left\lbrace k \in \mathbb{N} \mid 0 \leq k < |S| \right\rbrace$.

Constraints

• $n \geq 0$
• <Compare> is any one of std::less<int>, std::less_equal<int>, std::greater<int> or std::greater_equal<int>.

Time Complexity

• $O(1)$

size

int f.size();

It returns $n$.

Constraints

• None

Time Complexity

• $O(1)$

compress

int f.compress(int i, int j);

It returns $f(i, j)$.

Constraints

• $0 \leq i < n$
• $0 \leq j < n$
• Compare()(i, j)

Time Complexity

• $O(1)$

decompress

std::pair<int, int> f.decompress(int k);

It returns $f^{-1}(k)$.

Constraints

• (<Compare> is std::less<int> or std::greater<int>): $0 \leq k < \frac{n (n - 1)}{2}$
• (<Compare> is std::less_equal<int> or std::greater_equal<int>): $0 \leq k < \frac{n (n + 1)}{2}$

Time Complexity

• $O(1)$

Required by

• Triangular array (tools/triangular_array.hpp)

Verified with

• tests/triangular_array.test.cpp
• tests/triangular_array_compressor.test.cpp

Code

#ifndef TOOLS_TRIANGULAR_ARRAY_COMPRESSOR_HPP
#define TOOLS_TRIANGULAR_ARRAY_COMPRESSOR_HPP

#include <cassert>
#include <functional>
#include <utility>

namespace tools {
  template <typename Compare>
  class triangular_array_compressor;

  template <>
  class triangular_array_compressor<::std::less<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= i && i < j && j < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * (n - 1) - 1 : i * (n - 2) - 1) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n - 1) / 2);
      auto i = k / (n - 1);
      auto j = k % (n - 1);
      if (j < n - 1 - i) {
        j += i + 1;
      } else {
        i = n - 1 - i;
        ++j;
      }
      return {i, j};
    }
  };

  template <>
  class triangular_array_compressor<::std::less_equal<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= i && i <= j && j < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * (n + 1) + 1 : i * n) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n + 1) / 2);
      auto i = k / (n + 1);
      auto j = k % (n + 1);
      if (j < n - i) {
        j += i;
      } else {
        i = n - 1 - i;
        --j;
      }
      return {i, j};
    }
  };

  template <>
  class triangular_array_compressor<::std::greater<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= j && j < i && i < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * n : i * (n - 1)) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n - 1) / 2);
      auto i = k / (n - 1);
      auto j = k % (n - 1);
      if (i <= j) {
        j -= i;
        i = n - 1 - i;
      }
      return {i, j};
    }
  };

  template <>
  class triangular_array_compressor<::std::greater_equal<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= j && j <= i && i < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * (n + 1) + n - i : i * (n + 1)) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n + 1) / 2);
      auto i = k / (n + 1);
      auto j = k % (n + 1);
      if (i + 1 <= j) {
        j -= i + 1;
        i = n - 1 - i;
      }
      return {i, j};
    }
  };
}

#endif

#line 1 "tools/triangular_array_compressor.hpp"



#include <cassert>
#include <functional>
#include <utility>

namespace tools {
  template <typename Compare>
  class triangular_array_compressor;

  template <>
  class triangular_array_compressor<::std::less<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= i && i < j && j < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * (n - 1) - 1 : i * (n - 2) - 1) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n - 1) / 2);
      auto i = k / (n - 1);
      auto j = k % (n - 1);
      if (j < n - 1 - i) {
        j += i + 1;
      } else {
        i = n - 1 - i;
        ++j;
      }
      return {i, j};
    }
  };

  template <>
  class triangular_array_compressor<::std::less_equal<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= i && i <= j && j < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * (n + 1) + 1 : i * n) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n + 1) / 2);
      auto i = k / (n + 1);
      auto j = k % (n + 1);
      if (j < n - i) {
        j += i;
      } else {
        i = n - 1 - i;
        --j;
      }
      return {i, j};
    }
  };

  template <>
  class triangular_array_compressor<::std::greater<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= j && j < i && i < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * n : i * (n - 1)) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n - 1) / 2);
      auto i = k / (n - 1);
      auto j = k % (n - 1);
      if (i <= j) {
        j -= i;
        i = n - 1 - i;
      }
      return {i, j};
    }
  };

  template <>
  class triangular_array_compressor<::std::greater_equal<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= j && j <= i && i < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * (n + 1) + n - i : i * (n + 1)) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n + 1) / 2);
      auto i = k / (n + 1);
      auto j = k % (n + 1);
      if (i + 1 <= j) {
        j -= i + 1;
        i = n - 1 - i;
      }
      return {i, j};
    }
  };
}

Back to top page