Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
rel.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2002
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/int/rel.hh>
35#include <gecode/int/bool.hh>
36
37#include <algorithm>
38
39namespace Gecode {
40
41 void
42 rel(Home home, IntVar x0, IntRelType irt, int n, IntPropLevel) {
43 using namespace Int;
44 Limits::check(n,"Int::rel");
46 IntView x(x0);
47 switch (irt) {
48 case IRT_EQ: GECODE_ME_FAIL(x.eq(home,n)); break;
49 case IRT_NQ: GECODE_ME_FAIL(x.nq(home,n)); break;
50 case IRT_LQ: GECODE_ME_FAIL(x.lq(home,n)); break;
51 case IRT_LE: GECODE_ME_FAIL(x.le(home,n)); break;
52 case IRT_GQ: GECODE_ME_FAIL(x.gq(home,n)); break;
53 case IRT_GR: GECODE_ME_FAIL(x.gr(home,n)); break;
54 default: throw UnknownRelation("Int::rel");
55 }
56 }
57
58 void
59 rel(Home home, const IntVarArgs& x, IntRelType irt, int n, IntPropLevel) {
60 using namespace Int;
61 Limits::check(n,"Int::rel");
63 switch (irt) {
64 case IRT_EQ:
65 for (int i=0; i<x.size(); i++) {
66 IntView xi(x[i]); GECODE_ME_FAIL(xi.eq(home,n));
67 }
68 break;
69 case IRT_NQ:
70 for (int i=0; i<x.size(); i++) {
71 IntView xi(x[i]); GECODE_ME_FAIL(xi.nq(home,n));
72 }
73 break;
74 case IRT_LQ:
75 for (int i=0; i<x.size(); i++) {
76 IntView xi(x[i]); GECODE_ME_FAIL(xi.lq(home,n));
77 }
78 break;
79 case IRT_LE:
80 for (int i=0; i<x.size(); i++) {
81 IntView xi(x[i]); GECODE_ME_FAIL(xi.le(home,n));
82 }
83 break;
84 case IRT_GQ:
85 for (int i=0; i<x.size(); i++) {
86 IntView xi(x[i]); GECODE_ME_FAIL(xi.gq(home,n));
87 }
88 break;
89 case IRT_GR:
90 for (int i=0; i<x.size(); i++) {
91 IntView xi(x[i]); GECODE_ME_FAIL(xi.gr(home,n));
92 }
93 break;
94 default:
95 throw UnknownRelation("Int::rel");
96 }
97 }
98
99 void
100 rel(Home home, IntVar x0, IntRelType irt, IntVar x1, IntPropLevel ipl) {
101 using namespace Int;
103 switch (irt) {
104 case IRT_EQ:
105 if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
107 } else {
109 }
110 break;
111 case IRT_NQ:
113 case IRT_GQ:
114 std::swap(x0,x1); // Fall through
115 case IRT_LQ:
117 case IRT_GR:
118 std::swap(x0,x1); // Fall through
119 case IRT_LE:
121 default:
122 throw UnknownRelation("Int::rel");
123 }
124 }
125
126 void
127 rel(Home home, const IntVarArgs& x, IntRelType irt, IntVar y,
128 IntPropLevel ipl) {
129 using namespace Int;
131 switch (irt) {
132 case IRT_EQ:
133 {
134 ViewArray<IntView> xv(home,x.size()+1);
135 xv[x.size()]=y;
136 for (int i=0; i<x.size(); i++)
137 xv[i]=x[i];
138 if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
140 } else {
142 }
143 }
144 break;
145 case IRT_NQ:
146 for (int i=0; i<x.size(); i++) {
148 }
149 break;
150 case IRT_GQ:
151 for (int i=0; i<x.size(); i++) {
153 }
154 break;
155 case IRT_LQ:
156 for (int i=0; i<x.size(); i++) {
158 }
159 break;
160 case IRT_GR:
161 for (int i=0; i<x.size(); i++) {
163 }
164 break;
165 case IRT_LE:
166 for (int i=0; i<x.size(); i++) {
168 }
169 break;
170 default:
171 throw UnknownRelation("Int::rel");
172 }
173 }
174
175
176 void
177 rel(Home home, IntVar x0, IntRelType irt, IntVar x1, Reify r,
178 IntPropLevel ipl) {
179 using namespace Int;
181 switch (irt) {
182 case IRT_EQ:
183 if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
184 switch (r.mode()) {
185 case RM_EQV:
187 ::post(home,x0,x1,r.var())));
188 break;
189 case RM_IMP:
191 ::post(home,x0,x1,r.var())));
192 break;
193 case RM_PMI:
195 ::post(home,x0,x1,r.var())));
196 break;
197 default: throw UnknownReifyMode("Int::rel");
198 }
199 } else {
200 switch (r.mode()) {
201 case RM_EQV:
203 ::post(home,x0,x1,r.var())));
204 break;
205 case RM_IMP:
207 ::post(home,x0,x1,r.var())));
208 break;
209 case RM_PMI:
211 ::post(home,x0,x1,r.var())));
212 break;
213 default: throw UnknownReifyMode("Int::rel");
214 }
215 }
216 break;
217 case IRT_NQ:
218 {
219 NegBoolView n(r.var());
220 if (vbd(ipl) == IPL_BND) {
221 switch (r.mode()) {
222 case RM_EQV:
224 ::post(home,x0,x1,n)));
225 break;
226 case RM_IMP:
228 ::post(home,x0,x1,n)));
229 break;
230 case RM_PMI:
232 ::post(home,x0,x1,n)));
233 break;
234 default: throw UnknownReifyMode("Int::rel");
235 }
236 } else {
237 switch (r.mode()) {
238 case RM_EQV:
240 ::post(home,x0,x1,n)));
241 break;
242 case RM_IMP:
244 ::post(home,x0,x1,n)));
245 break;
246 case RM_PMI:
248 ::post(home,x0,x1,n)));
249 break;
250 default: throw UnknownReifyMode("Int::rel");
251 }
252 }
253 }
254 break;
255 case IRT_GQ:
256 std::swap(x0,x1); // Fall through
257 case IRT_LQ:
258 switch (r.mode()) {
259 case RM_EQV:
261 ::post(home,x0,x1,r.var())));
262 break;
263 case RM_IMP:
265 ::post(home,x0,x1,r.var())));
266 break;
267 case RM_PMI:
269 ::post(home,x0,x1,r.var())));
270 break;
271 default: throw UnknownReifyMode("Int::rel");
272 }
273 break;
274 case IRT_LE:
275 std::swap(x0,x1); // Fall through
276 case IRT_GR:
277 {
278 NegBoolView n(r.var());
279 switch (r.mode()) {
280 case RM_EQV:
282 ::post(home,x0,x1,n)));
283 break;
284 case RM_IMP:
286 ::post(home,x0,x1,n)));
287 break;
288 case RM_PMI:
290 ::post(home,x0,x1,n)));
291 break;
292 default: throw UnknownReifyMode("Int::rel");
293 }
294 }
295 break;
296 default:
297 throw UnknownRelation("Int::rel");
298 }
299 }
300
301 void
302 rel(Home home, IntVar x, IntRelType irt, int n, Reify r,
303 IntPropLevel ipl) {
304 using namespace Int;
305 Limits::check(n,"Int::rel");
307 switch (irt) {
308 case IRT_EQ:
309 if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
310 switch (r.mode()) {
311 case RM_EQV:
313 ::post(home,x,n,r.var())));
314 break;
315 case RM_IMP:
317 ::post(home,x,n,r.var())));
318 break;
319 case RM_PMI:
321 ::post(home,x,n,r.var())));
322 break;
323 default: throw UnknownReifyMode("Int::rel");
324 }
325 } else {
326 switch (r.mode()) {
327 case RM_EQV:
329 ::post(home,x,n,r.var())));
330 break;
331 case RM_IMP:
333 ::post(home,x,n,r.var())));
334 break;
335 case RM_PMI:
337 ::post(home,x,n,r.var())));
338 break;
339 default: throw UnknownReifyMode("Int::rel");
340 }
341 }
342 break;
343 case IRT_NQ:
344 {
345 NegBoolView nb(r.var());
346 if (vbd(ipl) == IPL_BND) {
347 switch (r.mode()) {
348 case RM_EQV:
350 ::post(home,x,n,nb)));
351 break;
352 case RM_IMP:
354 ::post(home,x,n,nb)));
355 break;
356 case RM_PMI:
358 ::post(home,x,n,nb)));
359 break;
360 default: throw UnknownReifyMode("Int::rel");
361 }
362 } else {
363 switch (r.mode()) {
364 case RM_EQV:
366 ::post(home,x,n,nb)));
367 break;
368 case RM_IMP:
370 ::post(home,x,n,nb)));
371 break;
372 case RM_PMI:
374 ::post(home,x,n,nb)));
375 break;
376 default: throw UnknownReifyMode("Int::rel");
377 }
378 }
379 }
380 break;
381 case IRT_LE:
382 n--; // Fall through
383 case IRT_LQ:
384 switch (r.mode()) {
385 case RM_EQV:
387 ::post(home,x,n,r.var())));
388 break;
389 case RM_IMP:
391 ::post(home,x,n,r.var())));
392 break;
393 case RM_PMI:
395 ::post(home,x,n,r.var())));
396 break;
397 default: throw UnknownReifyMode("Int::rel");
398 }
399 break;
400 case IRT_GQ:
401 n--; // Fall through
402 case IRT_GR:
403 {
404 NegBoolView nb(r.var());
405 switch (r.mode()) {
406 case RM_EQV:
408 ::post(home,x,n,nb)));
409 break;
410 case RM_IMP:
412 ::post(home,x,n,nb)));
413 break;
414 case RM_PMI:
416 ::post(home,x,n,nb)));
417 break;
418 default: throw UnknownReifyMode("Int::rel");
419 }
420 }
421 break;
422 default:
423 throw UnknownRelation("Int::rel");
424 }
425 }
426
427 void
428 rel(Home home, const IntVarArgs& x, IntRelType irt,
429 IntPropLevel ipl) {
430 using namespace Int;
432 if ((irt != IRT_NQ) && (x.size() < 2))
433 return;
434 switch (irt) {
435 case IRT_EQ:
436 {
437 ViewArray<IntView> xv(home,x);
438 if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
440 } else {
442 }
443 }
444 break;
445 case IRT_NQ:
446 {
447 ViewArray<IntView> y(home,x);
449 }
450 break;
451 case IRT_LE:
452 {
453 ViewArray<IntView> y(home,x);
455 }
456 break;
457 case IRT_LQ:
458 {
459 ViewArray<IntView> y(home,x);
461 }
462 break;
463 case IRT_GR:
464 {
465 ViewArray<IntView> y(home,x.size());
466 for (int i=0; i<x.size(); i++)
467 y[i] = x[x.size()-1-i];
469 }
470 break;
471 case IRT_GQ:
472 {
473 ViewArray<IntView> y(home,x.size());
474 for (int i=0; i<x.size(); i++)
475 y[i] = x[x.size()-1-i];
477 }
478 break;
479 default:
480 throw UnknownRelation("Int::rel");
481 }
482 }
483
484 void
485 rel(Home home, const IntVarArgs& x, IntRelType irt, const IntVarArgs& y,
486 IntPropLevel ipl) {
487 using namespace Int;
489
490 switch (irt) {
491 case IRT_GR:
492 {
493 ViewArray<IntView> xv(home,x), yv(home,y);
495 ::post(home,yv,xv,true)));
496 }
497 break;
498 case IRT_LE:
499 {
500 ViewArray<IntView> xv(home,x), yv(home,y);
502 ::post(home,xv,yv,true)));
503 }
504 break;
505 case IRT_GQ:
506 {
507 ViewArray<IntView> xv(home,x), yv(home,y);
509 ::post(home,yv,xv,false)));
510 }
511 break;
512 case IRT_LQ:
513 {
514 ViewArray<IntView> xv(home,x), yv(home,y);
516 ::post(home,xv,yv,false)));
517 }
518 break;
519 case IRT_EQ:
520 if (x.size() != y.size()) {
521 home.fail();
522 } else if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF))
523 for (int i=0; i<x.size(); i++) {
525 ::post(home,x[i],y[i])));
526 }
527 else
528 for (int i=0; i<x.size(); i++) {
530 ::post(home,x[i],y[i])));
531 }
532 break;
533 case IRT_NQ:
534 {
535 ViewArray<IntView> xv(home,x), yv(home,y);
537 ::post(home,xv,yv)));
538 }
539 break;
540 default:
541 throw UnknownRelation("Int::rel");
542 }
543 }
544
545 namespace {
546
548 ViewArray<Int::ConstIntView>
549 viewarray(Space& home, const IntArgs& x) {
550 ViewArray<Int::ConstIntView> xv(home, x.size());
551 for (int i=0; i<x.size(); i++) {
552 Int::Limits::check(x[i],"Int::rel");
553 xv[i] = Int::ConstIntView(x[i]);
554 }
555 return xv;
556 }
557
558 }
559
560 void
561 rel(Home home, const IntVarArgs& x, IntRelType irt, const IntArgs& y,
562 IntPropLevel) {
563 using namespace Int;
565
566 switch (irt) {
567 case IRT_GR:
568 {
569 ViewArray<IntView> xv(home,x);
570 ViewArray<ConstIntView> yv(viewarray(home,y));
572 ::post(home,yv,xv,true)));
573 }
574 break;
575 case IRT_LE:
576 {
577 ViewArray<IntView> xv(home,x);
578 ViewArray<ConstIntView> yv(viewarray(home,y));
580 ::post(home,xv,yv,true)));
581 }
582 break;
583 case IRT_GQ:
584 {
585 ViewArray<IntView> xv(home,x);
586 ViewArray<ConstIntView> yv(viewarray(home,y));
588 ::post(home,yv,xv,false)));
589 }
590 break;
591 case IRT_LQ:
592 {
593 ViewArray<IntView> xv(home,x);
594 ViewArray<ConstIntView> yv(viewarray(home,y));
596 ::post(home,xv,yv,false)));
597 }
598 break;
599 case IRT_EQ:
600 if (x.size() != y.size()) {
601 home.fail();
602 } else {
603 for (int i=0; i<x.size(); i++)
604 GECODE_ME_FAIL(IntView(x[i]).eq(home,y[i]));
605 }
606 break;
607 case IRT_NQ:
608 {
609 ViewArray<IntView> xv(home,x);
610 ViewArray<ConstIntView> yv(viewarray(home,y));
612 ::post(home,xv,yv)));
613 }
614 break;
615 default:
616 throw UnknownRelation("Int::rel");
617 }
618 }
619
620 void
621 rel(Home home, const IntArgs& x, IntRelType irt, const IntVarArgs& y,
622 IntPropLevel ipl) {
623 rel(home,y,irt,x,ipl);
624 }
625
626}
627
628// STATISTICS: int-post
int n
Number of negative literals for node type.
Home class for posting propagators
Definition core.hpp:856
void fail(void)
Mark space as failed.
Definition core.hpp:4039
Passing integer arguments.
Definition int.hh:628
Passing integer variables.
Definition int.hh:656
Integer variables.
Definition int.hh:371
Integer view for integer variables.
Definition view.hpp:129
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition int.hpp:148
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition int.hpp:121
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition int.hpp:130
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition int.hpp:139
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition int.hpp:157
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:166
Negated Boolean view.
Definition view.hpp:1574
Binary bounds consistent equality propagator.
Definition rel.hh:134
Binary domain consistent equality propagator.
Definition rel.hh:68
Less propagator.
Definition rel.hh:517
Lexical ordering propagator.
Definition rel.hh:623
Lexical disequality propagator.
Definition rel.hh:657
Less or equal propagator.
Definition rel.hh:493
n-ary bounds consistent equality propagator
Definition rel.hh:196
n-ary domain consistent equality propagator
Definition rel.hh:164
n-ary less and less or equal propagator
Definition rel.hh:230
Nary disequality propagator.
Definition rel.hh:318
Binary disequality propagator.
Definition rel.hh:460
Reified bounds consistent equality with integer propagator.
Definition rel.hh:425
Reified binary bounds consistent equality propagator.
Definition rel.hh:372
Reified domain consistent equality with integer propagator.
Definition rel.hh:398
Reified binary domain consistent equality propagator.
Definition rel.hh:346
Reified less or equal with integer propagator.
Definition rel.hh:575
Reified less or equal propagator.
Definition rel.hh:548
Exception: Unknown reification mode passed as argument
Exception: Unknown relation passed as argument
Definition exception.hpp:87
Reification specification.
Definition int.hh:876
View arrays.
Definition array.hpp:253
#define GECODE_POST
Check for failure in a constraint post function.
Definition macros.hpp:40
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition macros.hpp:103
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition macros.hpp:77
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
IntRelType
Relation types for integers.
Definition int.hh:925
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:974
@ IRT_EQ
Equality ( )
Definition int.hh:926
@ IRT_NQ
Disequality ( )
Definition int.hh:927
@ IRT_GQ
Greater or equal ( )
Definition int.hh:930
@ IRT_LE
Less ( )
Definition int.hh:929
@ IRT_GR
Greater ( )
Definition int.hh:931
@ IRT_LQ
Less or equal ( )
Definition int.hh:928
@ RM_IMP
Implication for reification.
Definition int.hh:862
@ RM_PMI
Inverse implication for reification.
Definition int.hh:869
@ RM_EQV
Equivalence for reification (default)
Definition int.hh:855
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:979
@ IPL_DEF
Simple propagation levels.
Definition int.hh:976
@ IPL_BND
Bounds propagation.
Definition int.hh:978
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition limits.hpp:46
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition ipl.hpp:37
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition filter.cpp:138
Post propagator for SetVar x
Definition set.hh:767