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 default: GECODE_NEVER;
00156 }
00157 }
00158 return true;
00159 }
00161 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00162 if (x.size() == 1)
00163 Gecode::dom(home, x[0], srt, is);
00164 else
00165 Gecode::dom(home, x, srt, is);
00166 }
00168 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00169 assert(x.size() == 1);
00170 if (Base::rand(2) != 0) {
00171 Gecode::dom(home, x[0], srt, is, r);
00172 } else {
00173 switch (r.mode()) {
00174 case Gecode::RM_EQV:
00175 Gecode::rel(home, Gecode::dom(x[0], srt, is) == r.var()); break;
00176 case Gecode::RM_IMP:
00177 Gecode::rel(home, Gecode::dom(x[0], srt, is) << r.var()); break;
00178 case Gecode::RM_PMI:
00179 Gecode::rel(home, Gecode::dom(x[0], srt, is) >> r.var()); break;
00180 default: GECODE_NEVER;
00181 }
00182 }
00183 }
00184 };
00185
00187 class DomIntRange : public SetTest {
00188 private:
00189 Gecode::SetRelType srt;
00190 public:
00192 DomIntRange(Gecode::SetRelType srt0, int n)
00193 : SetTest("Dom::IntRange::"+str(srt0)+"::"+str(n),1,ds_33,n==1),
00194 srt(srt0) {}
00196 virtual bool solution(const SetAssignment& x) const {
00197 for (int i=x.size(); i--; ) {
00198 CountableSetRanges xr(x.lub, x[i]);
00199 IntSet is(-3,-1);
00200 IntSetRanges dr(is);
00201 switch (srt) {
00202 case SRT_EQ:
00203 if (!Iter::Ranges::equal(xr, dr))
00204 return false;
00205 break;
00206 case SRT_LQ:
00207 if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00208 return false;
00209 break;
00210 case SRT_LE:
00211 if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00212 return false;
00213 break;
00214 case SRT_GQ:
00215 if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00216 return false;
00217 break;
00218 case SRT_GR:
00219 if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00220 return false;
00221 break;
00222 case SRT_NQ:
00223 if (!(!Iter::Ranges::equal(xr, dr)))
00224 return false;
00225 break;
00226 case SRT_SUB:
00227 if (!(Iter::Ranges::subset(xr, dr)))
00228 return false;
00229 break;
00230 case SRT_SUP:
00231 if (!(Iter::Ranges::subset(dr, xr)))
00232 return false;
00233 break;
00234 case SRT_DISJ:
00235 {
00236 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00237 inter(xr, dr);
00238 if (inter())
00239 return false;
00240 }
00241 break;
00242 case SRT_CMPL:
00243 {
00244 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00245 if (!Iter::Ranges::equal(xr,drc))
00246 return false;
00247 }
00248 break;
00249 default: GECODE_NEVER;
00250 }
00251 }
00252 return true;
00253 }
00255 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00256 if (x.size() == 1)
00257 Gecode::dom(home, x[0], srt, -3, -1);
00258 else
00259 Gecode::dom(home, x, srt, -3, -1);
00260 }
00262 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00263 assert(x.size() == 1);
00264 if (Base::rand(2) != 0) {
00265 Gecode::dom(home, x[0], srt, -3, -1, r);
00266 } else {
00267 switch (r.mode()) {
00268 case Gecode::RM_EQV:
00269 Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) == r.var()); break;
00270 case Gecode::RM_IMP:
00271 Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) << r.var()); break;
00272 case Gecode::RM_PMI:
00273 Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) >> r.var()); break;
00274 default: GECODE_NEVER;
00275 }
00276 }
00277 }
00278 };
00279
00281 class DomInt : public SetTest {
00282 private:
00283 Gecode::SetRelType srt;
00284 public:
00286 DomInt(Gecode::SetRelType srt0, int n) :
00287 SetTest("Dom::Int::"+str(srt0)+"::"+str(n),n,ds_33,n==1),
00288 srt(srt0) {}
00290 virtual bool solution(const SetAssignment& x) const {
00291 IntSet is(-3,-3);
00292 for (int i=x.size(); i--; ) {
00293 CountableSetRanges xr(x.lub, x[i]);
00294 IntSetRanges dr(is);
00295 switch (srt) {
00296 case SRT_EQ:
00297 if (!Iter::Ranges::equal(xr, dr))
00298 return false;
00299 break;
00300 case SRT_LQ:
00301 if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00302 return false;
00303 break;
00304 case SRT_LE:
00305 if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00306 return false;
00307 break;
00308 case SRT_GQ:
00309 if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00310 return false;
00311 break;
00312 case SRT_GR:
00313 if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00314 return false;
00315 break;
00316 case SRT_NQ:
00317 if (Iter::Ranges::equal(xr, dr))
00318 return false;
00319 break;
00320 case SRT_SUB:
00321 if (!(Iter::Ranges::subset(xr, dr)))
00322 return false;
00323 break;
00324 case SRT_SUP:
00325 if (!(Iter::Ranges::subset(dr, xr)))
00326 return false;
00327 break;
00328 case SRT_DISJ:
00329 {
00330 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00331 inter(xr, dr);
00332
00333 if (inter())
00334 return false;
00335 break;
00336 }
00337 case SRT_CMPL:
00338 {
00339 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00340
00341 if (!Iter::Ranges::equal(xr,drc))
00342 return false;
00343 break;
00344 }
00345 default: GECODE_NEVER;
00346 }
00347 }
00348 return true;
00349 }
00351 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00352 if (x.size() == 1)
00353 Gecode::dom(home, x[0], srt, -3);
00354 else
00355 Gecode::dom(home, x, srt, -3);
00356 }
00358 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00359 assert(x.size() == 1);
00360 if (Base::rand(2) != 0) {
00361 Gecode::dom(home, x[0], srt, -3, r);
00362 } else {
00363 switch (r.mode()) {
00364 case Gecode::RM_EQV:
00365 Gecode::rel(home, Gecode::dom(x[0], srt, -3) == r.var()); break;
00366 case Gecode::RM_IMP:
00367 Gecode::rel(home, Gecode::dom(x[0], srt, -3) << r.var()); break;
00368 case Gecode::RM_PMI:
00369 Gecode::rel(home, Gecode::dom(x[0], srt, -3) >> r.var()); break;
00370 default: GECODE_NEVER;
00371 }
00372 }
00373 }
00374 };
00375
00377 class DomDom : public SetTest {
00378 private:
00379 Gecode::SetRelType srt;
00380 Gecode::IntSet is;
00381 public:
00383 DomDom(Gecode::SetRelType srt0, int n) :
00384 SetTest("Dom::Dom::"+str(srt0)+"::"+str(n),n,d1,(n == 1)),
00385 srt(srt0), is(srt == Gecode::SRT_CMPL ? d1c: d1) {}
00387 virtual bool solution(const SetAssignment& x) const {
00388 for (int i=x.size(); i--; ) {
00389 CountableSetRanges xr(x.lub, x[i]);
00390 IntSetRanges dr(is);
00391 switch (srt) {
00392 case SRT_EQ:
00393 if (!Iter::Ranges::equal(xr, dr))
00394 return false;
00395 break;
00396 case SRT_LQ:
00397 if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00398 return false;
00399 break;
00400 case SRT_LE:
00401 if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00402 return false;
00403 break;
00404 case SRT_GQ:
00405 if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00406 return false;
00407 break;
00408 case SRT_GR:
00409 if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00410 return false;
00411 break;
00412 case SRT_NQ:
00413 if (Iter::Ranges::equal(xr, dr))
00414 return false;
00415 break;
00416 case SRT_SUB:
00417 if (!Iter::Ranges::subset(xr, dr))
00418 return false;
00419 break;
00420 case SRT_SUP:
00421 if (!Iter::Ranges::subset(dr, xr))
00422 return false;
00423 break;
00424 case SRT_DISJ:
00425 {
00426 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00427 inter(xr, dr);
00428 if (inter())
00429 return false;
00430 }
00431 break;
00432 case SRT_CMPL:
00433 {
00434 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00435 if (!Iter::Ranges::equal(xr,drc))
00436 return false;
00437 }
00438 break;
00439 default: GECODE_NEVER;
00440 }
00441 }
00442 return true;
00443 }
00445 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00446 if (x.size() == 1)
00447 Gecode::dom(home, x[0], srt, is);
00448 else
00449 Gecode::dom(home, x, srt, is);
00450 }
00452 virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00453 assert(x.size() == 1);
00454 Gecode::dom(home, x[0], srt, is, r);
00455 }
00456 };
00457
00459 class CardRange : public SetTest {
00460 public:
00462 CardRange(int n)
00463 : SetTest("Dom::CardRange::"+str(n),n,d1,false) {}
00465 virtual bool solution(const SetAssignment& x) const {
00466 for (int i=x.size(); i--; ) {
00467 CountableSetRanges xr(x.lub, x[i]);
00468 unsigned int card = Iter::Ranges::size(xr);
00469 if ((card < 2) || (card > 3))
00470 return false;
00471 }
00472 return true;
00473 }
00475 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00476 if (x.size() == 1)
00477 Gecode::cardinality(home, x[0], 2, 3);
00478 else
00479 Gecode::cardinality(home, x, 2, 3);
00480 }
00481 };
00482
00483 DomRange _domrange_eq1(SRT_EQ,1);
00484 DomRange _domrange_lq1(SRT_LQ,1);
00485 DomRange _domrange_le1(SRT_LE,1);
00486 DomRange _domrange_gq1(SRT_GQ,1);
00487 DomRange _domrange_gr1(SRT_GR,1);
00488 DomRange _domrange_nq1(SRT_NQ,1);
00489 DomRange _domrange_sub1(SRT_SUB,1);
00490 DomRange _domrange_sup1(SRT_SUP,1);
00491 DomRange _domrange_disj1(SRT_DISJ,1);
00492 DomRange _domrange_cmpl1(SRT_CMPL,1);
00493 DomRange _domrange_eq2(SRT_EQ,2);
00494 DomRange _domrange_lq2(SRT_LQ,2);
00495 DomRange _domrange_le2(SRT_LE,2);
00496 DomRange _domrange_gq2(SRT_GQ,2);
00497 DomRange _domrange_gr2(SRT_GR,2);
00498 DomRange _domrange_nq2(SRT_NQ,2);
00499 DomRange _domrange_sub2(SRT_SUB,2);
00500 DomRange _domrange_sup2(SRT_SUP,2);
00501 DomRange _domrange_disj2(SRT_DISJ,2);
00502 DomRange _domrange_cmpl2(SRT_CMPL,2);
00503
00504 DomIntRange _domintrange_eq1(SRT_EQ,1);
00505 DomIntRange _domintrange_lq1(SRT_LQ,1);
00506 DomIntRange _domintrange_le1(SRT_LE,1);
00507 DomIntRange _domintrange_gq1(SRT_GQ,1);
00508 DomIntRange _domintrange_gr1(SRT_GR,1);
00509 DomIntRange _domintrange_nq1(SRT_NQ,1);
00510 DomIntRange _domintrange_sub1(SRT_SUB,1);
00511 DomIntRange _domintrange_sup1(SRT_SUP,1);
00512 DomIntRange _domintrange_disj1(SRT_DISJ,1);
00513 DomIntRange _domintrange_cmpl1(SRT_CMPL,1);
00514 DomIntRange _domintrange_eq2(SRT_EQ,2);
00515 DomIntRange _domintrange_lq2(SRT_LQ,2);
00516 DomIntRange _domintrange_le2(SRT_LE,2);
00517 DomIntRange _domintrange_gq2(SRT_GQ,2);
00518 DomIntRange _domintrange_gr2(SRT_GR,2);
00519 DomIntRange _domintrange_nq2(SRT_NQ,2);
00520 DomIntRange _domintrange_sub2(SRT_SUB,2);
00521 DomIntRange _domintrange_sup2(SRT_SUP,2);
00522 DomIntRange _domintrange_disj2(SRT_DISJ,2);
00523 DomIntRange _domintrange_cmpl2(SRT_CMPL,2);
00524
00525 DomInt _domint_eq1(SRT_EQ,1);
00526 DomInt _domint_lq1(SRT_LQ,1);
00527 DomInt _domint_le1(SRT_LE,1);
00528 DomInt _domint_gq1(SRT_GQ,1);
00529 DomInt _domint_gr1(SRT_GR,1);
00530 DomInt _domint_nq1(SRT_NQ,1);
00531 DomInt _domint_sub1(SRT_SUB,1);
00532 DomInt _domint_sup1(SRT_SUP,1);
00533 DomInt _domint_disj1(SRT_DISJ,1);
00534 DomInt _domint_cmpl1(SRT_CMPL,1);
00535 DomInt _domint_eq2(SRT_EQ,2);
00536 DomInt _domint_lq2(SRT_LQ,2);
00537 DomInt _domint_le2(SRT_LE,2);
00538 DomInt _domint_gq2(SRT_GQ,2);
00539 DomInt _domint_gr2(SRT_GR,2);
00540 DomInt _domint_nq2(SRT_NQ,2);
00541 DomInt _domint_sub2(SRT_SUB,2);
00542 DomInt _domint_sup2(SRT_SUP,2);
00543 DomInt _domint_disj2(SRT_DISJ,2);
00544 DomInt _domint_cmpl2(SRT_CMPL,2);
00545
00546 DomDom _domdom_eq1(SRT_EQ,1);
00547 DomDom _domdom_lq1(SRT_LQ,1);
00548 DomDom _domdom_le1(SRT_LE,1);
00549 DomDom _domdom_gq1(SRT_GQ,1);
00550 DomDom _domdom_gr1(SRT_GR,1);
00551 DomDom _domdom_nq1(SRT_NQ,1);
00552 DomDom _domdom_sub1(SRT_SUB,1);
00553 DomDom _domdom_sup1(SRT_SUP,1);
00554 DomDom _domdom_disj1(SRT_DISJ,1);
00555 DomDom _domdom_cmpl1(SRT_CMPL,1);
00556 DomDom _domdom_eq2(SRT_EQ,2);
00557 DomDom _domdom_lq2(SRT_LQ,2);
00558 DomDom _domdom_le2(SRT_LE,2);
00559 DomDom _domdom_gq2(SRT_GQ,2);
00560 DomDom _domdom_gr2(SRT_GR,2);
00561 DomDom _domdom_nq2(SRT_NQ,2);
00562 DomDom _domdom_sub2(SRT_SUB,2);
00563 DomDom _domdom_sup2(SRT_SUP,2);
00564 DomDom _domdom_disj2(SRT_DISJ,2);
00565 DomDom _domdom_cmpl2(SRT_CMPL,2);
00566
00567 CardRange _cr1(1);
00568 CardRange _cr2(2);
00569
00570 }}}
00571
00572