Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
element.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 <gecode/minimodel.hh>
35
36#include "test/set.hh"
37
38using namespace Gecode;
39
40namespace Test { namespace Set {
41
43 namespace Element {
44
50
51 static IntSet ds_12(-1,2);
52 static IntSet ds_13(-1,3);
53
55 class ElementUnion : public SetTest {
56 public:
58 ElementUnion(const char* t)
59 : SetTest(t,5,ds_12,false) {}
61 virtual bool solution(const SetAssignment& x) const {
62 int selected = 0;
63 for (CountableSetValues sel2(x.lub, x[3]); sel2();
64 ++sel2, selected++) {}
65 CountableSetValues x4v(x.lub, x[4]);
66 if (selected==0)
67 return !x4v();
68 CountableSetRanges* sel = new CountableSetRanges[selected];
69 CountableSetValues selector(x.lub, x[3]);
70 for (int i=selected; i--;++selector) {
71 if (selector.val()>=3 || selector.val()<0) {
72 delete[] sel;
73 return false;
74 }
75 sel[i].init(x.lub, x[selector.val()]);
76 }
77
78 bool ret;
79 {
80 Region r;
81 Iter::Ranges::NaryUnion u(r, sel, selected);
82
83 CountableSetRanges z(x.lub, x[4]);
84 ret = Iter::Ranges::equal(u, z);
85 }
86 delete[] sel;
87 return ret;
88 }
90 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
91 SetVarArgs xs(x.size()-2);
92 for (int i=x.size()-2; i--;)
93 xs[i]=x[i];
94 Gecode::element(home, SOT_UNION, xs, x[x.size()-2], x[x.size()-1]);
95 }
96 };
97 ElementUnion _elementunion("Element::Union");
98
100 class ElementUnionConst : public SetTest {
101 private:
102 const IntSet i0;
103 const IntSet i1;
104 const IntSet i2;
105 public:
107 ElementUnionConst(const char* t)
108 : SetTest(t,2,ds_13,false), i0(-3,-3), i1(-1,1), i2(0,2) {}
110 virtual bool solution(const SetAssignment& x) const {
111 int selected = 0;
112 for (CountableSetValues sel2(x.lub, x[0]); sel2();
113 ++sel2, selected++) {}
114 CountableSetValues x4v(x.lub, x[1]);
115 if (selected==0)
116 return !x4v();
117 IntSet iss[] = {i0, i1, i2};
118 IntSetRanges* sel = new IntSetRanges[selected];
119 CountableSetValues selector(x.lub, x[0]);
120 for (int i=selected; i--;++selector) {
121 if (selector.val()>=3 || selector.val()<0) {
122 delete[] sel;
123 return false;
124 }
125 sel[i].init(iss[selector.val()]);
126 }
127
128 bool ret;
129 {
130 Region r;
131 Iter::Ranges::NaryUnion u(r, sel, selected);
132
133 CountableSetRanges z(x.lub, x[1]);
134 ret = Iter::Ranges::equal(u, z);
135 }
136 delete[] sel;
137 return ret;
138 }
140 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
141 IntSetArgs xs(3);
142 xs[0] = i0; xs[1] = i1; xs[2] = i2;
143 Gecode::element(home, SOT_UNION, xs, x[0], x[1]);
144 }
145 };
146 ElementUnionConst _elementunionconst("Element::UnionConst");
147
149 class ElementInter : public SetTest {
150 public:
152 ElementInter(const char* t)
153 : SetTest(t,5,ds_12,false) {}
155 virtual bool solution(const SetAssignment& x) const {
156 int selected = 0;
157 for (CountableSetValues sel2(x.lub, x[3]); sel2();
158 ++sel2, selected++) {}
159 CountableSetRanges x4r(x.lub, x[4]);
160 if (selected==0)
162 CountableSetRanges* sel = new CountableSetRanges[selected];
163 CountableSetValues selector(x.lub, x[3]);
164 for (int i=selected; i--;++selector) {
165 if (selector.val()>=3 || selector.val()<0) {
166 delete[] sel;
167 return false;
168 }
169 sel[i].init(x.lub, x[selector.val()]);
170 }
171 bool ret;
172 {
173 Region r;
174 Iter::Ranges::NaryInter u(r, sel, selected);
175
176 CountableSetRanges z(x.lub, x[4]);
177 ret = Iter::Ranges::equal(u, z);
178 }
179 delete [] sel;
180 return ret;
181 }
183 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
184 SetVarArgs xs(x.size()-2);
185 for (int i=x.size()-2; i--;)
186 xs[i]=x[i];
187 Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1]);
188 }
189 };
190 ElementInter _elementinter("Element::Inter");
191
193 class ElementInterIn : public SetTest {
194 public:
196 ElementInterIn(const char* t)
197 : SetTest(t,5,ds_12,false) {}
199 virtual bool solution(const SetAssignment& x) const {
200 int selected = 0;
201 for (CountableSetValues sel2(x.lub, x[3]); sel2();
202 ++sel2, selected++) {}
203 CountableSetRanges x4r(x.lub, x[4]);
204 if (selected==0)
205 return Iter::Ranges::size(x4r)==4;
206 CountableSetRanges* sel = new CountableSetRanges[selected];
207 CountableSetValues selector(x.lub, x[3]);
208 for (int i=selected; i--;++selector) {
209 if (selector.val()>=3 || selector.val()<0) {
210 delete[] sel;
211 return false;
212 }
213 sel[i].init(x.lub, x[selector.val()]);
214 }
215 bool ret;
216 {
217 Region r;
218 Iter::Ranges::NaryInter u(r,sel, selected);
219
220 CountableSetRanges z(x.lub, x[4]);
221 ret = Iter::Ranges::equal(u, z);
222 }
223 delete [] sel;
224 return ret;
225 }
227 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
228 SetVarArgs xs(x.size()-2);
229 for (int i=x.size()-2; i--;)
230 xs[i]=x[i];
231 Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1],
232 ds_12);
233 }
234 };
235 ElementInterIn _elementinterin("Element::InterIn");
236
238 class ElementDisjoint : public SetTest {
239 public:
241 ElementDisjoint(const char* t)
242 : SetTest(t,5,ds_12,false) {}
244 virtual bool solution(const SetAssignment& x) const {
245 int selected = 0;
246 for (CountableSetValues sel2(x.lub, x[3]); sel2();
247 ++sel2, selected++) {
248 if (sel2.val() < 0)
249 return false;
250 }
251 CountableSetValues x4v(x.lub, x[4]);
252 if (selected == 0)
253 return !x4v();
254 CountableSetRanges* sel = new CountableSetRanges[selected];
255 CountableSetValues selector(x.lub, x[3]);
256 unsigned int cardsum = 0;
257 for (int i=selected; i--;++selector) {
258 if (selector.val()>=3 || selector.val()<0) {
259 delete[] sel;
260 return false;
261 }
262 sel[i].init(x.lub, x[selector.val()]);
263 CountableSetRanges xicard(x.lub, x[selector.val()]);
264 cardsum += Iter::Ranges::size(xicard);
265 }
266
267 bool ret;
268 {
269 Region r;
270 Iter::Ranges::NaryUnion u(r, sel, selected);
271 ret = Iter::Ranges::size(u) == cardsum;
272 u.reset();
273 CountableSetRanges z(x.lub, x[4]);
274 ret &= Iter::Ranges::equal(u, z);
275 }
276 delete[] sel;
277 return ret;
278 }
280 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
281 SetVarArgs xs(x.size()-2);
282 for (int i=x.size()-2; i--;)
283 xs[i]=x[i];
284 Gecode::element(home, SOT_DUNION, xs, x[x.size()-2], x[x.size()-1]);
285 }
286 };
287 ElementDisjoint _elementdisjoint("Element::Disjoint");
288
290 class ElementSet : public SetTest {
291 public:
293 ElementSet(const char* t)
294 : SetTest(t,4,ds_12,false,true) {}
296 virtual bool solution(const SetAssignment& x) const {
297 if (x.intval() < 0 || x.intval() > 2)
298 return false;
299 CountableSetRanges z(x.lub, x[3]);
300 CountableSetRanges y(x.lub, x[x.intval()]);
301 return Iter::Ranges::equal(y, z);
302 }
304 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
305 SetVarArgs xs(x.size()-1);
306 for (int i=x.size()-1; i--;)
307 xs[i]=x[i];
308 Gecode::element(home, xs, y[0], x[x.size()-1]);
309 }
310 };
311 ElementSet _elementset("Element::Set");
312
314 class ElementSetConst : public SetTest {
315 private:
316 const IntSet i0;
317 const IntSet i1;
318 const IntSet i2;
319 public:
321 ElementSetConst(const char* t)
322 : SetTest(t,1,ds_13,false,true), i0(-3,-3), i1(-1,1), i2(0,2) {}
324 virtual bool solution(const SetAssignment& x) const {
325 if (x.intval() < 0 || x.intval() > 2)
326 return false;
327 CountableSetRanges xr(x.lub, x[0]);
328 IntSet iss[] = {i0, i1, i2};
329 IntSetRanges isr(iss[x.intval()]);
330 return Iter::Ranges::equal(xr, isr);
331 }
333 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
334 IntSetArgs xs(3);
335 xs[0] = i0; xs[1] = i1; xs[2] = i2;
336 Gecode::element(home, xs, y[0], x[0]);
337 }
338 };
339 ElementSetConst _elementsetconst("Element::SetConst");
340
342 class MatrixIntSet : public SetTest {
343 protected:
346 public:
349 : SetTest("Element::Matrix::IntSet",1,IntSet(0,3),false,2),
350 tm(4) {
351 tm[0]=IntSet(0,0); tm[1]=IntSet(1,1);
352 tm[2]=IntSet(2,2); tm[3]=IntSet(3,3);
353 }
355 virtual bool solution(const SetAssignment& x) const {
356 // Get integer assignment
357 const Int::Assignment& y = x.ints();
358 // x-coordinate: y[0], y-coordinate: y[1], result: x[0]
359 using namespace Gecode;
360 if ((y[0] > 1) || (y[1] > 1))
361 return false;
362 Matrix<IntSetArgs> m(tm,2,2);
363 IntSetRanges a(m(y[0],y[1]));
364 CountableSetRanges b(x.lub, x[0]);
365 return Iter::Ranges::equal(a,b);
366 }
370 // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
371 using namespace Gecode;
372 Matrix<IntSetArgs> m(tm,2,2);
373 element(home, m, y[0], y[1], x[0]);
374 }
375 };
376
378
380
381}}}
382
383// 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.
NodeType t
Type of node.
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
void init(const IntSet &s)
Initialize with ranges for set s.
Integer sets.
Definition int.hh:174
Integer variable array.
Definition int.hh:763
Range iterator for intersection of iterators.
Range iterator for union of iterators.
Matrix-interface for arrays.
Passing set variables.
Definition set.hh:488
Set variable array
Definition set.hh:570
Computation spaces.
Definition core.hpp:1742
Base class for assignments
Definition int.hh:59
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
Value iterator producing subsets of an IntSet.
Definition set.hh:60
int val(void) const
Return current value.
Definition set.hh:94
Test for ElementDisjoint constraint
Definition element.cpp:238
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:244
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition element.cpp:280
ElementDisjoint(const char *t)
Create and register test.
Definition element.cpp:241
Test for ElementInter constraint
Definition element.cpp:193
ElementInterIn(const char *t)
Create and register test.
Definition element.cpp:196
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition element.cpp:227
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:199
Test for ElementInter constraint
Definition element.cpp:149
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:155
ElementInter(const char *t)
Create and register test.
Definition element.cpp:152
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition element.cpp:183
Test for ElementSetConst constraint
Definition element.cpp:314
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:324
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition element.cpp:333
ElementSetConst(const char *t)
Create and register test.
Definition element.cpp:321
Test for ElementSet constraint
Definition element.cpp:290
ElementSet(const char *t)
Create and register test.
Definition element.cpp:293
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition element.cpp:304
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:296
Test for ElementUnionConst constraint
Definition element.cpp:100
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:110
ElementUnionConst(const char *t)
Create and register test.
Definition element.cpp:107
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition element.cpp:140
Test for ElementUnion constraint
Definition element.cpp:55
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:61
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition element.cpp:90
ElementUnion(const char *t)
Create and register test.
Definition element.cpp:58
Test for matrix element with integer set array and set variable
Definition element.cpp:342
Gecode::IntSetArgs tm
Array for test matrix.
Definition element.cpp:345
virtual void post(Gecode::Space &home, Gecode::SetVarArray &x, Gecode::IntVarArray &y)
Post constraint on x and y.
Definition element.cpp:368
MatrixIntSet(void)
Create and register test.
Definition element.cpp:348
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition element.cpp:355
Generate all set assignments.
Definition set.hh:142
Base class for tests with set constraints
Definition set.hh:273
@ SOT_DUNION
Disjoint union.
Definition set.hh:662
@ SOT_UNION
Union.
Definition set.hh:661
@ SOT_INTER
Intersection
Definition set.hh:663
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
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
Definition element.cpp:39
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
ElementInter _elementinter("Element::Inter")
ElementInterIn _elementinterin("Element::InterIn")
ElementSetConst _elementsetconst("Element::SetConst")
ElementUnionConst _elementunionconst("Element::UnionConst")
MatrixIntSet _emis
Definition element.cpp:377
ElementDisjoint _elementdisjoint("Element::Disjoint")
ElementUnion _elementunion("Element::Union")
ElementSet _elementset("Element::Set")
General test support.
Definition afc.cpp:39
Region r
Definition region.cpp:65