ExtendedNumber.h

Go to the documentation of this file.

#pragma once
 
#include <functional>
#include <limits>
#include <ostream>
#include <type_traits>
#include <utility>
#include <vector>
 
#include "storm/exceptions/InvalidOperationException.h"
#include "storm/exceptions/NotSupportedException.h"
#include "storm/utility/NumberTraits.h"
#include "storm/utility/constants.h"
#include "storm/utility/macros.h"
 
namespace storm::utility {

template<typename ValueType>
class ExtendedNumber {
   public:
    enum class Kind { NegativeInfinity, Finite, PositiveInfinity };

    ExtendedNumber() : kind(Kind::Finite), value(storm::utility::zero<ValueType>()) {
        // Intentionally left empty
    }

    ExtendedNumber(ValueType const& value) : kind(Kind::Finite), value(value) {
        // Intentionally left empty
    }
 
    ExtendedNumber(ValueType&& value) : kind(Kind::Finite), value(std::move(value)) {
        // Intentionally left empty
    }
 
    ExtendedNumber(ExtendedNumber const&) = default;
    ExtendedNumber(ExtendedNumber&&) = default;
    ExtendedNumber& operator=(ExtendedNumber const&) = default;
    ExtendedNumber& operator=(ExtendedNumber&&) = default;
    ~ExtendedNumber() = default;

    static ExtendedNumber infinity() {
        return ExtendedNumber(Kind::PositiveInfinity);
    }

    static ExtendedNumber negativeInfinity() {
        return ExtendedNumber(Kind::NegativeInfinity);
    }

    bool isFinite() const {
        return kind == Kind::Finite;
    }

    bool isInfinite() const {
        return kind != Kind::Finite;
    }

    bool isPositiveInfinity() const {
        return kind == Kind::PositiveInfinity;
    }

    bool isNegativeInfinity() const {
        return kind == Kind::NegativeInfinity;
    }

    ValueType const& getFinite() const {
        STORM_LOG_ASSERT(isFinite(), "Tried to get the finite value of " << *this << ".");
        return value;
    }

    ValueType& getFinite() {
        STORM_LOG_ASSERT(isFinite(), "Tried to get the finite value of " << *this << ".");
        return value;
    }
 
    friend bool operator==(ExtendedNumber const& first, ExtendedNumber const& second) {
        if (first.kind != second.kind) {
            return false;
        }
        return !first.isFinite() || first.value == second.value;
    }
 
    friend bool operator!=(ExtendedNumber const& first, ExtendedNumber const& second) {
        return !(first == second);
    }
 
    friend bool operator<(ExtendedNumber const& first, ExtendedNumber const& second) {
        if (first.kind != second.kind) {
            return first.kind < second.kind;
        }
        return first.isFinite() && first.value < second.value;
    }
 
    friend bool operator<=(ExtendedNumber const& first, ExtendedNumber const& second) {
        return !(second < first);
    }
 
    friend bool operator>(ExtendedNumber const& first, ExtendedNumber const& second) {
        return second < first;
    }
 
    friend bool operator>=(ExtendedNumber const& first, ExtendedNumber const& second) {
        return !(first < second);
    }

    friend bool operator==(ExtendedNumber const& first, ValueType const& second) {
        return first.isFinite() && first.value == second;
    }
 
    friend bool operator==(ValueType const& first, ExtendedNumber const& second) {
        return second.isFinite() && first == second.value;
    }
 
    friend bool operator!=(ExtendedNumber const& first, ValueType const& second) {
        return !(first == second);
    }
 
    friend bool operator!=(ValueType const& first, ExtendedNumber const& second) {
        return !(first == second);
    }
 
    friend bool operator<(ExtendedNumber const& first, ValueType const& second) {
        // Every finite value is above -infinity and below +infinity.
        return first.isFinite() ? first.value < second : first.isNegativeInfinity();
    }
 
    friend bool operator<(ValueType const& first, ExtendedNumber const& second) {
        return second.isFinite() ? first < second.value : second.isPositiveInfinity();
    }
 
    friend bool operator<=(ExtendedNumber const& first, ValueType const& second) {
        return !(second < first);
    }
 
    friend bool operator<=(ValueType const& first, ExtendedNumber const& second) {
        return !(second < first);
    }
 
