Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
630 dom(Home home, SetVar x, SetVar d) {
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:1613
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.
int max(int i) const
Return maximum of range at position i.
int ranges(void) const
Return number of ranges of the specification.
unsigned int size(void) const
Return size (cardinality) of set.
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
Exception: Unknown relation passed as argument
Definition exception.hpp:87
Reification specification.
Definition int.hh:891
Passing set variables.
Definition set.hh:491
Set variables
Definition set.hh:127
Constant view.
Definition view.hpp:186
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Range iterator for the least upper bound.
Definition var-imp.hpp:317
A complement iterator spezialized for the BndSet limits.
Definition var-imp.hpp:293
Propagator for negated equality
Definition rel.hh:296
static ExecStatus post(Home home, View0 x, ConstSetView y)
Post propagator .
Definition nq.hpp:99
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
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition set.hpp:164
ModEvent include(Space &home, int i, int j)
Update greatest lower bound to include all elements between and including i and j.
Definition set.hpp:126
unsigned int cardMin(void) const
Return minimum cardinality.
Definition set.hpp:82
unsigned int cardMax(void) const
Return maximum cardinality.
Definition set.hpp:86
ModEvent intersect(Space &home, int i, int j)
Update least upper bound to contain at most all elements between and including i and j.
Definition set.hpp:141
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
Definition set.hpp:160
ModEvent exclude(Space &home, int i, int j)
Restrict least upper bound to not contain all elements between and including i and j.
Definition set.hpp:156
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
Definition set.hpp:151
#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:877
@ RM_PMI
Inverse implication for reification.
Definition int.hh:884
@ RM_EQV
Equivalence for reification (default)
Definition int.hh:870
SetRelType
Common relation types for sets.
Definition set.hh:649
@ SRT_GQ
Greater or equal ( )
Definition set.hh:658
@ SRT_CMPL
Complement.
Definition set.hh:655
@ SRT_GR
Greater ( )
Definition set.hh:659
@ SRT_LQ
Less or equal ( )
Definition set.hh:656
@ SRT_NQ
Disequality ( )
Definition set.hh:651
@ SRT_LE
Less ( )
Definition set.hh:657
@ SRT_EQ
Equality ( )
Definition set.hh:650
@ SRT_SUP
Superset ( )
Definition set.hh:653
@ SRT_DISJ
Disjoint ( )
Definition set.hh:654
@ SRT_SUB
Subset ( )
Definition set.hh:652
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
Finite integer sets.
Definition var-imp.hpp:137
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
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:773