boost/safe_numerics/interval.hpp

0001 #ifndef BOOST_SAFE_NUMERICS_INTERVAL_HPP
0002 #define BOOST_SAFE_NUMERICS_INTERVAL_HPP
0003
0004 //  Copyright (c) 2012 Robert Ramey
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009
0010 #include <limits>
0011 #include <cassert>
0012 #include <type_traits>
0013 #include <initializer_list>
0014 #include <algorithm> // minmax, min, max
0015
0016 #include <boost/logic/tribool.hpp>
0017
0018 #include "utility.hpp" // log
0019
0020 // from stack overflow
0021 // http://stackoverflow.com/questions/23815138/implementing-variadic-min-max-functions
0022
0023 namespace boost {
0024 namespace safe_numerics {
0025
0026 template<typename R>
0027 struct interval {
0028     const R l;
0029     const R u;
0030
0031     template<typename T>
0032     constexpr interval(const T & lower, const T & upper) :
0033         l(lower),
0034         u(upper)
0035     {
0036         // assert(static_cast<bool>(l <= u));
0037     }
0038     template<typename T>
0039     constexpr interval(const std::pair<T, T> & p) :
0040         l(p.first),
0041         u(p.second)
0042     {}
0043     template<class T>
0044     constexpr interval(const interval<T> & rhs) :
0045         l(rhs.l),
0046         u(rhs.u)
0047     {}
0048     constexpr interval() :
0049         l(std::numeric_limits<R>::min()),
0050         u(std::numeric_limits<R>::max())
0051     {}
0052     // return true if this interval contains the given point
0053     constexpr tribool includes(const R & t) const {
0054         return l <= t && t <= u;
0055     }
0056     // if this interval contains every point found in some other inteval t
0057     //  return true
0058     // otherwise
0059     //  return false or indeterminate
0060     constexpr tribool includes(const interval<R> & t) const {
0061         return u >= t.u && l <= t.l;
0062     }
0063
0064     // return true if this interval contains the given point
0065     constexpr tribool excludes(const R & t) const {
0066         return t < l || t > u;
0067     }
0068     // if this interval excludes every point found in some other inteval t
0069     //  return true
0070     // otherwise
0071     //  return false or indeterminate
0072     constexpr tribool excludes(const interval<R> & t) const {
0073         return t.u < l || u < t.l;
0074     }
0075
0076 };
0077
0078 template<class R>
0079 constexpr inline interval<R> make_interval(){
0080     return interval<R>();
0081 }
0082 template<class R>
0083 constexpr  inline interval<R> make_interval(const R &){
0084     return interval<R>();
0085 }
0086
0087 // account for the fact that for floats and doubles
0088 // the most negative value is called "lowest" rather
0089 // than min
0090 template<>
0091 constexpr inline interval<float>::interval() :
0092     l(std::numeric_limits<float>::lowest()),
0093     u(std::numeric_limits<float>::max())
0094 {}
0095 template<>
0096 constexpr inline interval<double>::interval() :
0097     l(std::numeric_limits<double>::lowest()),
0098     u(std::numeric_limits<double>::max())
0099 {}
0100
0101 template<typename T>
0102 constexpr inline interval<T> operator+(const interval<T> & t, const interval<T> & u){
0103     // adapted from https://en.wikipedia.org/wiki/Interval_arithmetic
0104     return {t.l + u.l, t.u + u.u};
0105 }
0106
0107 template<typename T>
0108 constexpr inline interval<T> operator-(const interval<T> & t, const interval<T> & u){
0109     // adapted from https://en.wikipedia.org/wiki/Interval_arithmetic
0110     return {t.l - u.u, t.u - u.l};
0111 }
0112
0113 template<typename T>
0114 constexpr inline interval<T> operator*(const interval<T> & t, const interval<T> & u){
0115     // adapted from https://en.wikipedia.org/wiki/Interval_arithmetic
0116     return utility::minmax<T>(
0117         std::initializer_list<T> {
0118             t.l * u.l,
0119             t.l * u.u,
0120             t.u * u.l,
0121             t.u * u.u
0122         }
0123     );
0124 }
0125
0126 // interval division
0127 // note: presumes 0 is not included in the range of the denominator
0128 template<typename T>
0129 constexpr inline interval<T> operator/(const interval<T> & t, const interval<T> & u){
0130     assert(static_cast<bool>(u.excludes(T(0))));
0131     return utility::minmax<T>(
0132         std::initializer_list<T> {
0133             t.l / u.l,
0134             t.l / u.u,
0135             t.u / u.l,
0136             t.u / u.u
0137         }
0138     );
0139 }
0140
0141 // modulus of two intervals.  This will give a new range of for the modulus.
0142 // note: presumes 0 is not included in the range of the denominator
0143 template<typename T>
0144 constexpr inline interval<T> operator%(const interval<T> & t, const interval<T> & u){
0145     assert(static_cast<bool>(u.excludes(T(0))));
0146     return utility::minmax<T>(
0147         std::initializer_list<T> {
0148             t.l % u.l,
0149             t.l % u.u,
0150             t.u % u.l,
0151             t.u % u.u
0152         }
0153     );
0154 }
0155
0156 template<typename T>
0157 constexpr inline interval<T> operator<<(const interval<T> & t, const interval<T> & u){
0158     //return interval<T>{t.l << u.l, t.u << u.u};
0159     return utility::minmax<T>(
0160         std::initializer_list<T> {
0161             t.l << u.l,
0162             t.l << u.u,
0163             t.u << u.l,
0164             t.u << u.u
0165         }
0166     );
0167 }
0168
0169 template<typename T>
0170 constexpr inline interval<T> operator>>(const interval<T> & t, const interval<T> & u){
0171     //return interval<T>{t.l >> u.u, t.u >> u.l};
0172     return utility::minmax<T>(
0173         std::initializer_list<T> {
0174             t.l >> u.l,
0175             t.l >> u.u,
0176             t.u >> u.l,
0177             t.u >> u.u
0178         }
0179     );
0180 }
0181
0182 // union of two intervals
0183 template<typename T>
0184 constexpr interval<T> operator|(const interval<T> & t, const interval<T> & u){
0185     const T & rl = std::min(t.l, u.l);
0186     const T & ru = std::max(t.u, u.u);
0187     return interval<T>(rl, ru);
0188 }
0189
0190 // intersection of two intervals
0191 template<typename T>
0192 constexpr inline interval<T> operator&(const interval<T> & t, const interval<T> & u){
0193     const T & rl = std::max(t.l, u.l);
0194     const T & ru = std::min(t.u, u.u);
0195     return interval<T>(rl, ru);
0196 }
0197
0198 // determine whether two intervals intersect
0199 template<typename T>
0200 constexpr inline boost::logic::tribool intersect(const interval<T> & t, const interval<T> & u){
0201     return t.u >= u.l || t.l <= u.u;
0202 }
0203
0204 template<typename T>
0205 constexpr inline boost::logic::tribool operator<(
0206     const interval<T> & t,
0207     const interval<T> & u
0208 ){
0209     return
0210         // if every element in t is less than every element in u
0211         t.u < u.l ? boost::logic::tribool(true):
0212         // if every element in t is greater than every element in u
0213         t.l > u.u ? boost::logic::tribool(false):
0214         // otherwise some element(s) in t are greater than some element in u
0215         boost::logic::indeterminate
0216     ;
0217 }
0218
0219 template<typename T>
0220 constexpr inline boost::logic::tribool operator>(
0221     const interval<T> & t,
0222     const interval<T> & u
0223 ){
0224     return
0225         // if every element in t is greater than every element in u
0226         t.l > u.u ? boost::logic::tribool(true) :
0227         // if every element in t is less than every element in u
0228         t.u < u.l ? boost::logic::tribool(false) :
0229         // otherwise some element(s) in t are greater than some element in u
0230         boost::logic::indeterminate
0231     ;
0232 }
0233
0234 template<typename T>
0235 constexpr inline bool operator==(
0236     const interval<T> & t,
0237     const interval<T> & u
0238 ){
0239     // intervals have the same limits
0240     return t.l == u.l && t.u == u.u;
0241 }
0242
0243 template<typename T>
0244 constexpr inline bool operator!=(
0245     const interval<T> & t,
0246     const interval<T> & u
0247 ){
0248     return ! (t == u);
0249 }
0250
0251 template<typename T>
0252 constexpr inline boost::logic::tribool operator<=(
0253     const interval<T> & t,
0254     const interval<T> & u
0255 ){
0256     return ! (t > u);
0257 }
0258
0259 template<typename T>
0260 constexpr inline boost::logic::tribool operator>=(
0261     const interval<T> & t,
0262     const interval<T> & u
0263 ){
0264     return ! (t < u);
0265 }
0266
0267 } // safe_numerics
0268 } // boost
0269
0270 #include <iosfwd>
0271
0272 namespace std {
0273
0274 template<typename CharT, typename Traits, typename T>
0275 inline std::basic_ostream<CharT, Traits> &
0276 operator<<(
0277     std::basic_ostream<CharT, Traits> & os,
0278     const boost::safe_numerics::interval<T> & i
0279 ){
0280     return os << '[' << i.l << ',' << i.u << ']';
0281 }
0282 template<typename CharT, typename Traits>
0283 inline std::basic_ostream<CharT, Traits> &
0284 operator<<(
0285     std::basic_ostream<CharT, Traits> & os,
0286     const boost::safe_numerics::interval<unsigned char> & i
0287 ){
0288     os << "[" << (unsigned)i.l << "," << (unsigned)i.u << "]";
0289     return os;
0290 }
0291
0292 template<typename CharT, typename Traits>
0293 inline std::basic_ostream<CharT, Traits> &
0294 operator<<(
0295     std::basic_ostream<CharT, Traits> & os,
0296     const boost::safe_numerics::interval<signed char> & i
0297 ){
0298     os << "[" << (int)i.l << "," << (int)i.u << "]";
0299     return os;
0300 }
0301
0302 } // std
0303
0304 #endif // BOOST_SAFE_NUMERICS_INTERVAL_HPP