    friend bool operator>(ExtendedNumber const& first, ValueType const& second) {
        return second < first;
    }
 
    friend bool operator>(ValueType const& first, ExtendedNumber const& second) {
        return second < first;
    }
 
    friend bool operator>=(ExtendedNumber const& first, ValueType const& second) {
        return !(first < second);
    }
 
    friend bool operator>=(ValueType const& first, ExtendedNumber const& second) {
        return !(first < second);
    }
 
    ExtendedNumber operator-() const {
        switch (kind) {
            case Kind::PositiveInfinity:
                return negativeInfinity();
            case Kind::NegativeInfinity:
                return infinity();
            default:
                return ExtendedNumber(-value);
        }
    }
 
    ExtendedNumber const& operator+() const {
        return *this;
    }
 
    friend ExtendedNumber operator+(ExtendedNumber const& first, ExtendedNumber const& second) {
        if (first.isFinite() && second.isFinite()) {
            return ExtendedNumber(first.value + second.value);
        }
        if (first.isInfinite() && second.isInfinite()) {
            STORM_LOG_THROW(first.kind == second.kind, storm::exceptions::InvalidOperationException, "Tried to compute " << first << " + " << second << ".");
            return first;
        }
        return first.isInfinite() ? first : second;
    }
 
    friend ExtendedNumber operator-(ExtendedNumber const& first, ExtendedNumber const& second) {
        return first + (-second);
    }
 
    friend ExtendedNumber operator*(ExtendedNumber const& first, ExtendedNumber const& second) {
        if (first.isFinite() && second.isFinite()) {
            return ExtendedNumber(first.value * second.value);
        }
        // At least one operand is infinite, so the result is determined by the signs unless the other operand is zero.
        int const signs = first.sign() * second.sign();
        STORM_LOG_THROW(signs != 0, storm::exceptions::InvalidOperationException, "Tried to compute " << first << " * " << second << ".");
        return signs > 0 ? infinity() : negativeInfinity();
    }
 
    friend ExtendedNumber operator/(ExtendedNumber const& first, ExtendedNumber const& second) {
        STORM_LOG_THROW(!(first.isInfinite() && second.isInfinite()), storm::exceptions::InvalidOperationException,
                        "Tried to compute " << first << " / " << second << ".");
        if (second.isInfinite()) {
            // A finite value divided by an infinite one.
            return ExtendedNumber(storm::utility::zero<ValueType>());
        }
        int const divisorSign = second.sign();
        STORM_LOG_THROW(divisorSign != 0, storm::exceptions::InvalidOperationException, "Tried to compute " << first << " / " << second << ".");
        if (first.isFinite()) {
            return ExtendedNumber(first.value / second.value);
        }
        return (first.sign() * divisorSign) > 0 ? infinity() : negativeInfinity();
    }
 
    ExtendedNumber& operator+=(ExtendedNumber const& other) {
        return *this = *this + other;
    }
 
    ExtendedNumber& operator-=(ExtendedNumber const& other) {
        return *this = *this - other;
    }
 
    ExtendedNumber& operator*=(ExtendedNumber const& other) {
        return *this = *this * other;
    }
 
    ExtendedNumber& operator/=(ExtendedNumber const& other) {
        return *this = *this / other;
    }
 
    friend std::ostream& operator<<(std::ostream& out, ExtendedNumber const& number) {
        switch (number.kind) {
            case Kind::PositiveInfinity:
                out << "inf";
                break;
            case Kind::NegativeInfinity:
                out << "-inf";
                break;
            default:
                out << number.value;
                break;
        }
        return out;
    }
 
   private:
    explicit ExtendedNumber(Kind kind) : kind(kind), value(storm::utility::zero<ValueType>()) {
        // Intentionally left empty
    }

    int sign() const {
        switch (kind) {
            case Kind::PositiveInfinity:
                return 1;
            case Kind::NegativeInfinity:
                return -1;
            default:
                if (storm::utility::isZero(value)) {
                    return 0;
                }
                return value < storm::utility::zero<ValueType>() ? -1 : 1;
        }
    }
 
    Kind kind;

