Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.9.4
dom.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 *
6 * Contributing authors:
7 * Gabor Szokoli <szokoli@gecode.org>
8 *
9 * Copyright:
10 * Guido Tack, 2004, 2005
11 *
12 * This file is part of Gecode, the generic constraint
13 * development environment:
14 * http://www.gecode.org
15 *
16 * Permission is hereby granted, free of charge, to any person obtaining
17 * a copy of this software and associated documentation files (the
18 * "Software"), to deal in the Software without restriction, including
19 * without limitation the rights to use, copy, modify, merge, publish,
20 * distribute, sublicense, and/or sell copies of the Software, and to
21 * permit persons to whom the Software is furnished to do so, subject to
22 * the following conditions:
23 *
24 * The above copyright notice and this permission notice shall be
25 * included in all copies or substantial portions of the Software.
26 *
27 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
28 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
29 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
30 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
31 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
32 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
33 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
34 *
35 */
36
37#include <gecode/set.hh>
38#include <gecode/set/rel.hh>
39
40namespace Gecode {
41
42 void
43 dom(Home home, SetVar s, SetRelType r, int i) {
44 Set::Limits::check(i, "Set::dom");
45 IntSet d(i,i);
46 dom(home, s, r, d);
47 }
48
49 void
50 dom(Home home, const SetVarArgs& s, SetRelType r, int i) {
51 Set::Limits::check(i, "Set::dom");
52 IntSet d(i,i);
53 dom(home, s, r, d);
54 }
55
56 void
57 dom(Home home, SetVar s, SetRelType r, int i, int j) {
58 Set::Limits::check(i, "Set::dom");
59 Set::Limits::check(j, "Set::dom");
60 IntSet d(i,j);
61 dom(home, s, r, d);
62 }
63
64 void
65 dom(Home home, const SetVarArgs& s, SetRelType r, int i, int j) {
66 Set::Limits::check(i, "Set::dom");
67 Set::Limits::check(j, "Set::dom");
68 IntSet d(i,j);
69 dom(home, s, r, d);
70 }
71
72 void
73 dom(Home home, SetVar s, SetRelType r, const IntSet& is) {
74 Set::Limits::check(is, "Set::dom");
76
77 Set::SetView _s(s);
78
79 switch (r) {
80 case SRT_EQ:
81 {
82 if (is.ranges() == 1) {
83 GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
84 GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
85 } else {
86 IntSetRanges rd1(is);
87 GECODE_ME_FAIL(_s.includeI(home, rd1));
88 IntSetRanges rd2(is);
89 GECODE_ME_FAIL(_s.intersectI(home, rd2));
90 }
91 }
92 break;
93 case SRT_LQ:
94 {
95 Set::ConstSetView cv(home, is);
98 ::post(home,s,cv)));
99 }
100 break;
101 case SRT_LE:
102 {
103 Set::ConstSetView cv(home, is);
106 ::post(home,s,cv)));
107 }
108 break;
109 case SRT_GQ:
110 {
111 Set::ConstSetView cv(home, is);
114 ::post(home,cv,s)));
115 }
116 break;
117 case SRT_GR:
118 {
119 Set::ConstSetView cv(home, is);
122 ::post(home,cv,s)));
123 }
124 break;
125 case SRT_DISJ:
126 {
127 if (is.ranges() == 1) {
128 GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
129 } else {
130 IntSetRanges rd(is);
131 GECODE_ME_FAIL(_s.excludeI(home, rd));
132 }
133 }
134 break;
135 case SRT_NQ:
136 {
137 Set::ConstSetView cv(home, is);
140 cv)));
141 }
142 break;
143 case SRT_SUB:
144 {
145 if (is.ranges() == 1) {
146 GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
147 } else {
148 IntSetRanges rd(is);
149 GECODE_ME_FAIL(_s.intersectI(home, rd));
150 }
151 }
152 break;
153 case SRT_SUP:
154 {
155 if (is.ranges() == 1) {
156 GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
157 } else {
158 IntSetRanges rd(is);
159 GECODE_ME_FAIL(_s.includeI(home, rd));
160 }
161 }
162 break;
163 case SRT_CMPL:
164 {
165 if (is.ranges() == 1) {
166 GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
168 _s.include(home,
170 is.min()-1) );
172 _s.include(home, is.max()+1,
174 } else {
175 IntSetRanges rd1(is);
177 GECODE_ME_FAIL(_s.includeI(home, rdC1));
178 IntSetRanges rd2(is);
180 GECODE_ME_FAIL(_s.intersectI(home, rdC2));
181 }
182 }
183 break;
184 default:
185 throw Set::UnknownRelation("Set::dom");
186 }
187 }
188
189 void
190 dom(Home home, const SetVarArgs& s, SetRelType r, const IntSet& is) {
191 Set::Limits::check(is, "Set::dom");
193
194 switch (r) {
195 case SRT_EQ:
196 {
197 if (is.ranges() == 1) {
198 for (int i=s.size(); i--; ) {
199 Set::SetView _s(s[i]);
200 GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
201 GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
202 }
203 } else {
204 for (int i=s.size(); i--; ) {
205 Set::SetView _s(s[i]);
206 IntSetRanges rd1(is);
207 GECODE_ME_FAIL(_s.includeI(home, rd1));
208 IntSetRanges rd2(is);
209 GECODE_ME_FAIL(_s.intersectI(home, rd2));
210 }
211 }
212 }
213 break;
214 case SRT_LQ:
215 {
216 Set::ConstSetView cv(home, is);
217 for (int i=s.size(); i--; ) {
218 Set::SetView _s(s[i]);
220 ::post(home,_s,cv)));
221 }
222 }
223 break;
224 case SRT_LE:
225 {
226 Set::ConstSetView cv(home, is);
227 for (int i=s.size(); i--; ) {
228 Set::SetView _s(s[i]);
230 ::post(home,_s,cv)));
231 }
232 }
233 break;
234 case SRT_GQ:
235 {
236 Set::ConstSetView cv(home, is);
237 for (int i=s.size(); i--; ) {
238 Set::SetView _s(s[i]);
240 ::post(home,cv,_s)));
241 }
242 }
243 break;
244 case SRT_GR:
245 {
246 Set::ConstSetView cv(home, is);
247 for (int i=s.size(); i--; ) {
248 Set::SetView _s(s[i]);
250 ::post(home,cv,_s)));
251 }
252 }
253 break;
254 case SRT_DISJ:
255 {
256 if (is.ranges() == 1) {
257 for (int i=s.size(); i--; ) {
258 Set::SetView _s(s[i]);
259 GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
260 }
261 } else {
262 for (int i=s.size(); i--; ) {
263 Set::SetView _s(s[i]);
264 IntSetRanges rd(is);
265 GECODE_ME_FAIL(_s.excludeI(home, rd));
266 }
267 }
268 }
269 break;
270 case SRT_NQ:
271 {
272 Set::ConstSetView cv(home, is);
273 for (int i=s.size(); i--; ) {
274 Set::SetView _s(s[i]);
276 ::post(home,_s,cv)));
277 }
278 }
279 break;
280 case SRT_SUB:
281 {
282 if (is.ranges() == 1) {
283 for (int i=s.size(); i--; ) {
284 Set::SetView _s(s[i]);
285 GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
286 }
287 } else {
288 for (int i=s.size(); i--; ) {
289 Set::SetView _s(s[i]);
290 IntSetRanges rd(is);
291 GECODE_ME_FAIL(_s.intersectI(home, rd));
292 }
293 }
294 }
295 break;
296 case SRT_SUP:
297 {
298 if (is.ranges() == 1) {
299 for (int i=s.size(); i--; ) {
300 Set::SetView _s(s[i]);
301 GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
302 }
303 } else {
304 for (int i=s.size(); i--; ) {
305 Set::SetView _s(s[i]);
306 IntSetRanges rd(is);
307 GECODE_ME_FAIL(_s.includeI(home, rd));
308 }
309 }
310 }
311 break;
312 case SRT_CMPL:
313 {
314 if (is.ranges() == 1) {
315 for (int i=s.size(); i--; ) {
316 Set::SetView _s(s[i]);
317 GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
318 GECODE_ME_FAIL(_s.include(home,
320 is.min()-1) );
321 GECODE_ME_FAIL(_s.include(home, is.max()+1,
323 }
324 } else {
325 for (int i=s.size(); i--; ) {
326 Set::SetView _s(s[i]);
327 IntSetRanges rd1(is);
329 GECODE_ME_FAIL(_s.includeI(home, rdC1));
330 IntSetRanges rd2(is);
332 GECODE_ME_FAIL(_s.intersectI(home, rdC2));
333 }
334 }
335 }
336 break;
337 default:
338 throw Set::UnknownRelation("Set::dom");
339 }
340 }
341
342 void
343 dom(Home home, SetVar s, SetRelType rt, int i, Reify r) {
344 Set::Limits::check(i, "Set::dom");
345 IntSet d(i,i);
346 dom(home, s, rt, d, r);
347 }
348
349 void
350 dom(Home home, SetVar s, SetRelType rt, int i, int j, Reify r) {
351 Set::Limits::check(i, "Set::dom");
352 Set::Limits::check(j, "Set::dom");
353 IntSet d(i,j);
354 dom(home, s, rt, d, r);
355 }
356
357 void
358 dom(Home home, SetVar s, SetRelType rt, const IntSet& is, Reify r) {
359 Set::Limits::check(is, "Set::dom");
361 switch (rt) {
362 case SRT_EQ:
363 {
364 Set::ConstSetView cv(home, is);
365 switch (r.mode()) {
366 case RM_EQV:
370 ::post(home, s, cv, r.var())));
371 break;
372 case RM_IMP:
376 ::post(home, s, cv, r.var())));
377 break;
378 case RM_PMI:
382 ::post(home, s, cv, r.var())));
383 break;
384 default: throw Gecode::Int::UnknownReifyMode("Set::dom");
385 }
386 }
387 break;
388 case SRT_LQ:
389 {
390 Set::ConstSetView cv(home, is);
391 switch (r.mode()) {
392 case RM_EQV:
395 Set::ConstSetView,RM_EQV,false>::post(home, s, cv, r.var())));
396 break;
397 case RM_IMP:
400 Set::ConstSetView,RM_IMP,false>::post(home, s, cv, r.var())));
401 break;
402 case RM_PMI:
405 Set::ConstSetView,RM_PMI,false>::post(home, s, cv, r.var())));
406 break;
407 default: throw Gecode::Int::UnknownReifyMode("Set::dom");
408 }
409 }
410 break;
411 case SRT_LE:
412 {
413 Set::ConstSetView cv(home, is);
414 switch (r.mode()) {
415 case RM_EQV:
418 Set::ConstSetView,RM_EQV,true>::post(home, s, cv, r.var())));
419 break;
420 case RM_IMP:
423 Set::ConstSetView,RM_IMP,true>::post(home, s, cv, r.var())));
424 break;
425 case RM_PMI:
428 Set::ConstSetView,RM_PMI,true>::post(home, s, cv, r.var())));
429 break;
430 default: throw Gecode::Int::UnknownReifyMode("Set::dom");
431 }
432 }
433 break;
434 case SRT_GQ:
435 {
436 Set::ConstSetView cv(home, is);
437 switch (r.mode()) {
438 case RM_EQV:
441 ::post(home,cv,s,r.var())));
442 break;
443 case RM_IMP:
446 ::post(home,cv,s,r.var())));
447 break;
448 case RM_PMI:
451 ::post(home,cv,s,r.var())));
452 break;
453 default: throw Gecode::Int::UnknownReifyMode("Set::dom");
454 }
455 }
456 break;
457 case SRT_GR:
458 {
459 Set::ConstSetView cv(home, is);
460 switch (r.mode()) {
461 case RM_EQV:
464 ::post(home,cv,s,r.var())));
465 break;
466 case RM_IMP:
469 ::post(home,cv,s,r.var())));
470 break;
471 case RM_PMI:
474 ::post(home,cv,s,r.var())));
475 break;
476 default: throw Gecode::Int::UnknownReifyMode("Set::dom");
477 }
478 }
479 break;
480 case SRT_NQ:
481 {
482 Gecode::Int::NegBoolView notb(r.var());
483 Set::ConstSetView cv(home, is);
484 switch (r.mode()) {
485 case RM_EQV:
489 ::post(home, s, cv, notb)));
490 break;
491 case RM_IMP:
495 ::post(home, s, cv, notb)));
496 break;
497 case RM_PMI:
501 ::post(home, s, cv, notb)));
502 break;
503 default: throw Gecode::Int::UnknownReifyMode("Set::dom");
504 }
505 }
506 break;
507 case SRT_SUB:
508 {
509 Set::ConstSetView cv(home, is);
510 switch (r.mode()) {
511 case RM_EQV:
515 ::post(home, s, cv, r.var())));
516 break;
517 case RM_IMP:
521 ::post(home, s, cv, r.var())));
522 break;
523 case RM_PMI:
527 ::post(home, s, cv, r.var())));
528 break;
529 default: throw Gecode::Int::UnknownReifyMode("Set::dom");
530 }
531 }
532 break;
533 case SRT_SUP:
534 {
535 Set::ConstSetView cv(home, is);
536 switch (r.mode()) {
537 case RM_EQV:
541 ::post(home, cv, s, r.var())));
542 break;
543 case RM_IMP:
547 ::post(home, cv, s, r.var())));
548 break;
549 case RM_PMI:
553 ::post(home, cv, s, r.var())));
554 break;
555 default: throw Gecode::Int::UnknownReifyMode("Set::dom");
556 }
557 }
558 break;
559 case SRT_DISJ:
560 {
561 // x||y <=> b is equivalent to
562 // ( y <= complement(x) and x<=complement(y) ) <=> b
563
564 // compute complement of is
565 IntSetRanges dr1(is);
567 IntSet dcompl(dc1);
568 Set::ConstSetView cvcompl(home, dcompl);
569 switch (r.mode()) {
570 case RM_EQV:
574 ::post(home, s, cvcompl, r.var())));
575 break;
576 case RM_IMP:
580 ::post(home, s, cvcompl, r.var())));
581 break;
582 case RM_PMI:
586 ::post(home, s, cvcompl, r.var())));
587 break;
588 default: throw Gecode::Int::UnknownReifyMode("Set::dom");
589 }
590 }
591 break;
592 case SRT_CMPL:
593 {
594 Set::SetView sv(s);
595
596 IntSetRanges dr1(is);
598 IntSet dcompl(dc1);
599 Set::ConstSetView cvcompl(home, dcompl);
600
601 switch (r.mode()) {
602 case RM_EQV:
606 ::post(home, s, cvcompl, r.var())));
607 break;
608 case RM_IMP:
612 ::post(home, s, cvcompl, r.var())));
613 break;
614 case RM_PMI:
618 ::post(home, s, cvcompl, r.var())));
619 break;
620 default: throw Gecode::Int::UnknownReifyMode("Set::dom");
621 }
622 }
623 break;
624 default:
625 throw Set::UnknownRelation("Set::dom");
626 }
627 }
628
629 void
631 using namespace Set;
633 SetView xv(x), dv(d);
634 if (xv != dv) {
635 GECODE_ME_FAIL(xv.cardMax(home,dv.cardMax()));
636 GECODE_ME_FAIL(xv.cardMin(home,dv.cardMin()));
637 GlbRanges<SetView> lb(dv);
638 GECODE_ME_FAIL(xv.includeI(home,lb));
639 LubRanges<SetView> ub(dv);
640 GECODE_ME_FAIL(xv.intersectI(home,ub));
641 }
642 }
643
644 void
645 dom(Home home, const SetVarArgs& x, const SetVarArgs& d) {
646 using namespace Set;
647 if (x.size() != d.size())
648 throw ArgumentSizeMismatch("Set::dom");
649 for (int i=x.size(); i--; ) {
651 SetView xv(x[i]), dv(d[i]);
652 if (xv != dv) {
653 GECODE_ME_FAIL(xv.cardMax(home,dv.cardMax()));
654 GECODE_ME_FAIL(xv.cardMin(home,dv.cardMin()));
655 GlbRanges<SetView> lb(dv);
656 GECODE_ME_FAIL(xv.includeI(home,lb));
657 LubRanges<SetView> ub(dv);
658 GECODE_ME_FAIL(xv.intersectI(home,ub));
659 }
660 }
661 }
662
663}
664
665// STATISTICS: set-post
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
Home class for posting propagators
Definition: core.hpp:856
Range iterator for integer sets.
Definition: int.hh:292
Integer sets.
Definition: int.hh:174
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:152
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:158
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:171
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:198
Exception: Arguments are of different size
Definition: exception.hpp:73
Boolean view for Boolean variables.
Definition: view.hpp:1380
Negated Boolean view.
Definition: view.hpp:1574
Exception: Unknown reification mode passed as argument
Definition: exception.hpp:115
Exception: Unknown relation passed as argument
Definition: exception.hpp:87
Reification specification.
Definition: int.hh:876
Passing set variables.
Definition: set.hh:488
Set variables
Definition: set.hh:127
Constant view.
Definition: view.hpp:186
Range iterator for greatest lower bound of set variable views
Definition: set.hpp:242
Range iterator for least upper bound of set variable views
Definition: set.hpp:211
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:293
Propagator for negated equality
Definition: rel.hh:296
Propagator for set less than or equal
Definition: rel.hh:208
Reified equality propagator
Definition: rel.hh:174
Reified propagator for set less than or equal
Definition: rel.hh:234
Reified subset propagator
Definition: rel.hh:115
Set view for set variables
Definition: view.hpp:56
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: set.hpp:82
unsigned int cardMax(void) const
Return maximum cardinality.
Definition: set.hpp:86
#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
@ 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
SetRelType
Common relation types for sets.
Definition: set.hh:643
@ SRT_GQ
Greater or equal ( )
Definition: set.hh:652
@ SRT_CMPL
Complement.
Definition: set.hh:649
@ SRT_GR
Greater ( )
Definition: set.hh:653
@ SRT_LQ
Less or equal ( )
Definition: set.hh:650
@ SRT_NQ
Disequality ( )
Definition: set.hh:645
@ SRT_LE
Less ( )
Definition: set.hh:651
@ SRT_EQ
Equality ( )
Definition: set.hh:644
@ SRT_SUP
Superset ( )
Definition: set.hh:647
@ SRT_DISJ
Disjoint ( )
Definition: set.hh:648
@ SRT_SUB
Subset ( )
Definition: set.hh:646
void check(int n, const char *l)
Check whether integer n is in range, otherwise throw overflow exception with information l.
Definition: limits.hpp:37
const int min
Smallest allowed integer in integer set.
Definition: set.hh:99
const int max
Largest allowed integer in integer set.
Definition: set.hh:97
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:40
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
Gecode::IntArgs i({1, 2, 3, 4})
DomRange dr1(1)
Gecode::IntSet d(r, 4)