sigma  1.0.0
Loading...
Searching...
No Matches
interval.hpp
Go to the documentation of this file.
1#pragma once
3#include <algorithm>
4#include <boost/numeric/interval.hpp>
5#include <cmath>
6#include <iostream>
7#include <optional>
8#include <tuple>
9#include <type_traits>
10
14
15namespace sigma {
16
28template<typename ValueType>
29class Interval {
30public:
32 using value_t = ValueType;
33
41
50 Interval(value_t value) : Interval(value, value) {}
51
61 m_interval_(interval_t(std::min(lower, upper), std::max(lower, upper))) {}
62
73 value_t width() const {
74 assert_not_empty_();
75 return boost::numeric::width(*m_interval_);
76 }
77
84 value_t median() const {
85 assert_not_empty_();
86 return boost::numeric::median(*m_interval_);
87 }
88
98 value_t radius() const { return width() / value_t{2}; }
99
108 bool empty() const { return !m_interval_; }
109
116 value_t lower() const {
117 assert_not_empty_();
118 return m_interval_->lower();
119 }
120
127 value_t upper() const {
128 assert_not_empty_();
129 return m_interval_->upper();
130 }
131
144 bool contains(value_t value) const {
145 return !empty() && std::isfinite(value) && lower() <= value &&
146 value <= upper();
147 }
148
158 bool contains(const Interval& other) const {
159 if(other.empty()) { return true; }
160 // Compare bounds directly, since contains(value) rejects an infinite
161 // bound and an unbounded interval must still contain itself.
162 return !empty() && lower() <= other.lower() && other.upper() <= upper();
163 }
164
177 Interval set_union(const Interval& other) const;
178
189 Interval set_intersection(const Interval& other) const;
190
191 // -- Arithmetic in-place operators ----------------------------------------
192
202 if(empty()) { return Interval(); }
203 return Interval(-upper(), -lower());
204 }
205
214
222 Interval& operator+=(value_t rhs) { return *this += Interval(rhs, rhs); }
223
231 Interval& operator-=(const Interval& rhs) { return *this += -rhs; }
232
240 Interval& operator-=(value_t rhs) { return *this -= Interval(rhs, rhs); }
241
250
258 Interval& operator*=(value_t rhs) { return *this *= Interval(rhs); }
259
269
277 Interval& operator/=(value_t rhs) { return *this /= Interval(rhs, rhs); }
278
287 std::string print_interval_form() const;
288
289private:
292 void assert_not_empty_() const {
293 if(empty()) { throw std::domain_error("Interval is empty"); }
294 }
295
298 using interval_t = detail_::boost_interval_t<value_t>;
299
301 std::optional<interval_t> m_interval_;
302
303}; // class Interval
304
305// -- Out-of-line Definitions --------------------------------------------------
306
307template<typename ValueType>
309 const Interval& other) const {
310 if(empty()) { return other; }
311 if(other.empty()) { return *this; }
312 if(set_intersection(other).empty()) {
313 throw std::domain_error("Intervals do not overlap");
314 }
315 return Interval(std::min(lower(), other.lower()),
316 std::max(upper(), other.upper()));
317}
318
319template<typename ValueType>
321 const Interval& other) const {
322 if(empty() || other.empty()) { return Interval(); }
323 if(other.upper() < lower() || other.lower() > upper()) {
324 return Interval();
325 }
326 return Interval(std::max(lower(), other.lower()),
327 std::min(upper(), other.upper()));
328}
329
330template<typename ValueType>
332 if(empty()) {
333 return *this = rhs;
334 } else if(rhs.empty()) {
335 return *this;
336 } else {
337 m_interval_ = *m_interval_ + *rhs.m_interval_;
338 }
339 return *this;
340}
341
342template<typename ValueType>
344 /* Putting this here in case it's helpful for optimizing.
345 * Given two intervals X = [a, b] and Y = [c, d], the product X * Y is:
346 * [min(ac, ad, bc, bd), max(ac, ad, bc, bd)]. Thus the entire product
347 * is determined by four sub-products: ac, ad, bc, and bd. Simple
348 * combinatorics suggests that there are 16 possible products for X*Y,
349 * (i.e., chose one sub-product for the new lower bound and one for the
350 * new upper bound).
351 *
352 * If we know that a < b and c < d, i.e., our intervals are not points,
353 * we can immediately rule out eight products:
354 *
355 * - [ac, ac], [ad, ad], [bc, bc], and [bd,bd].
356 * - [ac, ad], [ac, bc], [bd, bc], and [bd,ad].
357 *
358 * Proofs that these products are impossible are given below.
359 *
360 * To prove the first four products are impossible consider [ac, ac],
361 * which implies:
362 *
363 * - ac <= ad <= ac,
364 * - ac <= bc <= ac, and
365 * -ac <= bd <= ac
366 *
367 * The first inequality means c == d, the second means a == b. Which
368 * means X = [a, a] and Y = [c, c], i.e. X and Y must be points. This
369 * contridicts our assumption that X and Y are not points and thus these
370 * four products will never appear. Similar logic holds for the other
371 * three products of the form [xy, xy].
372 *
373 * Now consider the product [ac, ad]. This implies:
374 *
375 * - ac <= bc <= ad, and
376 * - ac <= bd <= ad
377 *
378 * If a is negative, then d <= bc/a <= c, which is not possible with the
379 * assumption c < d. If a is zero, the product [ac, ad] is [0, 0], which
380 * means bc and bd must be zero. b can't be zero because then
381 * X = [0, 0]. This would then mean that both c and d must be zero, but
382 * c and d both can't be zero because then Y = [0, 0]. Thus a must be
383 * positive. If a is positive, then so is b. If c >= 0 then d is
384 * positive and then we have that bd > ad, which is not consistent with
385 * bd <= ad. c also can't be negative because then bc < ac. We thus
386 * conclude that [ac, ad] is not possible.
387 *
388 * The remaining three proofs follow similarly. Let "target interval"
389 * refer to the interval we are proving is not possible. Then the proof
390 * proceeds by showing:
391 *
392 * - We get two inequalities by forcing the remaining two sub-products
393 * to be bounded by the target interval. Above this showed that bc and
394 * bd must be in the interval [ac, ad]. We term these the "implicit
395 * sub-products" because they do not show up explicitly in the target
396 * interval.
397 * - One of X or Y's bounds will appear twice in the target interval. We
398 * term this the "common bound". Above this bound was "a".
399 * - If the common bound is the lower bound of X(Y) try assuming the
400 * commonbound is negative and dividing the inequalities by it. If the
401 * common bound is the upper bound, instead divide the inequalities by
402 * the positive of it. This will cause one of the two inequalities to
403 * be a contradiction eliminating that possibility. Above this ruled
404 * out "a" being negative.
405 * - The common bound can't be zero otherwise X and Y collapse to
406 * point intervals.
407 * - This means the common bound must be positive (negative) for a lower
408 * (upper) bound. In turn, the "other bound" must be positive
409 * (negative) too. Above this "other bound" was "b".
410 * - The implicit sub-products will share other bound. If other bound is
411 * the upper (lower) bound, then assume that the lower (upper) bound
412 * of the other interval is positive (negative) or zero. This
413 * will force the upper (lower) bound of the other interval to be
414 * positive (negative) too. All bounds will now have the same sign
415 * and violate one of the inequalities.
416 * - The last possibility is then that the lower (upper) bound of the
417 * other interval has the opposite sign as the common bound. This too
418 * will violate one of the inequalities and we conclude that the
419 * target interval is not possible.
420 */
421
422 if(empty() || rhs.empty()) { return *this = Interval(); }
423
424 // Boost rounds each of the four sub-products outward before taking the
425 // extremes.
426 m_interval_ = *m_interval_ * *rhs.m_interval_;
427 return *this;
428}
429
430template<typename ValueType>
432 if(empty() || rhs.empty()) { return *this = Interval(); }
433 if(rhs.contains(value_t(0))) {
434 throw std::domain_error("Division by zero");
435 }
436 m_interval_ = *m_interval_ / *rhs.m_interval_;
437 return *this;
438}
439
440template<typename ValueType>
442 if(empty()) { return "[∅]"; }
443 return "[" + std::to_string(lower()) + ", " + std::to_string(upper()) + "]";
444}
445
446// -- Utility functions --------------------------------------------------------
447
460template<typename ValueType>
461std::ostream& operator<<(std::ostream& os, const Interval<ValueType>& i) {
462 if(i.empty()) {
463 os << "∅";
464 return os;
465 }
466 os << i.median() << "+/-" << i.radius();
467 return os;
468}
469
480template<typename T1, typename T2>
481bool operator==(const Interval<T1>& lhs, const Interval<T2>& rhs) {
482 if constexpr(!std::is_same_v<T1, T2>) return false;
483 if(lhs.empty() && rhs.empty()) { return true; }
484 if(lhs.empty() || rhs.empty()) { return false; }
485 return lhs.lower() == rhs.lower() && lhs.upper() == rhs.upper();
486}
487
498template<typename T1, typename T2>
499bool operator!=(const Interval<T1>& lhs, const Interval<T2>& rhs) {
500 return !(lhs == rhs);
501}
502
525template<typename T>
526bool operator<(const Interval<T>& lhs, const Interval<T>& rhs) {
527 if(rhs.empty()) { return false; }
528 if(lhs.empty()) { return true; }
529 return std::make_tuple(lhs.median(), lhs.lower(), lhs.upper()) <
530 std::make_tuple(rhs.median(), rhs.lower(), rhs.upper());
531}
532
535template<typename T>
536bool operator>(const Interval<T>& lhs, const Interval<T>& rhs) {
537 return rhs < lhs;
538}
539
542template<typename T>
543bool operator<=(const Interval<T>& lhs, const Interval<T>& rhs) {
544 return !(rhs < lhs);
545}
546
549template<typename T>
550bool operator>=(const Interval<T>& lhs, const Interval<T>& rhs) {
551 return !(lhs < rhs);
552}
553
569template<typename T>
571 if(a.empty()) { return Interval<T>(point); }
572 if(point < a.lower()) { return Interval<T>(point, a.upper()); }
573 if(point > a.upper()) { return Interval<T>(a.lower(), point); }
574 return a;
575}
576
577// -- Arithmetic free functions ------------------------------------------------
578
590template<typename T>
592 return lhs += rhs;
593}
594
596template<typename T>
598 return lhs += rhs;
599}
600
602template<typename T>
604 return rhs + lhs;
605}
606
618template<typename T>
620 return lhs -= rhs;
621}
622
624template<typename T>
626 return lhs -= rhs;
627}
628
630template<typename T>
632 return Interval<T>(lhs, lhs) -= rhs;
633}
634
646template<typename T>
648 return lhs *= rhs;
649}
650
652template<typename T>
654 return lhs *= rhs;
655}
656
658template<typename T>
660 return rhs * lhs;
661}
662
677template<typename T>
679 return lhs /= rhs;
680}
681
683template<typename T>
685 if(rhs == 0) { throw std::domain_error("Division by zero"); }
686 return lhs /= Interval<T>(rhs);
687}
688
690template<typename T>
692 if(rhs.empty()) { return rhs; }
693 if(rhs.contains(0)) { throw std::domain_error("Division by zero"); }
694 return Interval<T>(lhs) / rhs;
695}
696
699
702
703} // namespace sigma
704
705namespace std {
706
708template<typename ValueType>
709struct hash<sigma::Interval<ValueType>> {
713 size_t operator()(const sigma::Interval<ValueType>& i) const {
714 if(i.empty()) { return 0; }
715 std::size_t hash_low = std::hash<ValueType>()(i.lower());
716 std::size_t hash_high = std::hash<ValueType>()(i.upper());
717 std::size_t seed = hash_low;
718 seed ^= hash_high + 0x9e3779b9 + (seed << 6) + (seed >> 2);
719 return seed;
720 }
721};
722
723} // namespace std
724
Models a closed numeric interval.
Definition interval.hpp:29
Interval & operator-=(const Interval &rhs)
In-place subtraction of another interval.
Definition interval.hpp:231
Interval set_intersection(const Interval &other) const
Returns the intersection of this interval and another interval.
Definition interval.hpp:320
value_t median() const
Returns the midpoint of the interval.
Definition interval.hpp:84
value_t width() const
Returns the distance between the interval's bounds.
Definition interval.hpp:73
Interval< T > operator/(Interval< T > lhs, const Interval< T > &rhs)
Division of two intervals.
Definition interval.hpp:678
Interval & operator-=(value_t rhs)
In-place subtraction of a scalar.
Definition interval.hpp:240
value_t value_t
Definition interval.hpp:32
Interval & operator+=(value_t rhs)
In-place addition of a scalar.
Definition interval.hpp:222
Interval< T > widen(const Interval< T > &a, typename Interval< T >::value_t point)
Widens an interval just enough to contain a point.
Definition interval.hpp:570
value_t upper() const
Definition interval.hpp:127
Interval< T > operator-(Interval< T > lhs, const Interval< T > &rhs)
Subtraction of two intervals.
Definition interval.hpp:619
std::string print_interval_form() const
Print the interval in interval form.
Definition interval.hpp:441
value_t lower() const
Definition interval.hpp:116
Interval(value_t lower, value_t upper)
Construct an interval from two bounds.
Definition interval.hpp:60
Interval & operator/=(value_t rhs)
In-place division by a scalar.
Definition interval.hpp:277
Interval set_union(const Interval &other) const
Returns the union of this interval and another interval.
Definition interval.hpp:308
bool contains(value_t value) const
Whether a scalar lies in this interval.
Definition interval.hpp:144
Interval & operator*=(const Interval &rhs)
In-place multiplication by another interval.
Definition interval.hpp:343
bool operator==(const Interval< T1 > &lhs, const Interval< T2 > &rhs)
Compare two intervals for equality.
Definition interval.hpp:481
std::ostream & operator<<(std::ostream &os, const Interval< ValueType > &i)
Overload stream insertion to print an interval.
Definition interval.hpp:461
Interval()
Default constructor.
Definition interval.hpp:40
value_t radius() const
Returns the half-width of the interval.
Definition interval.hpp:98
Interval operator-() const
Negation of an interval.
Definition interval.hpp:201
bool operator>=(const Interval< T > &lhs, const Interval< T > &rhs)
Same ordering as operator<, negated and reversed.
Definition interval.hpp:550
Interval & operator/=(const Interval &rhs)
In-place division by another interval.
Definition interval.hpp:431
bool empty() const
Is *this the empty interval?
Definition interval.hpp:108
Interval & operator+=(const Interval &rhs)
In-place addition of another interval.
Definition interval.hpp:331
bool contains(const Interval &other) const
Is other fully contained in this interval?
Definition interval.hpp:158
Interval< T > operator*(Interval< T > lhs, const Interval< T > &rhs)
Multiplication of two intervals.
Definition interval.hpp:647
bool operator<=(const Interval< T > &lhs, const Interval< T > &rhs)
Same ordering as operator<, negated.
Definition interval.hpp:543
bool operator<(const Interval< T > &lhs, const Interval< T > &rhs)
Orders two intervals, primarily by their median.
Definition interval.hpp:526
Interval & operator*=(value_t rhs)
In-place multiplication by a scalar.
Definition interval.hpp:258
bool operator>(const Interval< T > &lhs, const Interval< T > &rhs)
Same ordering as operator<, with the operands reversed.
Definition interval.hpp:536
Interval< T > operator+(Interval< T > lhs, const Interval< T > &rhs)
Addition of two intervals.
Definition interval.hpp:591
Interval(value_t value)
Construct an interval from a single value.
Definition interval.hpp:50
bool operator!=(const Interval< T1 > &lhs, const Interval< T2 > &rhs)
Compare two intervals for inequality.
Definition interval.hpp:499
Components for compatibility with Eigen.
Convenience header for interval operations.
boost::numeric::interval< T, interval_policies_t< T > > boost_interval_t
The boost interval type sigma::Interval wraps.
Definition policies.hpp:485
The primary namespace for the sigma library.
Definition affine.hpp:12
Interval< T > operator/(Interval< T > lhs, T rhs)
Definition interval.hpp:684
Interval< float > IFloat
Typedef for an interval of floats.
Definition interval.hpp:698
Interval< T > operator-(Interval< T > lhs, T rhs)
Definition interval.hpp:625
Interval< T > operator*(Interval< T > lhs, T rhs)
Definition interval.hpp:653
Interval< T > operator+(Interval< T > lhs, T rhs)
Definition interval.hpp:597
Interval< double > IDouble
Typedef for an interval of doubles.
Definition interval.hpp:701
Rounding and checking policies used by the boost interval sigma wraps.
size_t operator()(const sigma::Interval< ValueType > &i) const
Definition interval.hpp:713