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
00035
00036
00037
00038 #include "test/set.hh"
00039
00040 #include <algorithm>
00041
00042 namespace Test { namespace Set {
00043
00044 CountableSet::CountableSet(const Gecode::IntSet& d0) : d(d0), cur(0) {
00045 Gecode::IntSetRanges isr(d);
00046 lubmax =
00047 static_cast<unsigned int>(pow(static_cast<double>(2.0),
00048 static_cast<int>(Gecode::Iter::Ranges::size(isr))));
00049 }
00050
00051 void CountableSet::operator++(void) {
00052 cur++;
00053 }
00054
00055 void CountableSet::init(const Gecode::IntSet& d0) {
00056 d = d0;
00057 cur = 0;
00058 Gecode::IntSetRanges isr(d);
00059 lubmax =
00060 static_cast<unsigned int>(pow(static_cast<double>(2.0),
00061 static_cast<int>(Gecode::Iter::Ranges::size(isr))));
00062 }
00063
00064 int CountableSet::val(void) const {
00065 return cur;
00066 }
00067
00068 SetAssignment::SetAssignment(int n0, const Gecode::IntSet& d0, int _withInt)
00069 : n(n0), dsv(new CountableSet[n]), ir(_withInt, d0), done(false), lub(d0),
00070 withInt(_withInt) {
00071 for (int i=n; i--; )
00072 dsv[i].init(lub);
00073 }
00074
00075 void
00076 SetAssignment::operator++(void) {
00077 int i = n-1;
00078 while (true) {
00079 ++dsv[i];
00080 if (dsv[i]())
00081 return;
00082 dsv[i].init(lub);
00083 --i;
00084 if (i<0) {
00085 if (withInt==0) {
00086 done = true;
00087 return;
00088 }
00089 ++ir;
00090 if (ir()) {
00091 i = n-1;
00092 for (int j=n; j--; )
00093 dsv[j].init(lub);
00094 } else {
00095 done = true;
00096 return;
00097 }
00098 }
00099 }
00100 }
00101
00102 }}
00103
00104 std::ostream&
00105 operator<<(std::ostream& os, const Test::Set::SetAssignment& a) {
00106 int n = a.size();
00107 os << "{";
00108 for (int i=0; i<n; i++) {
00109 Test::Set::CountableSetRanges csv(a.lub, a[i]);
00110 Gecode::IntSet icsv(csv);
00111 os << icsv << ((i!=n-1) ? "," : "}");
00112 }
00113 if (a.withInt > 0)
00114 os << a.ints();
00115 return os;
00116 }
00117
00118 namespace Test { namespace Set {
00119
00120 SetTestSpace::SetTestSpace(int n, Gecode::IntSet& d0, int i,
00121 SetTest* t, bool log)
00122 : d(d0), y(*this, i, d),
00123 withInt(i), r(Gecode::BoolVar(*this, 0, 1),Gecode::RM_EQV),
00124 reified(false), test(t) {
00125 using namespace Gecode;
00126 IntSet u(Gecode::Set::Limits::min,Gecode::Set::Limits::max);
00127 x = SetVarArray(*this, n, Gecode::IntSet::empty, u);
00128 SetVarArgs _x(*this, n, Gecode::IntSet::empty, d);
00129 if (x.size() == 1)
00130 dom(*this,x[0],_x[0]);
00131 else
00132 dom(*this,x,_x);
00133 if (opt.log && log) {
00134 olog << ind(2) << "Initial: x[]=" << x;
00135 olog << " y[]=" << y;
00136 olog << std::endl;
00137 }
00138 }
00139
00140 SetTestSpace::SetTestSpace(int n, Gecode::IntSet& d0, int i,
00141 SetTest* t, Gecode::ReifyMode rm, bool log)
00142 : d(d0), x(*this, n, Gecode::IntSet::empty, d), y(*this, i, d),
00143 withInt(i), r(Gecode::BoolVar(*this, 0, 1),rm),
00144 reified(true), test(t) {
00145 if (opt.log && log) {
00146 olog << ind(2) << "Initial: x[]=" << x;
00147 olog << " y[]=" << y;
00148 olog << " b=" << r.var();
00149 olog << std::endl;
00150 }
00151 }
00152
00153 SetTestSpace::SetTestSpace(SetTestSpace& s)
00154 : Gecode::Space(s), d(s.d), withInt(s.withInt),
00155 reified(s.reified), test(s.test) {
00156 x.update(*this, s.x);
00157 y.update(*this, s.y);
00158 Gecode::BoolVar b;
00159 Gecode::BoolVar sr(s.r.var());
00160 b.update(*this, sr);
00161 r.var(b); r.mode(s.r.mode());
00162 }
00163
00164 Gecode::Space*
00165 SetTestSpace::copy(void) {
00166 return new SetTestSpace(*this);
00167 }
00168
00169 void
00170 SetTestSpace::post(void) {
00171 if (reified){
00172 test->post(*this,x,y,r);
00173 if (opt.log)
00174 olog << ind(3) << "Posting reified propagator" << std::endl;
00175 } else {
00176 test->post(*this,x,y);
00177 if (opt.log)
00178 olog << ind(3) << "Posting propagator" << std::endl;
00179 }
00180 }
00181
00182 bool
00183 SetTestSpace::failed(void) {
00184 if (opt.log) {
00185 olog << ind(3) << "Fixpoint: x[]=" << x
00186 << " y[]=" << y << std::endl;
00187 bool f=(status() == Gecode::SS_FAILED);
00188 olog << ind(3) << " --> x[]=" << x
00189 << " y[]=" << y << std::endl;
00190 return f;
00191 } else {
00192 return status() == Gecode::SS_FAILED;
00193 }
00194 }
00195
00196 bool
00197 SetTestSpace::subsumed(bool b) {
00198 return b ? (propagators() == 0) : true;
00199 }
00200
00201 void
00202 SetTestSpace::rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is) {
00203 if (opt.log) {
00204 olog << ind(4) << "x[" << i << "] ";
00205 switch (srt) {
00206 case Gecode::SRT_EQ: olog << "="; break;
00207 case Gecode::SRT_LQ: olog << "<="; break;
00208 case Gecode::SRT_LE: olog << "<"; break;
00209 case Gecode::SRT_GQ: olog << ">="; break;
00210 case Gecode::SRT_GR: olog << ">"; break;
00211 case Gecode::SRT_NQ: olog << "!="; break;
00212 case Gecode::SRT_SUB: olog << "sub"; break;
00213 case Gecode::SRT_SUP: olog << "sup"; break;
00214 case Gecode::SRT_DISJ: olog << "||"; break;
00215 case Gecode::SRT_CMPL: olog << "^-1 = "; break;
00216 }
00217 olog << is << std::endl;
00218 }
00219 Gecode::dom(*this, x[i], srt, is);
00220 }
00221
00222 void
00223 SetTestSpace::cardinality(int i, int cmin, int cmax) {
00224 if (opt.log) {
00225 olog << ind(4) << cmin << " <= #(x[" << i << "]) <= " << cmax
00226 << std::endl;
00227 }
00228 Gecode::cardinality(*this, x[i], cmin, cmax);
00229 }
00230
00231 void
00232 SetTestSpace::rel(int i, Gecode::IntRelType irt, int n) {
00233 if (opt.log) {
00234 olog << ind(4) << "y[" << i << "] ";
00235 switch (irt) {
00236 case Gecode::IRT_EQ: olog << "="; break;
00237 case Gecode::IRT_NQ: olog << "!="; break;
00238 case Gecode::IRT_LQ: olog << "<="; break;
00239 case Gecode::IRT_LE: olog << "<"; break;
00240 case Gecode::IRT_GQ: olog << ">="; break;
00241 case Gecode::IRT_GR: olog << ">"; break;
00242 }
00243 olog << " " << n << std::endl;
00244 }
00245 Gecode::rel(*this, y[i], irt, n);
00246 }
00247
00248 void
00249 SetTestSpace::rel(bool sol) {
00250 int n = sol ? 1 : 0;
00251 assert(reified);
00252 if (opt.log)
00253 olog << ind(4) << "b = " << n << std::endl;
00254 Gecode::rel(*this, r.var(), Gecode::IRT_EQ, n);
00255 }
00256
00257 void
00258 SetTestSpace::assign(const SetAssignment& a) {
00259 for (int i=a.size(); i--; ) {
00260 CountableSetRanges csv(a.lub, a[i]);
00261 Gecode::IntSet ai(csv);
00262 rel(i, Gecode::SRT_EQ, ai);
00263 if (Base::fixpoint() && failed())
00264 return;
00265 }
00266 for (int i=withInt; i--; ) {
00267 rel(i, Gecode::IRT_EQ, a.ints()[i]);
00268 if (Base::fixpoint() && failed())
00269 return;
00270 }
00271 }
00272
00273 bool
00274 SetTestSpace::assigned(void) const {
00275 for (int i=x.size(); i--; )
00276 if (!x[i].assigned())
00277 return false;
00278 for (int i=y.size(); i--; )
00279 if (!y[i].assigned())
00280 return false;
00281 return true;
00282 }
00283
00284 void
00285 SetTestSpace::removeFromLub(int v, int i, const SetAssignment& a) {
00286 using namespace Gecode;
00287 SetVarUnknownRanges ur(x[i]);
00288 CountableSetRanges air(a.lub, a[i]);
00289 Gecode::Iter::Ranges::Diff<Gecode::SetVarUnknownRanges,
00290 CountableSetRanges> diff(ur, air);
00291 Gecode::Iter::Ranges::ToValues<Gecode::Iter::Ranges::Diff
00292 <Gecode::SetVarUnknownRanges, CountableSetRanges> > diffV(diff);
00293 for (int j=0; j<v; j++, ++diffV) {}
00294 rel(i, Gecode::SRT_DISJ, Gecode::IntSet(diffV.val(), diffV.val()));
00295 }
00296
00297 void
00298 SetTestSpace::removeFromLub(int v, int i, const SetAssignment& a,
00299 SetTestSpace& c) {
00300 using namespace Gecode;
00301 SetVarUnknownRanges ur(x[i]);
00302 CountableSetRanges air(a.lub, a[i]);
00303 Gecode::Iter::Ranges::Diff<Gecode::SetVarUnknownRanges,
00304 CountableSetRanges> diff(ur, air);
00305 Gecode::Iter::Ranges::ToValues<Gecode::Iter::Ranges::Diff
00306 <Gecode::SetVarUnknownRanges, CountableSetRanges> > diffV(diff);
00307 for (int j=0; j<v; j++, ++diffV) {}
00308 rel(i, Gecode::SRT_DISJ, Gecode::IntSet(diffV.val(), diffV.val()));
00309 c.rel(i, Gecode::SRT_DISJ, Gecode::IntSet(diffV.val(), diffV.val()));
00310 }
00311
00312 void
00313 SetTestSpace::addToGlb(int v, int i, const SetAssignment& a) {
00314 using namespace Gecode;
00315 SetVarUnknownRanges ur(x[i]);
00316 CountableSetRanges air(a.lub, a[i]);
00317 Gecode::Iter::Ranges::Inter<Gecode::SetVarUnknownRanges,
00318 CountableSetRanges> inter(ur, air);
00319 Gecode::Iter::Ranges::ToValues<Gecode::Iter::Ranges::Inter
00320 <Gecode::SetVarUnknownRanges, CountableSetRanges> > interV(inter);
00321 for (int j=0; j<v; j++, ++interV) {}
00322 rel(i, Gecode::SRT_SUP, Gecode::IntSet(interV.val(), interV.val()));
00323 }
00324
00325 void
00326 SetTestSpace::addToGlb(int v, int i, const SetAssignment& a,
00327 SetTestSpace& c) {
00328 using namespace Gecode;
00329 SetVarUnknownRanges ur(x[i]);
00330 CountableSetRanges air(a.lub, a[i]);
00331 Gecode::Iter::Ranges::Inter<Gecode::SetVarUnknownRanges,
00332 CountableSetRanges> inter(ur, air);
00333 Gecode::Iter::Ranges::ToValues<Gecode::Iter::Ranges::Inter
00334 <Gecode::SetVarUnknownRanges, CountableSetRanges> > interV(inter);
00335 for (int j=0; j<v; j++, ++interV) {}
00336 rel(i, Gecode::SRT_SUP, Gecode::IntSet(interV.val(), interV.val()));
00337 c.rel(i, Gecode::SRT_SUP, Gecode::IntSet(interV.val(), interV.val()));
00338 }
00339
00340 bool
00341 SetTestSpace::fixprob(void) {
00342 if (failed())
00343 return true;
00344 SetTestSpace* c = static_cast<SetTestSpace*>(clone());
00345 if (opt.log)
00346 olog << ind(3) << "Testing fixpoint on copy" << std::endl;
00347 c->post();
00348 if (c->failed()) {
00349 delete c; return false;
00350 }
00351
00352 for (int i=x.size(); i--; )
00353 if (x[i].glbSize() != c->x[i].glbSize() ||
00354 x[i].lubSize() != c->x[i].lubSize() ||
00355 x[i].cardMin() != c->x[i].cardMin() ||
00356 x[i].cardMax() != c->x[i].cardMax()) {
00357 delete c;
00358 return false;
00359 }
00360 for (int i=y.size(); i--; )
00361 if (y[i].size() != c->y[i].size()) {
00362 delete c; return false;
00363 }
00364 if (reified && (r.var().size() != c->r.var().size())) {
00365 delete c; return false;
00366 }
00367 if (opt.log)
00368 olog << ind(3) << "Finished testing fixpoint on copy" << std::endl;
00369 delete c;
00370 return true;
00371 }
00372
00373 bool
00374 SetTestSpace::same(SetTestSpace& c) {
00375 if (opt.log)
00376 olog << ind(3) << "Testing whether enabled space is the same"
00377 << std::endl;
00378 bool f = failed();
00379 bool cf = c.failed();
00380 if (f != cf)
00381 return false;
00382 if (f)
00383 return true;
00384
00385 for (int i=x.size(); i--; )
00386 if (x[i].glbSize() != c.x[i].glbSize() ||
00387 x[i].lubSize() != c.x[i].lubSize() ||
00388 x[i].cardMin() != c.x[i].cardMin() ||
00389 x[i].cardMax() != c.x[i].cardMax())
00390 return false;
00391
00392 for (int i=y.size(); i--; )
00393 if (y[i].size() != c.y[i].size())
00394 return false;
00395
00396 if (reified && (r.var().size() != c.r.var().size()))
00397 return false;
00398 if (opt.log)
00399 olog << ind(3) << "Finished testing whether enabled space is the same"
00400 << std::endl;
00401 return true;
00402 }
00403
00404 bool
00405 SetTestSpace::prune(const SetAssignment& a) {
00406 using namespace Gecode;
00407 bool setsAssigned = true;
00408 for (int j=x.size(); j--; )
00409 if (!x[j].assigned()) {
00410 setsAssigned = false;
00411 break;
00412 }
00413 bool intsAssigned = true;
00414 for (int j=y.size(); j--; )
00415 if (!y[j].assigned()) {
00416 intsAssigned = false;
00417 break;
00418 }
00419
00420
00421 int i;
00422 if (intsAssigned) {
00423 i = Base::rand(x.size());
00424 } else if (setsAssigned) {
00425 i = Base::rand(y.size());
00426 } else {
00427 i = Base::rand(x.size()+y.size());
00428 }
00429
00430 if (setsAssigned || i>=x.size()) {
00431 if (i>=x.size())
00432 i = i-x.size();
00433 while (y[i].assigned()) {
00434 i = (i+1) % y.size();
00435 }
00436
00437
00438
00439 switch (Base::rand(3)) {
00440 case 0:
00441 if (a.ints()[i] < y[i].max()) {
00442 int v=a.ints()[i]+1+
00443 Base::rand(static_cast<unsigned int>(y[i].max()-a.ints()[i]));
00444 assert((v > a.ints()[i]) && (v <= y[i].max()));
00445 rel(i, Gecode::IRT_LE, v);
00446 }
00447 break;
00448 case 1:
00449 if (a.ints()[i] > y[i].min()) {
00450 int v=y[i].min()+
00451 Base::rand(static_cast<unsigned int>(a.ints()[i]-y[i].min()));
00452 assert((v < a.ints()[i]) && (v >= y[i].min()));
00453 rel(i, Gecode::IRT_GR, v);
00454 }
00455 break;
00456 default:
00457 int v;
00458 Gecode::Int::ViewRanges<Gecode::Int::IntView> it(y[i]);
00459 unsigned int skip = Base::rand(y[i].size()-1);
00460 while (true) {
00461 if (it.width() > skip) {
00462 v = it.min() + skip;
00463 if (v == a.ints()[i]) {
00464 if (it.width() == 1) {
00465 ++it; v = it.min();
00466 } else if (v < it.max()) {
00467 ++v;
00468 } else {
00469 --v;
00470 }
00471 }
00472 break;
00473 }
00474 skip -= it.width();
00475 ++it;
00476 }
00477 rel(i, Gecode::IRT_NQ, v);
00478 }
00479 return (!Base::fixpoint() || fixprob());
00480 }
00481 while (x[i].assigned()) {
00482 i = (i+1) % x.size();
00483 }
00484 Gecode::SetVarUnknownRanges ur1(x[i]);
00485 CountableSetRanges air1(a.lub, a[i]);
00486 Gecode::Iter::Ranges::Diff<Gecode::SetVarUnknownRanges,
00487 CountableSetRanges> diff(ur1, air1);
00488 Gecode::SetVarUnknownRanges ur2(x[i]);
00489 CountableSetRanges air2(a.lub, a[i]);
00490 Gecode::Iter::Ranges::Inter<Gecode::SetVarUnknownRanges,
00491 CountableSetRanges> inter(ur2, air2);
00492
00493 CountableSetRanges aisizer(a.lub, a[i]);
00494 unsigned int aisize = Gecode::Iter::Ranges::size(aisizer);
00495
00496
00497 switch (Base::rand(5)) {
00498 case 0:
00499 if (inter()) {
00500 int v = Base::rand(Gecode::Iter::Ranges::size(inter));
00501 addToGlb(v, i, a);
00502 }
00503 break;
00504 case 1:
00505 if (diff()) {
00506 int v = Base::rand(Gecode::Iter::Ranges::size(diff));
00507 removeFromLub(v, i, a);
00508 }
00509 break;
00510 case 2:
00511 if (x[i].cardMin() < aisize) {
00512 unsigned int newc = x[i].cardMin() + 1 +
00513 Base::rand(aisize - x[i].cardMin());
00514 assert( newc > x[i].cardMin() );
00515 assert( newc <= aisize );
00516 cardinality(i, newc, Gecode::Set::Limits::card);
00517 }
00518 break;
00519 case 3:
00520 if (x[i].cardMax() > aisize) {
00521 unsigned int newc = x[i].cardMax() - 1 -
00522 Base::rand(x[i].cardMax() - aisize);
00523 assert( newc < x[i].cardMax() );
00524 assert( newc >= aisize );
00525 cardinality(i, 0, newc);
00526 }
00527 break;
00528 default:
00529 if (inter()) {
00530 int v = Base::rand(Gecode::Iter::Ranges::size(inter));
00531 addToGlb(v, i, a);
00532 } else {
00533 int v = Base::rand(Gecode::Iter::Ranges::size(diff));
00534 removeFromLub(v, i, a);
00535 }
00536 }
00537 return (!Base::fixpoint() || fixprob());
00538 }
00539
00540 bool
00541 SetTestSpace::disabled(const SetAssignment& a, SetTestSpace& c) {
00542 c.disable();
00543 using namespace Gecode;
00544 bool setsAssigned = true;
00545 for (int j=x.size(); j--; )
00546 if (!x[j].assigned()) {
00547 setsAssigned = false;
00548 break;
00549 }
00550 bool intsAssigned = true;
00551 for (int j=y.size(); j--; )
00552 if (!y[j].assigned()) {
00553 intsAssigned = false;
00554 break;
00555 }
00556
00557
00558 int i;
00559 if (intsAssigned) {
00560 i = Base::rand(x.size());
00561 } else if (setsAssigned) {
00562 i = Base::rand(y.size());
00563 } else {
00564 i = Base::rand(x.size()+y.size());
00565 }
00566
00567 if (setsAssigned || i>=x.size()) {
00568 if (i>=x.size())
00569 i = i-x.size();
00570 while (y[i].assigned()) {
00571 i = (i+1) % y.size();
00572 }
00573
00574
00575
00576 switch (Base::rand(3)) {
00577 case 0:
00578 if (a.ints()[i] < y[i].max()) {
00579 int v=a.ints()[i]+1+
00580 Base::rand(static_cast<unsigned int>(y[i].max()-a.ints()[i]));
00581 assert((v > a.ints()[i]) && (v <= y[i].max()));
00582 rel(i, Gecode::IRT_LE, v);
00583 c.rel(i, Gecode::IRT_LE, v);
00584 }
00585 break;
00586 case 1:
00587 if (a.ints()[i] > y[i].min()) {
00588 int v=y[i].min()+
00589 Base::rand(static_cast<unsigned int>(a.ints()[i]-y[i].min()));
00590 assert((v < a.ints()[i]) && (v >= y[i].min()));
00591 rel(i, Gecode::IRT_GR, v);
00592 c.rel(i, Gecode::IRT_GR, v);
00593 }
00594 break;
00595 default:
00596 int v;
00597 Gecode::Int::ViewRanges<Gecode::Int::IntView> it(y[i]);
00598 unsigned int skip = Base::rand(y[i].size()-1);
00599 while (true) {
00600 if (it.width() > skip) {
00601 v = it.min() + skip;
00602 if (v == a.ints()[i]) {
00603 if (it.width() == 1) {
00604 ++it; v = it.min();
00605 } else if (v < it.max()) {
00606 ++v;
00607 } else {
00608 --v;
00609 }
00610 }
00611 break;
00612 }
00613 skip -= it.width();
00614 ++it;
00615 }
00616 rel(i, Gecode::IRT_NQ, v);
00617 c.rel(i, Gecode::IRT_NQ, v);
00618 }
00619 c.enable();
00620 return same(c);
00621 }
00622 while (x[i].assigned()) {
00623 i = (i+1) % x.size();
00624 }
00625 Gecode::SetVarUnknownRanges ur1(x[i]);
00626 CountableSetRanges air1(a.lub, a[i]);
00627 Gecode::Iter::Ranges::Diff<Gecode::SetVarUnknownRanges,
00628 CountableSetRanges> diff(ur1, air1);
00629 Gecode::SetVarUnknownRanges ur2(x[i]);
00630 CountableSetRanges air2(a.lub, a[i]);
00631 Gecode::Iter::Ranges::Inter<Gecode::SetVarUnknownRanges,
00632 CountableSetRanges> inter(ur2, air2);
00633
00634 CountableSetRanges aisizer(a.lub, a[i]);
00635 unsigned int aisize = Gecode::Iter::Ranges::size(aisizer);
00636
00637
00638 switch (Base::rand(5)) {
00639 case 0:
00640 if (inter()) {
00641 int v = Base::rand(Gecode::Iter::Ranges::size(inter));
00642 addToGlb(v, i, a, c);
00643 }
00644 break;
00645 case 1:
00646 if (diff()) {
00647 int v = Base::rand(Gecode::Iter::Ranges::size(diff));
00648 removeFromLub(v, i, a, c);
00649 }
00650 break;
00651 case 2:
00652 if (x[i].cardMin() < aisize) {
00653 unsigned int newc = x[i].cardMin() + 1 +
00654 Base::rand(aisize - x[i].cardMin());
00655 assert( newc > x[i].cardMin() );
00656 assert( newc <= aisize );
00657 cardinality(i, newc, Gecode::Set::Limits::card);
00658 c.cardinality(i, newc, Gecode::Set::Limits::card);
00659 }
00660 break;
00661 case 3:
00662 if (x[i].cardMax() > aisize) {
00663 unsigned int newc = x[i].cardMax() - 1 -
00664 Base::rand(x[i].cardMax() - aisize);
00665 assert( newc < x[i].cardMax() );
00666 assert( newc >= aisize );
00667 cardinality(i, 0, newc);
00668 c.cardinality(i, 0, newc);
00669 }
00670 break;
00671 default:
00672 if (inter()) {
00673 int v = Base::rand(Gecode::Iter::Ranges::size(inter));
00674 addToGlb(v, i, a, c);
00675 } else {
00676 int v = Base::rand(Gecode::Iter::Ranges::size(diff));
00677 removeFromLub(v, i, a, c);
00678 }
00679 }
00680 c.enable();
00681 return same(c);
00682 }
00683
00684 unsigned int
00685 SetTestSpace::propagators(void) {
00686 return Gecode::PropagatorGroup::all.size(*this);
00687 }
00688
00689 void
00690 SetTestSpace::enable(void) {
00691 Gecode::PropagatorGroup::all.enable(*this);
00692 }
00693
00694 void
00695 SetTestSpace::disable(void) {
00696 Gecode::PropagatorGroup::all.disable(*this);
00697 (void) status();
00698 }
00699
00700
00702 #define CHECK_TEST(T,M) \
00703 if (opt.log) \
00704 olog << ind(3) << "Check: " << (M) << std::endl; \
00705 if (!(T)) { \
00706 problem = (M); delete s; goto failed; \
00707 }
00708
00710 #define START_TEST(T) \
00711 if (opt.log) { \
00712 olog.str(""); \
00713 olog << ind(2) << "Testing: " << (T) << std::endl; \
00714 } \
00715 test = (T);
00716
00717 bool
00718 SetTest::run(void) {
00719 using namespace Gecode;
00720 const char* test = "NONE";
00721 const char* problem = "NONE";
00722
00723 SetAssignment* ap = new SetAssignment(arity,lub,withInt);
00724 SetAssignment& a = *ap;
00725 while (a()) {
00726 bool is_sol = solution(a);
00727 if (opt.log)
00728 olog << ind(1) << "Assignment: " << a
00729 << (is_sol ? " (solution)" : " (no solution)")
00730 << std::endl;
00731 START_TEST("Assignment (after posting)");
00732 {
00733 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this);
00734 SetTestSpace* sc = NULL;
00735 s->post();
00736 switch (Base::rand(2)) {
00737 case 0:
00738 if (opt.log)
00739 olog << ind(3) << "No copy" << std::endl;
00740 sc = s;
00741 s = NULL;
00742 break;
00743 case 1:
00744 if (opt.log)
00745 olog << ind(3) << "Copy" << std::endl;
00746 if (s->status() != Gecode::SS_FAILED) {
00747 sc = static_cast<SetTestSpace*>(s->clone());
00748 } else {
00749 sc = s; s = NULL;
00750 }
00751 break;
00752 default: assert(false);
00753 }
00754 sc->assign(a);
00755 if (is_sol) {
00756 CHECK_TEST(!sc->failed(), "Failed on solution");
00757 CHECK_TEST(sc->subsumed(testsubsumed), "No subsumption");
00758 } else {
00759 CHECK_TEST(sc->failed(), "Solved on non-solution");
00760 }
00761 delete s; delete sc;
00762 }
00763 START_TEST("Assignment (after posting, disable)");
00764 {
00765 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this);
00766 s->post();
00767 s->disable();
00768 s->assign(a);
00769 s->enable();
00770 if (is_sol) {
00771 CHECK_TEST(!s->failed(), "Failed on solution");
00772 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00773 } else {
00774 CHECK_TEST(s->failed(), "Solved on non-solution");
00775 }
00776 delete s;
00777 }
00778 START_TEST("Assignment (before posting)");
00779 {
00780 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this);
00781 s->assign(a);
00782 s->post();
00783 if (is_sol) {
00784 CHECK_TEST(!s->failed(), "Failed on solution");
00785 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00786 } else {
00787 CHECK_TEST(s->failed(), "Solved on non-solution");
00788 }
00789 delete s;
00790 }
00791 START_TEST("Prune");
00792 {
00793 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this);
00794 s->post();
00795 while (!s->failed() && !s->assigned())
00796 if (!s->prune(a)) {
00797 problem = "No fixpoint";
00798 delete s;
00799 goto failed;
00800 }
00801 s->assign(a);
00802 if (is_sol) {
00803 CHECK_TEST(!s->failed(), "Failed on solution");
00804 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00805 } else {
00806 CHECK_TEST(s->failed(), "Solved on non-solution");
00807 }
00808 delete s;
00809 }
00810 if (disabled) {
00811 START_TEST("Prune (disable)");
00812 {
00813 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this);
00814 SetTestSpace* c = new SetTestSpace(arity,lub,withInt,this);
00815 s->post(); c->post();
00816 while (!s->failed() && !s->assigned())
00817 if (!s->disabled(a,*c)) {
00818 problem = "Different result after re-enable";
00819 delete s; delete c;
00820 goto failed;
00821 }
00822 s->assign(a); c->assign(a);
00823 if (s->failed() != c->failed()) {
00824 problem = "Different failure after re-enable";
00825 delete s; delete c;
00826 goto failed;
00827 }
00828 delete s; delete c;
00829 }
00830 }
00831 if (reified) {
00832 START_TEST("Assignment reified (rewrite after post, <=>)");
00833 {
00834 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
00835 s->post();
00836 s->rel(is_sol);
00837 s->assign(a);
00838 CHECK_TEST(!s->failed(), "Failed");
00839 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00840 delete s;
00841 }
00842 START_TEST("Assignment reified (rewrite after post, =>)");
00843 {
00844 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
00845 s->post();
00846 s->rel(is_sol);
00847 s->assign(a);
00848 CHECK_TEST(!s->failed(), "Failed");
00849 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00850 delete s;
00851 }
00852 START_TEST("Assignment reified (rewrite after post, <=)");
00853 {
00854 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
00855 s->post();
00856 s->rel(is_sol);
00857 s->assign(a);
00858 CHECK_TEST(!s->failed(), "Failed");
00859 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00860 delete s;
00861 }
00862 {
00863 START_TEST("Assignment reified (rewrite failure, <=>)");
00864 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
00865 s->post();
00866 s->rel(!is_sol);
00867 s->assign(a);
00868 CHECK_TEST(s->failed(), "Not failed");
00869 delete s;
00870 }
00871 {
00872 START_TEST("Assignment reified (rewrite failure, =>)");
00873 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
00874 s->post();
00875 s->rel(!is_sol);
00876 s->assign(a);
00877 if (is_sol) {
00878 CHECK_TEST(!s->failed(), "Failed");
00879 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00880 } else {
00881 CHECK_TEST(s->failed(), "Not failed");
00882 }
00883 delete s;
00884 }
00885 {
00886 START_TEST("Assignment reified (rewrite failure, <=)");
00887 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
00888 s->post();
00889 s->rel(!is_sol);
00890 s->assign(a);
00891 if (is_sol) {
00892 CHECK_TEST(s->failed(), "Not failed");
00893 } else {
00894 CHECK_TEST(!s->failed(), "Failed");
00895 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00896 }
00897 delete s;
00898 }
00899 START_TEST("Assignment reified (immediate rewrite, <=>)");
00900 {
00901 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
00902 s->rel(is_sol);
00903 s->post();
00904 s->assign(a);
00905 CHECK_TEST(!s->failed(), "Failed");
00906 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00907 delete s;
00908 }
00909 START_TEST("Assignment reified (immediate rewrite, =>)");
00910 {
00911 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
00912 s->rel(is_sol);
00913 s->post();
00914 s->assign(a);
00915 CHECK_TEST(!s->failed(), "Failed");
00916 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00917 delete s;
00918 }
00919 START_TEST("Assignment reified (immediate rewrite, <=)");
00920 {
00921 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
00922 s->rel(is_sol);
00923 s->post();
00924 s->assign(a);
00925 CHECK_TEST(!s->failed(), "Failed");
00926 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00927 delete s;
00928 }
00929 START_TEST("Assignment reified (immediate failure, <=>)");
00930 {
00931 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
00932 s->rel(!is_sol);
00933 s->post();
00934 s->assign(a);
00935 CHECK_TEST(s->failed(), "Not failed");
00936 delete s;
00937 }
00938 START_TEST("Assignment reified (immediate failure, =>)");
00939 {
00940 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
00941 s->rel(!is_sol);
00942 s->post();
00943 s->assign(a);
00944 if (is_sol) {
00945 CHECK_TEST(!s->failed(), "Failed");
00946 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00947 } else {
00948 CHECK_TEST(s->failed(), "Not failed");
00949 }
00950 delete s;
00951 }
00952 START_TEST("Assignment reified (immediate failure, <=)");
00953 {
00954 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
00955 s->rel(!is_sol);
00956 s->post();
00957 s->assign(a);
00958 if (is_sol) {
00959 CHECK_TEST(s->failed(), "Not failed");
00960 } else {
00961 CHECK_TEST(!s->failed(), "Failed");
00962 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00963 }
00964 delete s;
00965 }
00966 START_TEST("Assignment reified (before posting, <=>)");
00967 {
00968 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
00969 s->assign(a);
00970 s->post();
00971 CHECK_TEST(!s->failed(), "Failed");
00972 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00973 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00974 if (is_sol) {
00975 CHECK_TEST(s->r.var().val()==1, "Zero on solution");
00976 } else {
00977 CHECK_TEST(s->r.var().val()==0, "One on non-solution");
00978 }
00979 delete s;
00980 }
00981 START_TEST("Assignment reified (before posting, =>)");
00982 {
00983 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
00984 s->assign(a);
00985 s->post();
00986 CHECK_TEST(!s->failed(), "Failed");
00987 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
00988 if (is_sol) {
00989 CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
00990 } else {
00991 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00992 CHECK_TEST(s->r.var().val()==0, "One on non-solution");
00993 }
00994 delete s;
00995 }
00996 START_TEST("Assignment reified (before posting, <=)");
00997 {
00998 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
00999 s->assign(a);
01000 s->post();
01001 CHECK_TEST(!s->failed(), "Failed");
01002 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
01003 if (is_sol) {
01004 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01005 CHECK_TEST(s->r.var().val()==1, "Zero on solution");
01006 } else {
01007 CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
01008 }
01009 delete s;
01010 }
01011 START_TEST("Assignment reified (after posting, <=>)");
01012 {
01013 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
01014 s->post();
01015 s->assign(a);
01016 CHECK_TEST(!s->failed(), "Failed");
01017 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
01018 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01019 if (is_sol) {
01020 CHECK_TEST(s->r.var().val()==1, "Zero on solution");
01021 } else {
01022 CHECK_TEST(s->r.var().val()==0, "One on non-solution");
01023 }
01024 delete s;
01025 }
01026 START_TEST("Assignment reified (after posting, =>)");
01027 {
01028 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
01029 s->post();
01030 s->assign(a);
01031 CHECK_TEST(!s->failed(), "Failed");
01032 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
01033 if (is_sol) {
01034 CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
01035 } else {
01036 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01037 CHECK_TEST(s->r.var().val()==0, "One on non-solution");
01038 }
01039 delete s;
01040 }
01041 START_TEST("Assignment reified (after posting, <=)");
01042 {
01043 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
01044 s->post();
01045 s->assign(a);
01046 CHECK_TEST(!s->failed(), "Failed");
01047 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
01048 if (is_sol) {
01049 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01050 CHECK_TEST(s->r.var().val()==1, "Zero on solution");
01051 } else {
01052 CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
01053 }
01054 delete s;
01055 }
01056 START_TEST("Assignment reified (after posting, <=>, disable)");
01057 {
01058 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
01059 s->post();
01060 s->disable();
01061 s->assign(a);
01062 s->enable();
01063 CHECK_TEST(!s->failed(), "Failed");
01064 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
01065 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01066 if (is_sol) {
01067 CHECK_TEST(s->r.var().val()==1, "Zero on solution");
01068 } else {
01069 CHECK_TEST(s->r.var().val()==0, "One on non-solution");
01070 }
01071 delete s;
01072 }
01073 START_TEST("Assignment reified (after posting, =>, disable)");
01074 {
01075 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
01076 s->post();
01077 s->disable();
01078 s->assign(a);
01079 s->enable();
01080 CHECK_TEST(!s->failed(), "Failed");
01081 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
01082 if (is_sol) {
01083 CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
01084 } else {
01085 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01086 CHECK_TEST(s->r.var().val()==0, "One on non-solution");
01087 }
01088 delete s;
01089 }
01090 START_TEST("Assignment reified (after posting, <=, disable)");
01091 {
01092 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
01093 s->post();
01094 s->disable();
01095 s->assign(a);
01096 s->enable();
01097 CHECK_TEST(!s->failed(), "Failed");
01098 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
01099 if (is_sol) {
01100 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01101 CHECK_TEST(s->r.var().val()==1, "Zero on solution");
01102 } else {
01103 CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
01104 }
01105 delete s;
01106 }
01107 START_TEST("Prune reified, <=>");
01108 {
01109 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
01110 s->post();
01111 while (!s->failed() &&
01112 (!s->assigned() || !s->r.var().assigned()))
01113 if (!s->prune(a)) {
01114 problem = "No fixpoint";
01115 delete s;
01116 goto failed;
01117 }
01118 CHECK_TEST(!s->failed(), "Failed");
01119 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
01120 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01121 if (is_sol) {
01122 CHECK_TEST(s->r.var().val()==1, "Zero on solution");
01123 } else {
01124 CHECK_TEST(s->r.var().val()==0, "One on non-solution");
01125 }
01126 delete s;
01127 }
01128 START_TEST("Prune reified, =>");
01129 {
01130 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
01131 s->post();
01132 while (!s->failed() &&
01133 (!s->assigned() || (!is_sol && !s->r.var().assigned()))) {
01134 if (!s->prune(a)) {
01135 problem = "No fixpoint";
01136 delete s;
01137 goto failed;
01138 }
01139 }
01140 CHECK_TEST(!s->failed(), "Failed");
01141 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
01142 if (is_sol) {
01143 CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
01144 } else {
01145 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01146 CHECK_TEST(s->r.var().val()==0, "One on non-solution");
01147 }
01148 delete s;
01149 }
01150 START_TEST("Prune reified, <=");
01151 {
01152 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
01153 s->post();
01154 while (!s->failed() &&
01155 (!s->assigned() || (is_sol && !s->r.var().assigned())))
01156 if (!s->prune(a)) {
01157 problem = "No fixpoint";
01158 delete s;
01159 goto failed;
01160 }
01161 CHECK_TEST(!s->failed(), "Failed");
01162 CHECK_TEST(s->subsumed(testsubsumed), "No subsumption");
01163 if (is_sol) {
01164 CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01165 CHECK_TEST(s->r.var().val()==1, "Zero on solution");
01166 } else {
01167 CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
01168 }
01169 delete s;
01170 }
01171 }
01172 ++a;
01173 }
01174 delete ap;
01175 return true;
01176 failed:
01177 if (opt.log)
01178 olog << "FAILURE" << std::endl
01179 << ind(1) << "Test: " << test << std::endl
01180 << ind(1) << "Problem: " << problem << std::endl;
01181 if (a() && opt.log)
01182 olog << ind(1) << "Assignment: " << a << std::endl;
01183 delete ap;
01184
01185 return false;
01186 }
01187
01188 const Gecode::SetRelType SetRelTypes::srts[] =
01189 {Gecode::SRT_EQ,Gecode::SRT_NQ,Gecode::SRT_SUB,
01190 Gecode::SRT_SUP,Gecode::SRT_DISJ,Gecode::SRT_CMPL};
01191
01192 const Gecode::SetOpType SetOpTypes::sots[] =
01193 {Gecode::SOT_UNION, Gecode::SOT_DUNION,
01194 Gecode::SOT_INTER, Gecode::SOT_MINUS};
01195
01196 }}
01197
01198 #undef START_TEST
01199 #undef CHECK_TEST
01200
01201