this repo has no description
dekker.one
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");
75 GECODE_POST;
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);
96 GECODE_ES_FAIL(
97 (Set::Rel::Lq<Set::SetView,Set::ConstSetView,false>
98 ::post(home,s,cv)));
99 }
100 break;
101 case SRT_LE:
102 {
103 Set::ConstSetView cv(home, is);
104 GECODE_ES_FAIL(
105 (Set::Rel::Lq<Set::SetView,Set::ConstSetView,true>
106 ::post(home,s,cv)));
107 }
108 break;
109 case SRT_GQ:
110 {
111 Set::ConstSetView cv(home, is);
112 GECODE_ES_FAIL(
113 (Set::Rel::Lq<Set::ConstSetView,Set::SetView,false>
114 ::post(home,cv,s)));
115 }
116 break;
117 case SRT_GR:
118 {
119 Set::ConstSetView cv(home, is);
120 GECODE_ES_FAIL(
121 (Set::Rel::Lq<Set::ConstSetView,Set::SetView,true>
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);
138 GECODE_ES_FAIL(
139 (Set::Rel::DistinctDoit<Set::SetView>::post(home, s,
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()));
167 GECODE_ME_FAIL(
168 _s.include(home,
169 Set::Limits::min,
170 is.min()-1) );
171 GECODE_ME_FAIL(
172 _s.include(home, is.max()+1,
173 Set::Limits::max) );
174 } else {
175 IntSetRanges rd1(is);
176 Set::RangesCompl<IntSetRanges > rdC1(rd1);
177 GECODE_ME_FAIL(_s.includeI(home, rdC1));
178 IntSetRanges rd2(is);
179 Set::RangesCompl<IntSetRanges > rdC2(rd2);
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");
192 GECODE_POST;
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]);
219 GECODE_ES_FAIL((Set::Rel::Lq<Set::SetView,Set::ConstSetView,false>
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]);
229 GECODE_ES_FAIL((Set::Rel::Lq<Set::SetView,Set::ConstSetView,true>
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]);
239 GECODE_ES_FAIL((Set::Rel::Lq<Set::ConstSetView,Set::SetView,false>
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]);
249 GECODE_ES_FAIL((Set::Rel::Lq<Set::ConstSetView,Set::SetView,true>
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]);
275 GECODE_ES_FAIL((Set::Rel::DistinctDoit<Set::SetView>
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,
319 Set::Limits::min,
320 is.min()-1) );
321 GECODE_ME_FAIL(_s.include(home, is.max()+1,
322 Set::Limits::max) );
323 }
324 } else {
325 for (int i=s.size(); i--; ) {
326 Set::SetView _s(s[i]);
327 IntSetRanges rd1(is);
328 Set::RangesCompl<IntSetRanges > rdC1(rd1);
329 GECODE_ME_FAIL(_s.includeI(home, rdC1));
330 IntSetRanges rd2(is);
331 Set::RangesCompl<IntSetRanges > rdC2(rd2);
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");
360 GECODE_POST;
361 switch (rt) {
362 case SRT_EQ:
363 {
364 Set::ConstSetView cv(home, is);
365 switch (r.mode()) {
366 case RM_EQV:
367 GECODE_ES_FAIL(
368 (Set::Rel::ReEq<Set::SetView,
369 Set::ConstSetView,Gecode::Int::BoolView,RM_EQV>
370 ::post(home, s, cv, r.var())));
371 break;
372 case RM_IMP:
373 GECODE_ES_FAIL(
374 (Set::Rel::ReEq<Set::SetView,
375 Set::ConstSetView,Gecode::Int::BoolView,RM_IMP>
376 ::post(home, s, cv, r.var())));
377 break;
378 case RM_PMI:
379 GECODE_ES_FAIL(
380 (Set::Rel::ReEq<Set::SetView,
381 Set::ConstSetView,Gecode::Int::BoolView,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:
393 GECODE_ES_FAIL(
394 (Set::Rel::ReLq<Set::SetView,
395 Set::ConstSetView,RM_EQV,false>::post(home, s, cv, r.var())));
396 break;
397 case RM_IMP:
398 GECODE_ES_FAIL(
399 (Set::Rel::ReLq<Set::SetView,
400 Set::ConstSetView,RM_IMP,false>::post(home, s, cv, r.var())));
401 break;
402 case RM_PMI:
403 GECODE_ES_FAIL(
404 (Set::Rel::ReLq<Set::SetView,
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:
416 GECODE_ES_FAIL(
417 (Set::Rel::ReLq<Set::SetView,
418 Set::ConstSetView,RM_EQV,true>::post(home, s, cv, r.var())));
419 break;
420 case RM_IMP:
421 GECODE_ES_FAIL(
422 (Set::Rel::ReLq<Set::SetView,
423 Set::ConstSetView,RM_IMP,true>::post(home, s, cv, r.var())));
424 break;
425 case RM_PMI:
426 GECODE_ES_FAIL(
427 (Set::Rel::ReLq<Set::SetView,
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:
439 GECODE_ES_FAIL(
440 (Set::Rel::ReLq<Set::ConstSetView,Set::SetView,RM_EQV,false>
441 ::post(home,cv,s,r.var())));
442 break;
443 case RM_IMP:
444 GECODE_ES_FAIL(
445 (Set::Rel::ReLq<Set::ConstSetView,Set::SetView,RM_IMP,false>
446 ::post(home,cv,s,r.var())));
447 break;
448 case RM_PMI:
449 GECODE_ES_FAIL(
450 (Set::Rel::ReLq<Set::ConstSetView,Set::SetView,RM_PMI,false>
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:
462 GECODE_ES_FAIL(
463 (Set::Rel::ReLq<Set::ConstSetView,Set::SetView,RM_EQV,true>
464 ::post(home,cv,s,r.var())));
465 break;
466 case RM_IMP:
467 GECODE_ES_FAIL(
468 (Set::Rel::ReLq<Set::ConstSetView,Set::SetView,RM_IMP,true>
469 ::post(home,cv,s,r.var())));
470 break;
471 case RM_PMI:
472 GECODE_ES_FAIL(
473 (Set::Rel::ReLq<Set::ConstSetView,Set::SetView,RM_PMI,true>
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:
486 GECODE_ES_FAIL(
487 (Set::Rel::ReEq<Set::SetView,
488 Set::ConstSetView,Gecode::Int::NegBoolView,RM_EQV>
489 ::post(home, s, cv, notb)));
490 break;
491 case RM_IMP:
492 GECODE_ES_FAIL(
493 (Set::Rel::ReEq<Set::SetView,
494 Set::ConstSetView,Gecode::Int::NegBoolView,RM_PMI>
495 ::post(home, s, cv, notb)));
496 break;
497 case RM_PMI:
498 GECODE_ES_FAIL(
499 (Set::Rel::ReEq<Set::SetView,
500 Set::ConstSetView,Gecode::Int::NegBoolView,RM_IMP>
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:
512 GECODE_ES_FAIL(
513 (Set::Rel::ReSubset<Set::SetView,
514 Set::ConstSetView,Gecode::Int::BoolView,RM_EQV>
515 ::post(home, s, cv, r.var())));
516 break;
517 case RM_IMP:
518 GECODE_ES_FAIL(
519 (Set::Rel::ReSubset<Set::SetView,
520 Set::ConstSetView,Gecode::Int::BoolView,RM_IMP>
521 ::post(home, s, cv, r.var())));
522 break;
523 case RM_PMI:
524 GECODE_ES_FAIL(
525 (Set::Rel::ReSubset<Set::SetView,
526 Set::ConstSetView,Gecode::Int::BoolView,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:
538 GECODE_ES_FAIL(
539 (Set::Rel::ReSubset<Set::ConstSetView,Set::SetView,
540 Gecode::Int::BoolView,RM_EQV>
541 ::post(home, cv, s, r.var())));
542 break;
543 case RM_IMP:
544 GECODE_ES_FAIL(
545 (Set::Rel::ReSubset<Set::ConstSetView,Set::SetView,
546 Gecode::Int::BoolView,RM_IMP>
547 ::post(home, cv, s, r.var())));
548 break;
549 case RM_PMI:
550 GECODE_ES_FAIL(
551 (Set::Rel::ReSubset<Set::ConstSetView,Set::SetView,
552 Gecode::Int::BoolView,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);
566 Set::RangesCompl<IntSetRanges > dc1(dr1);
567 IntSet dcompl(dc1);
568 Set::ConstSetView cvcompl(home, dcompl);
569 switch (r.mode()) {
570 case RM_EQV:
571 GECODE_ES_FAIL(
572 (Set::Rel::ReSubset<Set::SetView,
573 Set::ConstSetView,Gecode::Int::BoolView,RM_EQV>
574 ::post(home, s, cvcompl, r.var())));
575 break;
576 case RM_IMP:
577 GECODE_ES_FAIL(
578 (Set::Rel::ReSubset<Set::SetView,
579 Set::ConstSetView,Gecode::Int::BoolView,RM_IMP>
580 ::post(home, s, cvcompl, r.var())));
581 break;
582 case RM_PMI:
583 GECODE_ES_FAIL(
584 (Set::Rel::ReSubset<Set::SetView,
585 Set::ConstSetView,Gecode::Int::BoolView,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);
597 Set::RangesCompl<IntSetRanges> dc1(dr1);
598 IntSet dcompl(dc1);
599 Set::ConstSetView cvcompl(home, dcompl);
600
601 switch (r.mode()) {
602 case RM_EQV:
603 GECODE_ES_FAIL(
604 (Set::Rel::ReEq<Set::SetView,
605 Set::ConstSetView,Gecode::Int::BoolView,RM_EQV>
606 ::post(home, s, cvcompl, r.var())));
607 break;
608 case RM_IMP:
609 GECODE_ES_FAIL(
610 (Set::Rel::ReEq<Set::SetView,
611 Set::ConstSetView,Gecode::Int::BoolView,RM_IMP>
612 ::post(home, s, cvcompl, r.var())));
613 break;
614 case RM_PMI:
615 GECODE_ES_FAIL(
616 (Set::Rel::ReEq<Set::SetView,
617 Set::ConstSetView,Gecode::Int::BoolView,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;
632 GECODE_POST;
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--; ) {
650 GECODE_POST;
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