1 /* Constraint class implementation: inline 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_Constraint_inlines_hh
25 #define PPL_Constraint_inlines_hh 1
26
27 #include "Linear_Expression_defs.hh"
28
29 namespace Parma_Polyhedra_Library {
30
31 inline bool
is_necessarily_closed() const32 Constraint::is_necessarily_closed() const {
33 return (topology_ == NECESSARILY_CLOSED);
34 }
35
36 inline bool
is_not_necessarily_closed() const37 Constraint::is_not_necessarily_closed() const {
38 return !is_necessarily_closed();
39 }
40
41 inline Constraint::expr_type
expression() const42 Constraint::expression() const {
43 return expr_type(expr, is_not_necessarily_closed());
44 }
45
46 inline dimension_type
space_dimension() const47 Constraint::space_dimension() const {
48 return expression().space_dimension();
49 }
50
51 inline void
shift_space_dimensions(Variable v,dimension_type n)52 Constraint::shift_space_dimensions(Variable v, dimension_type n) {
53 expr.shift_space_dimensions(v, n);
54 }
55
56 inline bool
is_line_or_equality() const57 Constraint::is_line_or_equality() const {
58 return (kind_ == LINE_OR_EQUALITY);
59 }
60
61 inline bool
is_ray_or_point_or_inequality() const62 Constraint::is_ray_or_point_or_inequality() const {
63 return (kind_ == RAY_OR_POINT_OR_INEQUALITY);
64 }
65
66 inline Topology
topology() const67 Constraint::topology() const {
68 return topology_;
69 }
70
71 inline void
set_is_line_or_equality()72 Constraint::set_is_line_or_equality() {
73 kind_ = LINE_OR_EQUALITY;
74 }
75
76 inline void
set_is_ray_or_point_or_inequality()77 Constraint::set_is_ray_or_point_or_inequality() {
78 kind_ = RAY_OR_POINT_OR_INEQUALITY;
79 }
80
81 inline void
set_topology(Topology x)82 Constraint::set_topology(Topology x) {
83 if (topology() == x) {
84 return;
85 }
86 if (topology() == NECESSARILY_CLOSED) {
87 // Add a column for the epsilon dimension.
88 expr.set_space_dimension(expr.space_dimension() + 1);
89 }
90 else {
91 PPL_ASSERT(expr.space_dimension() != 0);
92 expr.set_space_dimension(expr.space_dimension() - 1);
93 }
94 topology_ = x;
95 }
96
97 inline void
mark_as_necessarily_closed()98 Constraint::mark_as_necessarily_closed() {
99 PPL_ASSERT(is_not_necessarily_closed());
100 topology_ = NECESSARILY_CLOSED;
101 }
102
103 inline void
mark_as_not_necessarily_closed()104 Constraint::mark_as_not_necessarily_closed() {
105 PPL_ASSERT(is_necessarily_closed());
106 topology_ = NOT_NECESSARILY_CLOSED;
107 }
108
109 inline void
set_necessarily_closed()110 Constraint::set_necessarily_closed() {
111 set_topology(NECESSARILY_CLOSED);
112 }
113
114 inline void
set_not_necessarily_closed()115 Constraint::set_not_necessarily_closed() {
116 set_topology(NOT_NECESSARILY_CLOSED);
117 }
118
119 inline
Constraint(Representation r)120 Constraint::Constraint(Representation r)
121 : expr(r),
122 kind_(RAY_OR_POINT_OR_INEQUALITY),
123 topology_(NECESSARILY_CLOSED) {
124 PPL_ASSERT(OK());
125 }
126
127 inline
Constraint(dimension_type space_dim,Kind kind,Topology topology,Representation r)128 Constraint::Constraint(dimension_type space_dim, Kind kind, Topology topology,
129 Representation r)
130 : expr(r),
131 kind_(kind),
132 topology_(topology) {
133 expr.set_space_dimension(space_dim + 1);
134 PPL_ASSERT(space_dimension() == space_dim);
135 PPL_ASSERT(OK());
136 }
137
138 inline
Constraint(Linear_Expression & e,Kind kind,Topology topology)139 Constraint::Constraint(Linear_Expression& e, Kind kind, Topology topology)
140 : kind_(kind),
141 topology_(topology) {
142 PPL_ASSERT(kind != RAY_OR_POINT_OR_INEQUALITY || topology == NOT_NECESSARILY_CLOSED);
143 swap(expr, e);
144 if (topology == NOT_NECESSARILY_CLOSED) {
145 // Add the epsilon dimension.
146 expr.set_space_dimension(expr.space_dimension() + 1);
147 }
148 strong_normalize();
149 PPL_ASSERT(OK());
150 }
151
152 inline
Constraint(Linear_Expression & e,Type type,Topology topology)153 Constraint::Constraint(Linear_Expression& e, Type type, Topology topology)
154 : topology_(topology) {
155 PPL_ASSERT(type != STRICT_INEQUALITY || topology == NOT_NECESSARILY_CLOSED);
156 swap(expr, e);
157 if (topology == NOT_NECESSARILY_CLOSED) {
158 expr.set_space_dimension(expr.space_dimension() + 1);
159 }
160 if (type == EQUALITY) {
161 kind_ = LINE_OR_EQUALITY;
162 }
163 else {
164 kind_ = RAY_OR_POINT_OR_INEQUALITY;
165 }
166 strong_normalize();
167 PPL_ASSERT(OK());
168 }
169
170 inline
Constraint(const Constraint & c)171 Constraint::Constraint(const Constraint& c)
172 : expr(c.expr),
173 kind_(c.kind_),
174 topology_(c.topology_) {
175 // NOTE: This does not call PPL_ASSERT(OK()) because this is called by OK().
176 }
177
178 inline
Constraint(const Constraint & c,Representation r)179 Constraint::Constraint(const Constraint& c, Representation r)
180 : expr(c.expr, r),
181 kind_(c.kind_),
182 topology_(c.topology_) {
183 PPL_ASSERT(OK());
184 }
185
186 inline
Constraint(const Constraint & c,const dimension_type space_dim)187 Constraint::Constraint(const Constraint& c, const dimension_type space_dim)
188 : expr(c.expr, c.is_necessarily_closed() ? space_dim : (space_dim + 1)),
189 kind_(c.kind_), topology_(c.topology_) {
190 PPL_ASSERT(space_dimension() == space_dim);
191 PPL_ASSERT(OK());
192 }
193
194 inline
Constraint(const Constraint & c,const dimension_type space_dim,Representation r)195 Constraint::Constraint(const Constraint& c, const dimension_type space_dim,
196 Representation r)
197 : expr(c.expr, c.is_necessarily_closed() ? space_dim : (space_dim + 1), r),
198 kind_(c.kind_), topology_(c.topology_) {
199 PPL_ASSERT(space_dimension() == space_dim);
200 PPL_ASSERT(OK());
201 }
202
203 inline
~Constraint()204 Constraint::~Constraint() {
205 }
206
207 inline Constraint&
operator =(const Constraint & c)208 Constraint::operator=(const Constraint& c) {
209 Constraint tmp = c;
210 swap(*this, tmp);
211
212 return *this;
213 }
214
215 inline Representation
representation() const216 Constraint::representation() const {
217 return expr.representation();
218 }
219
220 inline void
set_representation(Representation r)221 Constraint::set_representation(Representation r) {
222 expr.set_representation(r);
223 }
224
225 inline dimension_type
max_space_dimension()226 Constraint::max_space_dimension() {
227 return Linear_Expression::max_space_dimension();
228 }
229
230 inline void
set_space_dimension_no_ok(dimension_type space_dim)231 Constraint::set_space_dimension_no_ok(dimension_type space_dim) {
232 const dimension_type old_expr_space_dim = expr.space_dimension();
233 if (topology() == NECESSARILY_CLOSED) {
234 expr.set_space_dimension(space_dim);
235 }
236 else {
237 const dimension_type old_space_dim = space_dimension();
238 if (space_dim > old_space_dim) {
239 expr.set_space_dimension(space_dim + 1);
240 expr.swap_space_dimensions(Variable(space_dim), Variable(old_space_dim));
241 }
242 else {
243 expr.swap_space_dimensions(Variable(space_dim), Variable(old_space_dim));
244 expr.set_space_dimension(space_dim + 1);
245 }
246 }
247 PPL_ASSERT(space_dimension() == space_dim);
248 if (expr.space_dimension() < old_expr_space_dim) {
249 strong_normalize();
250 }
251 }
252
253 inline void
set_space_dimension(dimension_type space_dim)254 Constraint::set_space_dimension(dimension_type space_dim) {
255 set_space_dimension_no_ok(space_dim);
256 PPL_ASSERT(OK());
257 }
258
259 inline bool
remove_space_dimensions(const Variables_Set & vars)260 Constraint::remove_space_dimensions(const Variables_Set& vars) {
261 expr.remove_space_dimensions(vars);
262 return true;
263 }
264
265 inline bool
is_equality() const266 Constraint::is_equality() const {
267 return is_line_or_equality();
268 }
269
270 inline bool
is_inequality() const271 Constraint::is_inequality() const {
272 return is_ray_or_point_or_inequality();
273 }
274
275 inline Constraint::Type
type() const276 Constraint::type() const {
277 if (is_equality()) {
278 return EQUALITY;
279 }
280 if (is_necessarily_closed()) {
281 return NONSTRICT_INEQUALITY;
282 }
283 if (epsilon_coefficient() < 0) {
284 return STRICT_INEQUALITY;
285 }
286 else {
287 return NONSTRICT_INEQUALITY;
288 }
289 }
290
291 inline bool
is_nonstrict_inequality() const292 Constraint::is_nonstrict_inequality() const {
293 return type() == NONSTRICT_INEQUALITY;
294 }
295
296 inline bool
is_strict_inequality() const297 Constraint::is_strict_inequality() const {
298 return type() == STRICT_INEQUALITY;
299 }
300
301 inline void
set_is_equality()302 Constraint::set_is_equality() {
303 set_is_line_or_equality();
304 }
305
306 inline void
set_is_inequality()307 Constraint::set_is_inequality() {
308 set_is_ray_or_point_or_inequality();
309 }
310
311 inline Coefficient_traits::const_reference
coefficient(const Variable v) const312 Constraint::coefficient(const Variable v) const {
313 if (v.space_dimension() > space_dimension()) {
314 throw_dimension_incompatible("coefficient(v)", "v", v);
315 }
316 return expr.coefficient(v);
317 }
318
319 inline Coefficient_traits::const_reference
inhomogeneous_term() const320 Constraint::inhomogeneous_term() const {
321 return expr.inhomogeneous_term();
322 }
323
324 inline memory_size_type
external_memory_in_bytes() const325 Constraint::external_memory_in_bytes() const {
326 return expr.external_memory_in_bytes();
327 }
328
329 inline memory_size_type
total_memory_in_bytes() const330 Constraint::total_memory_in_bytes() const {
331 return sizeof(*this) + external_memory_in_bytes();
332 }
333
334 inline void
strong_normalize()335 Constraint::strong_normalize() {
336 expr.normalize();
337 sign_normalize();
338 }
339
340 /*! \relates Constraint */
341 inline bool
operator ==(const Constraint & x,const Constraint & y)342 operator==(const Constraint& x, const Constraint& y) {
343 return x.is_equivalent_to(y);
344 }
345
346 /*! \relates Constraint */
347 inline bool
operator !=(const Constraint & x,const Constraint & y)348 operator!=(const Constraint& x, const Constraint& y) {
349 return !x.is_equivalent_to(y);
350 }
351
352 /*! \relates Constraint */
353 inline Constraint
operator ==(const Linear_Expression & e1,const Linear_Expression & e2)354 operator==(const Linear_Expression& e1, const Linear_Expression& e2) {
355 Linear_Expression diff(e1,
356 std::max(e1.space_dimension(), e2.space_dimension()),
357 Constraint::default_representation);
358 diff -= e2;
359 return Constraint(diff, Constraint::EQUALITY, NECESSARILY_CLOSED);
360 }
361
362 /*! \relates Constraint */
363 inline Constraint
operator ==(Variable v1,Variable v2)364 operator==(Variable v1, Variable v2) {
365 if (v1.space_dimension() > v2.space_dimension()) {
366 swap(v1, v2);
367 }
368 PPL_ASSERT(v1.space_dimension() <= v2.space_dimension());
369
370 Linear_Expression diff(v1, Constraint::default_representation);
371 diff -= v2;
372 return Constraint(diff, Constraint::EQUALITY, NECESSARILY_CLOSED);
373 }
374
375 /*! \relates Constraint */
376 inline Constraint
operator >=(const Linear_Expression & e1,const Linear_Expression & e2)377 operator>=(const Linear_Expression& e1, const Linear_Expression& e2) {
378 Linear_Expression diff(e1,
379 std::max(e1.space_dimension(), e2.space_dimension()),
380 Constraint::default_representation);
381 diff -= e2;
382 return Constraint(diff, Constraint::NONSTRICT_INEQUALITY, NECESSARILY_CLOSED);
383 }
384
385 /*! \relates Constraint */
386 inline Constraint
operator >=(const Variable v1,const Variable v2)387 operator>=(const Variable v1, const Variable v2) {
388 Linear_Expression diff(Constraint::default_representation);
389 diff.set_space_dimension(std::max(v1.space_dimension(),
390 v2.space_dimension()));
391 diff += v1;
392 diff -= v2;
393 return Constraint(diff, Constraint::NONSTRICT_INEQUALITY, NECESSARILY_CLOSED);
394 }
395
396 /*! \relates Constraint */
397 inline Constraint
operator >(const Linear_Expression & e1,const Linear_Expression & e2)398 operator>(const Linear_Expression& e1, const Linear_Expression& e2) {
399 Linear_Expression diff(e1, Constraint::default_representation);
400 diff -= e2;
401 Constraint c(diff, Constraint::STRICT_INEQUALITY, NOT_NECESSARILY_CLOSED);
402
403 // NOTE: this also enforces normalization.
404 c.set_epsilon_coefficient(-1);
405 PPL_ASSERT(c.OK());
406
407 return c;
408 }
409
410 /*! \relates Constraint */
411 inline Constraint
operator >(const Variable v1,const Variable v2)412 operator>(const Variable v1, const Variable v2) {
413 Linear_Expression diff(Constraint::default_representation);
414 diff.set_space_dimension(std::max(v1.space_dimension(),
415 v2.space_dimension()));
416 diff += v1;
417 diff -= v2;
418 Constraint c(diff, Constraint::STRICT_INEQUALITY, NOT_NECESSARILY_CLOSED);
419
420 c.set_epsilon_coefficient(-1);
421 PPL_ASSERT(c.OK());
422
423 return c;
424 }
425
426 /*! \relates Constraint */
427 inline Constraint
operator ==(Coefficient_traits::const_reference n,const Linear_Expression & e)428 operator==(Coefficient_traits::const_reference n, const Linear_Expression& e) {
429 Linear_Expression diff(e, Constraint::default_representation);
430 neg_assign(diff);
431 diff += n;
432 return Constraint(diff, Constraint::EQUALITY, NECESSARILY_CLOSED);
433 }
434
435 /*! \relates Constraint */
436 inline Constraint
operator >=(Coefficient_traits::const_reference n,const Linear_Expression & e)437 operator>=(Coefficient_traits::const_reference n, const Linear_Expression& e) {
438 Linear_Expression diff(e, Constraint::default_representation);
439 neg_assign(diff);
440 diff += n;
441 return Constraint(diff, Constraint::NONSTRICT_INEQUALITY, NECESSARILY_CLOSED);
442 }
443
444 /*! \relates Constraint */
445 inline Constraint
operator >(Coefficient_traits::const_reference n,const Linear_Expression & e)446 operator>(Coefficient_traits::const_reference n, const Linear_Expression& e) {
447 Linear_Expression diff(e, Constraint::default_representation);
448 neg_assign(diff);
449 diff += n;
450 Constraint c(diff, Constraint::STRICT_INEQUALITY, NOT_NECESSARILY_CLOSED);
451
452 // NOTE: this also enforces normalization.
453 c.set_epsilon_coefficient(-1);
454 PPL_ASSERT(c.OK());
455
456 return c;
457 }
458
459 /*! \relates Constraint */
460 inline Constraint
operator ==(const Linear_Expression & e,Coefficient_traits::const_reference n)461 operator==(const Linear_Expression& e, Coefficient_traits::const_reference n) {
462 Linear_Expression diff(e, Constraint::default_representation);
463 diff -= n;
464 return Constraint(diff, Constraint::EQUALITY, NECESSARILY_CLOSED);
465 }
466
467 /*! \relates Constraint */
468 inline Constraint
operator >=(const Linear_Expression & e,Coefficient_traits::const_reference n)469 operator>=(const Linear_Expression& e, Coefficient_traits::const_reference n) {
470 Linear_Expression diff(e, Constraint::default_representation);
471 diff -= n;
472 return Constraint(diff, Constraint::NONSTRICT_INEQUALITY, NECESSARILY_CLOSED);
473 }
474
475 /*! \relates Constraint */
476 inline Constraint
operator >(const Linear_Expression & e,Coefficient_traits::const_reference n)477 operator>(const Linear_Expression& e, Coefficient_traits::const_reference n) {
478 Linear_Expression diff(e, Constraint::default_representation);
479 diff -= n;
480 Constraint c(diff, Constraint::STRICT_INEQUALITY, NOT_NECESSARILY_CLOSED);
481
482 // NOTE: this also enforces normalization.
483 c.set_epsilon_coefficient(-1);
484 PPL_ASSERT(c.OK());
485
486 return c;
487 }
488
489 /*! \relates Constraint */
490 inline Constraint
operator <=(const Linear_Expression & e1,const Linear_Expression & e2)491 operator<=(const Linear_Expression& e1, const Linear_Expression& e2) {
492 return e2 >= e1;
493 }
494
495 /*! \relates Constraint */
496 inline Constraint
operator <=(const Variable v1,const Variable v2)497 operator<=(const Variable v1, const Variable v2) {
498 return v2 >= v1;
499 }
500
501 /*! \relates Constraint */
502 inline Constraint
operator <=(Coefficient_traits::const_reference n,const Linear_Expression & e)503 operator<=(Coefficient_traits::const_reference n, const Linear_Expression& e) {
504 return e >= n;
505 }
506
507 /*! \relates Constraint */
508 inline Constraint
operator <=(const Linear_Expression & e,Coefficient_traits::const_reference n)509 operator<=(const Linear_Expression& e, Coefficient_traits::const_reference n) {
510 return n >= e;
511 }
512
513 /*! \relates Constraint */
514 inline Constraint
operator <(const Linear_Expression & e1,const Linear_Expression & e2)515 operator<(const Linear_Expression& e1, const Linear_Expression& e2) {
516 return e2 > e1;
517 }
518
519 /*! \relates Constraint */
520 inline Constraint
operator <(const Variable v1,const Variable v2)521 operator<(const Variable v1, const Variable v2) {
522 return v2 > v1;
523 }
524
525 /*! \relates Constraint */
526 inline Constraint
operator <(Coefficient_traits::const_reference n,const Linear_Expression & e)527 operator<(Coefficient_traits::const_reference n, const Linear_Expression& e) {
528 return e > n;
529 }
530
531 /*! \relates Constraint */
532 inline Constraint
operator <(const Linear_Expression & e,Coefficient_traits::const_reference n)533 operator<(const Linear_Expression& e, Coefficient_traits::const_reference n) {
534 return n > e;
535 }
536
537 inline const Constraint&
zero_dim_false()538 Constraint::zero_dim_false() {
539 PPL_ASSERT(zero_dim_false_p != 0);
540 return *zero_dim_false_p;
541 }
542
543 inline const Constraint&
zero_dim_positivity()544 Constraint::zero_dim_positivity() {
545 PPL_ASSERT(zero_dim_positivity_p != 0);
546 return *zero_dim_positivity_p;
547 }
548
549 inline const Constraint&
epsilon_geq_zero()550 Constraint::epsilon_geq_zero() {
551 PPL_ASSERT(epsilon_geq_zero_p != 0);
552 return *epsilon_geq_zero_p;
553 }
554
555 inline const Constraint&
epsilon_leq_one()556 Constraint::epsilon_leq_one() {
557 PPL_ASSERT(epsilon_leq_one_p != 0);
558 return *epsilon_leq_one_p;
559 }
560
561 inline void
m_swap(Constraint & y)562 Constraint::m_swap(Constraint& y) {
563 using std::swap;
564 swap(expr, y.expr);
565 swap(kind_, y.kind_);
566 swap(topology_, y.topology_);
567 }
568
569 inline Coefficient_traits::const_reference
epsilon_coefficient() const570 Constraint::epsilon_coefficient() const {
571 PPL_ASSERT(is_not_necessarily_closed());
572 return expr.coefficient(Variable(expr.space_dimension() - 1));
573 }
574
575 inline void
set_epsilon_coefficient(Coefficient_traits::const_reference n)576 Constraint::set_epsilon_coefficient(Coefficient_traits::const_reference n) {
577 PPL_ASSERT(is_not_necessarily_closed());
578 expr.set_coefficient(Variable(expr.space_dimension() - 1), n);
579 }
580
581 /*! \relates Constraint */
582 inline void
swap(Constraint & x,Constraint & y)583 swap(Constraint& x, Constraint& y) {
584 x.m_swap(y);
585 }
586
587 } // namespace Parma_Polyhedra_Library
588
589 #endif // !defined(PPL_Constraint_inlines_hh)
590