Generated on Fri Jul 21 2023 00:00:00 for Gecode by doxygen 1.9.6
rel-op.cpp
Go to the documentation of this file.
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
41 namespace RelOp {
42
48
49 static IntSet ds_22(-2,2);
50 static IntSet ds_12(-1,2);
51
53 class Rel : public SetTest {
54 private:
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 {
70 return !inter();
71 }
72 case SRT_CMPL:
73 {
75 return Iter::Ranges::equal(i,jc);
76 }
77 default: GECODE_NEVER;
78 }
79 return false;
80 }
81
82 public:
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) {}
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 {
105 u(xr0,xr1);
106 return sol(u,xr2);
107 }
108 break;
109 case SOT_DUNION:
110 {
112 inter(xr0,xr1);
113 if (inter())
114 return false;
116 u(xr0,xr1);
117 return sol(u,xr2);
118 }
119 break;
120 case SOT_INTER:
121 {
123 u(xr0,xr1);
124 return sol(u,xr2);
125 }
126 break;
127 case SOT_MINUS:
128 {
130 u(xr0,xr1);
131 return sol(u,xr2);
132 }
133 break;
134 default: GECODE_NEVER;
135 }
137 return false;
138 }
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
154 class Create {
155 public:
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
170
172 class RelN : public SetTest {
173 private:
175 int n;
176 int shared;
177 bool withConst;
178 IntSet is;
179 public:
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 }
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:
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);
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);
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 =
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:
301 }
303 return false;
304 }
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:
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
337 class CreateN {
338 public:
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
358
360 class RelIntN : public SetTest {
361 private:
363 int n;
364 bool withConst;
365 IntSet is;
366 public:
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 }
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);
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);
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;
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:
463 }
465 return false;
466 }
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
478 public:
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
492
494
495}}}
496
497// STATISTICS: test-set
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
Range iterator for integer sets.
Definition: int.hh:292
Integer sets.
Definition: int.hh:174
Integer variable array.
Definition: int.hh:772
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
Range iterator for computing intersection (binary)
Range iterator for intersection of iterators.
Range iterator for union of iterators.
Range iterator for singleton range.
Range iterator for computing union (binary)
Passing set variables.
Definition: set.hh:491
Set variable array
Definition: set.hh:573
Set variables
Definition: set.hh:127
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:293
Computation spaces.
Definition: core.hpp:1744
Test for Region memory area
Definition: region.cpp:42
Range iterator producing subsets of an IntSet.
Definition: set.hh:99
void init(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:111
Help class to create and register tests.
Definition: rel-op.cpp:477
CreateIntN(void)
Perform creation and registration.
Definition: rel-op.cpp:480
Help class to create and register tests.
Definition: rel-op.cpp:337
CreateN(void)
Perform creation and registration.
Definition: rel-op.cpp:340
Help class to create and register tests.
Definition: rel-op.cpp:154
Create(void)
Perform creation and registration.
Definition: rel-op.cpp:157
Test for n-ary partition constraint
Definition: rel-op.cpp:360
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:376
RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
Create and register test.
Definition: rel-op.cpp:368
void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: rel-op.cpp:468
Test for n-ary partition constraint
Definition: rel-op.cpp:172
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel-op.cpp:306
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:189
RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
Create and register test.
Definition: rel-op.cpp:181
Test for ternary relation constraint
Definition: rel-op.cpp:53
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel-op.cpp:89
Rel(Gecode::SetOpType sot0, Gecode::SetRelType srt0, int share0=0)
Create and register test.
Definition: rel-op.cpp:84
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel-op.cpp:140
Generate all set assignments.
Definition: set.hh:142
Iterator for Boolean operation types.
Definition: set.hh:352
Iterator for set relation types.
Definition: set.hh:334
Base class for tests with set constraints
Definition: set.hh:273
static std::string str(Gecode::SetRelType srt)
Map set relation to string.
Definition: set.hpp:46
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition: rel.cpp:68
SetOpType
Common operations for sets.
Definition: set.hh:666
SetRelType
Common relation types for sets.
Definition: set.hh:649
@ SOT_MINUS
Difference.
Definition: set.hh:670
@ SOT_DUNION
Disjoint union.
Definition: set.hh:668
@ SOT_UNION
Union.
Definition: set.hh:667
@ SOT_INTER
Intersection
Definition: set.hh:669
@ SRT_CMPL
Complement.
Definition: set.hh:655
@ SRT_NQ
Disequality ( )
Definition: set.hh:651
@ SRT_EQ
Equality ( )
Definition: set.hh:650
@ SRT_SUP
Superset ( )
Definition: set.hh:653
@ SRT_DISJ
Disjoint ( )
Definition: set.hh:654
@ SRT_SUB
Subset ( )
Definition: set.hh:652
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
unsigned int size(I &i)
Size of all ranges of range iterator i.
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
Gecode toplevel namespace
SetExpr inter(const SetVarArgs &)
Intersection of set variables.
Definition: set-expr.cpp:696
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:773
CreateIntN intcn
Definition: rel-op.cpp:491
General test support.
Definition: afc.cpp:39
Region r
Definition: region.cpp:65
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56