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, bool r,
00125 SetTest* t, bool log)
00126 : d(d0), x(*this, n, Gecode::IntSet::empty, d), y(*this, i, d),
00127 withInt(i), b(*this, 0, 1), reified(r), test(t) {
00128 if (opt.log && log) {
00129 olog << ind(2) << "Initial: x[]=" << x;
00130 olog << " y[]=" << y;
00131 if (reified)
00132 olog << " b=" << b;
00133 olog << std::endl;
00134 }
00135 }
00136
00137 SetTestSpace::SetTestSpace(bool share, SetTestSpace& s)
00138 : Gecode::Space(share,s), d(s.d), withInt(s.withInt),
00139 reified(s.reified), test(s.test) {
00140 x.update(*this, share, s.x);
00141 y.update(*this, share, s.y);
00142 b.update(*this, share, s.b);
00143 }
00144
00145 Gecode::Space*
00146 SetTestSpace::copy(bool share) {
00147 return new SetTestSpace(share,*this);
00148 }
00149
00150 void
00151 SetTestSpace::post(void) {
00152 if (reified){
00153 test->post(*this,x,y,b);
00154 if (opt.log)
00155 olog << ind(3) << "Posting reified propagator" << std::endl;
00156 } else {
00157 test->post(*this,x,y);
00158 if (opt.log)
00159 olog << ind(3) << "Posting propagator" << std::endl;
00160 }
00161 }
00162
00163 bool
00164 SetTestSpace::failed(void) {
00165 if (opt.log) {
00166 olog << ind(3) << "Fixpoint: x[]=" << x
00167 << " y[]=" << y << std::endl;
00168 bool f=(status() == Gecode::SS_FAILED);
00169 olog << ind(3) << " --> x[]=" << x
00170 << " y[]=" << y << std::endl;
00171 return f;
00172 } else {
00173 return status() == Gecode::SS_FAILED;
00174 }
00175 }
00176
00177 void
00178 SetTestSpace::rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is) {
00179 if (opt.log) {
00180 olog << ind(4) << "x[" << i << "] ";
00181 switch (srt) {
00182 case Gecode::SRT_EQ: olog << "="; break;
00183 case Gecode::SRT_NQ: olog << "!="; break;
00184 case Gecode::SRT_SUB: olog << "<="; break;
00185 case Gecode::SRT_SUP: olog << ">="; break;
00186 case Gecode::SRT_DISJ: olog << "||"; break;
00187 case Gecode::SRT_CMPL: olog << "^-1 = "; break;
00188 }
00189 olog << is << std::endl;
00190 }
00191 Gecode::dom(*this, x[i], srt, is);
00192 }
00193
00194 void
00195 SetTestSpace::cardinality(int i, int cmin, int cmax) {
00196 if (opt.log) {
00197 olog << ind(4) << cmin << " <= #(x[" << i << "]) <= " << cmax
00198 << std::endl;
00199 }
00200 Gecode::cardinality(*this, x[i], cmin, cmax);
00201 }
00202
00203 void
00204 SetTestSpace::rel(int i, Gecode::IntRelType irt, int n) {
00205 if (opt.log) {
00206 olog << ind(4) << "y[" << i << "] ";
00207 switch (irt) {
00208 case Gecode::IRT_EQ: olog << "="; break;
00209 case Gecode::IRT_NQ: olog << "!="; break;
00210 case Gecode::IRT_LQ: olog << "<="; break;
00211 case Gecode::IRT_LE: olog << "<"; break;
00212 case Gecode::IRT_GQ: olog << ">="; break;
00213 case Gecode::IRT_GR: olog << ">"; break;
00214 }
00215 olog << " " << n << std::endl;
00216 }
00217 Gecode::rel(*this, y[i], irt, n);
00218 }
00219
00220 void
00221 SetTestSpace::rel(bool sol) {
00222 int n = sol ? 1 : 0;
00223 assert(reified);
00224 if (opt.log)
00225 olog << ind(4) << "b = " << n << std::endl;
00226 Gecode::rel(*this, b, Gecode::IRT_EQ, n);
00227 }
00228
00229 void
00230 SetTestSpace::assign(const SetAssignment& a) {
00231 for (int i=a.size(); i--; ) {
00232 CountableSetRanges csv(a.lub, a[i]);
00233 Gecode::IntSet ai(csv);
00234 rel(i, Gecode::SRT_EQ, ai);
00235 if (Base::fixpoint() && failed())
00236 return;
00237 }
00238 for (int i=withInt; i--; ) {
00239 rel(i, Gecode::IRT_EQ, a.ints()[i]);
00240 if (Base::fixpoint() && failed())
00241 return;
00242 }
00243 }
00244
00245 bool
00246 SetTestSpace::assigned(void) const {
00247 for (int i=x.size(); i--; )
00248 if (!x[i].assigned())
00249 return false;
00250 for (int i=y.size(); i--; )
00251 if (!y[i].assigned())
00252 return false;
00253 return true;
00254 }
00255
00256 void
00257 SetTestSpace::removeFromLub(int v, int i, const SetAssignment& a) {
00258 using namespace Gecode;
00259 SetVarUnknownRanges ur(x[i]);
00260 CountableSetRanges air(a.lub, a[i]);
00261 Gecode::Iter::Ranges::Diff<Gecode::SetVarUnknownRanges,
00262 CountableSetRanges> diff(ur, air);
00263 Gecode::Iter::Ranges::ToValues<Gecode::Iter::Ranges::Diff
00264 <Gecode::SetVarUnknownRanges, CountableSetRanges> > diffV(diff);
00265 for (int j=0; j<v; j++, ++diffV) {}
00266 rel(i, Gecode::SRT_DISJ, Gecode::IntSet(diffV.val(), diffV.val()));
00267 }
00268
00269 void
00270 SetTestSpace::addToGlb(int v, int i, const SetAssignment& a) {
00271 using namespace Gecode;
00272 SetVarUnknownRanges ur(x[i]);
00273 CountableSetRanges air(a.lub, a[i]);
00274 Gecode::Iter::Ranges::Inter<Gecode::SetVarUnknownRanges,
00275 CountableSetRanges> inter(ur, air);
00276 Gecode::Iter::Ranges::ToValues<Gecode::Iter::Ranges::Inter
00277 <Gecode::SetVarUnknownRanges, CountableSetRanges> > interV(inter);
00278 for (int j=0; j<v; j++, ++interV) {}
00279 rel(i, Gecode::SRT_SUP, Gecode::IntSet(interV.val(), interV.val()));
00280 }
00281
00282 bool
00283 SetTestSpace::fixprob(void) {
00284 if (failed())
00285 return true;
00286 SetTestSpace* c = static_cast<SetTestSpace*>(clone());
00287 if (opt.log)
00288 olog << ind(3) << "Testing fixpoint on copy" << std::endl;
00289 c->post();
00290 if (c->failed()) {
00291 delete c; return false;
00292 }
00293
00294 for (int i=x.size(); i--; )
00295 if (x[i].glbSize() != c->x[i].glbSize() ||
00296 x[i].lubSize() != c->x[i].lubSize() ||
00297 x[i].cardMin() != c->x[i].cardMin() ||
00298 x[i].cardMax() != c->x[i].cardMax()) {
00299 delete c;
00300 return false;
00301 }
00302 for (int i=y.size(); i--; )
00303 if (y[i].size() != c->y[i].size()) {
00304 delete c; return false;
00305 }
00306 if (reified && (b.size() != c->b.size())) {
00307 delete c; return false;
00308 }
00309 if (opt.log)
00310 olog << ind(3) << "Finished testing fixpoint on copy" << std::endl;
00311 delete c;
00312 return true;
00313 }
00314
00315 bool
00316 SetTestSpace::prune(const SetAssignment& a) {
00317 using namespace Gecode;
00318 bool setsAssigned = true;
00319 for (int j=x.size(); j--; )
00320 if (!x[j].assigned()) {
00321 setsAssigned = false;
00322 break;
00323 }
00324 bool intsAssigned = true;
00325 for (int j=y.size(); j--; )
00326 if (!y[j].assigned()) {
00327 intsAssigned = false;
00328 break;
00329 }
00330
00331
00332 int i;
00333 if (intsAssigned) {
00334 i = Base::rand(x.size());
00335 } else if (setsAssigned) {
00336 i = Base::rand(y.size());
00337 } else {
00338 i = Base::rand(x.size()+y.size());
00339 }
00340
00341 if (setsAssigned || i>=x.size()) {
00342 if (i>=x.size())
00343 i = i-x.size();
00344 while (y[i].assigned()) {
00345 i = (i+1) % y.size();
00346 }
00347
00348
00349
00350 switch (Base::rand(3)) {
00351 case 0:
00352 if (a.ints()[i] < y[i].max()) {
00353 int v=a.ints()[i]+1+
00354 Base::rand(static_cast<unsigned int>(y[i].max()-a.ints()[i]));
00355 assert((v > a.ints()[i]) && (v <= y[i].max()));
00356 rel(i, Gecode::IRT_LE, v);
00357 }
00358 break;
00359 case 1:
00360 if (a.ints()[i] > y[i].min()) {
00361 int v=y[i].min()+
00362 Base::rand(static_cast<unsigned int>(a.ints()[i]-y[i].min()));
00363 assert((v < a.ints()[i]) && (v >= y[i].min()));
00364 rel(i, Gecode::IRT_GR, v);
00365 }
00366 break;
00367 default:
00368 int v;
00369 Gecode::Int::ViewRanges<Gecode::Int::IntView> it(y[i]);
00370 unsigned int skip = Base::rand(y[i].size()-1);
00371 while (true) {
00372 if (it.width() > skip) {
00373 v = it.min() + skip;
00374 if (v == a.ints()[i]) {
00375 if (it.width() == 1) {
00376 ++it; v = it.min();
00377 } else if (v < it.max()) {
00378 ++v;
00379 } else {
00380 --v;
00381 }
00382 }
00383 break;
00384 }
00385 skip -= it.width();
00386 ++it;
00387 }
00388 rel(i, Gecode::IRT_NQ, v);
00389 }
00390 return (!Base::fixpoint() || fixprob());
00391 }
00392 while (x[i].assigned()) {
00393 i = (i+1) % x.size();
00394 }
00395 Gecode::SetVarUnknownRanges ur1(x[i]);
00396 CountableSetRanges air1(a.lub, a[i]);
00397 Gecode::Iter::Ranges::Diff<Gecode::SetVarUnknownRanges,
00398 CountableSetRanges> diff(ur1, air1);
00399 Gecode::SetVarUnknownRanges ur2(x[i]);
00400 CountableSetRanges air2(a.lub, a[i]);
00401 Gecode::Iter::Ranges::Inter<Gecode::SetVarUnknownRanges,
00402 CountableSetRanges> inter(ur2, air2);
00403
00404 CountableSetRanges aisizer(a.lub, a[i]);
00405 unsigned int aisize = Gecode::Iter::Ranges::size(aisizer);
00406
00407
00408 switch (Base::rand(5)) {
00409 case 0:
00410 if (inter()) {
00411 int v = Base::rand(Gecode::Iter::Ranges::size(inter));
00412 addToGlb(v, i, a);
00413 }
00414 break;
00415 case 1:
00416 if (diff()) {
00417 int v = Base::rand(Gecode::Iter::Ranges::size(diff));
00418 removeFromLub(v, i, a);
00419 }
00420 break;
00421 case 2:
00422 if (x[i].cardMin() < aisize) {
00423 unsigned int newc = x[i].cardMin() + 1 +
00424 Base::rand(aisize - x[i].cardMin());
00425 assert( newc > x[i].cardMin() );
00426 assert( newc <= aisize );
00427 cardinality(i, newc, Gecode::Set::Limits::card);
00428 }
00429 break;
00430 case 3:
00431 if (x[i].cardMax() > aisize) {
00432 unsigned int newc = x[i].cardMax() - 1 -
00433 Base::rand(x[i].cardMax() - aisize);
00434 assert( newc < x[i].cardMax() );
00435 assert( newc >= aisize );
00436 cardinality(i, 0, newc);
00437 }
00438 break;
00439 default:
00440 if (inter()) {
00441 int v = Base::rand(Gecode::Iter::Ranges::size(inter));
00442 addToGlb(v, i, a);
00443 } else {
00444 int v = Base::rand(Gecode::Iter::Ranges::size(diff));
00445 removeFromLub(v, i, a);
00446 }
00447 }
00448 return (!Base::fixpoint() || fixprob());
00449 }
00450
00451
00453 #define CHECK_TEST(T,M) \
00454 if (opt.log) \
00455 olog << ind(3) << "Check: " << (M) << std::endl; \
00456 if (!(T)) { \
00457 problem = (M); delete s; goto failed; \
00458 }
00459
00461 #define START_TEST(T) \
00462 if (opt.log) { \
00463 olog.str(""); \
00464 olog << ind(2) << "Testing: " << (T) << std::endl; \
00465 } \
00466 test = (T);
00467
00468 bool
00469 SetTest::run(void) {
00470 const char* test = "NONE";
00471 const char* problem = "NONE";
00472
00473 SetAssignment* ap = new SetAssignment(arity,lub,withInt);
00474 SetAssignment& a = *ap;
00475 while (a()) {
00476 bool is_sol = solution(a);
00477 if (opt.log)
00478 olog << ind(1) << "Assignment: " << a
00479 << (is_sol ? " (solution)" : " (no solution)")
00480 << std::endl;
00481
00482 START_TEST("Assignment (after posting)");
00483 {
00484 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,false,this);
00485 SetTestSpace* sc = NULL;
00486 s->post();
00487 switch (Base::rand(3)) {
00488 case 0:
00489 if (opt.log)
00490 olog << ind(3) << "No copy" << std::endl;
00491 sc = s;
00492 s = NULL;
00493 break;
00494 case 1:
00495 if (opt.log)
00496 olog << ind(3) << "Unshared copy" << std::endl;
00497 if (s->status() != Gecode::SS_FAILED) {
00498 sc = static_cast<SetTestSpace*>(s->clone(true));
00499 } else {
00500 sc = s; s = NULL;
00501 }
00502 break;
00503 case 2:
00504 if (opt.log)
00505 olog << ind(3) << "Unshared copy" << std::endl;
00506 if (s->status() != Gecode::SS_FAILED) {
00507 sc = static_cast<SetTestSpace*>(s->clone(false));
00508 } else {
00509 sc = s; s = NULL;
00510 }
00511 break;
00512 default: assert(false);
00513 }
00514 sc->assign(a);
00515 if (is_sol) {
00516 CHECK_TEST(!sc->failed(), "Failed on solution");
00517 CHECK_TEST(sc->propagators()==0, "No subsumption");
00518 } else {
00519 CHECK_TEST(sc->failed(), "Solved on non-solution");
00520 }
00521 delete s; delete sc;
00522 }
00523 START_TEST("Assignment (before posting)");
00524 {
00525 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,false,this);
00526 s->assign(a);
00527 s->post();
00528 if (is_sol) {
00529 CHECK_TEST(!s->failed(), "Failed on solution");
00530 CHECK_TEST(s->propagators()==0, "No subsumption");
00531 } else {
00532 CHECK_TEST(s->failed(), "Solved on non-solution");
00533 }
00534 delete s;
00535 }
00536 if (reified) {
00537 START_TEST("Assignment reified (before posting)");
00538 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,true,this);
00539 s->assign(a);
00540 s->post();
00541 CHECK_TEST(!s->failed(), "Failed");
00542 CHECK_TEST(s->propagators()==0, "No subsumption");
00543 CHECK_TEST(s->b.assigned(), "Control variable unassigned");
00544 if (is_sol) {
00545 CHECK_TEST(s->b.val()==1, "Zero on solution");
00546 } else {
00547 CHECK_TEST(s->b.val()==0, "One on non-solution");
00548 }
00549 delete s;
00550 }
00551 if (reified) {
00552 START_TEST("Assignment reified (after posting)");
00553 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,true,this);
00554 s->post();
00555 s->assign(a);
00556 CHECK_TEST(!s->failed(), "Failed");
00557 CHECK_TEST(s->propagators()==0, "No subsumption");
00558 CHECK_TEST(s->b.assigned(), "Control variable unassigned");
00559 if (is_sol) {
00560 CHECK_TEST(s->b.val()==1, "Zero on solution");
00561 } else {
00562 CHECK_TEST(s->b.val()==0, "One on non-solution");
00563 }
00564 delete s;
00565 }
00566 START_TEST("Prune");
00567 {
00568 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,false,this);
00569 s->post();
00570 while (!s->failed() && !s->assigned())
00571 if (!s->prune(a)) {
00572 problem = "No fixpoint";
00573 delete s;
00574 goto failed;
00575 }
00576 s->assign(a);
00577 if (is_sol) {
00578 CHECK_TEST(!s->failed(), "Failed on solution");
00579 CHECK_TEST(s->propagators()==0, "No subsumption");
00580 } else {
00581 CHECK_TEST(s->failed(), "Solved on non-solution");
00582 }
00583 delete s;
00584 }
00585 if (reified) {
00586 START_TEST("Prune reified");
00587 SetTestSpace* s = new SetTestSpace(arity,lub,withInt,true,this);
00588 s->post();
00589 while (!s->assigned() && !s->b.assigned())
00590 if (!s->prune(a)) {
00591 problem = "No fixpoint";
00592 delete s;
00593 goto failed;
00594 }
00595 CHECK_TEST(!s->failed(), "Failed");
00596 CHECK_TEST(s->propagators()==0, "No subsumption");
00597 CHECK_TEST(s->b.assigned(), "Control variable unassigned");
00598 if (is_sol) {
00599 CHECK_TEST(s->b.val()==1, "Zero on solution");
00600 } else {
00601 CHECK_TEST(s->b.val()==0, "One on non-solution");
00602 }
00603 delete s;
00604 }
00605 ++a;
00606 }
00607 delete ap;
00608 return true;
00609 failed:
00610 if (opt.log)
00611 olog << "FAILURE" << std::endl
00612 << ind(1) << "Test: " << test << std::endl
00613 << ind(1) << "Problem: " << problem << std::endl;
00614 if (a() && opt.log)
00615 olog << ind(1) << "Assignment: " << a << std::endl;
00616 delete ap;
00617
00618 return false;
00619 }
00620
00621 const Gecode::SetRelType SetRelTypes::srts[] =
00622 {Gecode::SRT_EQ,Gecode::SRT_NQ,Gecode::SRT_SUB,
00623 Gecode::SRT_SUP,Gecode::SRT_DISJ,Gecode::SRT_CMPL};
00624
00625 const Gecode::SetOpType SetOpTypes::sots[] =
00626 {Gecode::SOT_UNION, Gecode::SOT_DUNION,
00627 Gecode::SOT_INTER, Gecode::SOT_MINUS};
00628
00629 }}
00630
00631 #undef START_TEST
00632 #undef CHECK_TEST
00633
00634