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