#ifndef BOOST_SAFE_NUMERICS_INTERVAL_HPP
|
#define BOOST_SAFE_NUMERICS_INTERVAL_HPP
|
|
// Copyright (c) 2012 Robert Ramey
|
//
|
// Distributed under the Boost Software License, Version 1.0. (See
|
// accompanying file LICENSE_1_0.txt or copy at
|
// http://www.boost.org/LICENSE_1_0.txt)
|
|
#include <limits>
|
#include <cassert>
|
#include <type_traits>
|
#include <initializer_list>
|
#include <algorithm> // minmax, min, max
|
|
#include <boost/logic/tribool.hpp>
|
|
#include "utility.hpp" // log
|
|
#include "concept/integer.hpp"
|
|
// from stack overflow
|
// http://stackoverflow.com/questions/23815138/implementing-variadic-min-max-functions
|
|
namespace boost {
|
namespace safe_numerics {
|
|
template<typename R>
|
struct interval {
|
const R l;
|
const R u;
|
|
template<typename T>
|
constexpr interval(const T & lower, const T & upper) :
|
l(lower),
|
u(upper)
|
{
|
// assert(static_cast<bool>(l <= u));
|
}
|
template<typename T>
|
constexpr interval(const std::pair<T, T> & p) :
|
l(p.first),
|
u(p.second)
|
{}
|
template<class T>
|
constexpr interval(const interval<T> & rhs) :
|
l(rhs.l),
|
u(rhs.u)
|
{}
|
constexpr interval() :
|
l(std::numeric_limits<R>::min()),
|
u(std::numeric_limits<R>::max())
|
{}
|
// return true if this interval contains the given point
|
constexpr tribool includes(const R & t) const {
|
return l <= t && t <= u;
|
}
|
// if this interval contains every point found in some other inteval t
|
// return true
|
// otherwise
|
// return false or indeterminate
|
constexpr tribool includes(const interval<R> & t) const {
|
return u >= t.u && l <= t.l;
|
}
|
|
// return true if this interval contains the given point
|
constexpr tribool excludes(const R & t) const {
|
return t < l || t > u;
|
}
|
// if this interval excludes every point found in some other inteval t
|
// return true
|
// otherwise
|
// return false or indeterminate
|
constexpr tribool excludes(const interval<R> & t) const {
|
return t.u < l || u < t.l;
|
}
|
|
};
|
|
template<class R>
|
constexpr interval<R> make_interval(){
|
return interval<R>();
|
}
|
template<class R>
|
constexpr interval<R> make_interval(const R &){
|
return interval<R>();
|
}
|
|
// account for the fact that for floats and doubles
|
// the most negative value is called "lowest" rather
|
// than min
|
template<>
|
constexpr interval<float>::interval() :
|
l(std::numeric_limits<float>::lowest()),
|
u(std::numeric_limits<float>::max())
|
{}
|
template<>
|
constexpr interval<double>::interval() :
|
l(std::numeric_limits<double>::lowest()),
|
u(std::numeric_limits<double>::max())
|
{}
|
|
template<typename T>
|
constexpr interval<T> operator+(const interval<T> & t, const interval<T> & u){
|
// adapted from https://en.wikipedia.org/wiki/Interval_arithmetic
|
return {t.l + u.l, t.u + u.u};
|
}
|
|
template<typename T>
|
constexpr interval<T> operator-(const interval<T> & t, const interval<T> & u){
|
// adapted from https://en.wikipedia.org/wiki/Interval_arithmetic
|
return {t.l - u.u, t.u - u.l};
|
}
|
|
template<typename T>
|
constexpr interval<T> operator*(const interval<T> & t, const interval<T> & u){
|
// adapted from https://en.wikipedia.org/wiki/Interval_arithmetic
|
return utility::minmax<T>(
|
std::initializer_list<T> {
|
t.l * u.l,
|
t.l * u.u,
|
t.u * u.l,
|
t.u * u.u
|
}
|
);
|
}
|
|
// interval division
|
// note: presumes 0 is not included in the range of the denominator
|
template<typename T>
|
constexpr interval<T> operator/(const interval<T> & t, const interval<T> & u){
|
assert(static_cast<bool>(u.excludes(T(0))));
|
return utility::minmax<T>(
|
std::initializer_list<T> {
|
t.l / u.l,
|
t.l / u.u,
|
t.u / u.l,
|
t.u / u.u
|
}
|
);
|
}
|
|
// modulus of two intervals. This will give a new range of for the modulus.
|
// note: presumes 0 is not included in the range of the denominator
|
template<typename T>
|
constexpr interval<T> operator%(const interval<T> & t, const interval<T> & u){
|
assert(static_cast<bool>(u.excludes(T(0))));
|
return utility::minmax<T>(
|
std::initializer_list<T> {
|
t.l % u.l,
|
t.l % u.u,
|
t.u % u.l,
|
t.u % u.u
|
}
|
);
|
}
|
|
template<typename T>
|
constexpr interval<T> operator<<(const interval<T> & t, const interval<T> & u){
|
static_assert(
|
boost::safe_numerics::Integer<T>::value,
|
"left shift only defined for integral type"
|
);
|
//return interval<T>{t.l << u.l, t.u << u.u};
|
return utility::minmax<T>(
|
std::initializer_list<T> {
|
t.l << u.l,
|
t.l << u.u,
|
t.u << u.l,
|
t.u << u.u
|
}
|
);
|
}
|
|
template<typename T>
|
constexpr interval<T> operator>>(const interval<T> & t, const interval<T> & u){
|
static_assert(
|
boost::safe_numerics::Integer<T>::value,
|
"right shift only defined for integral type"
|
);
|
//return interval<T>{t.l >> u.u, t.u >> u.l};
|
return utility::minmax<T>(
|
std::initializer_list<T> {
|
t.l >> u.l,
|
t.l >> u.u,
|
t.u >> u.l,
|
t.u >> u.u
|
}
|
);
|
}
|
|
// union of two intervals
|
template<typename T>
|
constexpr interval<T> operator|(const interval<T> & t, const interval<T> & u){
|
const T & rl = std::min(t.l, u.l);
|
const T & ru = std::max(t.u, u.u);
|
return interval<T>(rl, ru);
|
}
|
|
// intersection of two intervals
|
template<typename T>
|
constexpr interval<T> operator&(const interval<T> & t, const interval<T> & u){
|
const T & rl = std::max(t.l, u.l);
|
const T & ru = std::min(t.u, u.u);
|
return interval<T>(rl, ru);
|
}
|
|
// determine whether two intervals intersect
|
template<typename T>
|
constexpr boost::logic::tribool intersect(const interval<T> & t, const interval<T> & u){
|
return t.u >= u.l || t.l <= u.u;
|
}
|
|
template<typename T>
|
constexpr boost::logic::tribool operator<(
|
const interval<T> & t,
|
const interval<T> & u
|
){
|
return
|
// if every element in t is less than every element in u
|
t.u < u.l ? boost::logic::tribool(true):
|
// if every element in t is greater than every element in u
|
t.l > u.u ? boost::logic::tribool(false):
|
// otherwise some element(s) in t are greater than some element in u
|
boost::logic::indeterminate
|
;
|
}
|
|
template<typename T>
|
constexpr boost::logic::tribool operator>(
|
const interval<T> & t,
|
const interval<T> & u
|
){
|
return
|
// if every element in t is greater than every element in u
|
t.l > u.u ? boost::logic::tribool(true) :
|
// if every element in t is less than every element in u
|
t.u < u.l ? boost::logic::tribool(false) :
|
// otherwise some element(s) in t are greater than some element in u
|
boost::logic::indeterminate
|
;
|
}
|
|
template<typename T>
|
constexpr bool operator==(
|
const interval<T> & t,
|
const interval<T> & u
|
){
|
// intervals have the same limits
|
return t.l == u.l && t.u == u.u;
|
}
|
|
template<typename T>
|
constexpr bool operator!=(
|
const interval<T> & t,
|
const interval<T> & u
|
){
|
return ! (t == u);
|
}
|
|
template<typename T>
|
constexpr boost::logic::tribool operator<=(
|
const interval<T> & t,
|
const interval<T> & u
|
){
|
return ! (t > u);
|
}
|
|
template<typename T>
|
constexpr boost::logic::tribool operator>=(
|
const interval<T> & t,
|
const interval<T> & u
|
){
|
return ! (t < u);
|
}
|
|
} // safe_numerics
|
} // boost
|
|
#include <iosfwd>
|
|
namespace std {
|
|
template<typename CharT, typename Traits, typename T>
|
inline std::basic_ostream<CharT, Traits> &
|
operator<<(
|
std::basic_ostream<CharT, Traits> & os,
|
const boost::safe_numerics::interval<T> & i
|
){
|
return os << '[' << i.l << ',' << i.u << ']';
|
}
|
template<typename CharT, typename Traits>
|
inline std::basic_ostream<CharT, Traits> &
|
operator<<(
|
std::basic_ostream<CharT, Traits> & os,
|
const boost::safe_numerics::interval<unsigned char> & i
|
){
|
os << "[" << (unsigned)i.l << "," << (unsigned)i.u << "]";
|
return os;
|
}
|
|
template<typename CharT, typename Traits>
|
inline std::basic_ostream<CharT, Traits> &
|
operator<<(
|
std::basic_ostream<CharT, Traits> & os,
|
const boost::safe_numerics::interval<signed char> & i
|
){
|
os << "[" << (int)i.l << "," << (int)i.u << "]";
|
return os;
|
}
|
|
} // std
|
|
#endif // BOOST_SAFE_NUMERICS_INTERVAL_HPP
|
