this repo has no description
dekker.one
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");
45 GECODE_POST;
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");
62 GECODE_POST;
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;
102 GECODE_POST;
103 switch (irt) {
104 case IRT_EQ:
105 if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
106 GECODE_ES_FAIL((Rel::EqDom<IntView,IntView>::post(home,x0,x1)));
107 } else {
108 GECODE_ES_FAIL((Rel::EqBnd<IntView,IntView>::post(home,x0,x1)));
109 }
110 break;
111 case IRT_NQ:
112 GECODE_ES_FAIL((Rel::Nq<IntView,IntView>::post(home,x0,x1))); break;
113 case IRT_GQ:
114 std::swap(x0,x1); // Fall through
115 case IRT_LQ:
116 GECODE_ES_FAIL((Rel::Lq<IntView,IntView>::post(home,x0,x1))); break;
117 case IRT_GR:
118 std::swap(x0,x1); // Fall through
119 case IRT_LE:
120 GECODE_ES_FAIL((Rel::Le<IntView,IntView>::post(home,x0,x1))); break;
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;
130 GECODE_POST;
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)) {
139 GECODE_ES_FAIL(Rel::NaryEqDom<IntView>::post(home,xv));
140 } else {
141 GECODE_ES_FAIL(Rel::NaryEqBnd<IntView>::post(home,xv));
142 }
143 }
144 break;
145 case IRT_NQ:
146 for (int i=0; i<x.size(); i++) {
147 GECODE_ES_FAIL((Rel::Nq<IntView,IntView>::post(home,x[i],y)));
148 }
149 break;
150 case IRT_GQ:
151 for (int i=0; i<x.size(); i++) {
152 GECODE_ES_FAIL((Rel::Lq<IntView,IntView>::post(home,y,x[i])));
153 }
154 break;
155 case IRT_LQ:
156 for (int i=0; i<x.size(); i++) {
157 GECODE_ES_FAIL((Rel::Lq<IntView,IntView>::post(home,x[i],y)));
158 }
159 break;
160 case IRT_GR:
161 for (int i=0; i<x.size(); i++) {
162 GECODE_ES_FAIL((Rel::Le<IntView,IntView>::post(home,y,x[i])));
163 }
164 break;
165 case IRT_LE:
166 for (int i=0; i<x.size(); i++) {
167 GECODE_ES_FAIL((Rel::Le<IntView,IntView>::post(home,x[i],y)));
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;
180 GECODE_POST;
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:
186 GECODE_ES_FAIL((Rel::ReEqDom<IntView,BoolView,RM_EQV>
187 ::post(home,x0,x1,r.var())));
188 break;
189 case RM_IMP:
190 GECODE_ES_FAIL((Rel::ReEqDom<IntView,BoolView,RM_IMP>
191 ::post(home,x0,x1,r.var())));
192 break;
193 case RM_PMI:
194 GECODE_ES_FAIL((Rel::ReEqDom<IntView,BoolView,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:
202 GECODE_ES_FAIL((Rel::ReEqBnd<IntView,BoolView,RM_EQV>
203 ::post(home,x0,x1,r.var())));
204 break;
205 case RM_IMP:
206 GECODE_ES_FAIL((Rel::ReEqBnd<IntView,BoolView,RM_IMP>
207 ::post(home,x0,x1,r.var())));
208 break;
209 case RM_PMI:
210 GECODE_ES_FAIL((Rel::ReEqBnd<IntView,BoolView,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:
223 GECODE_ES_FAIL((Rel::ReEqBnd<IntView,NegBoolView,RM_EQV>
224 ::post(home,x0,x1,n)));
225 break;
226 case RM_IMP:
227 GECODE_ES_FAIL((Rel::ReEqBnd<IntView,NegBoolView,RM_PMI>
228 ::post(home,x0,x1,n)));
229 break;
230 case RM_PMI:
231 GECODE_ES_FAIL((Rel::ReEqBnd<IntView,NegBoolView,RM_IMP>
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:
239 GECODE_ES_FAIL((Rel::ReEqDom<IntView,NegBoolView,RM_EQV>
240 ::post(home,x0,x1,n)));
241 break;
242 case RM_IMP:
243 GECODE_ES_FAIL((Rel::ReEqDom<IntView,NegBoolView,RM_PMI>
244 ::post(home,x0,x1,n)));
245 break;
246 case RM_PMI:
247 GECODE_ES_FAIL((Rel::ReEqDom<IntView,NegBoolView,RM_IMP>
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:
260 GECODE_ES_FAIL((Rel::ReLq<IntView,BoolView,RM_EQV>
261 ::post(home,x0,x1,r.var())));
262 break;
263 case RM_IMP:
264 GECODE_ES_FAIL((Rel::ReLq<IntView,BoolView,RM_IMP>
265 ::post(home,x0,x1,r.var())));
266 break;
267 case RM_PMI:
268 GECODE_ES_FAIL((Rel::ReLq<IntView,BoolView,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:
281 GECODE_ES_FAIL((Rel::ReLq<IntView,NegBoolView,RM_EQV>
282 ::post(home,x0,x1,n)));
283 break;
284 case RM_IMP:
285 GECODE_ES_FAIL((Rel::ReLq<IntView,NegBoolView,RM_PMI>
286 ::post(home,x0,x1,n)));
287 break;
288 case RM_PMI:
289 GECODE_ES_FAIL((Rel::ReLq<IntView,NegBoolView,RM_IMP>
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");
306 GECODE_POST;
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:
312 GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,BoolView,RM_EQV>
313 ::post(home,x,n,r.var())));
314 break;
315 case RM_IMP:
316 GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,BoolView,RM_IMP>
317 ::post(home,x,n,r.var())));
318 break;
319 case RM_PMI:
320 GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,BoolView,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:
328 GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,BoolView,RM_EQV>
329 ::post(home,x,n,r.var())));
330 break;
331 case RM_IMP:
332 GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,BoolView,RM_IMP>
333 ::post(home,x,n,r.var())));
334 break;
335 case RM_PMI:
336 GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,BoolView,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:
349 GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,NegBoolView,RM_EQV>
350 ::post(home,x,n,nb)));
351 break;
352 case RM_IMP:
353 GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,NegBoolView,RM_PMI>
354 ::post(home,x,n,nb)));
355 break;
356 case RM_PMI:
357 GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,NegBoolView,RM_IMP>
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:
365 GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,NegBoolView,RM_EQV>
366 ::post(home,x,n,nb)));
367 break;
368 case RM_IMP:
369 GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,NegBoolView,RM_PMI>
370 ::post(home,x,n,nb)));
371 break;
372 case RM_PMI:
373 GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,NegBoolView,RM_IMP>
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:
386 GECODE_ES_FAIL((Rel::ReLqInt<IntView,BoolView,RM_EQV>
387 ::post(home,x,n,r.var())));
388 break;
389 case RM_IMP:
390 GECODE_ES_FAIL((Rel::ReLqInt<IntView,BoolView,RM_IMP>
391 ::post(home,x,n,r.var())));
392 break;
393 case RM_PMI:
394 GECODE_ES_FAIL((Rel::ReLqInt<IntView,BoolView,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:
407 GECODE_ES_FAIL((Rel::ReLqInt<IntView,NegBoolView,RM_EQV>
408 ::post(home,x,n,nb)));
409 break;
410 case RM_IMP:
411 GECODE_ES_FAIL((Rel::ReLqInt<IntView,NegBoolView,RM_PMI>
412 ::post(home,x,n,nb)));
413 break;
414 case RM_PMI:
415 GECODE_ES_FAIL((Rel::ReLqInt<IntView,NegBoolView,RM_IMP>
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;
431 GECODE_POST;
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)) {
439 GECODE_ES_FAIL(Rel::NaryEqDom<IntView>::post(home,xv));
440 } else {
441 GECODE_ES_FAIL(Rel::NaryEqBnd<IntView>::post(home,xv));
442 }
443 }
444 break;
445 case IRT_NQ:
446 {
447 ViewArray<IntView> y(home,x);
448 GECODE_ES_FAIL((Rel::NaryNq<IntView>::post(home,y)));
449 }
450 break;
451 case IRT_LE:
452 {
453 ViewArray<IntView> y(home,x);
454 GECODE_ES_FAIL((Rel::NaryLqLe<IntView,1>::post(home,y)));
455 }
456 break;
457 case IRT_LQ:
458 {
459 ViewArray<IntView> y(home,x);
460 GECODE_ES_FAIL((Rel::NaryLqLe<IntView,0>::post(home,y)));
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];
468 GECODE_ES_FAIL((Rel::NaryLqLe<IntView,1>::post(home,y)));
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];
476 GECODE_ES_FAIL((Rel::NaryLqLe<IntView,0>::post(home,y)));
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;
488 GECODE_POST;
489
490 switch (irt) {
491 case IRT_GR:
492 {
493 ViewArray<IntView> xv(home,x), yv(home,y);
494 GECODE_ES_FAIL((Rel::LexLqLe<IntView,IntView>
495 ::post(home,yv,xv,true)));
496 }
497 break;
498 case IRT_LE:
499 {
500 ViewArray<IntView> xv(home,x), yv(home,y);
501 GECODE_ES_FAIL((Rel::LexLqLe<IntView,IntView>
502 ::post(home,xv,yv,true)));
503 }
504 break;
505 case IRT_GQ:
506 {
507 ViewArray<IntView> xv(home,x), yv(home,y);
508 GECODE_ES_FAIL((Rel::LexLqLe<IntView,IntView>
509 ::post(home,yv,xv,false)));
510 }
511 break;
512 case IRT_LQ:
513 {
514 ViewArray<IntView> xv(home,x), yv(home,y);
515 GECODE_ES_FAIL((Rel::LexLqLe<IntView,IntView>
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++) {
524 GECODE_ES_FAIL((Rel::EqDom<IntView,IntView>
525 ::post(home,x[i],y[i])));
526 }
527 else
528 for (int i=0; i<x.size(); i++) {
529 GECODE_ES_FAIL((Rel::EqBnd<IntView,IntView>
530 ::post(home,x[i],y[i])));
531 }
532 break;
533 case IRT_NQ:
534 {
535 ViewArray<IntView> xv(home,x), yv(home,y);
536 GECODE_ES_FAIL((Rel::LexNq<IntView,IntView>
537 ::post(home,xv,yv)));
538 }
539 break;
540 default:
541 throw UnknownRelation("Int::rel");
542 }
543 }
544
545 namespace {
546
547 /// Return view array
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;
564 GECODE_POST;
565
566 switch (irt) {
567 case IRT_GR:
568 {
569 ViewArray<IntView> xv(home,x);
570 ViewArray<ConstIntView> yv(viewarray(home,y));
571 GECODE_ES_FAIL((Rel::LexLqLe<ConstIntView,IntView>
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));
579 GECODE_ES_FAIL((Rel::LexLqLe<IntView,ConstIntView>
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));
587 GECODE_ES_FAIL((Rel::LexLqLe<ConstIntView,IntView>
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));
595 GECODE_ES_FAIL((Rel::LexLqLe<IntView,ConstIntView>
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));
611 GECODE_ES_FAIL((Rel::LexNq<IntView,ConstIntView>
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