carl  24.04
Computer ARithmetic Library
SetTheory.h
Go to the documentation of this file.
1 #pragma once
2 
3 #include "Interval.h"
4 
5 namespace carl {
6 
7 /**
8  * Calculates the complement in a set-theoretic manner (can result
9  * in two distinct intervals).
10  * @param interval Interval.
11  * @param resA Result a.
12  * @param resB Result b.
13  * @return True, if the result is twofold.
14  */
15 template<typename Number>
16 bool set_complement(const Interval<Number>& interval, Interval<Number>& resA, Interval<Number>& resB) {
17  assert(interval.is_consistent());
18 
19  if (interval.lower_bound_type() == BoundType::INFTY) {
20  if (interval.upper_bound_type() == BoundType::INFTY) {
21  resA = Interval<Number>::empty_interval();
22  resB = Interval<Number>::empty_interval();
23  return false;
24  } else {
25  resA = Interval<Number>(interval.upper(), get_other_bound_type(interval.upper_bound_type()), 0, BoundType::INFTY);
26  resB = Interval<Number>::empty_interval();
27  return false;
28  }
29  } else {
30  if (interval.upper_bound_type() == BoundType::INFTY) {
31  resA = Interval<Number>(0, BoundType::INFTY, interval.lower(), get_other_bound_type(interval.lower_bound_type()));
32  resB = Interval<Number>::empty_interval();
33  return false;
34  } else {
35  resA = Interval<Number>(0, BoundType::INFTY, interval.lower(), get_other_bound_type(interval.lower_bound_type()));
36  resB = Interval<Number>(interval.upper(), get_other_bound_type(interval.upper_bound_type()), 0, BoundType::INFTY);
37  return true;
38  }
39  }
40 }
41 
42 /**
43  * Calculates the difference of two intervals in a set-theoretic manner:
44  * lhs \ rhs (can result in two distinct intervals).
45  * @param lhs First interval.
46  * @param rhs Second interval.
47  * @param resA Result a.
48  * @param resB Result b.
49  * @return True, if the result is twofold.
50  */
51 template<typename Number>
52 bool set_difference(const Interval<Number>& lhs, const Interval<Number>& rhs, Interval<Number>& resA, Interval<Number>& resB) {
53  assert(lhs.is_consistent() && rhs.is_consistent());
54 
55  if (rhs.is_empty()) {
56  resA = lhs;
57  resB = Interval<Number>::empty_interval();
58  return false;
59  }
60  if (lhs.upper_bound() < rhs.lower_bound()) {
61  resA = lhs;
62  resB = Interval<Number>::empty_interval();
63  return false;
64  }
65  if (rhs.upper_bound() < lhs.lower_bound()) {
66  resA = lhs;
67  resB = Interval<Number>::empty_interval();
68  return false;
69  }
70  if (lhs.lower_bound() < rhs.lower_bound()) {
71  if (lhs.upper_bound() < rhs.upper_bound()) {
72  resA = Interval<Number>(lhs.lower_bound(), rhs.lower_bound());
73  return false;
74  } else {
75  resA = Interval<Number>(lhs.lower_bound(), rhs.lower_bound());
76  resB = Interval<Number>(rhs.upper_bound(), lhs.upper_bound());
77  return !resB.is_empty();
78  }
79  } else {
80  if (lhs.upper_bound() < rhs.upper_bound()) {
81  resA = Interval<Number>::empty_interval();
82  resB = Interval<Number>::empty_interval();
83  return false;
84  } else {
85  resA = Interval<Number>(rhs.upper_bound(), lhs.upper_bound());
86  resB = Interval<Number>::empty_interval();
87  return false;
88  }
89  }
90 }
91 
92 /**
93  * Intersects two intervals in a set-theoretic manner.
94  * @param lhs Lefthand side.
95  * @param rhs Righthand side.
96  * @return Result.
97  */
98 template<typename Number>
99 Interval<Number> set_intersection(const Interval<Number>& lhs, const Interval<Number>& rhs) {
100  assert(lhs.is_consistent() && rhs.is_consistent());
101 
102  if (lhs.lower_bound() < rhs.lower_bound()) {
103  if (lhs.upper_bound() < rhs.upper_bound()) {
104  return Interval<Number>(rhs.lower_bound(), lhs.upper_bound());
105  } else {
106  return rhs;
107  }
108  } else {
109  if (lhs.upper_bound() < rhs.upper_bound()) {
110  return lhs;
111  } else {
112  return Interval<Number>(lhs.lower_bound(), rhs.upper_bound());
113  }
114  }
115 }
116 
117 template<typename Number>
118 bool set_have_intersection(const Interval<Number>& lhs, const Interval<Number>& rhs) {
119  if (lhs.lower_bound() <= rhs.lower_bound() && rhs.lower_bound() <= lhs.upper_bound()) return true;
120  if (rhs.lower_bound() <= lhs.lower_bound() && lhs.lower_bound() <= rhs.upper_bound()) return true;
121  return false;
122 }
123 
124 /**
125  * Checks whether lhs is a proper subset of rhs.
126  */
127 template<typename Number>
128 bool set_is_proper_subset(const Interval<Number>& lhs, const Interval<Number>& rhs) {
129  assert(lhs.is_consistent() && rhs.is_consistent());
130 
131  if (lhs.is_empty()) return !rhs.is_empty();
132  if (lhs.lower_bound() < rhs.lower_bound()) return false;
133  if (rhs.upper_bound() < lhs.upper_bound()) return false;
134  if (rhs.lower_bound() < lhs.lower_bound()) return true;
135  if (lhs.upper_bound() < rhs.upper_bound()) return true;
136  return false;
137 }
138 
139 /**
140  * Checks whether lhs is a subset of rhs.
141  */
142 template<typename Number>
143 bool set_is_subset(const Interval<Number>& lhs, const Interval<Number>& rhs) {
144  assert(lhs.is_consistent() && rhs.is_consistent());
145 
146  if (lhs.is_empty()) return true;
147  if (lhs.lower_bound() < rhs.lower_bound()) return false;
148  if (rhs.upper_bound() < lhs.upper_bound()) return false;
149  return true;
150 }
151 
152 /**
153  * Calculates the symmetric difference of two intervals in a
154  * set-theoretic manner (can result in two distinct intervals).
155  * @param lhs First interval.
156  * @param rhs Second interval.
157  * @param resA Result a.
158  * @param resB Result b.
159  * @return True, if the result is twofold.
160  */
161 template<typename Number>
162 bool set_symmetric_difference(const Interval<Number>& lhs, const Interval<Number>& rhs, Interval<Number>& resA, Interval<Number>& resB) {
163  assert(lhs.is_consistent() && rhs.is_consistent());
164 
165  auto intersection = set_intersection(lhs, rhs);
166  if (intersection.is_empty()) {
167  resA = lhs;
168  resB = rhs;
169  return true;
170  } else {
171  Interval<Number> tmp;
172  bool res = set_union(lhs, rhs, tmp, tmp);
173  assert(!res);
174  return set_difference(tmp, intersection, resA, resB);
175  }
176 }
177 
178 /**
179  * Computes the union of two intervals (can result in two distinct intervals).
180  * @param lhs First interval.
181  * @param rhs Second interval.
182  * @param resA Result a.
183  * @param resB Result b.
184  * @return True, if the result is twofold.
185  */
186 template<typename Number>
187 bool set_union(const Interval<Number>& lhs, const Interval<Number>& rhs, Interval<Number>& resA, Interval<Number>& resB) {
188  assert(lhs.is_consistent() && rhs.is_consistent());
189 
190  if (carl::bounds_connect(lhs.upper_bound(), rhs.lower_bound())) {
191  resA = Interval<Number>(lhs.lower_bound(), rhs.upper_bound());
192  resB = Interval<Number>::empty_interval();
193  return false;
194  }
195  if (carl::bounds_connect(rhs.upper_bound(), lhs.lower_bound())) {
196  resA = Interval<Number>(rhs.lower_bound(), lhs.upper_bound());
197  resB = Interval<Number>::empty_interval();
198  return false;
199  }
200  if (lhs.upper_bound() < rhs.lower_bound()) {
201  resA = lhs;
202  resB = rhs;
203  return true;
204  }
205  if (rhs.upper_bound() < lhs.lower_bound()) {
206  resA = rhs;
207  resB = lhs;
208  return true;
209  }
210  if (lhs.lower_bound() < rhs.lower_bound()) {
211  if (lhs.upper_bound() < rhs.upper_bound()) {
212  resA = Interval<Number>(lhs.lower_bound(), rhs.upper_bound());
213  } else {
214  resA = lhs;
215  }
216  } else {
217  if (lhs.upper_bound() < rhs.upper_bound()) {
218  resA = rhs;
219  } else {
220  resA = Interval<Number>(rhs.lower_bound(), lhs.upper_bound());
221  }
222  }
223  resB = Interval<Number>::empty_interval();
224  return false;
225 }
226 
227 }
carl
carl is the main namespace for the library.
carl::set_symmetric_difference
bool set_symmetric_difference(const Interval< Number > &lhs, const Interval< Number > &rhs, Interval< Number > &resA, Interval< Number > &resB)
Calculates the symmetric difference of two intervals in a set-theoretic manner (can result in two dis...
Definition: SetTheory.h:162
carl::set_union
bool set_union(const Interval< Number > &lhs, const Interval< Number > &rhs, Interval< Number > &resA, Interval< Number > &resB)
Computes the union of two intervals (can result in two distinct intervals).
Definition: SetTheory.h:187
carl::set_is_proper_subset
bool set_is_proper_subset(const Interval< Number > &lhs, const Interval< Number > &rhs)
Checks whether lhs is a proper subset of rhs.
Definition: SetTheory.h:128
carl::get_other_bound_type
static BoundType get_other_bound_type(BoundType type)
Definition: BoundType.h:42
carl::set_intersection
Interval< Number > set_intersection(const Interval< Number > &lhs, const Interval< Number > &rhs)
Intersects two intervals in a set-theoretic manner.
Definition: SetTheory.h:99
carl::set_is_subset
bool set_is_subset(const Interval< Number > &lhs, const Interval< Number > &rhs)
Checks whether lhs is a subset of rhs.
Definition: SetTheory.h:143
carl::set_have_intersection
bool set_have_intersection(const Interval< Number > &lhs, const Interval< Number > &rhs)
Definition: SetTheory.h:118
carl::set_difference
bool set_difference(const Interval< Number > &lhs, const Interval< Number > &rhs, Interval< Number > &resA, Interval< Number > &resB)
Calculates the difference of two intervals in a set-theoretic manner: lhs \ rhs (can result in two di...
Definition: SetTheory.h:52
carl::set_complement
bool set_complement(const Interval< Number > &interval, Interval< Number > &resA, Interval< Number > &resB)
Calculates the complement in a set-theoretic manner (can result in two distinct intervals).
Definition: SetTheory.h:16
carl::BoundType::INFTY
@ INFTY
the given bound is interpreted as minus or plus infinity depending on whether it is the left or the r...
carl::bounds_connect
bool bounds_connect(const UpperBound< Number > &lhs, const LowerBound< Number > &rhs)
Check whether the two bounds connect, for example as for ...3),[3...
Definition: operators.h:74
carl::Interval
The class which contains the interval arithmetic including trigonometric functions.
Definition: Interval.h:134
carl::Interval::is_empty
bool is_empty() const
Function which determines, if the interval is empty.
Definition: Interval.h:1056
carl::Interval::lower_bound_type
BoundType lower_bound_type() const
The getter for the lower bound type of the interval.
Definition: Interval.h:883
carl::Interval::upper
const Number & upper() const
The getter for the upper boundary of the interval.
Definition: Interval.h:849
carl::Interval::lower_bound
auto lower_bound() const
Definition: Interval.h:854
carl::Interval::lower
const Number & lower() const
The getter for the lower boundary of the interval.
Definition: Interval.h:840
carl::Interval::is_consistent
bool is_consistent() const
A quick check for the bound values.
Definition: Interval.h:1426
carl::Interval::empty_interval
static Interval< Number > empty_interval()
Method which returns the empty interval rooted at 0.
Definition: Interval.h:813
carl::Interval::upper_bound_type
BoundType upper_bound_type() const
The getter for the upper bound type of the interval.
Definition: Interval.h:892
carl::Interval::upper_bound
auto upper_bound() const
Definition: Interval.h:857