1 /* Interval class implementation: non-inline template functions.
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #ifndef PPL_Interval_templates_hh
25 #define PPL_Interval_templates_hh 1
26
27 #include <algorithm>
28
29 namespace Parma_Polyhedra_Library {
30
31 template <typename Boundary, typename Info>
32 template <typename C>
33 typename Enable_If<Is_Same_Or_Derived<I_Constraint_Base, C>::value, I_Result>::type
lower_extend(const C & c)34 Interval<Boundary, Info>::lower_extend(const C& c) {
35 PPL_ASSERT(OK());
36 bool open;
37 switch (c.rel()) {
38 case V_LGE:
39 return lower_extend();
40 case V_NAN:
41 return I_NOT_EMPTY | I_EXACT | I_UNCHANGED;
42 case V_GT:
43 open = true;
44 break;
45 case V_GE: // Fall through.
46 case V_EQ:
47 open = false;
48 break;
49 default:
50 PPL_UNREACHABLE;
51 return I_NOT_EMPTY | I_EXACT | I_UNCHANGED;
52 }
53 min_assign(LOWER, lower(), info(), LOWER, c.value(), f_info(c.value(), open));
54 PPL_ASSERT(OK());
55 return I_ANY;
56 }
57
58 template <typename Boundary, typename Info>
59 template <typename C>
60 typename Enable_If<Is_Same_Or_Derived<I_Constraint_Base, C>::value, I_Result>::type
upper_extend(const C & c)61 Interval<Boundary, Info>::upper_extend(const C& c) {
62 PPL_ASSERT(OK());
63 bool open;
64 switch (c.rel()) {
65 case V_LGE:
66 return lower_extend();
67 case V_NAN:
68 return I_NOT_EMPTY | I_EXACT | I_UNCHANGED;
69 case V_LT:
70 open = true;
71 break;
72 case V_LE: // Fall through.
73 case V_EQ:
74 open = false;
75 break;
76 default:
77 PPL_UNREACHABLE;
78 return I_NOT_EMPTY | I_EXACT | I_UNCHANGED;
79 }
80 max_assign(UPPER, upper(), info(), UPPER, c.value(), f_info(c.value(), open));
81 PPL_ASSERT(OK());
82 return I_ANY;
83 }
84
85 template <typename Boundary, typename Info>
86 template <typename From, typename Iterator>
87 typename Enable_If<Is_Interval<From>::value, void>::type
CC76_widening_assign(const From & y,Iterator first,Iterator last)88 Interval<Boundary, Info>::CC76_widening_assign(const From& y,
89 Iterator first,
90 Iterator last) {
91 // We assume that `y' is contained in or equal to `*this'.
92 PPL_ASSERT(contains(y));
93 Interval<Boundary, Info>& x = *this;
94
95 // Upper bound.
96 if (!x.upper_is_boundary_infinity()) {
97 Boundary& x_ub = x.upper();
98 const Boundary& y_ub = y.upper();
99 PPL_ASSERT(!y.upper_is_boundary_infinity() && y_ub <= x_ub);
100 if (y_ub < x_ub) {
101 Iterator k = std::lower_bound(first, last, x_ub);
102 if (k != last) {
103 if (x_ub < *k) {
104 x_ub = *k;
105 }
106 }
107 else {
108 x.upper_extend();
109 }
110 }
111 }
112
113 // Lower bound.
114 if (!x.lower_is_boundary_infinity()) {
115 Boundary& x_lb = x.lower();
116 const Boundary& y_lb = y.lower();
117 PPL_ASSERT(!y.lower_is_boundary_infinity() && y_lb >= x_lb);
118 if (y_lb > x_lb) {
119 Iterator k = std::lower_bound(first, last, x_lb);
120 if (k != last) {
121 if (x_lb < *k) {
122 if (k != first) {
123 x_lb = *--k;
124 }
125 else {
126 x.lower_extend();
127 }
128 }
129 }
130 else {
131 if (k != first) {
132 x_lb = *--k;
133 }
134 else {
135 x.lower_extend();
136 }
137 }
138 }
139 }
140 }
141
142 template <typename Boundary, typename Info>
Interval(const char * s)143 Interval<Boundary, Info>::Interval(const char* s) {
144 // Get the lower bound.
145 Boundary lower_bound;
146 Result lower_r = assign_r(lower_bound, s, ROUND_DOWN);
147 if (lower_r == V_CVT_STR_UNK || lower_r == V_NAN) {
148 throw std::invalid_argument("PPL::Interval(const char* s)"
149 " with s invalid");
150 }
151 lower_r = result_relation_class(lower_r);
152
153 // Get the upper bound.
154 Boundary upper_bound;
155 Result upper_r = assign_r(upper_bound, s, ROUND_UP);
156 PPL_ASSERT(upper_r != V_CVT_STR_UNK && upper_r != V_NAN);
157 upper_r = result_relation_class(upper_r);
158
159 // Build the interval.
160 bool lower_open = false;
161 bool upper_open = false;
162 bool lower_boundary_infinity = false;
163 bool upper_boundary_infinity = false;
164 switch (lower_r) {
165 case V_EQ: // Fall through.
166 case V_GE:
167 break;
168 case V_GT:
169 lower_open = true;
170 break;
171 case V_GT_MINUS_INFINITY:
172 lower_open = true;
173 // Fall through.
174 case V_EQ_MINUS_INFINITY:
175 lower_boundary_infinity = true;
176 break;
177 case V_EQ_PLUS_INFINITY: // Fall through.
178 case V_LT_PLUS_INFINITY:
179 if (upper_r == V_EQ_PLUS_INFINITY || upper_r == V_LT_PLUS_INFINITY) {
180 assign(UNIVERSE);
181 }
182 else {
183 assign(EMPTY);
184 }
185 break;
186 default:
187 PPL_UNREACHABLE;
188 break;
189 }
190 switch (upper_r) {
191 case V_EQ: // Fall through.
192 case V_LE:
193 break;
194 case V_LT:
195 upper_open = true;
196 break;
197 case V_EQ_MINUS_INFINITY: // Fall through.
198 case V_GT_MINUS_INFINITY:
199 if (lower_r == V_EQ_MINUS_INFINITY || lower_r == V_GT_MINUS_INFINITY) {
200 assign(UNIVERSE);
201 }
202 else {
203 assign(EMPTY);
204 }
205 break;
206 case V_LT_PLUS_INFINITY:
207 upper_open = true;
208 // Fall through.
209 case V_EQ_PLUS_INFINITY:
210 upper_boundary_infinity = true;
211 break;
212 default:
213 PPL_UNREACHABLE;
214 break;
215 }
216
217 if (!lower_boundary_infinity
218 && !upper_boundary_infinity
219 && (lower_bound > upper_bound
220 || (lower_open && lower_bound == upper_bound))) {
221 assign(EMPTY);
222 }
223 else {
224 if (lower_boundary_infinity) {
225 set_minus_infinity(LOWER, lower(), info(), lower_open);
226 }
227 else {
228 Boundary_NS::assign(LOWER, lower(), info(),
229 LOWER, lower_bound, SCALAR_INFO, lower_open);
230 }
231 if (upper_boundary_infinity) {
232 set_plus_infinity(UPPER, upper(), info(), upper_open);
233 }
234 else {
235 Boundary_NS::assign(UPPER, upper(), info(),
236 UPPER, upper_bound, SCALAR_INFO, upper_open);
237 }
238 }
239 }
240
241
242 template <typename Boundary, typename Info>
243 inline std::istream&
operator >>(std::istream & is,Interval<Boundary,Info> & x)244 operator>>(std::istream& is, Interval<Boundary, Info>& x) {
245 Boundary lower_bound;
246 Boundary upper_bound;
247 bool lower_boundary_infinity = false;
248 bool upper_boundary_infinity = false;
249 bool lower_open = false;
250 bool upper_open = false;
251 Result lower_r;
252 Result upper_r;
253
254 // Eat leading white space.
255 char c;
256 do {
257 if (!is.get(c)) {
258 goto fail;
259 }
260 } while (is_space(c));
261
262 // Get the opening parenthesis and handle the empty interval case.
263 if (c == '(') {
264 lower_open = true;
265 }
266 else if (c == '[') {
267 if (!is.get(c)) {
268 goto fail;
269 }
270 if (c == ']') {
271 // Empty interval.
272 x.assign(EMPTY);
273 return is;
274 }
275 else {
276 is.unget();
277 }
278 }
279 else {
280 goto unexpected_char;
281 }
282
283 // Get the lower bound.
284 lower_r = input(lower_bound, is, ROUND_DOWN);
285 if (lower_r == V_CVT_STR_UNK || lower_r == V_NAN) {
286 goto fail;
287 }
288 lower_r = result_relation_class(lower_r);
289
290 // Match the comma separating the lower and upper bounds.
291 do {
292 if (!is.get(c)) {
293 goto fail;
294 }
295 } while (is_space(c));
296 if (c != ',') {
297 goto unexpected_char;
298 }
299
300 // Get the upper bound.
301 upper_r = input(upper_bound, is, ROUND_UP);
302 if (upper_r == V_CVT_STR_UNK || upper_r == V_NAN) {
303 goto fail;
304 }
305 upper_r = result_relation_class(upper_r);
306
307 // Get the closing parenthesis.
308 do {
309 if (!is.get(c)) {
310 goto fail;
311 }
312 } while (is_space(c));
313 if (c == ')') {
314 upper_open = true;
315 }
316 else if (c != ']') {
317 unexpected_char:
318 is.unget();
319 fail:
320 is.setstate(std::ios::failbit);
321 return is;
322 }
323
324 // Build interval.
325 switch (lower_r) {
326 case V_EQ: // Fall through.
327 case V_GE:
328 break;
329 case V_GT:
330 lower_open = true;
331 break;
332 case V_GT_MINUS_INFINITY:
333 lower_open = true;
334 // Fall through.
335 case V_EQ_MINUS_INFINITY:
336 lower_boundary_infinity = true;
337 break;
338 case V_EQ_PLUS_INFINITY: // Fall through.
339 case V_LT_PLUS_INFINITY:
340 if (upper_r == V_EQ_PLUS_INFINITY || upper_r == V_LT_PLUS_INFINITY) {
341 x.assign(UNIVERSE);
342 }
343 else {
344 x.assign(EMPTY);
345 }
346 return is;
347 default:
348 PPL_UNREACHABLE;
349 break;
350 }
351 switch (upper_r) {
352 case V_EQ: // Fall through.
353 case V_LE:
354 break;
355 case V_LT:
356 upper_open = true;
357 break;
358 case V_GT_MINUS_INFINITY:
359 upper_open = true;
360 // Fall through.
361 case V_EQ_MINUS_INFINITY:
362 if (lower_r == V_EQ_MINUS_INFINITY || lower_r == V_GT_MINUS_INFINITY) {
363 x.assign(UNIVERSE);
364 }
365 else {
366 x.assign(EMPTY);
367 }
368 return is;
369 case V_EQ_PLUS_INFINITY: // Fall through.
370 case V_LT_PLUS_INFINITY:
371 upper_boundary_infinity = true;
372 break;
373 default:
374 PPL_UNREACHABLE;
375 break;
376 }
377
378 if (!lower_boundary_infinity
379 && !upper_boundary_infinity
380 && (lower_bound > upper_bound
381 || (lower_open && lower_bound == upper_bound))) {
382 x.assign(EMPTY);
383 }
384 else {
385 if (lower_boundary_infinity) {
386 set_minus_infinity(LOWER, x.lower(), x.info(), lower_open);
387 }
388 else {
389 assign(LOWER, x.lower(), x.info(),
390 LOWER, lower_bound, SCALAR_INFO, lower_open);
391 }
392 if (upper_boundary_infinity) {
393 set_plus_infinity(UPPER, x.upper(), x.info(), upper_open);
394 }
395 else {
396 assign(UPPER, x.upper(), x.info(),
397 UPPER, upper_bound, SCALAR_INFO, upper_open);
398 }
399 }
400 return is;
401 }
402
403 template <typename Boundary, typename Info>
404 template <typename From>
405 typename Enable_If<Is_Interval<From>::value, bool>::type
simplify_using_context_assign(const From & y)406 Interval<Boundary, Info>::simplify_using_context_assign(const From& y) {
407 // FIXME: the following code wrongly assumes that intervals are closed
408 if (lt(UPPER, upper(), info(), LOWER, f_lower(y), f_info(y))) {
409 lower_extend();
410 return false;
411 }
412 if (gt(LOWER, lower(), info(), UPPER, f_upper(y), f_info(y))) {
413 upper_extend();
414 return false;
415 }
416 // Weakening the upper bound.
417 if (!upper_is_boundary_infinity() && !y.upper_is_boundary_infinity()
418 && y.upper() <= upper()) {
419 upper_extend();
420 }
421 // Weakening the lower bound.
422 if (!lower_is_boundary_infinity() && !y.lower_is_boundary_infinity()
423 && y.lower() >= lower()) {
424 lower_extend();
425 }
426 return true;
427 }
428
429 template <typename Boundary, typename Info>
430 template <typename From>
431 typename Enable_If<Is_Interval<From>::value, void>::type
empty_intersection_assign(const From &)432 Interval<Boundary, Info>::empty_intersection_assign(const From&) {
433 // FIXME: write me.
434 assign(EMPTY);
435 }
436
437 } // namespace Parma_Polyhedra_Library
438
439 #endif // !defined(PPL_Interval_templates_hh)
440