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 <gecode/minimodel.hh>
00035
00036 #include "test/set.hh"
00037
00038 using namespace Gecode;
00039
00040 namespace Test { namespace Set {
00041
00043 namespace Dom {
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 const int d1cr[5][2] = {
00057 {Gecode::Set::Limits::min,-5},
00058 {-2,-2},{0,0},{2,2},
00059 {6,Gecode::Set::Limits::max}
00060 };
00061 static IntSet d1c(d1cr,5);
00062
00063 static IntSet ds_33(-3,3);
00064
00065 static const int d2r[2][2] = {
00066 {Gecode::Set::Limits::min,-4}, {4,Gecode::Set::Limits::max}
00067 };
00068 static IntSet ds_33c(d2r,2);
00069
00070 namespace {
00071 static int minSymDiff(const SetAssignment& x, int i, const IntSet& is) {
00072 typedef Iter::Ranges::Diff<CountableSetRanges,IntSetRanges> DiffA;
00073 CountableSetRanges xr00(x.lub, x[i]);
00074 IntSetRanges xr10(is);
00075 DiffA a(xr00,xr10);
00076 typedef Iter::Ranges::Diff<IntSetRanges,CountableSetRanges> DiffB;
00077 CountableSetRanges xr01(x.lub, x[i]);
00078 IntSetRanges xr11(is);
00079 DiffB b(xr11,xr01);
00080 Iter::Ranges::Union<DiffA,DiffB> u(a,b);
00081 return u() ? u.min() : Gecode::Set::Limits::max+1;
00082 }
00083 template<class I>
00084 static bool in(int i, I& c, bool eq=false) {
00085 if (eq && i==Gecode::Set::Limits::max+1)
00086 return true;
00087 Iter::Ranges::Singleton s(i,i);
00088 return Iter::Ranges::subset(s,c);
00089 }
00090 }
00091
00093 class DomRange : public SetTest {
00094 private:
00095 Gecode::SetRelType srt;
00096 IntSet is;
00097 public:
00099 DomRange(SetRelType srt0, int n) :
00100 SetTest("Dom::Range::"+str(srt0)+"::"+str(n),n,ds_33,(n == 1)),
00101 srt(srt0), is(srt == Gecode::SRT_CMPL ? ds_33c: ds_33) {}
00103 virtual bool solution(const SetAssignment& x) const {
00104 for (int i=x.size(); i--; ) {
00105 CountableSetRanges xr(x.lub, x[i]);
00106 IntSetRanges dr(is);
00107 switch (srt) {
00108 case SRT_EQ:
00109 if (!Iter::Ranges::equal(xr, dr))
00110 return false;
00111 break;
00112 case SRT_LQ:
00113 if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00114 return false;
00115 break;
00116 case SRT_LE:
00117 if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00118 return false;
00119 break;
00120 case SRT_GQ:
00121 if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00122 return false;
00123 break;
00124 case SRT_GR:
00125 if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00126 return false;
00127 break;
00128 case SRT_NQ:
00129 if (Iter::Ranges::equal(xr, dr))
00130 return false;
00131 break;
00132 case SRT_SUB:
00133 if (!Iter::Ranges::subset(xr, dr))
00134 return false;
00135 break;
00136 case SRT_SUP:
00137 if (!Iter::Ranges::subset(dr, xr))
00138 return false;
00139 break;
00140 case SRT_DISJ:
00141 {
00142 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00143 inter(xr, dr);
00144 if (inter())
00145 return false;
00146 }
00147 break;
00148 case SRT_CMPL:
00149 {
00150 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00151 if (!Iter::Ranges::equal(xr,drc))
00152 return false;
00153 }
00154 break;
00155 }
00156 }
00157 return true;
00158 }
00160 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00161 if (x.size() == 1)
00162 Gecode::dom(home, x[0], srt, is);
00163 else
00164 Gecode::dom(home, x, srt, is);
00165 }
00167 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00168 assert(x.size() == 1);
00169 if (Base::rand(2) != 0) {
00170 Gecode::dom(home, x[0], srt, is, r);
00171 } else {
00172 switch (r.mode()) {
00173 case Gecode::RM_EQV:
00174 Gecode::rel(home, Gecode::dom(x[0], srt, is) == r.var()); break;
00175 case Gecode::RM_IMP:
00176 Gecode::rel(home, Gecode::dom(x[0], srt, is) << r.var()); break;
00177 case Gecode::RM_PMI:
00178 Gecode::rel(home, Gecode::dom(x[0], srt, is) >> r.var()); break;
00179 default: GECODE_NEVER;
00180 }
00181 }
00182 }
00183 };
00184
00186 class DomIntRange : public SetTest {
00187 private:
00188 Gecode::SetRelType srt;
00189 public:
00191 DomIntRange(Gecode::SetRelType srt0, int n)
00192 : SetTest("Dom::IntRange::"+str(srt0)+"::"+str(n),1,ds_33,n==1),
00193 srt(srt0) {}
00195 virtual bool solution(const SetAssignment& x) const {
00196 for (int i=x.size(); i--; ) {
00197 CountableSetRanges xr(x.lub, x[i]);
00198 IntSet is(-3,-1);
00199 IntSetRanges dr(is);
00200 switch (srt) {
00201 case SRT_EQ:
00202 if (!Iter::Ranges::equal(xr, dr))
00203 return false;
00204 break;
00205 case SRT_LQ:
00206 if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00207 return false;
00208 break;
00209 case SRT_LE:
00210 if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00211 return false;
00212 break;
00213 case SRT_GQ:
00214 if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00215 return false;
00216 break;
00217 case SRT_GR:
00218 if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00219 return false;
00220 break;
00221 case SRT_NQ:
00222 if (!(!Iter::Ranges::equal(xr, dr)))
00223 return false;
00224 break;
00225 case SRT_SUB:
00226 if (!(Iter::Ranges::subset(xr, dr)))
00227 return false;
00228 break;
00229 case SRT_SUP:
00230 if (!(Iter::Ranges::subset(dr, xr)))
00231 return false;
00232 break;
00233 case SRT_DISJ:
00234 {
00235 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00236 inter(xr, dr);
00237 if (inter())
00238 return false;
00239 }
00240 break;
00241 case SRT_CMPL:
00242 {
00243 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00244 if (!Iter::Ranges::equal(xr,drc))
00245 return false;
00246 }
00247 break;
00248 }
00249 }
00250 return true;
00251 }
00253 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00254 if (x.size() == 1)
00255 Gecode::dom(home, x[0], srt, -3, -1);
00256 else
00257 Gecode::dom(home, x, srt, -3, -1);
00258 }
00260 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00261 assert(x.size() == 1);
00262 if (Base::rand(2) != 0) {
00263 Gecode::dom(home, x[0], srt, -3, -1, r);
00264 } else {
00265 switch (r.mode()) {
00266 case Gecode::RM_EQV:
00267 Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) == r.var()); break;
00268 case Gecode::RM_IMP:
00269 Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) << r.var()); break;
00270 case Gecode::RM_PMI:
00271 Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) >> r.var()); break;
00272 default: GECODE_NEVER;
00273 }
00274 }
00275 }
00276 };
00277
00279 class DomInt : public SetTest {
00280 private:
00281 Gecode::SetRelType srt;
00282 public:
00284 DomInt(Gecode::SetRelType srt0, int n) :
00285 SetTest("Dom::Int::"+str(srt0)+"::"+str(n),n,ds_33,n==1),
00286 srt(srt0) {}
00288 virtual bool solution(const SetAssignment& x) const {
00289 IntSet is(-3,-3);
00290 for (int i=x.size(); i--; ) {
00291 CountableSetRanges xr(x.lub, x[i]);
00292 IntSetRanges dr(is);
00293 switch (srt) {
00294 case SRT_EQ:
00295 if (!Iter::Ranges::equal(xr, dr))
00296 return false;
00297 break;
00298 case SRT_LQ:
00299 if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00300 return false;
00301 break;
00302 case SRT_LE:
00303 if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00304 return false;
00305 break;
00306 case SRT_GQ:
00307 if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00308 return false;
00309 break;
00310 case SRT_GR:
00311 if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00312 return false;
00313 break;
00314 case SRT_NQ:
00315 if (Iter::Ranges::equal(xr, dr))
00316 return false;
00317 break;
00318 case SRT_SUB:
00319 if (!(Iter::Ranges::subset(xr, dr)))
00320 return false;
00321 break;
00322 case SRT_SUP:
00323 if (!(Iter::Ranges::subset(dr, xr)))
00324 return false;
00325 break;
00326 case SRT_DISJ:
00327 {
00328 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00329 inter(xr, dr);
00330
00331 if (inter())
00332 return false;
00333 break;
00334 }
00335 case SRT_CMPL:
00336 {
00337 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00338
00339 if (!Iter::Ranges::equal(xr,drc))
00340 return false;
00341 break;
00342 }
00343 }
00344 }
00345 return true;
00346 }
00348 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00349 if (x.size() == 1)
00350 Gecode::dom(home, x[0], srt, -3);
00351 else
00352 Gecode::dom(home, x, srt, -3);
00353 }
00355 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00356 assert(x.size() == 1);
00357 if (Base::rand(2) != 0) {
00358 Gecode::dom(home, x[0], srt, -3, r);
00359 } else {
00360 switch (r.mode()) {
00361 case Gecode::RM_EQV:
00362 Gecode::rel(home, Gecode::dom(x[0], srt, -3) == r.var()); break;
00363 case Gecode::RM_IMP:
00364 Gecode::rel(home, Gecode::dom(x[0], srt, -3) << r.var()); break;
00365 case Gecode::RM_PMI:
00366 Gecode::rel(home, Gecode::dom(x[0], srt, -3) >> r.var()); break;
00367 default: GECODE_NEVER;
00368 }
00369 }
00370 }
00371 };
00372
00374 class DomDom : public SetTest {
00375 private:
00376 Gecode::SetRelType srt;
00377 Gecode::IntSet is;
00378 public:
00380 DomDom(Gecode::SetRelType srt0, int n) :
00381 SetTest("Dom::Dom::"+str(srt0)+"::"+str(n),n,d1,(n == 1)),
00382 srt(srt0), is(srt == Gecode::SRT_CMPL ? d1c: d1) {}
00384 virtual bool solution(const SetAssignment& x) const {
00385 for (int i=x.size(); i--; ) {
00386 CountableSetRanges xr(x.lub, x[i]);
00387 IntSetRanges dr(is);
00388 switch (srt) {
00389 case SRT_EQ:
00390 if (!Iter::Ranges::equal(xr, dr))
00391 return false;
00392 break;
00393 case SRT_LQ:
00394 if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00395 return false;
00396 break;
00397 case SRT_LE:
00398 if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00399 return false;
00400 break;
00401 case SRT_GQ:
00402 if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00403 return false;
00404 break;
00405 case SRT_GR:
00406 if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00407 return false;
00408 break;
00409 case SRT_NQ:
00410 if (Iter::Ranges::equal(xr, dr))
00411 return false;
00412 break;
00413 case SRT_SUB:
00414 if (!Iter::Ranges::subset(xr, dr))
00415 return false;
00416 break;
00417 case SRT_SUP:
00418 if (!Iter::Ranges::subset(dr, xr))
00419 return false;
00420 break;
00421 case SRT_DISJ:
00422 {
00423 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00424 inter(xr, dr);
00425 if (inter())
00426 return false;
00427 }
00428 break;
00429 case SRT_CMPL:
00430 {
00431 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00432 if (!Iter::Ranges::equal(xr,drc))
00433 return false;
00434 }
00435 break;
00436 }
00437 }
00438 return true;
00439 }
00441 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00442 if (x.size() == 1)
00443 Gecode::dom(home, x[0], srt, is);
00444 else
00445 Gecode::dom(home, x, srt, is);
00446 }
00448 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00449 assert(x.size() == 1);
00450 Gecode::dom(home, x[0], srt, is, r);
00451 }
00452 };
00453
00455 class CardRange : public SetTest {
00456 public:
00458 CardRange(int n)
00459 : SetTest("Dom::CardRange::"+str(n),n,d1,false) {}
00461 virtual bool solution(const SetAssignment& x) const {
00462 for (int i=x.size(); i--; ) {
00463 CountableSetRanges xr(x.lub, x[i]);
00464 unsigned int card = Iter::Ranges::size(xr);
00465 if ((card < 2) || (card > 3))
00466 return false;
00467 }
00468 return true;
00469 }
00471 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00472 if (x.size() == 1)
00473 Gecode::cardinality(home, x[0], 2, 3);
00474 else
00475 Gecode::cardinality(home, x, 2, 3);
00476 }
00477 };
00478
00479 DomRange _domrange_eq1(SRT_EQ,1);
00480 DomRange _domrange_lq1(SRT_LQ,1);
00481 DomRange _domrange_le1(SRT_LE,1);
00482 DomRange _domrange_gq1(SRT_GQ,1);
00483 DomRange _domrange_gr1(SRT_GR,1);
00484 DomRange _domrange_nq1(SRT_NQ,1);
00485 DomRange _domrange_sub1(SRT_SUB,1);
00486 DomRange _domrange_sup1(SRT_SUP,1);
00487 DomRange _domrange_disj1(SRT_DISJ,1);
00488 DomRange _domrange_cmpl1(SRT_CMPL,1);
00489 DomRange _domrange_eq2(SRT_EQ,2);
00490 DomRange _domrange_lq2(SRT_LQ,2);
00491 DomRange _domrange_le2(SRT_LE,2);
00492 DomRange _domrange_gq2(SRT_GQ,2);
00493 DomRange _domrange_gr2(SRT_GR,2);
00494 DomRange _domrange_nq2(SRT_NQ,2);
00495 DomRange _domrange_sub2(SRT_SUB,2);
00496 DomRange _domrange_sup2(SRT_SUP,2);
00497 DomRange _domrange_disj2(SRT_DISJ,2);
00498 DomRange _domrange_cmpl2(SRT_CMPL,2);
00499
00500 DomIntRange _domintrange_eq1(SRT_EQ,1);
00501 DomIntRange _domintrange_lq1(SRT_LQ,1);
00502 DomIntRange _domintrange_le1(SRT_LE,1);
00503 DomIntRange _domintrange_gq1(SRT_GQ,1);
00504 DomIntRange _domintrange_gr1(SRT_GR,1);
00505 DomIntRange _domintrange_nq1(SRT_NQ,1);
00506 DomIntRange _domintrange_sub1(SRT_SUB,1);
00507 DomIntRange _domintrange_sup1(SRT_SUP,1);
00508 DomIntRange _domintrange_disj1(SRT_DISJ,1);
00509 DomIntRange _domintrange_cmpl1(SRT_CMPL,1);
00510 DomIntRange _domintrange_eq2(SRT_EQ,2);
00511 DomIntRange _domintrange_lq2(SRT_LQ,2);
00512 DomIntRange _domintrange_le2(SRT_LE,2);
00513 DomIntRange _domintrange_gq2(SRT_GQ,2);
00514 DomIntRange _domintrange_gr2(SRT_GR,2);
00515 DomIntRange _domintrange_nq2(SRT_NQ,2);
00516 DomIntRange _domintrange_sub2(SRT_SUB,2);
00517 DomIntRange _domintrange_sup2(SRT_SUP,2);
00518 DomIntRange _domintrange_disj2(SRT_DISJ,2);
00519 DomIntRange _domintrange_cmpl2(SRT_CMPL,2);
00520
00521 DomInt _domint_eq1(SRT_EQ,1);
00522 DomInt _domint_lq1(SRT_LQ,1);
00523 DomInt _domint_le1(SRT_LE,1);
00524 DomInt _domint_gq1(SRT_GQ,1);
00525 DomInt _domint_gr1(SRT_GR,1);
00526 DomInt _domint_nq1(SRT_NQ,1);
00527 DomInt _domint_sub1(SRT_SUB,1);
00528 DomInt _domint_sup1(SRT_SUP,1);
00529 DomInt _domint_disj1(SRT_DISJ,1);
00530 DomInt _domint_cmpl1(SRT_CMPL,1);
00531 DomInt _domint_eq2(SRT_EQ,2);
00532 DomInt _domint_lq2(SRT_LQ,2);
00533 DomInt _domint_le2(SRT_LE,2);
00534 DomInt _domint_gq2(SRT_GQ,2);
00535 DomInt _domint_gr2(SRT_GR,2);
00536 DomInt _domint_nq2(SRT_NQ,2);
00537 DomInt _domint_sub2(SRT_SUB,2);
00538 DomInt _domint_sup2(SRT_SUP,2);
00539 DomInt _domint_disj2(SRT_DISJ,2);
00540 DomInt _domint_cmpl2(SRT_CMPL,2);
00541
00542 DomDom _domdom_eq1(SRT_EQ,1);
00543 DomDom _domdom_lq1(SRT_LQ,1);
00544 DomDom _domdom_le1(SRT_LE,1);
00545 DomDom _domdom_gq1(SRT_GQ,1);
00546 DomDom _domdom_gr1(SRT_GR,1);
00547 DomDom _domdom_nq1(SRT_NQ,1);
00548 DomDom _domdom_sub1(SRT_SUB,1);
00549 DomDom _domdom_sup1(SRT_SUP,1);
00550 DomDom _domdom_disj1(SRT_DISJ,1);
00551 DomDom _domdom_cmpl1(SRT_CMPL,1);
00552 DomDom _domdom_eq2(SRT_EQ,2);
00553 DomDom _domdom_lq2(SRT_LQ,2);
00554 DomDom _domdom_le2(SRT_LE,2);
00555 DomDom _domdom_gq2(SRT_GQ,2);
00556 DomDom _domdom_gr2(SRT_GR,2);
00557 DomDom _domdom_nq2(SRT_NQ,2);
00558 DomDom _domdom_sub2(SRT_SUB,2);
00559 DomDom _domdom_sup2(SRT_SUP,2);
00560 DomDom _domdom_disj2(SRT_DISJ,2);
00561 DomDom _domdom_cmpl2(SRT_CMPL,2);
00562
00563 CardRange _cr1(1);
00564 CardRange _cr2(2);
00565
00566 }}}
00567
00568