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, 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 "test/int.hh"
35
36#include <gecode/minimodel.hh>
37
38namespace Test { namespace Int {
39
40 /// %Tests for Boolean constraints
41 namespace Bool {
42
43 inline int
44 check(int x0, Gecode::BoolOpType op, int x1) {
45 switch (op) {
46 case Gecode::BOT_AND: return x0 & x1;
47 case Gecode::BOT_OR: return x0 | x1;
48 case Gecode::BOT_IMP: return (!x0) | x1;
49 case Gecode::BOT_EQV: return x0 == x1;
50 case Gecode::BOT_XOR: return x0 != x1;
51 default: GECODE_NEVER;
52 }
53 GECODE_NEVER;
54 return 0;
55 }
56
57 /**
58 * \defgroup TaskTestIntBool Boolean constraints
59 * \ingroup TaskTestInt
60 */
61 //@{
62 /// %Test for binary Boolean operation
63 class BinXYZ : public Test {
64 protected:
65 /// Boolean operation type for test
66 Gecode::BoolOpType op;
67 public:
68 /// Construct and register test
69 BinXYZ(Gecode::BoolOpType op0)
70 : Test("Bool::Bin::XYZ::"+str(op0),3,0,1), op(op0) {}
71 /// Check whether \a x is solution
72 virtual bool solution(const Assignment& x) const {
73 return check(x[0],op,x[1]) == x[2];
74 }
75 /// Post constraint
76 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
77 using namespace Gecode;
78 rel(home,
79 channel(home,x[0]), op, channel(home,x[1]),
80 channel(home,x[2]));
81 }
82 };
83
84 /// %Test for binary Boolean operation with shared variables
85 class BinXXY : public Test {
86 protected:
87 /// Boolean operation type for test
88 Gecode::BoolOpType op;
89 public:
90 /// Construct and register test
91 BinXXY(Gecode::BoolOpType op0)
92 : Test("Bool::Bin::XXY::"+str(op0),2,0,1), op(op0) {}
93 /// Check whether \a x is solution
94 virtual bool solution(const Assignment& x) const {
95 return check(x[0],op,x[0]) == x[1];
96 }
97 /// Post constraint
98 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
99 using namespace Gecode;
100 BoolVar b = channel(home,x[0]);
101 rel(home, b, op, b, channel(home,x[1]));
102 }
103 };
104
105 /// %Test for binary Boolean operation with shared variables
106 class BinXYX : public Test {
107 protected:
108 /// Boolean operation type for test
109 Gecode::BoolOpType op;
110 public:
111 /// Construct and register test
112 BinXYX(Gecode::BoolOpType op0)
113 : Test("Bool::Bin::XYX::"+str(op0),2,0,1), op(op0) {}
114 /// Check whether \a x is solution
115 virtual bool solution(const Assignment& x) const {
116 return check(x[0],op,x[1]) == x[0];
117 }
118 /// Post constraint
119 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
120 using namespace Gecode;
121 BoolVar b = channel(home,x[0]);
122 rel(home, b, op, channel(home,x[1]), b);
123 }
124 };
125
126 /// %Test for binary Boolean operation with shared variables
127 class BinXYY : public Test {
128 protected:
129 /// Boolean operation type for test
130 Gecode::BoolOpType op;
131 public:
132 /// Construct and register test
133 BinXYY(Gecode::BoolOpType op0)
134 : Test("Bool::Bin::XYY::"+str(op0),2,0,1), op(op0) {}
135 /// Check whether \a x is solution
136 virtual bool solution(const Assignment& x) const {
137 return check(x[0],op,x[1]) == x[1];
138 }
139 /// Post constraint
140 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
141 using namespace Gecode;
142 BoolVar b = channel(home,x[1]);
143 rel(home, channel(home,x[0]), op, b, b);
144 }
145 };
146
147 /// %Test for binary Boolean operation with shared variables
148 class BinXXX : public Test {
149 protected:
150 /// Boolean operation type for test
151 Gecode::BoolOpType op;
152 public:
153 /// Construct and register test
154 BinXXX(Gecode::BoolOpType op0)
155 : Test("Bool::Bin::XXX::"+str(op0),1,0,1), op(op0) {}
156 /// Check whether \a x is solution
157 virtual bool solution(const Assignment& x) const {
158 return check(x[0],op,x[0]) == x[0];
159 }
160 /// Post constraint
161 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
162 using namespace Gecode;
163 BoolVar b = channel(home,x[0]);
164 rel(home, b, op, b, b);
165 }
166 };
167
168 /// %Test for binary Boolean operation with constant
169 class BinConstXY : public Test {
170 protected:
171 /// Boolean operation type for test
172 Gecode::BoolOpType op;
173 /// Integer constant
174 int c;
175 public:
176 /// Construct and register test
177 BinConstXY(Gecode::BoolOpType op0, int c0)
178 : Test("Bool::Bin::XY::"+str(op0)+"::"+str(c0),2,0,1),
179 op(op0), c(c0) {}
180 /// Check whether \a x is solution
181 virtual bool solution(const Assignment& x) const {
182 return check(x[0],op,x[1]) == c;
183 }
184 /// Post constraint
185 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
186 using namespace Gecode;
187 rel(home, channel(home,x[0]), op, channel(home,x[1]), c);
188 }
189 };
190
191 /// %Test for binary Boolean operation with shared variables and constant
192 class BinConstXX : public Test {
193 protected:
194 /// Boolean operation type for test
195 Gecode::BoolOpType op;
196 /// Integer constant
197 int c;
198 public:
199 /// Construct and register test
200 BinConstXX(Gecode::BoolOpType op0, int c0)
201 : Test("Bool::Bin::XX::"+str(op0)+"::"+str(c0),1,0,1),
202 op(op0), c(c0) {}
203 /// Check whether \a x is solution
204 virtual bool solution(const Assignment& x) const {
205 return check(x[0],op,x[0]) == c;
206 }
207 /// Post constraint
208 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
209 using namespace Gecode;
210 BoolVar b = channel(home,x[0]);
211 rel(home, b, op, b, c);
212 }
213 };
214
215 /// %Test for Nary Boolean operation
216 class Nary : public Test {
217 protected:
218 /// Boolean operation type for test
219 Gecode::BoolOpType op;
220 public:
221 /// Construct and register test
222 Nary(Gecode::BoolOpType op0, int n)
223 : Test("Bool::Nary::"+str(op0)+"::"+str(n),n+1,0,1), op(op0) {}
224 /// Check whether \a x is solution
225 virtual bool solution(const Assignment& x) const {
226 int n = x.size()-1;
227 int b = check(x[n-2],op,x[n-1]);
228 for (int i=0; i<n-2; i++)
229 b = check(x[i],op,b);
230 return b == x[n];
231 }
232 /// Post constraint
233 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
234 using namespace Gecode;
235 BoolVarArgs b(x.size()-1);
236 for (int i=x.size()-1; i--; )
237 b[i]=channel(home,x[i]);
238 rel(home, op, b, channel(home,x[x.size()-1]));
239 }
240 };
241
242 /// %Test for Nary Boolean operation
243 class NaryShared : public Test {
244 protected:
245 /// Boolean operation type for test
246 Gecode::BoolOpType op;
247 public:
248 /// Construct and register test
249 NaryShared(Gecode::BoolOpType op0, int n)
250 : Test("Bool::Nary::Shared::"+str(op0)+"::"+str(n),n,0,1),
251 op(op0) {
252 if ((op == Gecode::BOT_EQV) || (op == Gecode::BOT_XOR))
253 testfix = false;
254 }
255 /// Check whether \a x is solution
256 virtual bool solution(const Assignment& x) const {
257 int n = x.size();
258 int b = check(x[n-2],op,x[n-1]);
259 for (int i=0; i<n-2; i++)
260 b = check(x[i],op,b);
261 return b == x[n-1];
262 }
263 /// Post constraint
264 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
265 using namespace Gecode;
266 BoolVarArgs b(x.size());
267 for (int i=x.size(); i--; )
268 b[i]=channel(home,x[i]);
269 rel(home, op, b, b[x.size()-1]);
270 }
271 };
272
273 /// %Test for Nary Boolean operation with constant
274 class NaryConst : public Test {
275 protected:
276 /// Boolean operation type for test
277 Gecode::BoolOpType op;
278 /// Integer constant
279 int c;
280 public:
281 /// Construct and register test
282 NaryConst(Gecode::BoolOpType op0, int n, int c0)
283 : Test("Bool::Nary::"+str(op0)+"::"+str(n)+"::"+str(c0),n,0,1),
284 op(op0), c(c0) {}
285 /// Check whether \a x is solution
286 virtual bool solution(const Assignment& x) const {
287 int n = x.size();
288 int b = check(x[n-2],op,x[n-1]);
289 for (int i=0; i<n-2; i++)
290 b = check(x[i],op,b);
291 return b == c;
292 }
293 /// Post constraint
294 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
295 using namespace Gecode;
296 BoolVarArgs b(x.size());
297 for (int i=x.size(); i--; )
298 b[i]=channel(home,x[i]);
299 rel(home, op, b, c);
300 }
301 };
302
303
304 /// %Test for Clause Boolean operation
305 class ClauseXYZ : public Test {
306 protected:
307 /// Boolean operation type for test
308 Gecode::BoolOpType op;
309 public:
310 /// Construct and register test
311 ClauseXYZ(Gecode::BoolOpType op0, int n)
312 : Test("Bool::Clause::XYZ::"+str(op0)+"::"+str(n),n+1,0,1), op(op0) {}
313 /// Check whether \a x is solution
314 virtual bool solution(const Assignment& x) const {
315 int n = (x.size()-1) / 2;
316 int b;
317 if (n == 1) {
318 b = check(x[0],op,!x[1]);
319 } else {
320 b = check(x[0],op,!x[n]);
321 for (int i=1; i<n; i++)
322 b = check(b,op,check(x[i],op,!x[n+i]));
323 }
324 return b == x[x.size()-1];
325 }
326 /// Post constraint
327 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
328 using namespace Gecode;
329 int n = (x.size()-1) / 2;
330 BoolVarArgs a(n), b(n);
331 for (int i=n; i--; ) {
332 a[i]=channel(home,x[i]);
333 b[i]=channel(home,x[i+n]);
334 }
335 clause(home, op, a, b, channel(home,x[x.size()-1]));
336 }
337 };
338
339 /// %Test for Clause Boolean operation
340 class ClauseXXYYX : public Test {
341 protected:
342 /// Boolean operation type for test
343 Gecode::BoolOpType op;
344 public:
345 /// Construct and register test
346 ClauseXXYYX(Gecode::BoolOpType op0, int n)
347 : Test("Bool::Clause::XXYYX::"+str(op0)+"::"+str(n),n,0,1),
348 op(op0) {}
349 /// Check whether \a x is solution
350 virtual bool solution(const Assignment& x) const {
351 int n = x.size() / 2;
352 int b;
353 if (n == 1) {
354 b = check(x[0],op,!x[1]);
355 } else {
356 b = check(x[0],op,!x[n]);
357 for (int i=1; i<n; i++)
358 b = check(b,op,check(x[i],op,!x[n+i]));
359 }
360 return b == x[0];
361 }
362 /// Post constraint
363 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
364 using namespace Gecode;
365 int n = x.size() / 2;
366 BoolVarArgs a(2*n), b(2*n);
367 for (int i=n; i--; ) {
368 a[i]=a[i+n]=channel(home,x[i]);
369 b[i]=b[i+n]=channel(home,x[i+n]);
370 }
371 clause(home, op, a, b, a[0]);
372 }
373 };
374
375 /// %Test for Clause Boolean operation
376 class ClauseXXY : public Test {
377 protected:
378 /// Boolean operation type for test
379 Gecode::BoolOpType op;
380 public:
381 /// Construct and register test
382 ClauseXXY(Gecode::BoolOpType op0, int n)
383 : Test("Bool::Clause::XXY::"+str(op0)+"::"+str(n),n,0,1),
384 op(op0) {}
385 /// Check whether \a x is solution
386 virtual bool solution(const Assignment& x) const {
387 return (x[0] == 1) == (op == Gecode::BOT_OR);
388 }
389 /// Post constraint
390 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
391 using namespace Gecode;
392 int n = x.size() / 2;
393 BoolVarArgs a(2*n), b(2*n);
394 for (int i=n; i--; ) {
395 a[i]=b[i+n]=channel(home,x[i]);
396 b[i]=a[i+n]=channel(home,x[i+n]);
397 }
398 clause(home, op, a, b, a[0]);
399 }
400 };
401
402 /// %Test for Clause Boolean operation with constant
403 class ClauseConst : public Test {
404 protected:
405 /// Boolean operation type for test
406 Gecode::BoolOpType op;
407 /// Integer constant
408 int c;
409 public:
410 /// Construct and register test
411 ClauseConst(Gecode::BoolOpType op0, int n, int c0)
412 : Test("Bool::Clause::"+str(op0)+"::"+str(n)+"::"+str(c0),n,0,1),
413 op(op0), c(c0) {}
414 /// Check whether \a x is solution
415 virtual bool solution(const Assignment& x) const {
416 int n = x.size() / 2;
417 int b;
418 if (n == 1) {
419 b = check(x[0],op,!x[1]);
420 } else {
421 b = check(x[0],op,!x[n]);
422 for (int i=1; i<n; i++)
423 b = check(b,op,check(x[i],op,!x[n+i]));
424 }
425 return b == c;
426 }
427 /// Post constraint
428 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
429 using namespace Gecode;
430 int n = x.size() / 2;
431 BoolVarArgs a(n), b(n);
432 for (int i=n; i--; ) {
433 a[i]=channel(home,x[i]);
434 b[i]=channel(home,x[i+n]);
435 }
436 clause(home, op, a, b, c);
437 }
438 };
439
440 /// %Test for if-then-else-constraint
441 class ITEInt : public Test {
442 public:
443 /// Construct and register test
444 ITEInt(Gecode::IntPropLevel ipl)
445 : Test("ITE::Int::"+str(ipl),4,-4,4,false,ipl) {}
446 /// Check whether \a x is solution
447 virtual bool solution(const Assignment& x) const {
448 if ((x[0] < 0) || (x[0] > 1))
449 return false;
450 if (x[0] == 1)
451 return x[1] == x[3];
452 else
453 return x[2] == x[3];
454 }
455 /// Post constraint
456 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
457 using namespace Gecode;
458 if (_rand(2) != 0)
459 ite(home,channel(home,x[0]),x[1],x[2],x[3]);
460 else
461 rel(home, ite(channel(home,x[0]),x[1],x[2]) == x[3]);
462 }
463 };
464
465 /// %Test for if-then-else-constraint
466 class ITEBool : public Test {
467 public:
468 /// Construct and register test
469 ITEBool(void)
470 : Test("ITE::Bool",4,0,1,false) {}
471 /// Check whether \a x is solution
472 virtual bool solution(const Assignment& x) const {
473 if (x[0] == 1)
474 return x[1] == x[3];
475 else
476 return x[2] == x[3];
477 }
478 /// Post constraint
479 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
480 using namespace Gecode;
481 ite(home,channel(home,x[0]),channel(home,x[1]),
482 channel(home,x[2]),channel(home,x[3]));
483 }
484 };
485
486 /// Help class to create and register tests
487 class Create {
488 public:
489 /// Perform creation and registration
490 Create(void) {
491 using namespace Gecode;
492 for (BoolOpTypes bots; bots(); ++bots) {
493 (void) new BinXYZ(bots.bot());
494 (void) new BinXXY(bots.bot());
495 (void) new BinXYX(bots.bot());
496 (void) new BinXYY(bots.bot());
497 (void) new BinXXX(bots.bot());
498 (void) new BinConstXY(bots.bot(),0);
499 (void) new BinConstXY(bots.bot(),1);
500 (void) new BinConstXX(bots.bot(),0);
501 (void) new BinConstXX(bots.bot(),1);
502 (void) new Nary(bots.bot(),2);
503 (void) new Nary(bots.bot(),6);
504 (void) new Nary(bots.bot(),10);
505 (void) new NaryShared(bots.bot(),2);
506 (void) new NaryShared(bots.bot(),6);
507 (void) new NaryShared(bots.bot(),10);
508 (void) new NaryConst(bots.bot(),2,0);
509 (void) new NaryConst(bots.bot(),6,0);
510 (void) new NaryConst(bots.bot(),10,0);
511 (void) new NaryConst(bots.bot(),2,1);
512 (void) new NaryConst(bots.bot(),6,1);
513 (void) new NaryConst(bots.bot(),10,1);
514 if ((bots.bot() == BOT_AND) || (bots.bot() == BOT_OR)) {
515 (void) new ClauseXYZ(bots.bot(),2);
516 (void) new ClauseXYZ(bots.bot(),6);
517 (void) new ClauseXYZ(bots.bot(),10);
518 (void) new ClauseXXYYX(bots.bot(),2);
519 (void) new ClauseXXYYX(bots.bot(),6);
520 (void) new ClauseXXYYX(bots.bot(),10);
521 (void) new ClauseXXY(bots.bot(),2);
522 (void) new ClauseXXY(bots.bot(),6);
523 (void) new ClauseXXY(bots.bot(),10);
524 (void) new ClauseConst(bots.bot(),2,0);
525 (void) new ClauseConst(bots.bot(),6,0);
526 (void) new ClauseConst(bots.bot(),10,0);
527 (void) new ClauseConst(bots.bot(),2,1);
528 (void) new ClauseConst(bots.bot(),6,1);
529 (void) new ClauseConst(bots.bot(),10,1);
530 }
531 }
532 }
533 };
534
535 Create c;
536 ITEInt itebnd(Gecode::IPL_BND);
537 ITEInt itedom(Gecode::IPL_DOM);
538 ITEBool itebool;
539
540 //@}
541
542 }
543}}
544
545// STATISTICS: test-int
546