    ValueType value;
};

template<typename ValueType>
using ExtendedValueType = std::conditional_t<storm::NumberTraits<ValueType>::HasInfinity, ValueType, ExtendedNumber<ValueType>>;
 
namespace detail {
template<typename T>
struct IsExtendedNumber : std::false_type {};
 
template<typename T>
struct IsExtendedNumber<ExtendedNumber<T>> : std::true_type {};

template<typename T>
struct FiniteValueType {
    typedef T type;
};
 
template<typename T>
struct FiniteValueType<ExtendedNumber<T>> {
    typedef T type;
};
}  // namespace detail

template<typename ValueType>
using FiniteValueType = typename detail::FiniteValueType<ValueType>::type;

template<typename ValueType>
ExtendedValueType<ValueType> positiveInfinity() {
    if constexpr (detail::IsExtendedNumber<ExtendedValueType<ValueType>>::value) {
        return ExtendedValueType<ValueType>::infinity();
    } else {
        return storm::utility::infinity<ValueType>();
    }
}

template<typename ValueType>
ExtendedValueType<ValueType> negativeInfinity() {
    if constexpr (detail::IsExtendedNumber<ExtendedValueType<ValueType>>::value) {
        return ExtendedValueType<ValueType>::negativeInfinity();
    } else {
        return -storm::utility::infinity<ValueType>();
    }
}

template<typename ValueType>
ValueType const& getFinite(ExtendedNumber<ValueType> const& value) {
    return value.getFinite();
}
 
template<typename ValueType>
    requires(!detail::IsExtendedNumber<ValueType>::value)
ValueType const& getFinite(ValueType const& value) {
    return value;
}

template<typename ValueType>
bool isFinite(ExtendedNumber<ValueType> const& value) {
    return value.isFinite();
}
 
template<typename ValueType>
    requires(!detail::IsExtendedNumber<ValueType>::value)
bool isFinite(ValueType const& value) {
    if constexpr (storm::NumberTraits<ValueType>::HasInfinity) {
        // A NaN is not infinite, but it is not a finite value either: the guards built on this predicate are there to
        // keep a value that is not a number out of a computation, and a NaN is exactly that.
        return !storm::utility::isInfinity(value) && !storm::utility::isInfinity(ValueType(-value)) && !storm::utility::isNan(value);
    } else {
        return true;
    }
}

template<typename ValueType>
std::vector<ValueType> narrowFinite(std::vector<ExtendedValueType<ValueType>>&& values) {
    if constexpr (std::is_same_v<ExtendedValueType<ValueType>, ValueType>) {
        return std::move(values);
    } else {
        std::vector<ValueType> result;
        result.reserve(values.size());
        for (auto& value : values) {
            STORM_LOG_THROW(value.isFinite(), storm::exceptions::InvalidOperationException, "Tried to narrow " << value << " to a type that cannot hold it.");
            result.push_back(std::move(value.getFinite()));
        }
        return result;
    }
}

template<typename ValueType>
std::vector<ValueType> narrowFinite(std::vector<ExtendedValueType<ValueType>> const& values) {
    if constexpr (std::is_same_v<ExtendedValueType<ValueType>, ValueType>) {
        return values;
    } else {
        std::vector<ValueType> result;
        result.reserve(values.size());
        for (auto const& value : values) {
            STORM_LOG_THROW(value.isFinite(), storm::exceptions::InvalidOperationException, "Tried to narrow " << value << " to a type that cannot hold it.");
            result.push_back(value.getFinite());
        }
        return result;
    }
}

template<typename ValueType>
std::vector<ValueType> narrowFinite(std::vector<ExtendedValueType<ValueType>>&& values, ValueType const& defaultValue) {
    std::vector<ValueType> result;
    result.reserve(values.size());
    for (auto& value : values) {
        if constexpr (std::is_same_v<ExtendedValueType<ValueType>, ValueType>) {
            result.push_back(storm::utility::isFinite(value) ? std::move(value) : defaultValue);
        } else {
            result.push_back(value.isFinite() ? std::move(value.getFinite()) : defaultValue);
        }
    }
    return result;
}

template<typename ValueType>
ValueType narrow(ExtendedValueType<ValueType> const& value) {
    if constexpr (detail::IsExtendedNumber<ExtendedValueType<ValueType>>::value) {
        STORM_LOG_THROW(!value.isInfinite(), storm::exceptions::NotSupportedException,
                        "There is no representation of " << value << " in the value type it would have to be narrowed to.");
        return value.getFinite();
    } else {
        return value;
    }
}

template<typename ValueType>
std::vector<ExtendedValueType<ValueType>> widen(std::vector<ValueType>&& values) {
    if constexpr (std::is_same_v<ExtendedValueType<ValueType>, ValueType>) {
        return std::move(values);
    } else {
        std::vector<ExtendedValueType<ValueType>> result;
        result.reserve(values.size());
        for (auto& value : values) {
            result.push_back(ExtendedValueType<ValueType>(std::move(value)));
        }
        return result;
    }
}

template<typename ValueType>
    requires(!std::is_reference_v<ValueType>)
ExtendedValueType<ValueType> fromSentinel(ValueType&& value) {
    STORM_LOG_DEPRECATED(
        "storm::utility::fromSentinel, which exists only for as long as parts of Storm still produce the sentinel that storm::utility::infinity yields.");
    if (storm::utility::isInfinity(value)) {
        return storm::utility::positiveInfinity<ValueType>();
    }
    // The constraint above rules out a reference type, so this forward is a move.
    return std::forward<ValueType>(value);
}

template<typename ValueType>
std::vector<ExtendedValueType<ValueType>> fromSentinel(std::vector<ValueType>&& values) {
    STORM_LOG_DEPRECATED(
        "storm::utility::fromSentinel, which exists only for as long as parts of Storm still produce the sentinel that storm::utility::infinity yields.");
    if constexpr (std::is_same_v<ExtendedValueType<ValueType>, ValueType>) {
        return std::move(values);
    } else {
        std::vector<ExtendedValueType<ValueType>> result;
        result.reserve(values.size());
        ValueType const sentinel = storm::utility::infinity<ValueType>();
        for (auto& value : values) {
            if (value == sentinel) {
                result.push_back(storm::utility::positiveInfinity<ValueType>());
            } else {
                result.push_back(std::move(value));
            }
        }
        return result;
    }
}
 
template<typename ValueType>
ExtendedValueType<ValueType> fromSentinel(ValueType const& value) {
    STORM_LOG_DEPRECATED(
        "storm::utility::fromSentinel, which exists only for as long as parts of Storm still produce the sentinel that storm::utility::infinity yields.");
    if (storm::utility::isInfinity(value)) {
        return storm::utility::positiveInfinity<ValueType>();
    }
    return value;
}

template<typename ValueType>
ValueType toSentinel(ExtendedValueType<ValueType> const& value) {
    STORM_LOG_DEPRECATED(
        "storm::utility::toSentinel, which exists only for as long as parts of Storm still expect the sentinel that storm::utility::infinity yields.");
    if constexpr (detail::IsExtendedNumber<ExtendedValueType<ValueType>>::value) {
        if (value.isInfinite()) {
            STORM_LOG_THROW(value.isPositiveInfinity(), storm::exceptions::NotSupportedException, "There is no representation of " << value << " here.");
            return storm::utility::infinity<ValueType>();
        }
        return value.getFinite();
    } else {
        return value;
    }
}

template<typename ValueType>
    requires(detail::IsExtendedNumber<ValueType>::value)
ValueType zero() {
    return ValueType(storm::utility::zero<FiniteValueType<ValueType>>());
}
 
template<typename ValueType>
    requires(detail::IsExtendedNumber<ValueType>::value)
ValueType one() {
    return ValueType(storm::utility::one<FiniteValueType<ValueType>>());
}
 
template<typename ValueType>
    requires(detail::IsExtendedNumber<ValueType>::value)
ValueType infinity() {
    return ValueType::infinity();
}

template<typename ValueType>
bool isInfinity(ExtendedNumber<ValueType> const& number) {
    return number.isPositiveInfinity();
}

template<typename ValueType>
bool isNegativeInfinity(ExtendedNumber<ValueType> const& number) {
    return number.isNegativeInfinity();
}
 
template<typename ValueType>
    requires(!detail::IsExtendedNumber<ValueType>::value)
bool isNegativeInfinity(ValueType const& value) {
    if constexpr (storm::NumberTraits<ValueType>::HasInfinity) {
        return storm::utility::isInfinity(ValueType(-value));
    } else {
        return false;
    }
}
 
template<typename ValueType>
bool isZero(ExtendedNumber<ValueType> const& number) {
    return number.isFinite() && storm::utility::isZero(number.getFinite());
}
 
template<typename ValueType>
bool isOne(ExtendedNumber<ValueType> const& number) {
    return number.isFinite() && storm::utility::isOne(number.getFinite());
}
 
template<typename ValueType>
bool isConstant(ExtendedNumber<ValueType> const& number) {
    return number.isInfinite() || storm::utility::isConstant(number.getFinite());
}
 
template<typename ValueType>
ExtendedNumber<ValueType> abs(ExtendedNumber<ValueType> const& number) {
    if (number.isInfinite()) {
        return ExtendedNumber<ValueType>::infinity();
    }
    return ExtendedNumber<ValueType>(storm::utility::abs(number.getFinite()));
}

template<typename TargetType, typename SourceType>
TargetType convertNumber(ExtendedNumber<SourceType> const& number) {
    if (number.isFinite()) {
        return TargetType(convertNumber<FiniteValueType<TargetType>, SourceType>(number.getFinite()));
    }
    if constexpr (detail::IsExtendedNumber<TargetType>::value) {
        return number.isPositiveInfinity() ? TargetType::infinity() : TargetType::negativeInfinity();
    } else {
        static_assert(storm::NumberTraits<TargetType>::HasInfinity, "Tried to convert an infinite value to a target type that cannot represent infinity.");
        return number.isPositiveInfinity() ? storm::utility::infinity<TargetType>() : -storm::utility::infinity<TargetType>();
    }
}

template<typename TargetType, typename SourceType>
    requires(detail::IsExtendedNumber<TargetType>::value && !detail::IsExtendedNumber<SourceType>::value)
TargetType convertNumber(SourceType const& number) {
    if constexpr (storm::NumberTraits<SourceType>::HasInfinity) {
        // The source brings its own infinity, which the underlying conversion has no way of expressing.
        if (storm::utility::isInfinity(number)) {
            return TargetType::infinity();
        }
        if (storm::utility::isInfinity(SourceType(-number))) {
            return TargetType::negativeInfinity();
        }
    }
    return TargetType(convertNumber<FiniteValueType<TargetType>, SourceType>(number));
}
 
}  // namespace storm::utility
 
