00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #include "test/set.hh"
00035 #include "test/int.hh"
00036 #include <gecode/minimodel.hh>
00037
00038 using namespace Gecode;
00039
00040 namespace Test { namespace Set {
00041
00043 namespace Int {
00044
00050
00051 static const int d1r[4][2] = {
00052 {-4,-3},{-1,-1},{1,1},{3,5}
00053 };
00054 static IntSet d1(d1r,4);
00055
00056 static IntSet d2(-1,3);
00057 static IntSet d3(0,3);
00058
00059 static IntSet d4(0,4);
00060
00061 static IntSet ds_33(-3,3);
00062
00064 class Card : public SetTest {
00065 public:
00067 Card(const char* t)
00068 : SetTest(t,1,ds_33,true,1) {}
00070 virtual bool solution(const SetAssignment& x) const {
00071 unsigned int s = 0;
00072 for (CountableSetRanges xr(x.lub, x[0]);xr();++xr) s+= xr.width();
00073 if (x.intval() < 0)
00074 return false;
00075 return s==(unsigned int)x.intval();
00076 }
00078 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00079 Gecode::cardinality(home, x[0], y[0]);
00080 }
00082 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00083 Reify r) {
00084 Gecode::cardinality(home, x[0], y[0], r);
00085 }
00086 };
00087 Card _card("Int::Card");
00088
00090 class Min : public SetTest {
00091 public:
00093 Min(const char* t)
00094 : SetTest(t,1,ds_33,true,1) {}
00096 virtual bool solution(const SetAssignment& x) const {
00097 CountableSetRanges xr0(x.lub, x[0]);
00098 return xr0() && xr0.min()==x.intval();
00099 }
00101 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00102 Gecode::min(home, x[0], y[0]);
00103 }
00105 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00106 Reify r) {
00107 Gecode::min(home, x[0], y[0], r);
00108 }
00109 };
00110 Min _min("Int::Min");
00111
00113 class NotMin : public SetTest {
00114 public:
00116 NotMin(const char* t)
00117 : SetTest(t,1,ds_33,false,1) {}
00119 virtual bool solution(const SetAssignment& x) const {
00120 CountableSetRanges xr0(x.lub, x[0]);
00121 return !(xr0() && xr0.min()==x.intval());
00122 }
00124 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00125 Gecode::notMin(home, x[0], y[0]);
00126 }
00127 };
00128 NotMin _notmin("Int::NotMin");
00129
00131 class Max : public SetTest {
00132 public:
00134 Max(const char* t)
00135 : SetTest(t,1,ds_33,true,1) {}
00137 virtual bool solution(const SetAssignment& x) const {
00138 CountableSetRanges xr0(x.lub, x[0]);
00139 IntSet x0(xr0);
00140 return x0.ranges() > 0 && x0.max()==x.intval();
00141 }
00143 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00144 Gecode::max(home, x[0], y[0]);
00145 }
00147 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00148 Reify r) {
00149 Gecode::max(home, x[0], y[0], r);
00150 }
00151 };
00152 Max _max("Int::Max");
00153
00155 class NotMax : public SetTest {
00156 public:
00158 NotMax(const char* t)
00159 : SetTest(t,1,ds_33,false,1) {}
00161 virtual bool solution(const SetAssignment& x) const {
00162 CountableSetRanges xr0(x.lub, x[0]);
00163 IntSet x0(xr0);
00164 return !(x0.ranges() > 0 && x0.max()==x.intval());
00165 }
00167 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00168 Gecode::notMax(home, x[0], y[0]);
00169 }
00170 };
00171 NotMax _notmax("Int::NotMax");
00172
00174 class Elem : public SetTest {
00175 public:
00177 Elem(const char* t)
00178 : SetTest(t,1,ds_33,true,1) {}
00180 virtual bool solution(const SetAssignment& x) const {
00181 for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
00182 if (xr.val()==x.intval())
00183 return true;
00184 return false;
00185 }
00187 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00188 Gecode::rel(home, x[0], SRT_SUP, y[0]);
00189 }
00191 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00192 Reify r) {
00193 Gecode::rel(home, x[0], SRT_SUP, y[0], r);
00194 }
00195 };
00196 Elem _elem("Int::Elem");
00197
00199 class NoElem : public SetTest {
00200 public:
00202 NoElem(const char* t)
00203 : SetTest(t,1,ds_33,false,1) {}
00205 virtual bool solution(const SetAssignment& x) const {
00206 for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
00207 if (xr.val()==x.intval())
00208 return false;
00209 return true;
00210 }
00212 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00213 Gecode::rel(home, x[0], SRT_DISJ, y[0]);
00214 }
00215 };
00216 NoElem _noelem("Int::NoElem");
00217
00219 class Rel : public SetTest {
00220 private:
00222 Gecode::SetRelType srt;
00224 bool swapped;
00225 public:
00227 Rel(Gecode::SetRelType srt0, bool s)
00228 : SetTest("Int::Rel::"+str(srt0)+(s ? "::s" : ""),
00229 1,ds_33,true,1),
00230 srt(srt0), swapped(s) {}
00232 virtual bool solution(const SetAssignment& x) const {
00233 CountableSetRanges xr(x.lub, x[0]);
00234 IntSet is(x.intval(), x.intval());
00235 IntSetRanges dr(is);
00236 Gecode::SetRelType rsrt = srt;
00237 if (swapped) {
00238 switch (srt) {
00239 case SRT_SUB: rsrt = SRT_SUP; break;
00240 case SRT_SUP: rsrt = SRT_SUB; break;
00241 default: break;
00242 }
00243 }
00244 switch (rsrt) {
00245 case SRT_EQ: return Iter::Ranges::equal(xr, dr);
00246 case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
00247 case SRT_SUB: return Iter::Ranges::subset(xr, dr);
00248 case SRT_SUP: return Iter::Ranges::subset(dr, xr);
00249 case SRT_DISJ:
00250 {
00251 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00252 inter(xr, dr);
00253 return !inter();
00254 }
00255 case SRT_CMPL:
00256 {
00257 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00258 return Iter::Ranges::equal(xr,drc);
00259 }
00260 }
00261 GECODE_NEVER;
00262 return false;
00263 }
00265 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00266 if (!swapped)
00267 Gecode::rel(home, x[0], srt, y[0]);
00268 else
00269 Gecode::rel(home, y[0], srt, x[0]);
00270 }
00272 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00273 Reify r) {
00274 if (!swapped)
00275 Gecode::rel(home, x[0], srt, y[0], r);
00276 else
00277 Gecode::rel(home, y[0], srt, x[0], r);
00278 }
00279 };
00280 Rel _rel_eq(Gecode::SRT_EQ,false);
00281 Rel _rel_nq(Gecode::SRT_NQ,false);
00282 Rel _rel_sub(Gecode::SRT_SUB,false);
00283 Rel _rel_sup(Gecode::SRT_SUP,false);
00284 Rel _rel_disj(Gecode::SRT_DISJ,false);
00285 Rel _rel_cmpl(Gecode::SRT_CMPL,false);
00286 Rel _rel_eqs(Gecode::SRT_EQ,true);
00287 Rel _rel_nqs(Gecode::SRT_NQ,true);
00288 Rel _rel_subs(Gecode::SRT_SUB,true);
00289 Rel _rel_sups(Gecode::SRT_SUP,true);
00290 Rel _rel_disjs(Gecode::SRT_DISJ,true);
00291 Rel _rel_cmpls(Gecode::SRT_CMPL,true);
00292
00294 class IntRel : public SetTest {
00295 private:
00297 Gecode::IntRelType irt;
00299 bool swapped;
00300 public:
00302 IntRel(Gecode::IntRelType irt0, bool s)
00303 : SetTest("Int::IntRel::"+Test::Int::Test::str(irt0)+
00304 (s ? "::s" : ""),1,ds_33,true,1),
00305 irt(irt0), swapped(s) {
00306 testsubsumed = false;
00307 }
00309 virtual bool solution(const SetAssignment& x) const {
00310 CountableSetValues xr(x.lub, x[0]);
00311 if (!xr())
00312 return false;
00313 for (; xr(); ++xr)
00314 switch (irt) {
00315 case Gecode::IRT_EQ:
00316 if (xr.val() != x.intval()) return false;
00317 break;
00318 case Gecode::IRT_NQ:
00319 if (xr.val() == x.intval()) return false;
00320 break;
00321 case Gecode::IRT_GR:
00322 if (!swapped && xr.val() <= x.intval()) return false;
00323 if (swapped && xr.val() >= x.intval()) return false;
00324 break;
00325 case Gecode::IRT_GQ:
00326 if (!swapped && xr.val() < x.intval()) return false;
00327 if (swapped && xr.val() > x.intval()) return false;
00328 break;
00329 case Gecode::IRT_LE:
00330 if (!swapped && xr.val() >= x.intval()) return false;
00331 if (swapped && xr.val() <= x.intval()) return false;
00332 break;
00333 case Gecode::IRT_LQ:
00334 if (!swapped && xr.val() > x.intval()) return false;
00335 if (swapped && xr.val() < x.intval()) return false;
00336 break;
00337 default:
00338 GECODE_NEVER;
00339 return false;
00340 }
00341 return true;
00342 }
00344 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00345 if (!swapped)
00346 Gecode::rel(home, x[0], irt, y[0]);
00347 else
00348 Gecode::rel(home, y[0], irt, x[0]);
00349 }
00351 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00352 Reify r) {
00353 assert((x.size() == 1) && (y.size() == 1));
00354 if ((r.mode() != Gecode::RM_EQV) || (Base::rand(2) != 0)) {
00355 if (!swapped)
00356 Gecode::rel(home, x[0], irt, y[0], r);
00357 else
00358 Gecode::rel(home, y[0], irt, x[0], r);
00359 } else if (swapped) {
00360 switch (irt) {
00361 case Gecode::IRT_EQ:
00362 Gecode::rel(home, (y[0] == x[0]) == r.var()); break;
00363 case Gecode::IRT_NQ:
00364 Gecode::rel(home, (y[0] != x[0]) == r.var()); break;
00365 case Gecode::IRT_LE:
00366 Gecode::rel(home, (y[0] < x[0]) == r.var()); break;
00367 case Gecode::IRT_LQ:
00368 Gecode::rel(home, (y[0] <= x[0]) == r.var()); break;
00369 case Gecode::IRT_GR:
00370 Gecode::rel(home, (y[0] > x[0]) == r.var()); break;
00371 case Gecode::IRT_GQ:
00372 Gecode::rel(home, (y[0] >= x[0]) == r.var()); break;
00373 default: GECODE_NEVER;
00374 }
00375 } else {
00376 switch (irt) {
00377 case Gecode::IRT_EQ:
00378 Gecode::rel(home, (x[0] == y[0]) == r.var()); break;
00379 case Gecode::IRT_NQ:
00380 Gecode::rel(home, (x[0] != y[0]) == r.var()); break;
00381 case Gecode::IRT_LE:
00382 Gecode::rel(home, (x[0] < y[0]) == r.var()); break;
00383 case Gecode::IRT_LQ:
00384 Gecode::rel(home, (x[0] <= y[0]) == r.var()); break;
00385 case Gecode::IRT_GR:
00386 Gecode::rel(home, (x[0] > y[0]) == r.var()); break;
00387 case Gecode::IRT_GQ:
00388 Gecode::rel(home, (x[0] >= y[0]) == r.var()); break;
00389 default: GECODE_NEVER;
00390 }
00391 }
00392 }
00393 };
00394 IntRel _intrel_eq(Gecode::IRT_EQ,false);
00395 IntRel _intrel_nq(Gecode::IRT_NQ,false);
00396 IntRel _intrel_gr(Gecode::IRT_GR,false);
00397 IntRel _intrel_gq(Gecode::IRT_GQ,false);
00398 IntRel _intrel_le(Gecode::IRT_LE,false);
00399 IntRel _intrel_lq(Gecode::IRT_LQ,false);
00400 IntRel _intrel_eqs(Gecode::IRT_EQ,true);
00401 IntRel _intrel_nqs(Gecode::IRT_NQ,true);
00402 IntRel _intrel_grs(Gecode::IRT_GR,true);
00403 IntRel _intrel_gqs(Gecode::IRT_GQ,true);
00404 IntRel _intrel_les(Gecode::IRT_LE,true);
00405 IntRel _intrel_lqs(Gecode::IRT_LQ,true);
00406
00407
00408 template<class I>
00409 int weightI(const IntArgs& elements,
00410 const IntArgs& weights,
00411 I& iter) {
00412 int sum = 0;
00413 int i = 0;
00414 for (Iter::Ranges::ToValues<I> v(iter); v(); ++v) {
00415
00416 while (elements[i]<v.val()) i++;
00417 assert(elements[i] == v.val());
00418 sum += weights[i];
00419 }
00420 return sum;
00421 }
00422
00424 class Weights : public SetTest {
00425 public:
00426 IntArgs elements;
00427 IntArgs weights;
00428 int minWeight;
00429 int maxWeight;
00431 Weights(const char* t, IntArgs& el, IntArgs& w,
00432 int min = -10000, int max = 10000)
00433 : SetTest(t,1,ds_33,false,1),
00434 elements(el), weights(w), minWeight(min), maxWeight(max) {}
00436 virtual bool solution(const SetAssignment& x) const {
00437 CountableSetRanges x0(x.lub, x[0]);
00438 return x.intval()==weightI(elements,weights,x0) &&
00439 x.intval() >= minWeight && x.intval() <= maxWeight;
00440 }
00442 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00443 Gecode::rel(home, minWeight <= y[0]);
00444 Gecode::rel(home, maxWeight >= y[0]);
00445 Gecode::weights(home, elements, weights, x[0], y[0]);
00446 }
00447 };
00448
00449 const int el1v[] = {-3,-2,-1,0,1,2,3};
00450 IntArgs el1(7,el1v);
00451 const int w1v[] = {1,-2,1,1,1,6,1};
00452 IntArgs w1(7,w1v);
00453 Weights _weights1("Int::Weights::1", el1, w1);
00454
00455 const int w2v[] = {-1,-1,-1,10,-1,-1,-1};
00456 IntArgs w2(7,w2v);
00457 Weights _weights2("Int::Weights::2", el1, w2);
00458 Weights _weights3("Int::Weights::3", el1, w2, 3);
00459
00460 const int w4v[] = {1,1,0,0,0,0,0};
00461 IntArgs w4(7,w4v);
00462 Weights _weights4("Int::Weights::4", el1, w4);
00463
00464 }}}
00465
00466