Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Node * x
Pointer to corresponding Boolean expression node.
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
Range iterator for integer sets.
Definition int.hh:292
Integer sets.
Definition int.hh:174
Integer variable array.
Definition int.hh:763
Range iterator for computing set difference.
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:488
Set variable array
Definition set.hh:570
Set variables
Definition set.hh:127
A complement iterator spezialized for the BndSet limits.
Definition var-imp.hpp:293
Computation spaces.
Definition core.hpp:1742
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:660
SetRelType
Common relation types for sets.
Definition set.hh:643
@ SOT_MINUS
Difference.
Definition set.hh:664
@ SOT_DUNION
Disjoint union.
Definition set.hh:662
@ SOT_UNION
Union.
Definition set.hh:661
@ SOT_INTER
Intersection
Definition set.hh:663
@ SRT_CMPL
Complement.
Definition set.hh:649
@ SRT_NQ
Disequality ( )
Definition set.hh:645
@ SRT_EQ
Equality ( )
Definition set.hh:644
@ SRT_SUP
Superset ( )
Definition set.hh:647
@ SRT_DISJ
Disjoint ( )
Definition set.hh:648
@ SRT_SUB
Subset ( )
Definition set.hh:646
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:767
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