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#include "test/int.hh"
36#include <gecode/minimodel.hh>
37
38using namespace Gecode;
39
40namespace Test { namespace Set {
41
42 /// %Tests for combined int/set constraints
43 namespace Int {
44
45 /**
46 * \defgroup TaskTestSetInt Combined integer/set constraints
47 * \ingroup TaskTestSet
48 */
49 //@{
50
51 static const int d1r[4][2] = {
52 {-4,-3},{-1,-1},{1,1},{3,5}
53 };
54 static IntSet d1(d1r,4);
55
56 static IntSet d2(-1,3);
57 static IntSet d3(0,3);
58
59 static IntSet d4(0,4);
60
61 static IntSet ds_33(-3,3);
62
63 /// %Test for cardinality constraint
64 class Card : public SetTest {
65 public:
66 /// Create and register test
67 Card(const char* t)
68 : SetTest(t,1,ds_33,true,1) {}
69 /// %Test whether \a x is solution
70 virtual bool solution(const SetAssignment& x) const {
71 unsigned int s = 0;
72 for (CountableSetRanges xr(x.lub, x[0]);xr();++xr) s+= xr.width();
73 if (x.intval() < 0)
74 return false;
75 return s==(unsigned int)x.intval();
76 }
77 /// Post constraint on \a x
78 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
79 Gecode::cardinality(home, x[0], y[0]);
80 }
81 /// Post reified constraint on \a x
82 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
83 Reify r) {
84 Gecode::cardinality(home, x[0], y[0], r);
85 }
86 };
87 Card _card("Int::Card");
88
89 /// %Test for minimal element constraint
90 class Min : public SetTest {
91 public:
92 /// Create and register test
93 Min(const char* t)
94 : SetTest(t,1,ds_33,true,1) {}
95 /// %Test whether \a x is solution
96 virtual bool solution(const SetAssignment& x) const {
97 CountableSetRanges xr0(x.lub, x[0]);
98 return xr0() && xr0.min()==x.intval();
99 }
100 /// Post constraint on \a x
101 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
102 Gecode::min(home, x[0], y[0]);
103 }
104 /// Post reified constraint on \a x
105 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
106 Reify r) {
107 Gecode::min(home, x[0], y[0], r);
108 }
109 };
110 Min _min("Int::Min");
111
112 /// %Test for negated minimal element constraint
113 class NotMin : public SetTest {
114 public:
115 /// Create and register test
116 NotMin(const char* t)
117 : SetTest(t,1,ds_33,false,1) {}
118 /// %Test whether \a x is solution
119 virtual bool solution(const SetAssignment& x) const {
120 CountableSetRanges xr0(x.lub, x[0]);
121 return !(xr0() && xr0.min()==x.intval());
122 }
123 /// Post constraint on \a x
124 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
125 Gecode::notMin(home, x[0], y[0]);
126 }
127 };
128 NotMin _notmin("Int::NotMin");
129
130 /// %Test for maximal element constraint
131 class Max : public SetTest {
132 public:
133 /// Create and register test
134 Max(const char* t)
135 : SetTest(t,1,ds_33,true,1) {}
136 /// %Test whether \a x is solution
137 virtual bool solution(const SetAssignment& x) const {
138 CountableSetRanges xr0(x.lub, x[0]);
139 IntSet x0(xr0);
140 return x0.ranges() > 0 && x0.max()==x.intval();
141 }
142 /// Post constraint on \a x
143 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
144 Gecode::max(home, x[0], y[0]);
145 }
146 /// Post reified constraint on \a x
147 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
148 Reify r) {
149 Gecode::max(home, x[0], y[0], r);
150 }
151 };
152 Max _max("Int::Max");
153
154 /// %Test for negated maximal element constraint
155 class NotMax : public SetTest {
156 public:
157 /// Create and register test
158 NotMax(const char* t)
159 : SetTest(t,1,ds_33,false,1) {}
160 /// %Test whether \a x is solution
161 virtual bool solution(const SetAssignment& x) const {
162 CountableSetRanges xr0(x.lub, x[0]);
163 IntSet x0(xr0);
164 return !(x0.ranges() > 0 && x0.max()==x.intval());
165 }
166 /// Post constraint on \a x
167 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
168 Gecode::notMax(home, x[0], y[0]);
169 }
170 };
171 NotMax _notmax("Int::NotMax");
172
173 /// %Test for element constraint
174 class Elem : public SetTest {
175 public:
176 /// Create and register test
177 Elem(const char* t)
178 : SetTest(t,1,ds_33,true,1) {}
179 /// %Test whether \a x is solution
180 virtual bool solution(const SetAssignment& x) const {
181 for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
182 if (xr.val()==x.intval())
183 return true;
184 return false;
185 }
186 /// Post constraint on \a x
187 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
188 Gecode::rel(home, x[0], SRT_SUP, y[0]);
189 }
190 /// Post reified constraint on \a x for \a b
191 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
192 Reify r) {
193 Gecode::rel(home, x[0], SRT_SUP, y[0], r);
194 }
195 };
196 Elem _elem("Int::Elem");
197
198 /// %Test for negated element constraint
199 class NoElem : public SetTest {
200 public:
201 /// Create and register test
202 NoElem(const char* t)
203 : SetTest(t,1,ds_33,false,1) {}
204 /// %Test whether \a x is solution
205 virtual bool solution(const SetAssignment& x) const {
206 for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
207 if (xr.val()==x.intval())
208 return false;
209 return true;
210 }
211 /// Post constraint on \a x
212 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
213 Gecode::rel(home, x[0], SRT_DISJ, y[0]);
214 }
215 };
216 NoElem _noelem("Int::NoElem");
217
218 /// %Test for relation constraint
219 class Rel : public SetTest {
220 private:
221 /// The set relation type
222 Gecode::SetRelType srt;
223 /// Whether relation is swapped
224 bool swapped;
225 public:
226 /// Create and register test
227 Rel(Gecode::SetRelType srt0, bool s)
228 : SetTest("Int::Rel::"+str(srt0)+(s ? "::s" : ""),
229 1,ds_33,true,1),
230 srt(srt0), swapped(s) {}
231 /// %Test whether \a x is solution
232 virtual bool solution(const SetAssignment& x) const {
233 CountableSetRanges xr(x.lub, x[0]);
234 IntSet is(x.intval(), x.intval());
235 IntSetRanges dr(is);
236 Gecode::SetRelType rsrt = srt;
237 if (swapped) {
238 switch (srt) {
239 case SRT_SUB: rsrt = SRT_SUP; break;
240 case SRT_SUP: rsrt = SRT_SUB; break;
241 default: break;
242 }
243 }
244 switch (rsrt) {
245 case SRT_EQ: return Iter::Ranges::equal(xr, dr);
246 case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
247 case SRT_SUB: return Iter::Ranges::subset(xr, dr);
248 case SRT_SUP: return Iter::Ranges::subset(dr, xr);
249 case SRT_DISJ:
250 {
251 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
252 inter(xr, dr);
253 return !inter();
254 }
255 case SRT_CMPL:
256 {
257 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
258 return Iter::Ranges::equal(xr,drc);
259 }
260 default: GECODE_NEVER;
261 }
262 return false;
263 }
264 /// Post constraint on \a x
265 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
266 if (!swapped)
267 Gecode::rel(home, x[0], srt, y[0]);
268 else
269 Gecode::rel(home, y[0], srt, x[0]);
270 }
271 /// Post reified constraint on \a x for \a r
272 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
273 Reify r) {
274 if (!swapped)
275 Gecode::rel(home, x[0], srt, y[0], r);
276 else
277 Gecode::rel(home, y[0], srt, x[0], r);
278 }
279 };
280 Rel _rel_eq(Gecode::SRT_EQ,false);
281 Rel _rel_nq(Gecode::SRT_NQ,false);
282 Rel _rel_sub(Gecode::SRT_SUB,false);
283 Rel _rel_sup(Gecode::SRT_SUP,false);
284 Rel _rel_disj(Gecode::SRT_DISJ,false);
285 Rel _rel_cmpl(Gecode::SRT_CMPL,false);
286 Rel _rel_eqs(Gecode::SRT_EQ,true);
287 Rel _rel_nqs(Gecode::SRT_NQ,true);
288 Rel _rel_subs(Gecode::SRT_SUB,true);
289 Rel _rel_sups(Gecode::SRT_SUP,true);
290 Rel _rel_disjs(Gecode::SRT_DISJ,true);
291 Rel _rel_cmpls(Gecode::SRT_CMPL,true);
292
293 /// %Test for integer relation constraint
294 class IntRel : public SetTest {
295 private:
296 /// The integer relation type
297 Gecode::IntRelType irt;
298 /// Whether the arguments are swapped
299 bool swapped;
300 public:
301 /// Create and register test
302 IntRel(Gecode::IntRelType irt0, bool s)
303 : SetTest("Int::IntRel::"+Test::Int::Test::str(irt0)+
304 (s ? "::s" : ""),1,ds_33,true,1),
305 irt(irt0), swapped(s) {
306 testsubsumed = false;
307 }
308 /// %Test whether \a x is solution
309 virtual bool solution(const SetAssignment& x) const {
310 CountableSetValues xr(x.lub, x[0]);
311 if (!xr())
312 return false;
313 for (; xr(); ++xr)
314 switch (irt) {
315 case Gecode::IRT_EQ:
316 if (xr.val() != x.intval()) return false;
317 break;
318 case Gecode::IRT_NQ:
319 if (xr.val() == x.intval()) return false;
320 break;
321 case Gecode::IRT_GR:
322 if (!swapped && xr.val() <= x.intval()) return false;
323 if (swapped && xr.val() >= x.intval()) return false;
324 break;
325 case Gecode::IRT_GQ:
326 if (!swapped && xr.val() < x.intval()) return false;
327 if (swapped && xr.val() > x.intval()) return false;
328 break;
329 case Gecode::IRT_LE:
330 if (!swapped && xr.val() >= x.intval()) return false;
331 if (swapped && xr.val() <= x.intval()) return false;
332 break;
333 case Gecode::IRT_LQ:
334 if (!swapped && xr.val() > x.intval()) return false;
335 if (swapped && xr.val() < x.intval()) return false;
336 break;
337 default:
338 GECODE_NEVER;
339 return false;
340 }
341 return true;
342 }
343 /// Post constraint on \a x
344 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
345 if (!swapped)
346 Gecode::rel(home, x[0], irt, y[0]);
347 else
348 Gecode::rel(home, y[0], irt, x[0]);
349 }
350 /// Post reified constraint on \a x for \a r
351 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
352 Reify r) {
353 assert((x.size() == 1) && (y.size() == 1));
354 if ((r.mode() != Gecode::RM_EQV) || (_rand(2) != 0)) {
355 if (!swapped)
356 Gecode::rel(home, x[0], irt, y[0], r);
357 else
358 Gecode::rel(home, y[0], irt, x[0], r);
359 } else if (swapped) {
360 switch (irt) {
361 case Gecode::IRT_EQ:
362 Gecode::rel(home, (y[0] == x[0]) == r.var()); break;
363 case Gecode::IRT_NQ:
364 Gecode::rel(home, (y[0] != x[0]) == r.var()); break;
365 case Gecode::IRT_LE:
366 Gecode::rel(home, (y[0] < x[0]) == r.var()); break;
367 case Gecode::IRT_LQ:
368 Gecode::rel(home, (y[0] <= x[0]) == r.var()); break;
369 case Gecode::IRT_GR:
370 Gecode::rel(home, (y[0] > x[0]) == r.var()); break;
371 case Gecode::IRT_GQ:
372 Gecode::rel(home, (y[0] >= x[0]) == r.var()); break;
373 default: GECODE_NEVER;
374 }
375 } else {
376 switch (irt) {
377 case Gecode::IRT_EQ:
378 Gecode::rel(home, (x[0] == y[0]) == r.var()); break;
379 case Gecode::IRT_NQ:
380 Gecode::rel(home, (x[0] != y[0]) == r.var()); break;
381 case Gecode::IRT_LE:
382 Gecode::rel(home, (x[0] < y[0]) == r.var()); break;
383 case Gecode::IRT_LQ:
384 Gecode::rel(home, (x[0] <= y[0]) == r.var()); break;
385 case Gecode::IRT_GR:
386 Gecode::rel(home, (x[0] > y[0]) == r.var()); break;
387 case Gecode::IRT_GQ:
388 Gecode::rel(home, (x[0] >= y[0]) == r.var()); break;
389 default: GECODE_NEVER;
390 }
391 }
392 }
393 };
394 IntRel _intrel_eq(Gecode::IRT_EQ,false);
395 IntRel _intrel_nq(Gecode::IRT_NQ,false);
396 IntRel _intrel_gr(Gecode::IRT_GR,false);
397 IntRel _intrel_gq(Gecode::IRT_GQ,false);
398 IntRel _intrel_le(Gecode::IRT_LE,false);
399 IntRel _intrel_lq(Gecode::IRT_LQ,false);
400 IntRel _intrel_eqs(Gecode::IRT_EQ,true);
401 IntRel _intrel_nqs(Gecode::IRT_NQ,true);
402 IntRel _intrel_grs(Gecode::IRT_GR,true);
403 IntRel _intrel_gqs(Gecode::IRT_GQ,true);
404 IntRel _intrel_les(Gecode::IRT_LE,true);
405 IntRel _intrel_lqs(Gecode::IRT_LQ,true);
406
407
408 template<class I>
409 int weightI(const IntArgs& elements,
410 const IntArgs& weights,
411 I& iter) {
412 int sum = 0;
413 int i = 0;
414 for (Iter::Ranges::ToValues<I> v(iter); v(); ++v) {
415 // Skip all elements below the current
416 while (elements[i]<v.val()) i++;
417 assert(elements[i] == v.val());
418 sum += weights[i];
419 }
420 return sum;
421 }
422
423 /// %Test for set weight constraint
424 class Weights : public SetTest {
425 public:
426 IntArgs elements;
427 IntArgs weights;
428 int minWeight;
429 int maxWeight;
430 /// Create and register test
431 Weights(const char* t, IntArgs& el, IntArgs& w,
432 int min = -10000, int max = 10000)
433 : SetTest(t,1,ds_33,false,1),
434 elements(el), weights(w), minWeight(min), maxWeight(max) {}
435 /// %Test whether \a x is solution
436 virtual bool solution(const SetAssignment& x) const {
437 CountableSetRanges x0(x.lub, x[0]);
438 return x.intval()==weightI(elements,weights,x0) &&
439 x.intval() >= minWeight && x.intval() <= maxWeight;
440 }
441 /// Post constraint on \a x
442 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
443 Gecode::rel(home, minWeight <= y[0]);
444 Gecode::rel(home, maxWeight >= y[0]);
445 Gecode::weights(home, elements, weights, x[0], y[0]);
446 }
447 };
448
449 const int el1v[] = {-3,-2,-1,0,1,2,3};
450 IntArgs el1(7,el1v);
451 const int w1v[] = {1,-2,1,1,1,6,1};
452 IntArgs w1(7,w1v);
453 Weights _weights1("Int::Weights::1", el1, w1);
454
455 const int w2v[] = {-1,-1,-1,10,-1,-1,-1};
456 IntArgs w2(7,w2v);
457 Weights _weights2("Int::Weights::2", el1, w2);
458 Weights _weights3("Int::Weights::3", el1, w2, 3);
459
460 const int w4v[] = {1,1,0,0,0,0,0};
461 IntArgs w4(7,w4v);
462 Weights _weights4("Int::Weights::4", el1, w4);
463
464}}}
465
466// STATISTICS: test-set