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 * Copyright:
7 * Guido Tack, 2005
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/minimodel.hh>
35
36#include "test/set.hh"
37
38using namespace Gecode;
39
40namespace Test { namespace Set {
41
42 /// %Tests for domain constraints
43 namespace Dom {
44
45 /**
46 * \defgroup TaskTestSetDom Domain constraints
47 * \ingroup TaskTestSet
48 */
49 //@{
50
51 static const int d1r[4][2] = {
52 {-4,-3},{-1,-1},{1,1},{3,5}
53 };
54 static IntSet d1(d1r,4);
55
56 static const int d1cr[5][2] = {
57 {Gecode::Set::Limits::min,-5},
58 {-2,-2},{0,0},{2,2},
59 {6,Gecode::Set::Limits::max}
60 };
61 static IntSet d1c(d1cr,5);
62
63 static IntSet ds_33(-3,3);
64
65 static const int d2r[2][2] = {
66 {Gecode::Set::Limits::min,-4}, {4,Gecode::Set::Limits::max}
67 };
68 static IntSet ds_33c(d2r,2);
69
70 namespace {
71 static int minSymDiff(const SetAssignment& x, int i, const IntSet& is) {
72 typedef Iter::Ranges::Diff<CountableSetRanges,IntSetRanges> DiffA;
73 CountableSetRanges xr00(x.lub, x[i]);
74 IntSetRanges xr10(is);
75 DiffA a(xr00,xr10);
76 typedef Iter::Ranges::Diff<IntSetRanges,CountableSetRanges> DiffB;
77 CountableSetRanges xr01(x.lub, x[i]);
78 IntSetRanges xr11(is);
79 DiffB b(xr11,xr01);
80 Iter::Ranges::Union<DiffA,DiffB> u(a,b);
81 return u() ? u.min() : Gecode::Set::Limits::max+1;
82 }
83 template<class I>
84 static bool in(int i, I& c, bool eq=false) {
85 if (eq && i==Gecode::Set::Limits::max+1)
86 return true;
87 Iter::Ranges::Singleton s(i,i);
88 return Iter::Ranges::subset(s,c);
89 }
90 }
91
92 /// %Test for equality with a range
93 class DomRange : public SetTest {
94 private:
95 Gecode::SetRelType srt;
96 IntSet is;
97 public:
98 /// Create and register test
99 DomRange(SetRelType srt0, int n) :
100 SetTest("Dom::Range::"+str(srt0)+"::"+str(n),n,ds_33,(n == 1)),
101 srt(srt0), is(srt == Gecode::SRT_CMPL ? ds_33c: ds_33) {}
102 /// %Test whether \a x is solution
103 virtual bool solution(const SetAssignment& x) const {
104 for (int i=x.size(); i--; ) {
105 CountableSetRanges xr(x.lub, x[i]);
106 IntSetRanges dr(is);
107 switch (srt) {
108 case SRT_EQ:
109 if (!Iter::Ranges::equal(xr, dr))
110 return false;
111 break;
112 case SRT_LQ:
113 if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
114 return false;
115 break;
116 case SRT_LE:
117 if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
118 return false;
119 break;
120 case SRT_GQ:
121 if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
122 return false;
123 break;
124 case SRT_GR:
125 if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
126 return false;
127 break;
128 case SRT_NQ:
129 if (Iter::Ranges::equal(xr, dr))
130 return false;
131 break;
132 case SRT_SUB:
133 if (!Iter::Ranges::subset(xr, dr))
134 return false;
135 break;
136 case SRT_SUP:
137 if (!Iter::Ranges::subset(dr, xr))
138 return false;
139 break;
140 case SRT_DISJ:
141 {
142 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
143 inter(xr, dr);
144 if (inter())
145 return false;
146 }
147 break;
148 case SRT_CMPL:
149 {
150 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
151 if (!Iter::Ranges::equal(xr,drc))
152 return false;
153 }
154 break;
155 default: GECODE_NEVER;
156 }
157 }
158 return true;
159 }
160 /// Post constraint on \a x
161 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
162 if (x.size() == 1)
163 Gecode::dom(home, x[0], srt, is);
164 else
165 Gecode::dom(home, x, srt, is);
166 }
167 /// Post reified constraint on \a x for \a b
168 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
169 assert(x.size() == 1);
170 if (_rand(2) != 0) {
171 Gecode::dom(home, x[0], srt, is, r);
172 } else {
173 switch (r.mode()) {
174 case Gecode::RM_EQV:
175 Gecode::rel(home, Gecode::dom(x[0], srt, is) == r.var()); break;
176 case Gecode::RM_IMP:
177 Gecode::rel(home, Gecode::dom(x[0], srt, is) << r.var()); break;
178 case Gecode::RM_PMI:
179 Gecode::rel(home, Gecode::dom(x[0], srt, is) >> r.var()); break;
180 default: GECODE_NEVER;
181 }
182 }
183 }
184 };
185
186 /// %Test for equality with an integer range
187 class DomIntRange : public SetTest {
188 private:
189 Gecode::SetRelType srt;
190 public:
191 /// Create and register test
192 DomIntRange(Gecode::SetRelType srt0, int n)
193 : SetTest("Dom::IntRange::"+str(srt0)+"::"+str(n),1,ds_33,n==1),
194 srt(srt0) {}
195 /// %Test whether \a x is solution
196 virtual bool solution(const SetAssignment& x) const {
197 for (int i=x.size(); i--; ) {
198 CountableSetRanges xr(x.lub, x[i]);
199 IntSet is(-3,-1);
200 IntSetRanges dr(is);
201 switch (srt) {
202 case SRT_EQ:
203 if (!Iter::Ranges::equal(xr, dr))
204 return false;
205 break;
206 case SRT_LQ:
207 if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
208 return false;
209 break;
210 case SRT_LE:
211 if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
212 return false;
213 break;
214 case SRT_GQ:
215 if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
216 return false;
217 break;
218 case SRT_GR:
219 if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
220 return false;
221 break;
222 case SRT_NQ:
223 if (!(!Iter::Ranges::equal(xr, dr)))
224 return false;
225 break;
226 case SRT_SUB:
227 if (!(Iter::Ranges::subset(xr, dr)))
228 return false;
229 break;
230 case SRT_SUP:
231 if (!(Iter::Ranges::subset(dr, xr)))
232 return false;
233 break;
234 case SRT_DISJ:
235 {
236 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
237 inter(xr, dr);
238 if (inter())
239 return false;
240 }
241 break;
242 case SRT_CMPL:
243 {
244 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
245 if (!Iter::Ranges::equal(xr,drc))
246 return false;
247 }
248 break;
249 default: GECODE_NEVER;
250 }
251 }
252 return true;
253 }
254 /// Post constraint on \a x
255 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
256 if (x.size() == 1)
257 Gecode::dom(home, x[0], srt, -3, -1);
258 else
259 Gecode::dom(home, x, srt, -3, -1);
260 }
261 /// Post reified constraint on \a x for \a b
262 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
263 assert(x.size() == 1);
264 if (_rand(2) != 0) {
265 Gecode::dom(home, x[0], srt, -3, -1, r);
266 } else {
267 switch (r.mode()) {
268 case Gecode::RM_EQV:
269 Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) == r.var()); break;
270 case Gecode::RM_IMP:
271 Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) << r.var()); break;
272 case Gecode::RM_PMI:
273 Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) >> r.var()); break;
274 default: GECODE_NEVER;
275 }
276 }
277 }
278 };
279
280 /// %Test for equality with an integer
281 class DomInt : public SetTest {
282 private:
283 Gecode::SetRelType srt;
284 public:
285 /// Create and register test
286 DomInt(Gecode::SetRelType srt0, int n) :
287 SetTest("Dom::Int::"+str(srt0)+"::"+str(n),n,ds_33,n==1),
288 srt(srt0) {}
289 /// %Test whether \a x is solution
290 virtual bool solution(const SetAssignment& x) const {
291 IntSet is(-3,-3);
292 for (int i=x.size(); i--; ) {
293 CountableSetRanges xr(x.lub, x[i]);
294 IntSetRanges dr(is);
295 switch (srt) {
296 case SRT_EQ:
297 if (!Iter::Ranges::equal(xr, dr))
298 return false;
299 break;
300 case SRT_LQ:
301 if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
302 return false;
303 break;
304 case SRT_LE:
305 if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
306 return false;
307 break;
308 case SRT_GQ:
309 if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
310 return false;
311 break;
312 case SRT_GR:
313 if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
314 return false;
315 break;
316 case SRT_NQ:
317 if (Iter::Ranges::equal(xr, dr))
318 return false;
319 break;
320 case SRT_SUB:
321 if (!(Iter::Ranges::subset(xr, dr)))
322 return false;
323 break;
324 case SRT_SUP:
325 if (!(Iter::Ranges::subset(dr, xr)))
326 return false;
327 break;
328 case SRT_DISJ:
329 {
330 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
331 inter(xr, dr);
332
333 if (inter())
334 return false;
335 break;
336 }
337 case SRT_CMPL:
338 {
339 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
340
341 if (!Iter::Ranges::equal(xr,drc))
342 return false;
343 break;
344 }
345 default: GECODE_NEVER;
346 }
347 }
348 return true;
349 }
350 /// Post constraint on \a x
351 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
352 if (x.size() == 1)
353 Gecode::dom(home, x[0], srt, -3);
354 else
355 Gecode::dom(home, x, srt, -3);
356 }
357 /// Post reified constraint on \a x for \a b
358 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
359 assert(x.size() == 1);
360 if (_rand(2) != 0) {
361 Gecode::dom(home, x[0], srt, -3, r);
362 } else {
363 switch (r.mode()) {
364 case Gecode::RM_EQV:
365 Gecode::rel(home, Gecode::dom(x[0], srt, -3) == r.var()); break;
366 case Gecode::RM_IMP:
367 Gecode::rel(home, Gecode::dom(x[0], srt, -3) << r.var()); break;
368 case Gecode::RM_PMI:
369 Gecode::rel(home, Gecode::dom(x[0], srt, -3) >> r.var()); break;
370 default: GECODE_NEVER;
371 }
372 }
373 }
374 };
375
376 /// %Test for equality with a domain
377 class DomDom : public SetTest {
378 private:
379 Gecode::SetRelType srt;
380 Gecode::IntSet is;
381 public:
382 /// Create and register test
383 DomDom(Gecode::SetRelType srt0, int n) :
384 SetTest("Dom::Dom::"+str(srt0)+"::"+str(n),n,d1,(n == 1)),
385 srt(srt0), is(srt == Gecode::SRT_CMPL ? d1c: d1) {}
386 /// %Test whether \a x is solution
387 virtual bool solution(const SetAssignment& x) const {
388 for (int i=x.size(); i--; ) {
389 CountableSetRanges xr(x.lub, x[i]);
390 IntSetRanges dr(is);
391 switch (srt) {
392 case SRT_EQ:
393 if (!Iter::Ranges::equal(xr, dr))
394 return false;
395 break;
396 case SRT_LQ:
397 if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
398 return false;
399 break;
400 case SRT_LE:
401 if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
402 return false;
403 break;
404 case SRT_GQ:
405 if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
406 return false;
407 break;
408 case SRT_GR:
409 if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
410 return false;
411 break;
412 case SRT_NQ:
413 if (Iter::Ranges::equal(xr, dr))
414 return false;
415 break;
416 case SRT_SUB:
417 if (!Iter::Ranges::subset(xr, dr))
418 return false;
419 break;
420 case SRT_SUP:
421 if (!Iter::Ranges::subset(dr, xr))
422 return false;
423 break;
424 case SRT_DISJ:
425 {
426 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
427 inter(xr, dr);
428 if (inter())
429 return false;
430 }
431 break;
432 case SRT_CMPL:
433 {
434 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
435 if (!Iter::Ranges::equal(xr,drc))
436 return false;
437 }
438 break;
439 default: GECODE_NEVER;
440 }
441 }
442 return true;
443 }
444 /// Post constraint on \a x
445 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
446 if (x.size() == 1)
447 Gecode::dom(home, x[0], srt, is);
448 else
449 Gecode::dom(home, x, srt, is);
450 }
451 /// Post reified constraint on \a x for \a b
452 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
453 assert(x.size() == 1);
454 Gecode::dom(home, x[0], srt, is, r);
455 }
456 };
457
458 /// %Test for cardinality range
459 class CardRange : public SetTest {
460 public:
461 /// Create and register test
462 CardRange(int n)
463 : SetTest("Dom::CardRange::"+str(n),n,d1,false) {}
464 /// %Test whether \a x is solution
465 virtual bool solution(const SetAssignment& x) const {
466 for (int i=x.size(); i--; ) {
467 CountableSetRanges xr(x.lub, x[i]);
468 unsigned int card = Iter::Ranges::size(xr);
469 if ((card < 2) || (card > 3))
470 return false;
471 }
472 return true;
473 }
474 /// Post constraint on \a x
475 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
476 if (x.size() == 1)
477 Gecode::cardinality(home, x[0], 2, 3);
478 else
479 Gecode::cardinality(home, x, 2, 3);
480 }
481 };
482
483 DomRange _domrange_eq1(SRT_EQ,1);
484 DomRange _domrange_lq1(SRT_LQ,1);
485 DomRange _domrange_le1(SRT_LE,1);
486 DomRange _domrange_gq1(SRT_GQ,1);
487 DomRange _domrange_gr1(SRT_GR,1);
488 DomRange _domrange_nq1(SRT_NQ,1);
489 DomRange _domrange_sub1(SRT_SUB,1);
490 DomRange _domrange_sup1(SRT_SUP,1);
491 DomRange _domrange_disj1(SRT_DISJ,1);
492 DomRange _domrange_cmpl1(SRT_CMPL,1);
493 DomRange _domrange_eq2(SRT_EQ,2);
494 DomRange _domrange_lq2(SRT_LQ,2);
495 DomRange _domrange_le2(SRT_LE,2);
496 DomRange _domrange_gq2(SRT_GQ,2);
497 DomRange _domrange_gr2(SRT_GR,2);
498 DomRange _domrange_nq2(SRT_NQ,2);
499 DomRange _domrange_sub2(SRT_SUB,2);
500 DomRange _domrange_sup2(SRT_SUP,2);
501 DomRange _domrange_disj2(SRT_DISJ,2);
502 DomRange _domrange_cmpl2(SRT_CMPL,2);
503
504 DomIntRange _domintrange_eq1(SRT_EQ,1);
505 DomIntRange _domintrange_lq1(SRT_LQ,1);
506 DomIntRange _domintrange_le1(SRT_LE,1);
507 DomIntRange _domintrange_gq1(SRT_GQ,1);
508 DomIntRange _domintrange_gr1(SRT_GR,1);
509 DomIntRange _domintrange_nq1(SRT_NQ,1);
510 DomIntRange _domintrange_sub1(SRT_SUB,1);
511 DomIntRange _domintrange_sup1(SRT_SUP,1);
512 DomIntRange _domintrange_disj1(SRT_DISJ,1);
513 DomIntRange _domintrange_cmpl1(SRT_CMPL,1);
514 DomIntRange _domintrange_eq2(SRT_EQ,2);
515 DomIntRange _domintrange_lq2(SRT_LQ,2);
516 DomIntRange _domintrange_le2(SRT_LE,2);
517 DomIntRange _domintrange_gq2(SRT_GQ,2);
518 DomIntRange _domintrange_gr2(SRT_GR,2);
519 DomIntRange _domintrange_nq2(SRT_NQ,2);
520 DomIntRange _domintrange_sub2(SRT_SUB,2);
521 DomIntRange _domintrange_sup2(SRT_SUP,2);
522 DomIntRange _domintrange_disj2(SRT_DISJ,2);
523 DomIntRange _domintrange_cmpl2(SRT_CMPL,2);
524
525 DomInt _domint_eq1(SRT_EQ,1);
526 DomInt _domint_lq1(SRT_LQ,1);
527 DomInt _domint_le1(SRT_LE,1);
528 DomInt _domint_gq1(SRT_GQ,1);
529 DomInt _domint_gr1(SRT_GR,1);
530 DomInt _domint_nq1(SRT_NQ,1);
531 DomInt _domint_sub1(SRT_SUB,1);
532 DomInt _domint_sup1(SRT_SUP,1);
533 DomInt _domint_disj1(SRT_DISJ,1);
534 DomInt _domint_cmpl1(SRT_CMPL,1);
535 DomInt _domint_eq2(SRT_EQ,2);
536 DomInt _domint_lq2(SRT_LQ,2);
537 DomInt _domint_le2(SRT_LE,2);
538 DomInt _domint_gq2(SRT_GQ,2);
539 DomInt _domint_gr2(SRT_GR,2);
540 DomInt _domint_nq2(SRT_NQ,2);
541 DomInt _domint_sub2(SRT_SUB,2);
542 DomInt _domint_sup2(SRT_SUP,2);
543 DomInt _domint_disj2(SRT_DISJ,2);
544 DomInt _domint_cmpl2(SRT_CMPL,2);
545
546 DomDom _domdom_eq1(SRT_EQ,1);
547 DomDom _domdom_lq1(SRT_LQ,1);
548 DomDom _domdom_le1(SRT_LE,1);
549 DomDom _domdom_gq1(SRT_GQ,1);
550 DomDom _domdom_gr1(SRT_GR,1);
551 DomDom _domdom_nq1(SRT_NQ,1);
552 DomDom _domdom_sub1(SRT_SUB,1);
553 DomDom _domdom_sup1(SRT_SUP,1);
554 DomDom _domdom_disj1(SRT_DISJ,1);
555 DomDom _domdom_cmpl1(SRT_CMPL,1);
556 DomDom _domdom_eq2(SRT_EQ,2);
557 DomDom _domdom_lq2(SRT_LQ,2);
558 DomDom _domdom_le2(SRT_LE,2);
559 DomDom _domdom_gq2(SRT_GQ,2);
560 DomDom _domdom_gr2(SRT_GR,2);
561 DomDom _domdom_nq2(SRT_NQ,2);
562 DomDom _domdom_sub2(SRT_SUB,2);
563 DomDom _domdom_sup2(SRT_SUP,2);
564 DomDom _domdom_disj2(SRT_DISJ,2);
565 DomDom _domdom_cmpl2(SRT_CMPL,2);
566
567 CardRange _cr1(1);
568 CardRange _cr2(2);
569
570}}}
571
572// STATISTICS: test-set