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 relation constraints
41 namespace Rel {
42
43 /**
44 * \defgroup TaskTestIntRel Relation constraints
45 * \ingroup TaskTestInt
46 */
47 //@{
48 /// %Test for simple relation involving integer variables
49 class IntVarXY : public Test {
50 protected:
51 /// Integer relation type to propagate
52 Gecode::IntRelType irt;
53 public:
54 /// Create and register test
55 IntVarXY(Gecode::IntRelType irt0, int n, Gecode::IntPropLevel ipl)
56 : Test("Rel::Int::Var::XY::"+str(irt0)+"::"+str(ipl)+"::"+str(n),
57 n+1,-3,3,n==1,ipl),
58 irt(irt0) {}
59 /// %Test whether \a x is solution
60 virtual bool solution(const Assignment& x) const {
61 if (x.size() == 2) {
62 return cmp(x[0],irt,x[1]);
63 } else {
64 return cmp(x[0],irt,x[2]) && cmp(x[1],irt,x[2]);
65 }
66 }
67 /// Post constraint on \a x
68 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
69 using namespace Gecode;
70 if (x.size() == 2) {
71 rel(home, x[0], irt, x[1], ipl);
72 } else {
73 IntVarArgs y(2);
74 y[0]=x[0]; y[1]=x[1];
75 rel(home, y, irt, x[2], ipl);
76 }
77 }
78 /// Post reified constraint on \a x for \a r
79 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
80 Gecode::Reify r) {
81 assert(x.size() == 2);
82 Gecode::rel(home, x[0], irt, x[1], r, ipl);
83 }
84 };
85
86 /// %Test for simple relation involving shared integer variables
87 class IntVarXX : public Test {
88 protected:
89 /// Integer relation type to propagate
90 Gecode::IntRelType irt;
91 public:
92 /// Create and register test
93 IntVarXX(Gecode::IntRelType irt0, Gecode::IntPropLevel ipl)
94 : Test("Rel::Int::Var::XX::"+str(irt0)+"::"+str(ipl),
95 1,-3,3,true,ipl),
96 irt(irt0) {
97 contest = ((irt != Gecode::IRT_LE) &&
98 (irt != Gecode::IRT_GR) &&
99 (irt != Gecode::IRT_NQ))
100 ? CTL_DOMAIN : CTL_NONE;
101 }
102 /// %Test whether \a x is solution
103 virtual bool solution(const Assignment& x) const {
104 return cmp(x[0],irt,x[0]);
105 }
106 /// Post constraint on \a x
107 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
108 Gecode::rel(home, x[0], irt, x[0], ipl);
109 }
110 /// Post reified constraint on \a x for \a r
111 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
112 Gecode::Reify r) {
113 Gecode::rel(home, x[0], irt, x[0], r, ipl);
114 }
115 };
116
117 /// %Test for simple relation involving Boolean variables
118 class BoolVarXY : public Test {
119 protected:
120 /// Integer relation type to propagate
121 Gecode::IntRelType irt;
122 public:
123 /// Create and register test
124 BoolVarXY(Gecode::IntRelType irt0, int n)
125 : Test("Rel::Bool::Var::XY::"+str(irt0)+"::"+str(n),n+1,0,1,
126 n==1),
127 irt(irt0) {}
128 /// %Test whether \a x is solution
129 virtual bool solution(const Assignment& x) const {
130 if (x.size() == 2) {
131 return cmp(x[0],irt,x[1]);
132 } else {
133 return cmp(x[0],irt,x[2]) && cmp(x[1],irt,x[2]);
134 }
135 }
136 /// Post constraint on \a x
137 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
138 using namespace Gecode;
139 if (x.size() == 2) {
140 rel(home, channel(home,x[0]), irt, channel(home,x[1]));
141 } else {
142 BoolVarArgs y(2);
143 y[0]=channel(home,x[0]); y[1]=channel(home,x[1]);
144 rel(home, y, irt, channel(home,x[2]));
145 }
146 }
147 /// Post reified constraint on \a x for \a r
148 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
149 Gecode::Reify r) {
150 assert(x.size() == 2);
151 using namespace Gecode;
152 rel(home,
153 channel(home,x[0]), irt, channel(home,x[1]),
154 r);
155 }
156 };
157
158 /// %Test for simple relation involving shared Boolean variables
159 class BoolVarXX : public Test {
160 protected:
161 /// Integer relation type to propagate
162 Gecode::IntRelType irt;
163 public:
164 /// Create and register test
165 BoolVarXX(Gecode::IntRelType irt0)
166 : Test("Rel::Bool::Var::XX::"+str(irt0),1,0,1),
167 irt(irt0) {
168 contest = ((irt != Gecode::IRT_LE) &&
169 (irt != Gecode::IRT_GR) &&
170 (irt != Gecode::IRT_NQ))
171 ? CTL_DOMAIN : CTL_NONE;
172 }
173 /// %Test whether \a x is solution
174 virtual bool solution(const Assignment& x) const {
175 return cmp(x[0],irt,x[0]);
176 }
177 /// Post constraint on \a x
178 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
179 Gecode::BoolVar b = Gecode::channel(home,x[0]);
180 Gecode::rel(home, b, irt, b);
181 }
182 };
183
184 /// %Test for simple relation involving integer variable and integer constant
185 class IntInt : public Test {
186 protected:
187 /// Integer relation type to propagate
188 Gecode::IntRelType irt;
189 /// Integer constant
190 int c;
191 public:
192 /// Create and register test
193 IntInt(Gecode::IntRelType irt0, int n, int c0)
194 : Test("Rel::Int::Int::"+str(irt0)+"::"+str(n)+"::"+str(c0),
195 n,-3,3,n==1),
196 irt(irt0), c(c0) {}
197 /// %Test whether \a x is solution
198 virtual bool solution(const Assignment& x) const {
199 if (x.size() == 1)
200 return cmp(x[0],irt,c);
201 else
202 return cmp(x[0],irt,c) && cmp(x[1],irt,c);
203 }
204 /// Post constraint on \a x
205 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
206 using namespace Gecode;
207 if (x.size() == 1)
208 rel(home, x[0], irt, c);
209 else
210 rel(home, x, irt, c);
211 }
212 /// Post reified constraint on \a x for \a r
213 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
214 Gecode::Reify r) {
215 assert(x.size() == 1);
216 Gecode::rel(home, x[0], irt, c, r);
217 }
218 };
219
220 /// %Test for simple relation involving Boolean variable and integer constant
221 class BoolInt : public Test {
222 protected:
223 /// Integer relation type to propagate
224 Gecode::IntRelType irt;
225 /// Integer constant
226 int c;
227 public:
228 /// Create and register test
229 BoolInt(Gecode::IntRelType irt0, int n, int c0)
230 : Test("Rel::Bool::Int::"+str(irt0)+"::"+str(n)+"::"+str(c0),n,0,1,
231 n==1),
232 irt(irt0), c(c0) {}
233 /// %Test whether \a x is solution
234 virtual bool solution(const Assignment& x) const {
235 if (x.size() == 1)
236 return cmp(x[0],irt,c);
237 else
238 return cmp(x[0],irt,c) && cmp(x[1],irt,c);
239 }
240 /// Post constraint on \a x
241 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
242 using namespace Gecode;
243 if (x.size() == 1) {
244 rel(home, channel(home,x[0]), irt, c);
245 } else {
246 BoolVarArgs y(2);
247 y[0]=channel(home,x[0]); y[1]=channel(home,x[1]);
248 rel(home, y, irt, c);
249 }
250 }
251 /// Post reified constraint on \a x for \a r
252 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
253 Gecode::Reify r) {
254 assert(x.size() == 1);
255 using namespace Gecode;
256 rel(home, channel(home,x[0]), irt, c, r);
257 }
258 };
259
260 /// %Test for sequence of relations between integer variables
261 class IntSeq : public Test {
262 protected:
263 /// Integer relation type to propagate
264 Gecode::IntRelType irt;
265 public:
266 /// Create and register test
267 IntSeq(int n, Gecode::IntRelType irt0, Gecode::IntPropLevel ipl)
268 : Test("Rel::Int::Seq::"+str(n)+"::"+str(irt0)+"::"+str(ipl),
269 n,-3,3,false,ipl),
270 irt(irt0) {}
271 /// %Test whether \a x is solution
272 virtual bool solution(const Assignment& x) const {
273 if (irt == Gecode::IRT_NQ) {
274 if (x.size() < 2)
275 return false;
276 for (int i=0; i<x.size()-1; i++)
277 if (x[i] != x[i+1])
278 return true;
279 return false;
280 } else {
281 for (int i=0; i<x.size()-1; i++)
282 if (!cmp(x[i],irt,x[i+1]))
283 return false;
284 return true;
285 }
286 }
287 /// Post constraint on \a x
288 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
289 Gecode::rel(home, x, irt, ipl);
290 }
291 };
292
293 /// %Test for sequence of relations between shared integer variables
294 class IntSharedSeq : public Test {
295 protected:
296 /// Integer relation type to propagate
297 Gecode::IntRelType irt;
298 public:
299 /// Create and register test
300 IntSharedSeq(int n, Gecode::IntRelType irt0, Gecode::IntPropLevel ipl)
301 : Test("Rel::Int::Seq::Shared::"+str(n)+"::"+str(irt0)+"::"+str(ipl),
302 n,-3,3,false,ipl),
303 irt(irt0) {}
304 /// %Test whether \a x is solution
305 virtual bool solution(const Assignment& x) const {
306 if (irt == Gecode::IRT_NQ) {
307 if (x.size() < 2)
308 return false;
309 for (int i=0; i<x.size()-1; i++)
310 if (x[i] != x[i+1])
311 return true;
312 return false;
313 } else {
314 int n = x.size();
315 for (int i=0; i<2*n-1; i++)
316 if (!cmp(x[i % n],irt,x[(i+1) % n]))
317 return false;
318 return true;
319 }
320 }
321 /// Post constraint on \a x
322 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
323 using namespace Gecode;
324 int n = x.size();
325 IntVarArgs y(2*n);
326 for (int i=n; i--; )
327 y[i] = y[n+i] = x[i];
328 rel(home, y, irt, ipl);
329 }
330 };
331
332 /// %Test for sequence of relations between Boolean variables
333 class BoolSeq : public Test {
334 protected:
335 /// Integer relation type to propagate
336 Gecode::IntRelType irt;
337 public:
338 /// Create and register test
339 BoolSeq(int n, Gecode::IntRelType irt0)
340 : Test("Rel::Bool::Seq::"+str(n)+"::"+str(irt0),n,0,1),
341 irt(irt0) {}
342 /// %Test whether \a x is solution
343 virtual bool solution(const Assignment& x) const {
344 if (irt == Gecode::IRT_NQ) {
345 if (x.size() < 2)
346 return false;
347 for (int i=0; i<x.size()-1; i++)
348 if (x[i] != x[i+1])
349 return true;
350 return false;
351 } else {
352 for (int i=0; i<x.size()-1; i++)
353 if (!cmp(x[i],irt,x[i+1]))
354 return false;
355 return true;
356 }
357 }
358 /// Post constraint on \a x
359 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
360 using namespace Gecode;
361 BoolVarArgs b(x.size());
362 for (int i=x.size(); i--; )
363 b[i]=channel(home,x[i]);
364 rel(home, b, irt);
365 }
366 };
367
368 /// %Test for sequence of relations between shared Boolean variables
369 class BoolSharedSeq : public Test {
370 protected:
371 /// Integer relation type to propagate
372 Gecode::IntRelType irt;
373 public:
374 /// Create and register test
375 BoolSharedSeq(int n, Gecode::IntRelType irt0)
376 : Test("Rel::Bool::Seq::Shared::"+str(n)+"::"+str(irt0),n,0,1),
377 irt(irt0) {}
378 /// %Test whether \a x is solution
379 virtual bool solution(const Assignment& x) const {
380 if (irt == Gecode::IRT_NQ) {
381 if (x.size() < 2)
382 return false;
383 for (int i=0; i<x.size()-1; i++)
384 if (x[i] != x[i+1])
385 return true;
386 return false;
387 } else {
388 int n = x.size();
389 for (int i=0; i<2*n-1; i++)
390 if (!cmp(x[i % n],irt,x[(i+1) % n]))
391 return false;
392 return true;
393 }
394 }
395 /// Post constraint on \a x
396 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
397 using namespace Gecode;
398 int n = x.size();
399 BoolVarArgs b(2*n);
400 for (int i=n; i--; )
401 b[i]=b[n+i]=channel(home,x[i]);
402 rel(home, b, irt);
403 }
404 };
405
406 /// %Test for relation between same sized arrays of integer variables
407 class IntArrayVar : public Test {
408 protected:
409 /// Integer relation type to propagate
410 Gecode::IntRelType irt;
411 public:
412 /// Create and register test
413 IntArrayVar(Gecode::IntRelType irt0)
414 : Test("Rel::Int::Array::Var::"+str(irt0),6,-2,2), irt(irt0) {}
415 /// %Test whether \a x is solution
416 virtual bool solution(const Assignment& x) const {
417 int n=x.size() >> 1;
418 for (int i=0; i<n; i++)
419 if (x[i] != x[n+i])
420 return cmp(x[i],irt,x[n+i]);
421 return ((irt == Gecode::IRT_LQ) || (irt == Gecode::IRT_GQ) ||
422 (irt == Gecode::IRT_EQ));
423 GECODE_NEVER;
424 return false;
425 }
426 /// Post constraint on \a x
427 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
428 using namespace Gecode;
429 int n=x.size() >> 1;
430 IntVarArgs y(n); IntVarArgs z(n);
431 for (int i=0; i<n; i++) {
432 y[i]=x[i]; z[i]=x[n+i];
433 }
434 rel(home, y, irt, z);
435 }
436 };
437
438 /// %Test for relation between same sized arrays of integer variables and integers
439 class IntArrayInt : public Test {
440 protected:
441 /// Integer relation type to propagate
442 Gecode::IntRelType irt;
443 public:
444 /// Create and register test
445 IntArrayInt(Gecode::IntRelType irt0)
446 : Test("Rel::Int::Array::Int::"+str(irt0),3,-2,2), irt(irt0) {}
447 /// %Test whether \a x is solution
448 virtual bool solution(const Assignment& x) const {
449 Gecode::IntArgs y({0,0,0});
450 int n=x.size();
451 for (int i=0; i<n; i++)
452 if (x[i] != y[i])
453 return cmp(x[i],irt,y[i]);
454 return ((irt == Gecode::IRT_LQ) || (irt == Gecode::IRT_GQ) ||
455 (irt == Gecode::IRT_EQ));
456 GECODE_NEVER;
457 return false;
458 }
459 /// Post constraint on \a x
460 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
461 using namespace Gecode;
462 IntArgs y({0,0,0});
463 rel(home, x, irt, y);
464 }
465 };
466
467 /// %Test for relation between differently sized arrays of integer variables
468 class IntArrayDiff : public Test {
469 protected:
470 /// Integer relation type to propagate
471 Gecode::IntRelType irt;
472 /// How many variables in total
473 static const int n = 4;
474 /// How big is the first array
475 int n_fst;
476 public:
477 /// Create and register test
478 IntArrayDiff(Gecode::IntRelType irt0, int m)
479 : Test("Rel::Int::Array::"+str(irt0)+"::"+str(m)+"::"+str(n-m),
480 n,-2,2),
481 irt(irt0), n_fst(m) {
482 assert(n_fst <= n);
483 }
484 /// %Test whether \a x is solution
485 virtual bool solution(const Assignment& x) const {
486 int n_snd = n - n_fst;
487 for (int i=0; i<std::min(n_fst,n_snd); i++)
488 if (x[i] != x[n_fst+i])
489 return cmp(x[i],irt,x[n_fst+i]);
490 return cmp(n_fst,irt,n_snd);
491 }
492 /// Post constraint on \a x
493 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
494 using namespace Gecode;
495 int n_snd = n - n_fst;
496 IntVarArgs y(n_fst); IntVarArgs z(n_snd);
497 for (int i=0; i<n_fst; i++) {
498 y[i]=x[i];
499 }
500 for (int i=0; i<n_snd; i++) {
501 z[i]=x[n_fst + i];
502 }
503 rel(home, y, irt, z);
504 }
505 };
506
507 /// %Test for relation between arrays of Boolean variables
508 class BoolArrayVar : public Test {
509 protected:
510 /// Integer relation type to propagate
511 Gecode::IntRelType irt;
512 public:
513 /// Create and register test
514 BoolArrayVar(Gecode::IntRelType irt0)
515 : Test("Rel::Bool::Array::Var::"+str(irt0),10,0,1), irt(irt0) {}
516 /// %Test whether \a x is solution
517 virtual bool solution(const Assignment& x) const {
518 int n=x.size() >> 1;
519 for (int i=0; i<n; i++)
520 if (x[i] != x[n+i])
521 return cmp(x[i],irt,x[n+i]);
522 return ((irt == Gecode::IRT_LQ) || (irt == Gecode::IRT_GQ) ||
523 (irt == Gecode::IRT_EQ));
524 GECODE_NEVER;
525 return false;
526 }
527 /// Post constraint on \a x
528 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
529 using namespace Gecode;
530 int n=x.size() >> 1;
531 BoolVarArgs y(n); BoolVarArgs z(n);
532 for (int i=0; i<n; i++) {
533 y[i]=channel(home,x[i]); z[i]=channel(home,x[n+i]);
534 }
535 rel(home, y, irt, z);
536 }
537 };
538
539 /// %Test for relation between arrays of Boolean variables and integers
540 class BoolArrayInt : public Test {
541 protected:
542 /// Integer relation type to propagate
543 Gecode::IntRelType irt;
544 public:
545 /// Create and register test
546 BoolArrayInt(Gecode::IntRelType irt0)
547 : Test("Rel::Bool::Array::Int::"+str(irt0),5,0,1), irt(irt0) {}
548 /// %Test whether \a x is solution
549 virtual bool solution(const Assignment& x) const {
550 Gecode::IntArgs y({0,0,1,0,0});
551 for (int i=0; i<5; i++)
552 if (x[i] != y[i])
553 return cmp(x[i],irt,y[i]);
554 return ((irt == Gecode::IRT_LQ) || (irt == Gecode::IRT_GQ) ||
555 (irt == Gecode::IRT_EQ));
556 GECODE_NEVER;
557 return false;
558 }
559 /// Post constraint on \a x
560 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
561 using namespace Gecode;
562 Gecode::IntArgs z({0,0,1,0,0});
563 int n=x.size();
564 BoolVarArgs y(n);
565 for (int i=0; i<n; i++)
566 y[i]=channel(home,x[i]);
567 rel(home, y, irt, z);
568 }
569 };
570
571 /// Help class to create and register tests
572 class Create {
573 public:
574 /// Perform creation and registration
575 Create(void) {
576 using namespace Gecode;
577 for (IntRelTypes irts; irts(); ++irts) {
578 for (IntPropLevels ipls; ipls(); ++ipls) {
579 (void) new IntVarXY(irts.irt(),1,ipls.ipl());
580 (void) new IntVarXY(irts.irt(),2,ipls.ipl());
581 (void) new IntVarXX(irts.irt(),ipls.ipl());
582 (void) new IntSeq(1,irts.irt(),ipls.ipl());
583 (void) new IntSeq(2,irts.irt(),ipls.ipl());
584 (void) new IntSeq(3,irts.irt(),ipls.ipl());
585 (void) new IntSeq(5,irts.irt(),ipls.ipl());
586 (void) new IntSharedSeq(1,irts.irt(),ipls.ipl());
587 (void) new IntSharedSeq(2,irts.irt(),ipls.ipl());
588 (void) new IntSharedSeq(3,irts.irt(),ipls.ipl());
589 (void) new IntSharedSeq(4,irts.irt(),ipls.ipl());
590 }
591 (void) new BoolVarXY(irts.irt(),1);
592 (void) new BoolVarXY(irts.irt(),2);
593 (void) new BoolVarXX(irts.irt());
594 (void) new BoolSeq(1,irts.irt());
595 (void) new BoolSeq(2,irts.irt());
596 (void) new BoolSeq(3,irts.irt());
597 (void) new BoolSeq(10,irts.irt());
598 (void) new BoolSharedSeq(1,irts.irt());
599 (void) new BoolSharedSeq(2,irts.irt());
600 (void) new BoolSharedSeq(3,irts.irt());
601 (void) new BoolSharedSeq(4,irts.irt());
602 (void) new BoolSharedSeq(8,irts.irt());
603 for (int c=-4; c<=4; c++) {
604 (void) new IntInt(irts.irt(),1,c);
605 (void) new IntInt(irts.irt(),2,c);
606 }
607 for (int c=0; c<=1; c++) {
608 (void) new BoolInt(irts.irt(),1,c);
609 (void) new BoolInt(irts.irt(),2,c);
610 }
611 (void) new IntArrayVar(irts.irt());
612 (void) new IntArrayInt(irts.irt());
613 for (int n_fst=0; n_fst<=4; n_fst++)
614 (void) new IntArrayDiff(irts.irt(),n_fst);
615 (void) new BoolArrayVar(irts.irt());
616 (void) new BoolArrayInt(irts.irt());
617 }
618 }
619 };
620
621 Create c;
622 //@}
623
624 }
625}}
626
627// STATISTICS: test-int