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 <gecode/minimodel.hh>
35
36#include "test/set.hh"
37
38using namespace Gecode;
39
40namespace Test { namespace Set {
41
42 /// %Tests for set element constraints
43 namespace Element {
44
45 /**
46 * \defgroup TaskTestSetElement Element constraints
47 * \ingroup TaskTestSet
48 */
49 //@{
50
51 static IntSet ds_12(-1,2);
52 static IntSet ds_13(-1,3);
53
54 /// %Test for %ElementUnion constraint
55 class ElementUnion : public SetTest {
56 public:
57 /// Create and register test
58 ElementUnion(const char* t)
59 : SetTest(t,5,ds_12,false) {}
60 /// %Test whether \a x is solution
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 }
89 /// Post constraint on \a x
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
99 /// %Test for %ElementUnionConst constraint
100 class ElementUnionConst : public SetTest {
101 private:
102 const IntSet i0;
103 const IntSet i1;
104 const IntSet i2;
105 public:
106 /// Create and register test
107 ElementUnionConst(const char* t)
108 : SetTest(t,2,ds_13,false), i0(-3,-3), i1(-1,1), i2(0,2) {}
109 /// %Test whether \a x is solution
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 }
139 /// Post constraint on \a x
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
148 /// %Test for %ElementInter constraint
149 class ElementInter : public SetTest {
150 public:
151 /// Create and register test
152 ElementInter(const char* t)
153 : SetTest(t,5,ds_12,false) {}
154 /// %Test whether \a x is solution
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)
161 return Iter::Ranges::size(x4r)==Gecode::Set::Limits::card;
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 }
182 /// Post constraint on \a x
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
192 /// %Test for %ElementInter constraint
193 class ElementInterIn : public SetTest {
194 public:
195 /// Create and register test
196 ElementInterIn(const char* t)
197 : SetTest(t,5,ds_12,false) {}
198 /// %Test whether \a x is solution
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 }
226 /// Post constraint on \a x
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
237 /// %Test for %ElementDisjoint constraint
238 class ElementDisjoint : public SetTest {
239 public:
240 /// Create and register test
241 ElementDisjoint(const char* t)
242 : SetTest(t,5,ds_12,false) {}
243 /// %Test whether \a x is solution
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 }
279 /// Post constraint on \a x
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
289 /// %Test for %ElementSet constraint
290 class ElementSet : public SetTest {
291 public:
292 /// Create and register test
293 ElementSet(const char* t)
294 : SetTest(t,4,ds_12,false,true) {}
295 /// %Test whether \a x is solution
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 }
303 /// Post constraint on \a x
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
313 /// %Test for %ElementSetConst constraint
314 class ElementSetConst : public SetTest {
315 private:
316 const IntSet i0;
317 const IntSet i1;
318 const IntSet i2;
319 public:
320 /// Create and register test
321 ElementSetConst(const char* t)
322 : SetTest(t,1,ds_13,false,true), i0(-3,-3), i1(-1,1), i2(0,2) {}
323 /// %Test whether \a x is solution
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 }
332 /// Post constraint on \a x
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
341 /// %Test for matrix element with integer set array and set variable
342 class MatrixIntSet : public SetTest {
343 protected:
344 /// Array for test matrix
345 Gecode::IntSetArgs tm;
346 public:
347 /// Create and register test
348 MatrixIntSet(void)
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 }
354 /// %Test whether \a x is solution
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 }
367 /// Post constraint on \a x and \a y
368 virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
369 Gecode::IntVarArray& y) {
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
377 MatrixIntSet _emis;
378
379 //@}
380
381}}}
382
383// STATISTICS: test-set