namespace storm {
using ExtendedRationalNumber = storm::utility::ExtendedValueType<RationalNumber>;

using ExtendedRationalFunction = storm::utility::ExtendedValueType<RationalFunction>;

template<typename ValueType>
struct NumberTraits<storm::utility::ExtendedNumber<ValueType>> {
    static const bool SupportsExponential = NumberTraits<ValueType>::SupportsExponential;
    static const bool IsExact = NumberTraits<ValueType>::IsExact;
    static const bool HasInfinity = true;
};
}  // namespace storm
 
namespace std {
template<typename ValueType>
struct hash<storm::utility::ExtendedNumber<ValueType>> {
    size_t operator()(storm::utility::ExtendedNumber<ValueType> const& number) const {
        // The infinities have no payload to hash, so they get an arbitrary fixed value each.
        if (number.isPositiveInfinity()) {
            return 0x9e3779b9;
        }
        if (number.isNegativeInfinity()) {
            return 0x85ebca6b;
        }
        return std::hash<ValueType>()(number.getFinite());
    }
};

template<typename ValueType>
struct numeric_limits<storm::utility::ExtendedNumber<ValueType>> {
    typedef storm::utility::ExtendedNumber<ValueType> type;
 
    static constexpr bool is_specialized = true;
    static constexpr bool is_signed = true;
    static constexpr bool is_integer = false;
    static constexpr bool is_exact = storm::NumberTraits<ValueType>::IsExact;
    static constexpr bool has_infinity = true;
    static constexpr bool has_quiet_NaN = false;
    static constexpr bool has_signaling_NaN = false;
    static constexpr bool is_iec559 = false;
    static constexpr bool is_bounded = false;
 
    static type infinity() {
        return type::infinity();
    }
 
    static type lowest() {
        return type(std::numeric_limits<ValueType>::lowest());
    }
 
    static type min() {
        return type(std::numeric_limits<ValueType>::min());
    }
 
    static type max() {
        return type(std::numeric_limits<ValueType>::max());
    }
 
    static type epsilon() {
        return type(std::numeric_limits<ValueType>::epsilon());
    }
};
}  // namespace std