sigma  1.0.0
Loading...
Searching...
No Matches
general_interval.hpp
Go to the documentation of this file.
1#pragma once
3#include <algorithm>
4#include <cmath>
5#include <iostream>
6#include <limits>
7#include <stdexcept>
8#include <string>
9#include <tuple>
10#include <type_traits>
11#include <utility>
12
16
17namespace sigma {
18
35template<typename ValueType>
37public:
39 using value_t = ValueType;
40
43
50 GeneralInterval() = default;
51
60 GeneralInterval(value_t value) : GeneralInterval(value, value) {}
61
72 GeneralInterval(const closure_t& closed) {
73 if(!closed.empty()) {
74 *this = GeneralInterval(closed.lower(), closed.upper());
75 }
76 }
77
93 bool right_open = false);
94
103 value_t width() const { return m_closure_.width(); }
104
111 value_t median() const { return m_closure_.median(); }
112
119 value_t radius() const { return m_closure_.radius(); }
120
127 bool empty() const { return m_closure_.empty(); }
128
136 bool left_open() const { return m_is_left_open_; }
137
144 bool left_closed() const { return !left_open(); }
145
153 bool right_open() const { return m_is_right_open_; }
154
161 bool right_closed() const { return !right_open(); }
162
169 value_t lower() const { return m_closure_.lower(); }
170
177 value_t upper() const { return m_closure_.upper(); }
178
189 const closure_t& closure() const { return m_closure_; }
190
204 bool contains(value_t value) const;
205
215 bool contains(const GeneralInterval& other) const;
216
231
240
241 // -- Arithmetic in-place operators ----------------------------------------
242
253 if(empty()) { return GeneralInterval(); }
254 return GeneralInterval(-upper(), -lower(), right_open(), left_open());
255 }
256
267
276 return *this += -rhs;
277 }
278
291
307
317 std::string print_interval_form() const;
318
319 // -- Arithmetic free functions --------------------------------------------
320 //
321 // These are hidden friends rather than free templates so that an operand
322 // that is a closed Interval or a scalar converts implicitly: template
323 // argument deduction never considers conversions.
324
337 const GeneralInterval& rhs) {
338 return lhs += rhs;
339 }
340
353 const GeneralInterval& rhs) {
354 return lhs -= rhs;
355 }
356
369 const GeneralInterval& rhs) {
370 return lhs *= rhs;
371 }
372
386 const GeneralInterval& rhs) {
387 return lhs /= rhs;
388 }
389
390private:
417 static bool corner_bound_open_(value_t value, value_t ll, value_t lh,
418 value_t hl, value_t hh,
419 const GeneralInterval& lhs,
420 const GeneralInterval& rhs);
421
443 static GeneralInterval from_corners_(const closure_t& result, value_t ll,
444 value_t lh, value_t hl, value_t hh,
445 const GeneralInterval& lhs,
446 const GeneralInterval& rhs,
447 bool zero_attained);
448
463 static GeneralInterval reciprocal_(const GeneralInterval& a);
464
466 closure_t m_closure_;
467
469 bool m_is_left_open_ = false;
470
472 bool m_is_right_open_ = false;
473
474}; // class GeneralInterval
475
476// -- Out-of-line Definitions --------------------------------------------------
477
478template<typename ValueType>
480 bool left_open, bool right_open) :
481 m_closure_(lower, upper),
482 // Infinity is not a real number, so it is never a member
483 m_is_left_open_(left_open || std::isinf(m_closure_.lower())),
484 m_is_right_open_(right_open || std::isinf(m_closure_.upper())) {
485 // A single value in an open interval is actually empty
486 if((m_is_left_open_ || m_is_right_open_) && lower == upper) {
487 *this = GeneralInterval();
488 }
489}
490
491template<typename ValueType>
493 if(!m_closure_.contains(value)) { return false; }
494
495 // Not allowed to be a bound if the interval is open on that side
496 if(left_open() && value == lower()) { return false; }
497 if(right_open() && value == upper()) { return false; }
498
499 return true;
500}
501
502template<typename ValueType>
504 if(other.empty()) { return true; }
505 if(!m_closure_.contains(other.m_closure_)) { return false; }
506
507 // *this and other may share a bound. For each shared bound the choices
508 // are:
509 // *this open and other closed -> not okay
510 // *this open and other open -> okay
511 // *this closed and other closed -> okay
512 // *this closed and other open -> okay
513 if(other.lower() == lower()) {
514 if(left_open() && other.left_closed()) { return false; }
515 }
516 if(other.upper() == upper()) {
517 if(right_open() && other.right_closed()) { return false; }
518 }
519 return true;
520}
521
522template<typename ValueType>
524 const GeneralInterval& other) const {
525 if(empty()) { return other; }
526 if(other.empty()) { return *this; }
527 // The intervals need not share a point: [0, 1) and [1, 2] only touch, but
528 // their union is [0, 2]. What breaks the union is a gap, i.e., bounds that
529 // are separated or that coincide at a point neither interval contains.
530 const auto separated = [](const GeneralInterval& left,
531 const GeneralInterval& right) {
532 if(left.upper() < right.lower()) { return true; }
533 return left.upper() == right.lower() && left.right_open() &&
534 right.left_open();
535 };
536 if(separated(*this, other) || separated(other, *this)) {
537 throw std::domain_error("Intervals do not overlap");
538 }
539 value_t low = lower();
540 value_t hi = upper();
541 bool lower_is_open = false;
542 bool upper_is_open = false;
543 if(lower() < other.lower()) { // *this has the lower bound
544 lower_is_open = left_open();
545 } else if(lower() == other.lower()) {
546 // If both are open, then result is open; otherwise closed
547 lower_is_open = left_open() && other.left_open();
548 } else {
549 low = other.lower();
550 lower_is_open = other.left_open();
551 }
552
553 if(upper() > other.upper()) {
554 upper_is_open = right_open();
555 } else if(upper() == other.upper()) {
556 upper_is_open = right_open() && other.right_open();
557 } else {
558 hi = other.upper();
559 upper_is_open = other.right_open();
560 }
561
562 return GeneralInterval(low, hi, lower_is_open, upper_is_open);
563}
564
565template<typename ValueType>
567 const GeneralInterval& other) const {
568 if(empty() || other.empty()) { return GeneralInterval(); }
569 if(other.upper() < lower() || other.lower() > upper()) {
570 return GeneralInterval();
571 }
572 value_t low = lower();
573 value_t hi = upper();
574 bool lower_is_open = left_open();
575 bool upper_is_open = right_open();
576
577 if(lower() < other.lower()) {
578 low = other.lower();
579 lower_is_open = other.left_open();
580 } else if(lower() == other.lower()) {
581 lower_is_open = left_open() || other.left_open();
582 }
583
584 if(upper() > other.upper()) {
585 hi = other.upper();
586 upper_is_open = other.right_open();
587 } else if(upper() == other.upper()) {
588 upper_is_open = right_open() || other.right_open();
589 }
590 return GeneralInterval(low, hi, lower_is_open, upper_is_open);
591}
592
593template<typename ValueType>
595 const GeneralInterval& rhs) {
596 if(empty()) { return *this = rhs; }
597 if(rhs.empty()) { return *this; }
598 m_closure_ += rhs.m_closure_;
599 m_is_left_open_ = left_open() || rhs.left_open();
600 m_is_right_open_ = right_open() || rhs.right_open();
601 // The sum may have overflowed to an infinite bound
602 return *this = GeneralInterval(lower(), upper(), left_open(), right_open());
603}
604
605template<typename ValueType>
606bool GeneralInterval<ValueType>::corner_bound_open_(
607 value_t value, value_t ll, value_t lh, value_t hl, value_t hh,
608 const GeneralInterval& lhs, const GeneralInterval& rhs) {
609 bool is_open = true;
610 if(value == ll) { is_open &= lhs.left_open() || rhs.left_open(); }
611 if(value == lh) { is_open &= lhs.left_open() || rhs.right_open(); }
612 if(value == hl) { is_open &= lhs.right_open() || rhs.left_open(); }
613 if(value == hh) { is_open &= lhs.right_open() || rhs.right_open(); }
614 return is_open;
615}
616
617template<typename ValueType>
618GeneralInterval<ValueType> GeneralInterval<ValueType>::from_corners_(
619 const closure_t& result, value_t ll, value_t lh, value_t hl, value_t hh,
620 const GeneralInterval& lhs, const GeneralInterval& rhs, bool zero_attained) {
621 // fmin and fmax skip the NaN of a zero times an infinite bound, which is
622 // not a corner the result can come from.
623 auto low = std::fmin(std::fmin(ll, lh), std::fmin(hl, hh));
624 auto high = std::fmax(std::fmax(ll, lh), std::fmax(hl, hh));
625
626 // An attained zero is checked against the result rather than the corners,
627 // which are all NaN for, e.g., [0, 0] * (-inf, inf).
628 bool lower_is_open = !(zero_attained && result.lower() == value_t(0)) &&
629 corner_bound_open_(low, ll, lh, hl, hh, lhs, rhs);
630 bool upper_is_open = !(zero_attained && result.upper() == value_t(0)) &&
631 corner_bound_open_(high, ll, lh, hl, hh, lhs, rhs);
632
633 return GeneralInterval(result.lower(), result.upper(), lower_is_open,
634 upper_is_open);
635}
636
637template<typename ValueType>
639 const GeneralInterval& rhs) {
640 if(empty() || rhs.empty()) { return *this = GeneralInterval(); }
641
642 auto product = m_closure_ * rhs.m_closure_;
643
644 auto ll = lower() * rhs.lower();
645 auto lh = lower() * rhs.upper();
646 auto hl = upper() * rhs.lower();
647 auto hh = upper() * rhs.upper();
648
649 const bool zero_attained = contains(value_t(0)) || rhs.contains(value_t(0));
650 return *this =
651 from_corners_(product, ll, lh, hl, hh, *this, rhs, zero_attained);
652}
653
654template<typename ValueType>
655GeneralInterval<ValueType> GeneralInterval<ValueType>::reciprocal_(
656 const GeneralInterval& a) {
657 using interval_t = detail_::boost_interval_t<value_t>;
658 constexpr auto inf = std::numeric_limits<value_t>::infinity();
659 const interval_t one(value_t(1));
660
661 // A zero bound is necessarily an open one here, and the reciprocal runs
662 // off to infinity in that direction. Everything else is a directed
663 // division by a point.
664 value_t low =
665 a.upper() == value_t(0) ? -inf : (one / interval_t(a.upper())).lower();
666 value_t high =
667 a.lower() == value_t(0) ? inf : (one / interval_t(a.lower())).upper();
668
669 // The reciprocal is decreasing, so the bounds trade places
670 return GeneralInterval(low, high, a.right_open(), a.left_open());
671}
672
673template<typename ValueType>
675 const GeneralInterval& rhs) {
676 if(empty() || rhs.empty()) { return *this = GeneralInterval(); }
677 if(rhs.contains(value_t(0))) {
678 throw std::domain_error("Division by zero");
679 }
680
681 // The closure of a divisor bounded by an open zero contains zero, so
682 // closed division would reject it. Multiplying by the reciprocal keeps the
683 // information at the cost of one extra rounding.
684 if(rhs.lower() == value_t(0) || rhs.upper() == value_t(0)) {
685 return *this *= reciprocal_(rhs);
686 }
687
688 auto quotient = m_closure_ / rhs.m_closure_;
689
690 auto ll = lower() / rhs.lower();
691 auto lh = lower() / rhs.upper();
692 auto hl = upper() / rhs.lower();
693 auto hh = upper() / rhs.upper();
694
695 // A quotient is zero exactly when its dividend is
696 const bool zero_attained = contains(value_t(0));
697 return *this =
698 from_corners_(quotient, ll, lh, hl, hh, *this, rhs, zero_attained);
699}
700
701template<typename ValueType>
703 if(empty()) { return "[∅]"; }
704 std::string left_open_str = left_open() ? "(" : "[";
705 std::string right_open_str = right_open() ? ")" : "]";
706
707 return left_open_str + std::to_string(lower()) + ", " +
708 std::to_string(upper()) + right_open_str;
709}
710
711// -- Utility functions --------------------------------------------------------
712
725template<typename ValueType>
726std::ostream& operator<<(std::ostream& os,
728 return os << i.closure();
729}
730
743template<typename T1, typename T2>
745 const GeneralInterval<T2>& rhs) {
746 if constexpr(!std::is_same_v<T1, T2>) return false;
747 if(lhs.left_open() != rhs.left_open()) { return false; }
748 if(lhs.right_open() != rhs.right_open()) { return false; }
749 return lhs.closure() == rhs.closure();
750}
751
762template<typename T1, typename T2>
764 const GeneralInterval<T2>& rhs) {
765 return !(lhs == rhs);
766}
767
787template<typename T>
788bool operator<(const GeneralInterval<T>& lhs, const GeneralInterval<T>& rhs) {
789 if(lhs.closure() < rhs.closure()) { return true; }
790 if(rhs.closure() < lhs.closure()) { return false; }
791 return std::make_tuple(lhs.left_open(), lhs.right_open()) <
792 std::make_tuple(rhs.left_open(), rhs.right_open());
793}
794
797template<typename T>
798bool operator>(const GeneralInterval<T>& lhs, const GeneralInterval<T>& rhs) {
799 return rhs < lhs;
800}
801
804template<typename T>
806 return !(rhs < lhs);
807}
808
811template<typename T>
813 return !(lhs < rhs);
814}
815
835template<typename T>
837 typename GeneralInterval<T>::value_t point) {
838 if(a.empty()) { return GeneralInterval<T>(point); }
839 if(a.contains(point)) { return a; }
840 if(point <= a.lower()) {
841 return GeneralInterval<T>(point, a.upper(), false, a.right_open());
842 }
843 return GeneralInterval<T>(a.lower(), point, a.left_open(), false);
844}
845
848
851
852} // namespace sigma
853
854namespace std {
855
857template<typename ValueType>
858struct hash<sigma::GeneralInterval<ValueType>> {
861 std::size_t seed = std::hash<sigma::Interval<ValueType>>()(i.closure());
862 std::size_t openness =
863 (i.left_open() ? 1 : 0) + (i.right_open() ? 2 : 0);
864 seed ^= openness + 0x9e3779b9 + (seed << 6) + (seed >> 2);
865 return seed;
866 }
867};
868
869} // namespace std
870
Models an interval whose bounds may be open.
Definition general_interval.hpp:36
Interval< value_t > closure_t
Definition general_interval.hpp:42
GeneralInterval & operator/=(const GeneralInterval &rhs)
In-place division by another interval.
Definition general_interval.hpp:674
value_t width() const
Returns the distance between the interval's bounds.
Definition general_interval.hpp:103
const closure_t & closure() const
Returns the closure of the interval.
Definition general_interval.hpp:189
GeneralInterval(value_t lower, value_t upper, bool left_open=false, bool right_open=false)
Construct an interval from two bounds and their openness.
Definition general_interval.hpp:479
bool contains(value_t value) const
Whether a scalar lies in this interval.
Definition general_interval.hpp:492
GeneralInterval & operator+=(const GeneralInterval &rhs)
In-place addition of another interval.
Definition general_interval.hpp:594
bool operator!=(const GeneralInterval< T1 > &lhs, const GeneralInterval< T2 > &rhs)
Compare two intervals for inequality.
Definition general_interval.hpp:763
GeneralInterval()=default
Default constructor.
friend GeneralInterval operator+(GeneralInterval lhs, const GeneralInterval &rhs)
Addition of two intervals.
Definition general_interval.hpp:336
std::ostream & operator<<(std::ostream &os, const GeneralInterval< ValueType > &i)
Overload stream insertion to print an interval.
Definition general_interval.hpp:726
bool empty() const
Is *this the empty interval?
Definition general_interval.hpp:127
bool contains(const GeneralInterval &other) const
Is other fully contained in this interval?
Definition general_interval.hpp:503
bool left_open() const
Definition general_interval.hpp:136
bool right_closed() const
Is upper() contained in the interval?
Definition general_interval.hpp:161
bool right_open() const
Definition general_interval.hpp:153
friend GeneralInterval operator*(GeneralInterval lhs, const GeneralInterval &rhs)
Multiplication of two intervals.
Definition general_interval.hpp:368
value_t radius() const
Returns the half-width of the interval.
Definition general_interval.hpp:119
std::string print_interval_form() const
Print the interval in interval form.
Definition general_interval.hpp:702
GeneralInterval & operator-=(const GeneralInterval &rhs)
In-place subtraction of another interval.
Definition general_interval.hpp:275
float value_t
Definition general_interval.hpp:39
GeneralInterval operator-() const
Negation of an interval.
Definition general_interval.hpp:252
GeneralInterval< T > widen(const GeneralInterval< T > &a, typename GeneralInterval< T >::value_t point)
Widens an interval just enough to contain a point.
Definition general_interval.hpp:836
friend GeneralInterval operator-(GeneralInterval lhs, const GeneralInterval &rhs)
Subtraction of two intervals.
Definition general_interval.hpp:352
friend GeneralInterval operator/(GeneralInterval lhs, const GeneralInterval &rhs)
Division of two intervals.
Definition general_interval.hpp:385
GeneralInterval set_intersection(const GeneralInterval &other) const
Returns the intersection of this interval and another interval.
Definition general_interval.hpp:566
GeneralInterval & operator*=(const GeneralInterval &rhs)
In-place multiplication by another interval.
Definition general_interval.hpp:638
bool operator==(const GeneralInterval< T1 > &lhs, const GeneralInterval< T2 > &rhs)
Compare two intervals for equality.
Definition general_interval.hpp:744
GeneralInterval set_union(const GeneralInterval &other) const
Returns the union of this interval and another interval.
Definition general_interval.hpp:523
GeneralInterval(const closure_t &closed)
Construct from a closed interval.
Definition general_interval.hpp:72
bool left_closed() const
Is lower() contained in the interval?
Definition general_interval.hpp:144
bool operator<(const GeneralInterval< T > &lhs, const GeneralInterval< T > &rhs)
Orders two intervals, primarily by their median.
Definition general_interval.hpp:788
bool operator<=(const GeneralInterval< T > &lhs, const GeneralInterval< T > &rhs)
Same ordering as operator<, negated.
Definition general_interval.hpp:805
bool operator>=(const GeneralInterval< T > &lhs, const GeneralInterval< T > &rhs)
Same ordering as operator<, negated and reversed.
Definition general_interval.hpp:812
GeneralInterval(value_t value)
Construct a degenerate interval from a single value.
Definition general_interval.hpp:60
value_t median() const
Returns the midpoint of the interval.
Definition general_interval.hpp:111
bool operator>(const GeneralInterval< T > &lhs, const GeneralInterval< T > &rhs)
Same ordering as operator<, with the operands reversed.
Definition general_interval.hpp:798
value_t lower() const
Definition general_interval.hpp:169
value_t upper() const
Definition general_interval.hpp:177
Models a closed numeric interval.
Definition interval.hpp:29
value_t upper() const
Returns the upper bound of the interval.
Definition interval.hpp:127
value_t lower() const
Returns the lower bound of the interval.
Definition interval.hpp:116
bool empty() const
Is *this the empty interval?
Definition interval.hpp:108
Convenience header for general interval operations.
Defines the Interval class.
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
GeneralInterval< double > GIDouble
Typedef for a general interval of doubles.
Definition general_interval.hpp:850
GeneralInterval< float > GIFloat
Typedef for a general interval of floats.
Definition general_interval.hpp:847
size_t operator()(const sigma::GeneralInterval< ValueType > &i) const
Hashes the closure and then folds in the openness of each bound.
Definition general_interval.hpp:860