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 "test/set.hh"
35
36using namespace Gecode;
37
38namespace Test { namespace Set {
39
40 /// %Tests for relation/operation constraints
41 namespace RelOp {
42
43 /**
44 * \defgroup TaskTestSetRelOp Relation/operation constraints
45 * \ingroup TaskTestSet
46 */
47 //@{
48
49 static IntSet ds_22(-2,2);
50 static IntSet ds_12(-1,2);
51
52 /// %Test for ternary relation constraint
53 class Rel : public SetTest {
54 private:
55 Gecode::SetOpType sot;
56 Gecode::SetRelType srt;
57 int share;
58
59 template<class I, class J>
60 bool
61 sol(I& i, J& j) const {
62 switch (srt) {
63 case SRT_EQ: return Iter::Ranges::equal(i,j);
64 case SRT_NQ: return !Iter::Ranges::equal(i,j);
65 case SRT_SUB: return Iter::Ranges::subset(i,j);
66 case SRT_SUP: return Iter::Ranges::subset(j,i);
67 case SRT_DISJ:
68 {
69 Gecode::Iter::Ranges::Inter<I,J> inter(i,j);
70 return !inter();
71 }
72 case SRT_CMPL:
73 {
74 Gecode::Set::RangesCompl<J> jc(j);
75 return Iter::Ranges::equal(i,jc);
76 }
77 default: GECODE_NEVER;
78 }
79 return false;
80 }
81
82 public:
83 /// Create and register test
84 Rel(Gecode::SetOpType sot0, Gecode::SetRelType srt0, int share0=0)
85 : SetTest("RelOp::"+str(sot0)+"::"+str(srt0)+"::S"+str(share0),
86 share0 == 0 ? 3 : 2,ds_22,false)
87 , sot(sot0), srt(srt0), share(share0) {}
88 /// %Test whether \a x is solution
89 bool solution(const SetAssignment& x) const {
90 int a=0, b=0, c=0;
91 switch (share) {
92 case 0: a=x[0]; b=x[1]; c=x[2]; break;
93 case 1: a=x[0]; b=x[0]; c=x[0]; break;
94 case 2: a=x[0]; b=x[0]; c=x[1]; break;
95 case 3: a=x[0]; b=x[1]; c=x[0]; break;
96 case 4: a=x[0]; b=x[1]; c=x[1]; break;
97 }
98 CountableSetRanges xr0(x.lub, a);
99 CountableSetRanges xr1(x.lub, b);
100 CountableSetRanges xr2(x.lub, c);
101 switch (sot) {
102 case SOT_UNION:
103 {
104 Iter::Ranges::Union<CountableSetRanges, CountableSetRanges>
105 u(xr0,xr1);
106 return sol(u,xr2);
107 }
108 break;
109 case SOT_DUNION:
110 {
111 Iter::Ranges::Inter<CountableSetRanges, CountableSetRanges>
112 inter(xr0,xr1);
113 if (inter())
114 return false;
115 Iter::Ranges::Union<CountableSetRanges, CountableSetRanges>
116 u(xr0,xr1);
117 return sol(u,xr2);
118 }
119 break;
120 case SOT_INTER:
121 {
122 Iter::Ranges::Inter<CountableSetRanges, CountableSetRanges>
123 u(xr0,xr1);
124 return sol(u,xr2);
125 }
126 break;
127 case SOT_MINUS:
128 {
129 Iter::Ranges::Diff<CountableSetRanges, CountableSetRanges>
130 u(xr0,xr1);
131 return sol(u,xr2);
132 }
133 break;
134 default: GECODE_NEVER;
135 }
136 GECODE_NEVER;
137 return false;
138 }
139 /// Post constraint on \a x
140 void post(Space& home, SetVarArray& x, IntVarArray&) {
141 SetVar a,b,c;
142 switch (share) {
143 case 0: a=x[0]; b=x[1]; c=x[2]; break;
144 case 1: a=x[0]; b=x[0]; c=x[0]; break;
145 case 2: a=x[0]; b=x[0]; c=x[1]; break;
146 case 3: a=x[0]; b=x[1]; c=x[0]; break;
147 case 4: a=x[0]; b=x[1]; c=x[1]; break;
148 }
149 Gecode::rel(home, a, sot, b, srt, c);
150 }
151 };
152
153 /// Help class to create and register tests
154 class Create {
155 public:
156 /// Perform creation and registration
157 Create(void) {
158 using namespace Gecode;
159 for (SetRelTypes srts; srts(); ++srts) {
160 for (SetOpTypes sots; sots(); ++sots) {
161 for (int i=0; i<=4; i++) {
162 (void) new Rel(sots.sot(),srts.srt(),i);
163 }
164 }
165 }
166 }
167 };
168
169 Create c;
170
171 /// %Test for n-ary partition constraint
172 class RelN : public SetTest {
173 private:
174 Gecode::SetOpType sot;
175 int n;
176 int shared;
177 bool withConst;
178 IntSet is;
179 public:
180 /// Create and register test
181 RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
182 : SetTest("RelOp::N::"+str(sot0)+"::"+str(n0)+"::S"+str(shared0)+
183 "::C"+str(withConst0 ? 1 : 0),
184 shared0 == 0 ? n0+1 : (shared0 <= 2 ? 3 : 2),ds_12,false)
185 , sot(sot0), n(n0), shared(shared0), withConst(withConst0)
186 , is(0,1) {
187 }
188 /// %Test whether \a x is solution
189 bool solution(const SetAssignment& x) const {
190 int realN = shared == 0 ? n : 3;
191
192 CountableSetRanges* isrs = new CountableSetRanges[realN];
193
194 switch (shared) {
195 case 0:
196 for (int i=realN; i--; )
197 isrs[i].init(x.lub, x[i]);
198 break;
199 case 1:
200 isrs[0].init(x.lub, x[0]);
201 isrs[1].init(x.lub, x[0]);
202 isrs[2].init(x.lub, x[1]);
203 break;
204 case 2:
205 isrs[0].init(x.lub, x[0]);
206 isrs[1].init(x.lub, x[1]);
207 isrs[2].init(x.lub, x[2]);
208 break;
209 case 3:
210 isrs[0].init(x.lub, x[0]);
211 isrs[1].init(x.lub, x[1]);
212 isrs[2].init(x.lub, x[0]);
213 break;
214 default:
215 GECODE_NEVER;
216 }
217
218 int result = shared == 0 ? x.size() - 1 : (shared <= 2 ? 2 : 0);
219 CountableSetRanges xnr(x.lub, x[result]);
220
221 switch (sot) {
222 case SOT_DUNION:
223 {
224 if (shared == 1 && (isrs[0]() || isrs[1]())) {
225 delete[] isrs; return false;
226 }
227 if (shared == 3 && (isrs[0]() || isrs[2]())) {
228 delete[] isrs; return false;
229 }
230 unsigned int cardSum = 0;
231 if (shared == 1 || shared == 3) {
232 CountableSetRanges x1r(x.lub, x[1]);
233 cardSum = Iter::Ranges::size(x1r);
234 } else {
235 for (int i=0; i<realN; i++) {
236 CountableSetRanges xir(x.lub, x[i]);
237 cardSum += Iter::Ranges::size(xir);
238 }
239 }
240 if (withConst)
241 cardSum += 2;
242 CountableSetRanges xnr2(x.lub, x[result]);
243 if (cardSum != Iter::Ranges::size(xnr2)) {
244 delete[] isrs; return false;
245 }
246 }
247 // fall through to union case
248 case SOT_UNION:
249 {
250 bool eq;
251 if (withConst) {
252 Region r;
253 Iter::Ranges::NaryUnion u(r, isrs, realN);
254 IntSetRanges isr(is);
255 Iter::Ranges::Union<IntSetRanges,
256 Iter::Ranges::NaryUnion> uu(isr, u);
257 eq = Iter::Ranges::equal(uu, xnr);
258 } else {
259 Region r;
260 Iter::Ranges::NaryUnion u(r, isrs, realN);
261 eq = Iter::Ranges::equal(u, xnr);
262 }
263 delete [] isrs;
264 return eq;
265 }
266 case SOT_INTER:
267 {
268 if (withConst) {
269 bool eq;
270 {
271 Region r;
272 Iter::Ranges::NaryInter u(r, isrs, realN);
273 IntSetRanges isr(is);
274 Iter::Ranges::Inter<IntSetRanges,
275 Iter::Ranges::NaryInter> uu(isr, u);
276 eq = (realN == 0 ? Iter::Ranges::equal(isr, xnr) :
277 Iter::Ranges::equal(uu, xnr));
278 delete [] isrs;
279 }
280 return eq;
281 } else {
282 if (realN == 0) {
283 bool ret =
284 Iter::Ranges::size(xnr) == Gecode::Set::Limits::card;
285 delete [] isrs;
286 return ret;
287 } else {
288 bool eq;
289 {
290 Region r;
291 Iter::Ranges::NaryInter u(r,isrs, realN);
292 eq = Iter::Ranges::equal(u, xnr);
293 }
294 delete [] isrs;
295 return eq;
296 }
297 }
298 }
299 default:
300 GECODE_NEVER;
301 }
302 GECODE_NEVER;
303 return false;
304 }
305 /// Post constraint on \a x
306 void post(Space& home, SetVarArray& x, IntVarArray&) {
307 int size = shared == 0 ? x.size()-1 : 3;
308 SetVarArgs xs(size);
309 SetVar xn;
310 switch (shared) {
311 case 0:
312 for (int i=x.size()-1; i--;)
313 xs[i]=x[i];
314 xn = x[x.size()-1];
315 break;
316 case 1:
317 xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2];
318 break;
319 case 2:
320 xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2];
321 break;
322 case 3:
323 xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0];
324 break;
325 default:
326 GECODE_NEVER;
327 break;
328 }
329 if (!withConst)
330 Gecode::rel(home, sot, xs, xn);
331 else
332 Gecode::rel(home, sot, xs, is, xn);
333 }
334 };
335
336 /// Help class to create and register tests
337 class CreateN {
338 public:
339 /// Perform creation and registration
340 CreateN(void) {
341 for (int wc=0; wc<=1; wc++) {
342 for (int i=0; i<=3; i++) {
343 (void) new RelN(Gecode::SOT_UNION, i, 0, wc);
344 (void) new RelN(Gecode::SOT_DUNION, i, 0, wc);
345 (void) new RelN(Gecode::SOT_INTER, i, 0, wc);
346
347 if (i>0) {
348 (void) new RelN(Gecode::SOT_UNION, 0, i, wc);
349 (void) new RelN(Gecode::SOT_DUNION, 0, i, wc);
350 (void) new RelN(Gecode::SOT_INTER, 0, i, wc);
351 }
352 }
353 }
354 }
355 };
356
357 CreateN cn;
358
359 /// %Test for n-ary partition constraint
360 class RelIntN : public SetTest {
361 private:
362 Gecode::SetOpType sot;
363 int n;
364 bool withConst;
365 IntSet is;
366 public:
367 /// Create and register test
368 RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
369 : SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+
370 "::C"+str(withConst0 ? 1 : 0),
371 1,ds_12,false,n0)
372 , sot(sot0), n(n0), withConst(withConst0)
373 , is(0,1) {
374 }
375 /// %Test whether \a x is solution
376 bool solution(const SetAssignment& x) const {
377 int* isrs = new int[n];
378 for (int i=0; i<n; i++)
379 isrs[i] = x.ints()[i];
380
381 IntSet iss(isrs,n);
382 CountableSetRanges xnr(x.lub, x[0]);
383
384 switch (sot) {
385 case SOT_DUNION:
386 {
387 IntSetRanges issr(iss);
388 unsigned int cardSum = Iter::Ranges::size(issr);
389 if (cardSum != static_cast<unsigned int>(n)) {
390 delete[] isrs;
391 return false;
392 }
393 if (withConst) {
394 IntSetRanges isr(is);
395 cardSum += Iter::Ranges::size(isr);
396 }
397 CountableSetRanges xnr2(x.lub, x[0]);
398 if (cardSum != Iter::Ranges::size(xnr2)) {
399 delete[] isrs;
400 return false;
401 }
402 }
403 // fall through to union case
404 case SOT_UNION:
405 {
406 if (withConst) {
407 IntSetRanges issr(iss);
408 IntSetRanges isr(is);
409 Iter::Ranges::Union<IntSetRanges,IntSetRanges > uu(isr, issr);
410 delete[] isrs;
411 return Iter::Ranges::equal(uu, xnr);
412 } else {
413 IntSetRanges issr(iss);
414 delete[] isrs;
415 return Iter::Ranges::equal(issr, xnr);
416 }
417 }
418 case SOT_INTER:
419 {
420 bool allEqual = true;
421 for (int i=1; i<n; i++) {
422 if (isrs[i] != isrs[0]) {
423 allEqual = false;
424 break;
425 }
426 }
427 if (withConst) {
428 if (allEqual) {
429 if (n == 0) {
430 IntSetRanges isr(is);
431 delete[] isrs;
432 return Iter::Ranges::equal(isr, xnr);
433 } else {
434 Iter::Ranges::Singleton s(isrs[0],isrs[0]);
435 IntSetRanges isr(is);
436 Iter::Ranges::Inter<IntSetRanges,Iter::Ranges::Singleton>
437 uu(isr, s);
438 delete[] isrs;
439 return Iter::Ranges::equal(uu, xnr);
440 }
441 } else {
442 delete[] isrs;
443 return Iter::Ranges::size(xnr) == 0;
444 }
445 } else {
446 if (allEqual) {
447 if (n == 0) {
448 delete[] isrs;
449 return Iter::Ranges::size(xnr) == Gecode::Set::Limits::card;
450 } else {
451 Iter::Ranges::Singleton s(isrs[0],isrs[0]);
452 delete[] isrs;
453 return Iter::Ranges::equal(s, xnr);
454 }
455 } else {
456 delete[] isrs;
457 return Iter::Ranges::size(xnr) == 0;
458 }
459 }
460 }
461 default:
462 GECODE_NEVER;
463 }
464 GECODE_NEVER;
465 return false;
466 }
467 /// Post constraint on \a x
468 void post(Space& home, SetVarArray& x, IntVarArray& y) {
469 if (!withConst)
470 Gecode::rel(home, sot, y, x[0]);
471 else
472 Gecode::rel(home, sot, y, is, x[0]);
473 }
474 };
475
476 /// Help class to create and register tests
477 class CreateIntN {
478 public:
479 /// Perform creation and registration
480 CreateIntN(void) {
481 for (int wc=0; wc<=1; wc++) {
482 for (int i=0; i<=3; i++) {
483 (void) new RelIntN(Gecode::SOT_UNION, i, wc);
484 (void) new RelIntN(Gecode::SOT_DUNION, i, wc);
485 (void) new RelIntN(Gecode::SOT_INTER, i, wc);
486 }
487 }
488 }
489 };
490
491 CreateIntN intcn;
492
493 //@}
494
495}}}
496
497// STATISTICS: test-set