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