$\mathbb{Z} \cup \{\infty, -\infty, \mathrm{NaN}\}$ and $\mathbb{Z}_{\geq 0} \cup \{\infty, \mathrm{NaN}\}$ (tools/safe_int.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-07-02 15:32:40+09:00
• Include: #include "tools/safe_int.hpp"

Given a signed integral type <T>, it adds the three special elements $\infty$, $-\infty$ and $\mathrm{NaN}$ to <T>. Given an unsigned integral type <T>, it adds the two special elements $\infty$ and $\mathrm{NaN}$ to <T>. If an arithmetic operation on finite integers causes overflow, the arithmetic operation will return $\mathrm{NaN}$.

References

• INT32-C. 符号付き整数演算がオーバーフローを引き起こさないことを保証する

License

• CC0

Author

• anqooqie

infinity

tools::safe_int<T> tools::safe_int<T>::infinity();

It returns $\infty$.

Constraints

• None

Time Complexity

• $O(1)$

nan

tools::safe_int<T> tools::safe_int<T>::nan();

It returns $\mathrm{NaN}$.

Constraints

• None

Time Complexity

• $O(1)$

Constructor

(1) tools::safe_int<T> x();
(2) tools::safe_int<T> x(T n);

• (1)
  • It creates $0$.
• (2)
  • It creates the finite integer value which represents $n$.

Constraints

• <T> is a built-in integral type.

Time Complexity

• $O(1)$

is_finite

bool x.is_finite();

It returns true if $x \in \mathbb{Z}$. Otherwise, it returns false.

Constraints

• None

Time Complexity

• $O(1)$

is_nan

bool x.is_nan();

It returns true if $x = \mathrm{NaN}$. Otherwise, it returns false.

Constraints

• None

Time Complexity

• $O(1)$

val

T x.val();

It returns $x$ as <T>.

Constraints

• $x \in \mathbb{Z}$

Time Complexity

• $O(1)$

+x

tools::safe_int<T> +x;

It returns $x$.

Constraints

• None

Time Complexity

• $O(1)$

-x

tools::safe_int<T> -x;

If <T> is a signed integral type, it returns

\[\begin{align*} \left\{\begin{array}{ll} -x & \text{(if $x \in \mathbb{Z}$ and $-x$ does not cause an overflow)}\\ \mathrm{NaN} & \text{(if $x \in \mathbb{Z}$ and $-x$ causes an overflow)}\\ -\infty & \text{(if $x = \infty$)}\\ \infty & \text{(if $x = -\infty$)}\\ \mathrm{NaN} & \text{(if $x = \mathrm{NaN}$)} \end{array}\right.& \end{align*}\]

If <T> is an unsigned integral type, it returns

\[\begin{align*} \left\{\begin{array}{ll} 0 & \text{(if $x = 0$)}\\ \mathrm{NaN} & \text{(if $x > 0$)}\\ \mathrm{NaN} & \text{(if $x = \infty$)}\\ \mathrm{NaN} & \text{(if $x = \mathrm{NaN}$)} \end{array}\right.& \end{align*}\]

Constraints

• None

Time Complexity

• $O(1)$

x + y

tools::safe_int<T> x + y;

If <T> is a signed integral type, the return value is as follows.

$x \backslash y$	$-\infty$	$\mathbb{Z}$	$\infty$	$\mathrm{NaN}$
$-\infty$	$-\infty$	$-\infty$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathbb{Z}$	$-\infty$	(see below)	$\infty$	$\mathrm{NaN}$
$\infty$	$\mathrm{NaN}$	$\infty$	$\infty$	$\mathrm{NaN}$
$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$

If <T> is an unsigned integral type, the return value is as follows.

$x \backslash y$	$\mathbb{Z}_{\geq 0}$	$\infty$	$\mathrm{NaN}$
$\mathbb{Z}_{\geq 0}$	(see below)	$\infty$	$\mathrm{NaN}$
$\infty$	$\infty$	$\infty$	$\mathrm{NaN}$
$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$

If $x \in \mathbb{Z}$ and $y \in \mathbb{Z}$, it returns

\[\begin{align*} \left\{\begin{array}{ll} x + y & \text{(if $x + y$ does not cause an overflow)}\\ \mathrm{NaN} & \text{(if $x + y$ causes an overflow)} \end{array}\right.& \end{align*}\]

Constraints

• None

Time Complexity

• $O(1)$

x - y

tools::safe_int<T> x - y;

If <T> is a signed integral type, the return value is as follows.

$x \backslash y$	$-\infty$	$\mathbb{Z}$	$\infty$	$\mathrm{NaN}$
$-\infty$	$\mathrm{NaN}$	$-\infty$	$-\infty$	$\mathrm{NaN}$
$\mathbb{Z}$	$\infty$	(see below)	$-\infty$	$\mathrm{NaN}$
$\infty$	$\infty$	$\infty$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$

If <T> is an unsigned integral type, the return value is as follows.

$x \backslash y$	$\mathbb{Z}_{\geq 0}$	$\infty$	$\mathrm{NaN}$
$\mathbb{Z}_{\geq 0}$	(see below)	$\mathrm{NaN}$	$\mathrm{NaN}$
$\infty$	$\infty$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$

If $x \in \mathbb{Z}$ and $y \in \mathbb{Z}$, it returns

\[\begin{align*} \left\{\begin{array}{ll} x - y & \text{(if $x - y$ does not cause an overflow)}\\ \mathrm{NaN} & \text{(if $x - y$ causes an overflow)} \end{array}\right.& \end{align*}\]

Constraints

• None

Time Complexity

• $O(1)$

x * y

tools::safe_int<T> x * y;

If <T> is a signed integral type, the return value is as follows.

$x \backslash y$	$-\infty$	$\mathbb{Z}_{<0}$	$0$	$\mathbb{Z}_{>0}$	$\infty$	$\mathrm{NaN}$
$-\infty$	$\infty$	$\infty$	$\mathrm{NaN}$	$-\infty$	$-\infty$	$\mathrm{NaN}$
$\mathbb{Z}_{<0}$	$\infty$	(see below)	$0$	(see below)	$-\infty$	$\mathrm{NaN}$
$0$	$\mathrm{NaN}$	$0$	$0$	$0$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathbb{Z}_{>0}$	$-\infty$	(see below)	$0$	(see below)	$\infty$	$\mathrm{NaN}$
$\infty$	$-\infty$	$-\infty$	$\mathrm{NaN}$	$\infty$	$\infty$	$\mathrm{NaN}$
$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$

If <T> is an unsigned integral type, the return value is as follows.

$x \backslash y$	$0$	$\mathbb{Z}_{>0}$	$\infty$	$\mathrm{NaN}$
$0$	$0$	$0$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathbb{Z}_{>0}$	$0$	(see below)	$\infty$	$\mathrm{NaN}$
$\infty$	$\mathrm{NaN}$	$\infty$	$\infty$	$\mathrm{NaN}$
$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$

If $x \in \mathbb{Z}$ and $y \in \mathbb{Z}$, it returns

\[\begin{align*} \left\{\begin{array}{ll} xy & \text{(if $xy$ does not cause an overflow)}\\ \mathrm{NaN} & \text{(if $xy$ causes an overflow)} \end{array}\right.& \end{align*}\]

Constraints

• None

Time Complexity

• $O(1)$

x / y

tools::safe_int<T> x / y;

If <T> is a signed integral type, the return value is as follows.

$x \backslash y$	$-\infty$	$\mathbb{Z}_{<0}$	$0$	$\mathbb{Z}_{>0}$	$\infty$	$\mathrm{NaN}$
$-\infty$	$\mathrm{NaN}$	$\infty$	$\mathrm{NaN}$	$-\infty$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathbb{Z}_{<0}$	$0$	(see below)	$\mathrm{NaN}$	(see below)	$0$	$\mathrm{NaN}$
$0$	$0$	$0$	$\mathrm{NaN}$	$0$	$0$	$\mathrm{NaN}$
$\mathbb{Z}_{>0}$	$0$	(see below)	$\mathrm{NaN}$	(see below)	$0$	$\mathrm{NaN}$
$\infty$	$\mathrm{NaN}$	$-\infty$	$\mathrm{NaN}$	$\infty$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$

If <T> is an unsigned integral type, the return value is as follows.

$x \backslash y$	$0$	$\mathbb{Z}_{>0}$	$\infty$	$\mathrm{NaN}$
$0$	$\mathrm{NaN}$	$0$	$0$	$\mathrm{NaN}$
$\mathbb{Z}_{>0}$	$\mathrm{NaN}$	(see below)	$0$	$\mathrm{NaN}$
$\infty$	$\mathrm{NaN}$	$\infty$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$

If $x \in \mathbb{Z}$ and $y \in \mathbb{Z} \setminus \{0\}$, the return value is as follows.

• If $x = $ std::numeric_limits<T>::min() and $y = -1$, it returns $\mathrm{NaN}$.
• Otherwise, it returns the rounded $\frac{x}{y}$ towards zero.

Constraints

• None

Time Complexity

• $O(1)$

x % y

tools::safe_int<T> x % y;

If <T> is a signed integral type, the return value is as follows.

$x \backslash y$	$-\infty$	$\mathbb{Z}_{<0}$	$0$	$\mathbb{Z}_{>0}$	$\infty$	$\mathrm{NaN}$
$-\infty$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathbb{Z}_{<0}$	$\mathrm{NaN}$	(see below)	$\mathrm{NaN}$	(see below)	$\mathrm{NaN}$	$\mathrm{NaN}$
$0$	$\mathrm{NaN}$	$0$	$\mathrm{NaN}$	$0$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathbb{Z}_{>0}$	$\mathrm{NaN}$	(see below)	$\mathrm{NaN}$	(see below)	$\mathrm{NaN}$	$\mathrm{NaN}$
$\infty$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$

If <T> is an unsigned integral type, the return value is as follows.

$x \backslash y$	$0$	$\mathbb{Z}_{>0}$	$\infty$	$\mathrm{NaN}$
$0$	$\mathrm{NaN}$	$0$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathbb{Z}_{>0}$	$\mathrm{NaN}$	(see below)	$\mathrm{NaN}$	$\mathrm{NaN}$
$\infty$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$
$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$	$\mathrm{NaN}$

If $x \in \mathbb{Z}$ and $y \in \mathbb{Z} \setminus \{0\}$, the return value is as follows.

• If $x = $ std::numeric_limits<T>::min() and $y = -1$, it returns $\mathrm{NaN}$.
• Otherwise, it returns $x - qy$ where $q$ is the rounded $\frac{x}{y}$ towards zero.

Constraints

• None

Time Complexity

• $O(1)$

x += y

tools::safe_int<T>& x += y;

It runs x = x + y; and returns $x$.

Constraints

• None

Time Complexity

• $O(1)$

x -= y

tools::safe_int<T>& x -= y;

It runs x = x - y; and returns $x$.

Constraints

• None

Time Complexity

• $O(1)$

x *= y

tools::safe_int<T>& x *= y;

It runs x = x * y; and returns $x$.

Constraints

• None

Time Complexity

• $O(1)$

x /= y

tools::safe_int<T>& x /= y;

It runs x = x / y; and returns $x$.

Constraints

• None

Time Complexity

• $O(1)$

x %= y

tools::safe_int<T>& x %= y;

It runs x = x % y; and returns $x$.

Constraints

• None

Time Complexity

• $O(1)$

++x

tools::safe_int<T>& ++x;

It runs x = x + 1; and returns $x$.

Constraints

• None

Time Complexity

• $O(1)$

x++

tools::safe_int<T> x++;

It runs x = x + 1; and returns the previous $x$.

Constraints

• None

Time Complexity

• $O(1)$

--x

tools::safe_int<T>& --x;

It runs x = x - 1; and returns $x$.

Constraints

• None

Time Complexity

• $O(1)$

x--

tools::safe_int<T> x--;

It runs x = x - 1; and returns the previous $x$.

Constraints

• None

Time Complexity

• $O(1)$

x == y

bool x == y;

The return value is as follows.

$x \backslash y$	$-\infty$	$\mathbb{Z}$	$\infty$	$\mathrm{NaN}$
$-\infty$	true	false	false	false
$\mathbb{Z}$	false	$x == y$	false	false
$\infty$	false	false	true	false
$\mathrm{NaN}$	false	false	false	false

Constraints

• None

Time Complexity

• $O(1)$

x != y

bool x != y;

It returns !(x == y).

Constraints

• None

Time Complexity

• $O(1)$

x < y

bool x < y;

The return value is as follows.

$x \backslash y$	$-\infty$	$\mathbb{Z}$	$\infty$	$\mathrm{NaN}$
$-\infty$	false	true	true	false
$\mathbb{Z}$	false	$x < y$	true	false
$\infty$	false	false	false	false
$\mathrm{NaN}$	false	false	false	false

Constraints

• None

Time Complexity

• $O(1)$

x > y

bool x > y;

The return value is as follows.

$x \backslash y$	$-\infty$	$\mathbb{Z}$	$\infty$	$\mathrm{NaN}$
$-\infty$	false	false	false	false
$\mathbb{Z}$	true	$x > y$	false	false
$\infty$	true	true	false	false
$\mathrm{NaN}$	false	false	false	false

Constraints

• None

Time Complexity

• $O(1)$

x <= y

bool x <= y;

It returns (x < y) || (x == y).

Constraints

• None

Time Complexity

• $O(1)$

x >= y

bool x >= y;

It returns (x > y) || (x == y).

Constraints

• None

Time Complexity

• $O(1)$

operator>>

std::istream& operator>>(std::istream& is, safe_int<T>& x);

It reads a finite integer from standard input and updates $x$ to it.

Constraints

• None

Time Complexity

• $O(1)$

operator<<

std::ostream& operator<<(std::ostream& os, safe_int<T> x);

It prints the following value to os.

$x$	output value
$-\infty$	-inf
$\mathbb{Z}$	$x$
$\infty$	inf
$\mathrm{NaN}$	nan

Constraints

• None

Time Complexity

• $O(1)$

Required by

• $\left\lceil x^\frac{1}{k} \right\rceil$ (tools/ceil_kth_root.hpp)
• $\left\lfloor x^\frac{1}{k} \right\rfloor$ (tools/floor_kth_root.hpp)
• 0-1 knapsack problem (tools/zero_one_knapsack.hpp)

Verified with

• tests/ceil_kth_root.test.cpp
• tests/floor_kth_root.test.cpp
• tests/safe_int.test.cpp
• tests/zero_one_knapsack/solve_by_dp_maximizing_value.test.cpp
• tests/zero_one_knapsack/solve_by_dp_minimizing_weight.test.cpp
• tests/zero_one_knapsack/solve_by_meet_in_the_middle.test.cpp

Code

#ifndef TOOLS_SAFE_INT_HPP
#define TOOLS_SAFE_INT_HPP

#include <type_traits>
#include <cstddef>
#include <cassert>
#include <limits>
#include <array>
#include <optional>
#include <iostream>

namespace tools {
  template <typename T, typename = void>
  class safe_int;

  template <typename T>
  class safe_int<T, ::std::enable_if_t<::std::is_signed_v<T>>> {
  private:
    enum class type {
      finite,
      pos_inf,
      neg_inf,
      nan
    };
    typename ::tools::safe_int<T>::type m_type;
    T m_value;

    constexpr safe_int(const typename ::tools::safe_int<T>::type type) :
      m_type(type), m_value(T()) {
    }

  public:
    constexpr safe_int() :
      m_type(::tools::safe_int<T>::type::finite), m_value(T()) {
    }
    explicit constexpr safe_int(const T value) :
      m_type(::tools::safe_int<T>::type::finite), m_value(value) {
    }
    constexpr safe_int(const ::tools::safe_int<T>& other) :
      m_type(other.m_type), m_value(other.m_value) {
    }
    ~safe_int() = default;
    constexpr ::tools::safe_int<T>& operator=(const ::tools::safe_int<T>& other) {
      this->m_type = other.m_type;
      this->m_value = other.m_value;
      return *this;
    }

    static constexpr ::tools::safe_int<T> infinity() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf);
    }
    static constexpr ::tools::safe_int<T> nan() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::nan);
    }

  private:
    static constexpr int f1(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::neg_inf:
        return 0;
      case ::tools::safe_int<T>::type::finite:
        return 1;
      case ::tools::safe_int<T>::type::pos_inf:
        return 2;
      default: // nan
        return 3;
      }
    };
    static constexpr int f2(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::neg_inf:
        return 0;
      case ::tools::safe_int<T>::type::finite:
        if (n.m_value < 0) {
          return 1;
        } else if (n.m_value == 0) {
          return 2;
        } else {
          return 3;
        }
      case ::tools::safe_int<T>::type::pos_inf:
        return 4;
      default: // nan
        return 5;
      }
    };
    static constexpr ::std::optional<::tools::safe_int<T>> Q() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<::tools::safe_int<T>> Z() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(0));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> N() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::neg_inf));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> P() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> U() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::nan));
    }
    static constexpr ::std::optional<bool> BQ() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<bool> BF() {
      return ::std::optional<bool>(false);
    }
    static constexpr ::std::optional<bool> BT() {
      return ::std::optional<bool>(true);
    }

  public:
    constexpr bool is_finite() const {
      return this->m_type == ::tools::safe_int<T>::type::finite;
    }

    constexpr bool is_nan() const {
      return this->m_type == ::tools::safe_int<T>::type::nan;
    }

    constexpr T val() const {
      assert(this->is_finite());
      return this->m_value;
    }

    friend constexpr bool operator==(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{
        {BT(), BF(), BF(), BF()},
        {BF(), BQ(), BF(), BF()},
        {BF(), BF(), BT(), BF()},
        {BF(), BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value == y.m_value;
    }
    friend constexpr bool operator!=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return !(x == y);
    }

    constexpr ::tools::safe_int<T> operator+() const {
      return *this;
    }
    constexpr ::tools::safe_int<T> operator-() const {
      constexpr auto table = ::std::array<::std::optional<::tools::safe_int<T>>, 4>({
        {P(), Q(), N(), U()}
      });
      if (const auto r = table[f1(*this)]; r) return *r;

      if (this->m_value == ::std::numeric_limits<T>::min()) return *U();
      return ::tools::safe_int<T>(-this->m_value);
    }

    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {N(), N(), U(), U()},
        {N(), Q(), P(), U()},
        {U(), P(), P(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (y.m_value > 0 && x.m_value > ::std::numeric_limits<T>::max() - y.m_value) return *U();
      if (y.m_value < 0 && x.m_value < ::std::numeric_limits<T>::min() - y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value + y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const T& y) {
      return x + tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator+(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) + y;
    }

    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {U(), N(), N(), U()},
        {P(), Q(), N(), U()},
        {P(), P(), U(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (y.m_value < 0 && x.m_value > ::std::numeric_limits<T>::max() + y.m_value) return *U();
      if (y.m_value > 0 && x.m_value < ::std::numeric_limits<T>::min() + y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value - y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const T& y) {
      return x - tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator-(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) - y;
    }

    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{
        {P(), P(), U(), N(), N(), U()},
        {P(), Q(), Z(), Q(), N(), U()},
        {U(), Z(), Z(), Z(), U(), U()},
        {N(), Q(), Z(), Q(), P(), U()},
        {N(), N(), U(), P(), P(), U()},
        {U(), U(), U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value > 0) {
        if (y.m_value > 0) {
          if (x.m_value > ::std::numeric_limits<T>::max() / y.m_value) {
            return *U();
          }
        } else {
          if (y.m_value < ::std::numeric_limits<T>::min() / x.m_value) {
            return *U();
          }
        }
      } else {
        if (y.m_value > 0) {
          if (x.m_value < ::std::numeric_limits<T>::min() / y.m_value) {
            return *U();
          }
        } else {
          if (x.m_value != 0 && y.m_value < ::std::numeric_limits<T>::max() / x.m_value) {
            return *U();
          }
        }
      }
      return ::tools::safe_int<T>(x.m_value * y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const T& y) {
      return x * tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator*(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) * y;
    }

    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{
        {U(), P(), U(), N(), U(), U()},
        {Z(), Q(), U(), Q(), Z(), U()},
        {Z(), Z(), U(), Z(), Z(), U()},
        {Z(), Q(), U(), Q(), Z(), U()},
        {U(), N(), U(), P(), U(), U()},
        {U(), U(), U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value == ::std::numeric_limits<T>::min() && y.m_value == -1) return *U();
      return ::tools::safe_int<T>(x.m_value / y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const T& y) {
      return x / tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator/(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) / y;
    }

    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{
        {U(), U(), U(), U(), U(), U()},
        {U(), Q(), U(), Q(), U(), U()},
        {U(), Z(), U(), Z(), U(), U()},
        {U(), Q(), U(), Q(), U(), U()},
        {U(), U(), U(), U(), U(), U()},
        {U(), U(), U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value == ::std::numeric_limits<T>::min() && y.m_value == -1) return *U();
      return ::tools::safe_int<T>(x.m_value % y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const T& y) {
      return x % tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator%(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) % y;
    }

    constexpr ::tools::safe_int<T>& operator+=(const ::tools::safe_int<T>& other) {
      return *this = *this + other;
    }
    constexpr ::tools::safe_int<T>& operator+=(const T& other) {
      return *this = *this + ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator-=(const ::tools::safe_int<T>& other) {
      return *this = *this - other;
    }
    constexpr ::tools::safe_int<T>& operator-=(const T& other) {
      return *this = *this - ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator*=(const ::tools::safe_int<T>& other) {
      return *this = *this * other;
    }
    constexpr ::tools::safe_int<T>& operator*=(const T& other) {
      return *this = *this * ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator/=(const ::tools::safe_int<T>& other) {
      return *this = *this / other;
    }
    constexpr ::tools::safe_int<T>& operator/=(const T& other) {
      return *this = *this / ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator%=(const ::tools::safe_int<T>& other) {
      return *this = *this % other;
    }
    constexpr ::tools::safe_int<T>& operator%=(const T& other) {
      return *this = *this % ::tools::safe_int<T>(other);
    }

    constexpr ::tools::safe_int<T>& operator++() {
      return *this += ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator++(int) {
      const auto r = *this;
      ++(*this);
      return r;
    }
    constexpr ::tools::safe_int<T>& operator--() {
      return *this -= ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator--(int) {
      const auto r = *this;
      --(*this);
      return r;
    }

    friend constexpr bool operator<(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{
        {BF(), BT(), BT(), BF()},
        {BF(), BQ(), BT(), BF()},
        {BF(), BF(), BF(), BF()},
        {BF(), BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value < y.m_value;
    }
    friend constexpr bool operator>(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{
        {BF(), BF(), BF(), BF()},
        {BT(), BQ(), BF(), BF()},
        {BT(), BT(), BF(), BF()},
        {BF(), BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value > y.m_value;
    }
    friend constexpr bool operator<=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x < y || x == y;
    }
    friend constexpr bool operator>=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x > y || x == y;
    }

    friend ::std::istream& operator>>(::std::istream& is, ::tools::safe_int<T>& self) {
      self.m_type = ::tools::safe_int<T>::type::finite;
      return is >> self.m_value;
    }
    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::safe_int<T>& self) {
      switch (self.m_type) {
      case ::tools::safe_int<T>::type::neg_inf:
        return os << "-inf";
      case ::tools::safe_int<T>::type::finite:
        return os << self.m_value;
      case ::tools::safe_int<T>::type::pos_inf:
        return os << "inf";
      default: // nan
        return os << "nan";
      }
    }
  };

  template <typename T>
  class safe_int<T, ::std::enable_if_t<::std::is_unsigned_v<T>>> {
  private:
    enum class type {
      finite,
      pos_inf,
      nan
    };
    typename ::tools::safe_int<T>::type m_type;
    T m_value;

    constexpr safe_int(const typename ::tools::safe_int<T>::type type) :
      m_type(type), m_value(T()) {
    }

  public:
    constexpr safe_int() :
      m_type(::tools::safe_int<T>::type::finite), m_value(T()) {
    }
    explicit constexpr safe_int(const T value) :
      m_type(::tools::safe_int<T>::type::finite), m_value(value) {
    }
    constexpr safe_int(const ::tools::safe_int<T>& other) :
      m_type(other.m_type), m_value(other.m_value) {
    }
    ~safe_int() = default;
    constexpr ::tools::safe_int<T>& operator=(const ::tools::safe_int<T>& other) {
      this->m_type = other.m_type;
      this->m_value = other.m_value;
      return *this;
    }

    static constexpr ::tools::safe_int<T> infinity() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf);
    }
    static constexpr ::tools::safe_int<T> nan() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::nan);
    }

  private:
    static constexpr int f1(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::finite:
        return 0;
      case ::tools::safe_int<T>::type::pos_inf:
        return 1;
      default: // nan
        return 2;
      }
    };
    static constexpr int f2(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::finite:
        if (n.m_value == 0) {
          return 0;
        } else {
          return 1;
        }
      case ::tools::safe_int<T>::type::pos_inf:
        return 2;
      default: // nan
        return 3;
      }
    };
    static constexpr ::std::optional<::tools::safe_int<T>> Q() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<::tools::safe_int<T>> Z() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(0));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> P() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> U() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::nan));
    }
    static constexpr ::std::optional<bool> BQ() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<bool> BF() {
      return ::std::optional<bool>(false);
    }
    static constexpr ::std::optional<bool> BT() {
      return ::std::optional<bool>(true);
    }

  public:
    constexpr bool is_finite() const {
      return this->m_type == ::tools::safe_int<T>::type::finite;
    }

    constexpr bool is_nan() const {
      return this->m_type == ::tools::safe_int<T>::type::nan;
    }

    constexpr T val() const {
      assert(this->is_finite());
      return this->m_value;
    }

    friend constexpr bool operator==(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{
        {BQ(), BF(), BF()},
        {BF(), BT(), BF()},
        {BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value == y.m_value;
    }
    friend constexpr bool operator!=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return !(x == y);
    }

    constexpr ::tools::safe_int<T> operator+() const {
      return *this;
    }
    constexpr ::tools::safe_int<T> operator-() const {
      constexpr auto table = ::std::array<::std::optional<::tools::safe_int<T>>, 3>({
        {Q(), U(), U()}
      });
      if (const auto r = table[f1(*this)]; r) return *r;

      if (this->m_value > 0) return *U();
      return ::tools::safe_int<T>(0);
    }

    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 3>, 3>({{
        {Q(), P(), U()},
        {P(), P(), U()},
        {U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (y.m_value > 0 && x.m_value > ::std::numeric_limits<T>::max() - y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value + y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const T& y) {
      return x + tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator+(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) + y;
    }

    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 3>, 3>({{
        {Q(), U(), U()},
        {P(), U(), U()},
        {U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (x.m_value < y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value - y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const T& y) {
      return x - tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator-(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) - y;
    }

    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {Z(), Z(), U(), U()},
        {Z(), Q(), P(), U()},
        {U(), P(), P(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value > ::std::numeric_limits<T>::max() / y.m_value) {
        return *U();
      }
      return ::tools::safe_int<T>(x.m_value * y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const T& y) {
      return x * tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator*(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) * y;
    }

    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {U(), Z(), Z(), U()},
        {U(), Q(), Z(), U()},
        {U(), P(), U(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      return ::tools::safe_int<T>(x.m_value / y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const T& y) {
      return x / tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator/(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) / y;
    }

    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {U(), Z(), U(), U()},
        {U(), Q(), U(), U()},
        {U(), U(), U(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      return ::tools::safe_int<T>(x.m_value % y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const T& y) {
      return x % tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator%(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) % y;
    }

    constexpr ::tools::safe_int<T>& operator+=(const ::tools::safe_int<T>& other) {
      return *this = *this + other;
    }
    constexpr ::tools::safe_int<T>& operator+=(const T& other) {
      return *this = *this + ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator-=(const ::tools::safe_int<T>& other) {
      return *this = *this - other;
    }
    constexpr ::tools::safe_int<T>& operator-=(const T& other) {
      return *this = *this - ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator*=(const ::tools::safe_int<T>& other) {
      return *this = *this * other;
    }
    constexpr ::tools::safe_int<T>& operator*=(const T& other) {
      return *this = *this * ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator/=(const ::tools::safe_int<T>& other) {
      return *this = *this / other;
    }
    constexpr ::tools::safe_int<T>& operator/=(const T& other) {
      return *this = *this / ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator%=(const ::tools::safe_int<T>& other) {
      return *this = *this % other;
    }
    constexpr ::tools::safe_int<T>& operator%=(const T& other) {
      return *this = *this % ::tools::safe_int<T>(other);
    }

    constexpr ::tools::safe_int<T>& operator++() {
      return *this += ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator++(int) {
      const auto r = *this;
      ++(*this);
      return r;
    }
    constexpr ::tools::safe_int<T>& operator--() {
      return *this -= ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator--(int) {
      const auto r = *this;
      --(*this);
      return r;
    }

    friend constexpr bool operator<(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{
        {BQ(), BT(), BF()},
        {BF(), BF(), BF()},
        {BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value < y.m_value;
    }
    friend constexpr bool operator>(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{
        {BQ(), BF(), BF()},
        {BT(), BF(), BF()},
        {BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value > y.m_value;
    }
    friend constexpr bool operator<=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x < y || x == y;
    }
    friend constexpr bool operator>=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x > y || x == y;
    }

    friend ::std::istream& operator>>(::std::istream& is, ::tools::safe_int<T>& self) {
      self.m_type = ::tools::safe_int<T>::type::finite;
      return is >> self.m_value;
    }
    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::safe_int<T>& self) {
      switch (self.m_type) {
      case ::tools::safe_int<T>::type::finite:
        return os << self.m_value;
      case ::tools::safe_int<T>::type::pos_inf:
        return os << "inf";
      default: // nan
        return os << "nan";
      }
    }
  };
}

#endif

#line 1 "tools/safe_int.hpp"



#include <type_traits>
#include <cstddef>
#include <cassert>
#include <limits>
#include <array>
#include <optional>
#include <iostream>

namespace tools {
  template <typename T, typename = void>
  class safe_int;

  template <typename T>
  class safe_int<T, ::std::enable_if_t<::std::is_signed_v<T>>> {
  private:
    enum class type {
      finite,
      pos_inf,
      neg_inf,
      nan
    };
    typename ::tools::safe_int<T>::type m_type;
    T m_value;

    constexpr safe_int(const typename ::tools::safe_int<T>::type type) :
      m_type(type), m_value(T()) {
    }

  public:
    constexpr safe_int() :
      m_type(::tools::safe_int<T>::type::finite), m_value(T()) {
    }
    explicit constexpr safe_int(const T value) :
      m_type(::tools::safe_int<T>::type::finite), m_value(value) {
    }
    constexpr safe_int(const ::tools::safe_int<T>& other) :
      m_type(other.m_type), m_value(other.m_value) {
    }
    ~safe_int() = default;
    constexpr ::tools::safe_int<T>& operator=(const ::tools::safe_int<T>& other) {
      this->m_type = other.m_type;
      this->m_value = other.m_value;
      return *this;
    }

    static constexpr ::tools::safe_int<T> infinity() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf);
    }
    static constexpr ::tools::safe_int<T> nan() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::nan);
    }

  private:
    static constexpr int f1(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::neg_inf:
        return 0;
      case ::tools::safe_int<T>::type::finite:
        return 1;
      case ::tools::safe_int<T>::type::pos_inf:
        return 2;
      default: // nan
        return 3;
      }
    };
    static constexpr int f2(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::neg_inf:
        return 0;
      case ::tools::safe_int<T>::type::finite:
        if (n.m_value < 0) {
          return 1;
        } else if (n.m_value == 0) {
          return 2;
        } else {
          return 3;
        }
      case ::tools::safe_int<T>::type::pos_inf:
        return 4;
      default: // nan
        return 5;
      }
    };
    static constexpr ::std::optional<::tools::safe_int<T>> Q() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<::tools::safe_int<T>> Z() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(0));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> N() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::neg_inf));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> P() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> U() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::nan));
    }
    static constexpr ::std::optional<bool> BQ() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<bool> BF() {
      return ::std::optional<bool>(false);
    }
    static constexpr ::std::optional<bool> BT() {
      return ::std::optional<bool>(true);
    }

  public:
    constexpr bool is_finite() const {
      return this->m_type == ::tools::safe_int<T>::type::finite;
    }

    constexpr bool is_nan() const {
      return this->m_type == ::tools::safe_int<T>::type::nan;
    }

    constexpr T val() const {
      assert(this->is_finite());
      return this->m_value;
    }

    friend constexpr bool operator==(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{
        {BT(), BF(), BF(), BF()},
        {BF(), BQ(), BF(), BF()},
        {BF(), BF(), BT(), BF()},
        {BF(), BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value == y.m_value;
    }
    friend constexpr bool operator!=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return !(x == y);
    }

    constexpr ::tools::safe_int<T> operator+() const {
      return *this;
    }
    constexpr ::tools::safe_int<T> operator-() const {
      constexpr auto table = ::std::array<::std::optional<::tools::safe_int<T>>, 4>({
        {P(), Q(), N(), U()}
      });
      if (const auto r = table[f1(*this)]; r) return *r;

      if (this->m_value == ::std::numeric_limits<T>::min()) return *U();
      return ::tools::safe_int<T>(-this->m_value);
    }

    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {N(), N(), U(), U()},
        {N(), Q(), P(), U()},
        {U(), P(), P(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (y.m_value > 0 && x.m_value > ::std::numeric_limits<T>::max() - y.m_value) return *U();
      if (y.m_value < 0 && x.m_value < ::std::numeric_limits<T>::min() - y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value + y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const T& y) {
      return x + tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator+(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) + y;
    }

    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {U(), N(), N(), U()},
        {P(), Q(), N(), U()},
        {P(), P(), U(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (y.m_value < 0 && x.m_value > ::std::numeric_limits<T>::max() + y.m_value) return *U();
      if (y.m_value > 0 && x.m_value < ::std::numeric_limits<T>::min() + y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value - y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const T& y) {
      return x - tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator-(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) - y;
    }

    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{
        {P(), P(), U(), N(), N(), U()},
        {P(), Q(), Z(), Q(), N(), U()},
        {U(), Z(), Z(), Z(), U(), U()},
        {N(), Q(), Z(), Q(), P(), U()},
        {N(), N(), U(), P(), P(), U()},
        {U(), U(), U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value > 0) {
        if (y.m_value > 0) {
          if (x.m_value > ::std::numeric_limits<T>::max() / y.m_value) {
            return *U();
          }
        } else {
          if (y.m_value < ::std::numeric_limits<T>::min() / x.m_value) {
            return *U();
          }
        }
      } else {
        if (y.m_value > 0) {
          if (x.m_value < ::std::numeric_limits<T>::min() / y.m_value) {
            return *U();
          }
        } else {
          if (x.m_value != 0 && y.m_value < ::std::numeric_limits<T>::max() / x.m_value) {
            return *U();
          }
        }
      }
      return ::tools::safe_int<T>(x.m_value * y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const T& y) {
      return x * tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator*(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) * y;
    }

    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{
        {U(), P(), U(), N(), U(), U()},
        {Z(), Q(), U(), Q(), Z(), U()},
        {Z(), Z(), U(), Z(), Z(), U()},
        {Z(), Q(), U(), Q(), Z(), U()},
        {U(), N(), U(), P(), U(), U()},
        {U(), U(), U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value == ::std::numeric_limits<T>::min() && y.m_value == -1) return *U();
      return ::tools::safe_int<T>(x.m_value / y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const T& y) {
      return x / tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator/(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) / y;
    }

    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{
        {U(), U(), U(), U(), U(), U()},
        {U(), Q(), U(), Q(), U(), U()},
        {U(), Z(), U(), Z(), U(), U()},
        {U(), Q(), U(), Q(), U(), U()},
        {U(), U(), U(), U(), U(), U()},
        {U(), U(), U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value == ::std::numeric_limits<T>::min() && y.m_value == -1) return *U();
      return ::tools::safe_int<T>(x.m_value % y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const T& y) {
      return x % tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator%(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) % y;
    }

    constexpr ::tools::safe_int<T>& operator+=(const ::tools::safe_int<T>& other) {
      return *this = *this + other;
    }
    constexpr ::tools::safe_int<T>& operator+=(const T& other) {
      return *this = *this + ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator-=(const ::tools::safe_int<T>& other) {
      return *this = *this - other;
    }
    constexpr ::tools::safe_int<T>& operator-=(const T& other) {
      return *this = *this - ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator*=(const ::tools::safe_int<T>& other) {
      return *this = *this * other;
    }
    constexpr ::tools::safe_int<T>& operator*=(const T& other) {
      return *this = *this * ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator/=(const ::tools::safe_int<T>& other) {
      return *this = *this / other;
    }
    constexpr ::tools::safe_int<T>& operator/=(const T& other) {
      return *this = *this / ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator%=(const ::tools::safe_int<T>& other) {
      return *this = *this % other;
    }
    constexpr ::tools::safe_int<T>& operator%=(const T& other) {
      return *this = *this % ::tools::safe_int<T>(other);
    }

    constexpr ::tools::safe_int<T>& operator++() {
      return *this += ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator++(int) {
      const auto r = *this;
      ++(*this);
      return r;
    }
    constexpr ::tools::safe_int<T>& operator--() {
      return *this -= ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator--(int) {
      const auto r = *this;
      --(*this);
      return r;
    }

    friend constexpr bool operator<(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{
        {BF(), BT(), BT(), BF()},
        {BF(), BQ(), BT(), BF()},
        {BF(), BF(), BF(), BF()},
        {BF(), BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value < y.m_value;
    }
    friend constexpr bool operator>(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{
        {BF(), BF(), BF(), BF()},
        {BT(), BQ(), BF(), BF()},
        {BT(), BT(), BF(), BF()},
        {BF(), BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value > y.m_value;
    }
    friend constexpr bool operator<=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x < y || x == y;
    }
    friend constexpr bool operator>=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x > y || x == y;
    }

    friend ::std::istream& operator>>(::std::istream& is, ::tools::safe_int<T>& self) {
      self.m_type = ::tools::safe_int<T>::type::finite;
      return is >> self.m_value;
    }
    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::safe_int<T>& self) {
      switch (self.m_type) {
      case ::tools::safe_int<T>::type::neg_inf:
        return os << "-inf";
      case ::tools::safe_int<T>::type::finite:
        return os << self.m_value;
      case ::tools::safe_int<T>::type::pos_inf:
        return os << "inf";
      default: // nan
        return os << "nan";
      }
    }
  };

  template <typename T>
  class safe_int<T, ::std::enable_if_t<::std::is_unsigned_v<T>>> {
  private:
    enum class type {
      finite,
      pos_inf,
      nan
    };
    typename ::tools::safe_int<T>::type m_type;
    T m_value;

    constexpr safe_int(const typename ::tools::safe_int<T>::type type) :
      m_type(type), m_value(T()) {
    }

  public:
    constexpr safe_int() :
      m_type(::tools::safe_int<T>::type::finite), m_value(T()) {
    }
    explicit constexpr safe_int(const T value) :
      m_type(::tools::safe_int<T>::type::finite), m_value(value) {
    }
    constexpr safe_int(const ::tools::safe_int<T>& other) :
      m_type(other.m_type), m_value(other.m_value) {
    }
    ~safe_int() = default;
    constexpr ::tools::safe_int<T>& operator=(const ::tools::safe_int<T>& other) {
      this->m_type = other.m_type;
      this->m_value = other.m_value;
      return *this;
    }

    static constexpr ::tools::safe_int<T> infinity() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf);
    }
    static constexpr ::tools::safe_int<T> nan() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::nan);
    }

  private:
    static constexpr int f1(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::finite:
        return 0;
      case ::tools::safe_int<T>::type::pos_inf:
        return 1;
      default: // nan
        return 2;
      }
    };
    static constexpr int f2(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::finite:
        if (n.m_value == 0) {
          return 0;
        } else {
          return 1;
        }
      case ::tools::safe_int<T>::type::pos_inf:
        return 2;
      default: // nan
        return 3;
      }
    };
    static constexpr ::std::optional<::tools::safe_int<T>> Q() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<::tools::safe_int<T>> Z() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(0));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> P() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> U() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::nan));
    }
    static constexpr ::std::optional<bool> BQ() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<bool> BF() {
      return ::std::optional<bool>(false);
    }
    static constexpr ::std::optional<bool> BT() {
      return ::std::optional<bool>(true);
    }

  public:
    constexpr bool is_finite() const {
      return this->m_type == ::tools::safe_int<T>::type::finite;
    }

    constexpr bool is_nan() const {
      return this->m_type == ::tools::safe_int<T>::type::nan;
    }

    constexpr T val() const {
      assert(this->is_finite());
      return this->m_value;
    }

    friend constexpr bool operator==(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{
        {BQ(), BF(), BF()},
        {BF(), BT(), BF()},
        {BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value == y.m_value;
    }
    friend constexpr bool operator!=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return !(x == y);
    }

    constexpr ::tools::safe_int<T> operator+() const {
      return *this;
    }
    constexpr ::tools::safe_int<T> operator-() const {
      constexpr auto table = ::std::array<::std::optional<::tools::safe_int<T>>, 3>({
        {Q(), U(), U()}
      });
      if (const auto r = table[f1(*this)]; r) return *r;

      if (this->m_value > 0) return *U();
      return ::tools::safe_int<T>(0);
    }

    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 3>, 3>({{
        {Q(), P(), U()},
        {P(), P(), U()},
        {U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (y.m_value > 0 && x.m_value > ::std::numeric_limits<T>::max() - y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value + y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const T& y) {
      return x + tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator+(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) + y;
    }

    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 3>, 3>({{
        {Q(), U(), U()},
        {P(), U(), U()},
        {U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (x.m_value < y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value - y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const T& y) {
      return x - tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator-(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) - y;
    }

    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {Z(), Z(), U(), U()},
        {Z(), Q(), P(), U()},
        {U(), P(), P(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value > ::std::numeric_limits<T>::max() / y.m_value) {
        return *U();
      }
      return ::tools::safe_int<T>(x.m_value * y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const T& y) {
      return x * tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator*(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) * y;
    }

    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {U(), Z(), Z(), U()},
        {U(), Q(), Z(), U()},
        {U(), P(), U(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      return ::tools::safe_int<T>(x.m_value / y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const T& y) {
      return x / tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator/(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) / y;
    }

    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {U(), Z(), U(), U()},
        {U(), Q(), U(), U()},
        {U(), U(), U(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      return ::tools::safe_int<T>(x.m_value % y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const T& y) {
      return x % tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator%(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) % y;
    }

    constexpr ::tools::safe_int<T>& operator+=(const ::tools::safe_int<T>& other) {
      return *this = *this + other;
    }
    constexpr ::tools::safe_int<T>& operator+=(const T& other) {
      return *this = *this + ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator-=(const ::tools::safe_int<T>& other) {
      return *this = *this - other;
    }
    constexpr ::tools::safe_int<T>& operator-=(const T& other) {
      return *this = *this - ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator*=(const ::tools::safe_int<T>& other) {
      return *this = *this * other;
    }
    constexpr ::tools::safe_int<T>& operator*=(const T& other) {
      return *this = *this * ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator/=(const ::tools::safe_int<T>& other) {
      return *this = *this / other;
    }
    constexpr ::tools::safe_int<T>& operator/=(const T& other) {
      return *this = *this / ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator%=(const ::tools::safe_int<T>& other) {
      return *this = *this % other;
    }
    constexpr ::tools::safe_int<T>& operator%=(const T& other) {
      return *this = *this % ::tools::safe_int<T>(other);
    }

    constexpr ::tools::safe_int<T>& operator++() {
      return *this += ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator++(int) {
      const auto r = *this;
      ++(*this);
      return r;
    }
    constexpr ::tools::safe_int<T>& operator--() {
      return *this -= ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator--(int) {
      const auto r = *this;
      --(*this);
      return r;
    }

    friend constexpr bool operator<(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{
        {BQ(), BT(), BF()},
        {BF(), BF(), BF()},
        {BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value < y.m_value;
    }
    friend constexpr bool operator>(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{
        {BQ(), BF(), BF()},
        {BT(), BF(), BF()},
        {BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value > y.m_value;
    }
    friend constexpr bool operator<=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x < y || x == y;
    }
    friend constexpr bool operator>=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x > y || x == y;
    }

    friend ::std::istream& operator>>(::std::istream& is, ::tools::safe_int<T>& self) {
      self.m_type = ::tools::safe_int<T>::type::finite;
      return is >> self.m_value;
    }
    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::safe_int<T>& self) {
      switch (self.m_type) {
      case ::tools::safe_int<T>::type::finite:
        return os << self.m_value;
      case ::tools::safe_int<T>::type::pos_inf:
        return os << "inf";
      default: // nan
        return os << "nan";
      }
    }
  };
}

Back to top page