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 #include "test/int.hh"
00041
00042 #include <algorithm>
00043
00044 namespace Test { namespace Int {
00045
00046
00047
00048
00049
00050
00051 void
00052 CpltAssignment::operator++(void) {
00053 int i = n-1;
00054 while (true) {
00055 ++dsv[i];
00056 if (dsv[i]() || (i == 0))
00057 return;
00058 dsv[i--].init(d);
00059 }
00060 }
00061
00062
00063
00064
00065
00066 void
00067 RandomAssignment::operator++(void) {
00068 for (int i = n; i--; )
00069 vals[i]=randval();
00070 a--;
00071 }
00072
00073 }}
00074
00075 std::ostream&
00076 operator<<(std::ostream& os, const Test::Int::Assignment& a) {
00077 int n = a.size();
00078 os << "{";
00079 for (int i=0; i<n; i++)
00080 os << a[i] << ((i!=n-1) ? "," : "}");
00081 return os;
00082 }
00083
00084 namespace Test { namespace Int {
00085
00086 TestSpace::TestSpace(int n, Gecode::IntSet& d0, bool r, Test* t, bool log)
00087 : d(d0), x(*this,n,d), b(*this,0,1), reified(r), test(t) {
00088 if (opt.log && log) {
00089 olog << ind(2) << "Initial: x[]=" << x;
00090 if (reified)
00091 olog << " b=" << b;
00092 olog << std::endl;
00093 }
00094 }
00095
00096 TestSpace::TestSpace(bool share, TestSpace& s)
00097 : Gecode::Space(share,s), d(s.d), reified(s.reified), test(s.test) {
00098 x.update(*this, share, s.x);
00099 b.update(*this, share, s.b);
00100 }
00101
00102 Gecode::Space*
00103 TestSpace::copy(bool share) {
00104 return new TestSpace(share,*this);
00105 }
00106
00107 bool
00108 TestSpace::assigned(void) const {
00109 for (int i=x.size(); i--; )
00110 if (!x[i].assigned())
00111 return false;
00112 return true;
00113 }
00114
00115 void
00116 TestSpace::post(void) {
00117 if (reified){
00118 test->post(*this,x,b);
00119 if (opt.log)
00120 olog << ind(3) << "Posting reified propagator" << std::endl;
00121 } else {
00122 test->post(*this,x);
00123 if (opt.log)
00124 olog << ind(3) << "Posting propagator" << std::endl;
00125 }
00126 }
00127
00128 bool
00129 TestSpace::failed(void) {
00130 if (opt.log) {
00131 olog << ind(3) << "Fixpoint: " << x;
00132 bool f=(status() == Gecode::SS_FAILED);
00133 olog << std::endl << ind(3) << " --> " << x << std::endl;
00134 return f;
00135 } else {
00136 return status() == Gecode::SS_FAILED;
00137 }
00138 }
00139
00140 void
00141 TestSpace::rel(int i, Gecode::IntRelType irt, int n) {
00142 if (opt.log) {
00143 olog << ind(4) << "x[" << i << "] ";
00144 switch (irt) {
00145 case Gecode::IRT_EQ: olog << "="; break;
00146 case Gecode::IRT_NQ: olog << "!="; break;
00147 case Gecode::IRT_LQ: olog << "<="; break;
00148 case Gecode::IRT_LE: olog << "<"; break;
00149 case Gecode::IRT_GQ: olog << ">="; break;
00150 case Gecode::IRT_GR: olog << ">"; break;
00151 }
00152 olog << " " << n << std::endl;
00153 }
00154 Gecode::rel(*this, x[i], irt, n);
00155 }
00156
00157 void
00158 TestSpace::rel(bool sol) {
00159 int n = sol ? 1 : 0;
00160 assert(reified);
00161 if (opt.log)
00162 olog << ind(4) << "b = " << n << std::endl;
00163 Gecode::rel(*this, b, Gecode::IRT_EQ, n);
00164 }
00165
00166 void
00167 TestSpace::assign(const Assignment& a, bool skip) {
00168 using namespace Gecode;
00169 int i = skip ? static_cast<int>(Base::rand(a.size())) : -1;
00170 for (int j=a.size(); j--; )
00171 if (i != j) {
00172 rel(j, IRT_EQ, a[j]);
00173 if (Base::fixpoint() && failed())
00174 return;
00175 }
00176 }
00177
00178 void
00179 TestSpace::bound(void) {
00180 using namespace Gecode;
00181
00182 int i = Base::rand(x.size());
00183 while (x[i].assigned()) {
00184 i = (i+1) % x.size();
00185 }
00186 bool min = Base::rand(2);
00187 rel(i, IRT_EQ, min ? x[i].min() : x[i].max());
00188 }
00189
00190 void
00191 TestSpace::prune(int i, bool bounds_only) {
00192 using namespace Gecode;
00193
00194 if (bounds_only) {
00195 if (Base::rand(2) && !x[i].assigned()) {
00196 int v=x[i].min()+1+Base::rand(static_cast
00197 <unsigned int>(x[i].max()-x[i].min()));
00198 assert((v > x[i].min()) && (v <= x[i].max()));
00199 rel(i, Gecode::IRT_LE, v);
00200 }
00201 if (Base::rand(2) && !x[i].assigned()) {
00202 int v=x[i].min()+Base::rand(static_cast
00203 <unsigned int>(x[i].max()-x[i].min()));
00204 assert((v < x[i].max()) && (v >= x[i].min()));
00205 rel(i, Gecode::IRT_GR, v);
00206 }
00207 } else {
00208 for (int vals = Base::rand(x[i].size()-1)+1; vals--; ) {
00209 int v;
00210 Gecode::Int::ViewRanges<Gecode::Int::IntView> it(x[i]);
00211 unsigned int skip = Base::rand(x[i].size()-1);
00212 while (true) {
00213 if (it.width() > skip) {
00214 v = it.min() + skip; break;
00215 }
00216 skip -= it.width(); ++it;
00217 }
00218 rel(i, IRT_NQ, v);
00219 }
00220 }
00221 }
00222
00223 void
00224 TestSpace::prune(void) {
00225 using namespace Gecode;
00226
00227 int i = Base::rand(x.size());
00228 while (x[i].assigned()) {
00229 i = (i+1) % x.size();
00230 }
00231 prune(i, false);
00232 }
00233
00234 bool
00235 TestSpace::prune(const Assignment& a) {
00236
00237 int i = Base::rand(x.size());
00238 while (x[i].assigned())
00239 i = (i+1) % x.size();
00240
00241 switch (Base::rand(3)) {
00242 case 0:
00243 if (a[i] < x[i].max()) {
00244 int v=a[i]+1+Base::rand(static_cast
00245 <unsigned int>(x[i].max()-a[i]));
00246 assert((v > a[i]) && (v <= x[i].max()));
00247 rel(i, Gecode::IRT_LE, v);
00248 }
00249 break;
00250 case 1:
00251 if (a[i] > x[i].min()) {
00252 int v=x[i].min()+Base::rand(static_cast
00253 <unsigned int>(a[i]-x[i].min()));
00254 assert((v < a[i]) && (v >= x[i].min()));
00255 rel(i, Gecode::IRT_GR, v);
00256 }
00257 break;
00258 default:
00259 {
00260 int v;
00261 Gecode::Int::ViewRanges<Gecode::Int::IntView> it(x[i]);
00262 unsigned int skip = Base::rand(x[i].size()-1);
00263 while (true) {
00264 if (it.width() > skip) {
00265 v = it.min() + skip;
00266 if (v == a[i]) {
00267 if (it.width() == 1) {
00268 ++it; v = it.min();
00269 } else if (v < it.max()) {
00270 ++v;
00271 } else {
00272 --v;
00273 }
00274 }
00275 break;
00276 }
00277 skip -= it.width(); ++it;
00278 }
00279 rel(i, Gecode::IRT_NQ, v);
00280 break;
00281 }
00282 }
00283 if (Base::fixpoint()) {
00284 if (failed())
00285 return true;
00286 TestSpace* c = static_cast<TestSpace*>(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 for (int i=x.size(); i--; )
00294 if (x[i].size() != c->x[i].size()) {
00295 delete c; return false;
00296 }
00297 if (reified && (b.size() != c->b.size())) {
00298 delete c; return false;
00299 }
00300 if (opt.log)
00301 olog << ind(3) << "Finished testing fixpoint on copy" << std::endl;
00302 delete c;
00303 }
00304 return true;
00305 }
00306
00307
00308 const Gecode::IntConLevel IntConLevels::icls[] =
00309 {Gecode::ICL_DOM,Gecode::ICL_BND,Gecode::ICL_VAL};
00310
00311 const Gecode::IntRelType IntRelTypes::irts[] =
00312 {Gecode::IRT_EQ,Gecode::IRT_NQ,Gecode::IRT_LQ,
00313 Gecode::IRT_LE,Gecode::IRT_GQ,Gecode::IRT_GR};
00314
00315 const Gecode::BoolOpType BoolOpTypes::bots[] =
00316 {Gecode::BOT_AND,Gecode::BOT_OR,Gecode::BOT_IMP,
00317 Gecode::BOT_EQV,Gecode::BOT_XOR};
00318
00319 Assignment*
00320 Test::assignment(void) const {
00321 return new CpltAssignment(arity,dom);
00322 }
00323
00324
00326 #define CHECK_TEST(T,M) \
00327 if (opt.log) \
00328 olog << ind(3) << "Check: " << (M) << std::endl; \
00329 if (!(T)) { \
00330 problem = (M); delete s; goto failed; \
00331 }
00332
00334 #define START_TEST(T) \
00335 if (opt.log) { \
00336 olog.str(""); \
00337 olog << ind(2) << "Testing: " << (T) << std::endl; \
00338 } \
00339 test = (T);
00340
00341 bool
00342 Test::ignore(const Assignment&) const {
00343 return false;
00344 }
00345
00346 void
00347 Test::post(Gecode::Space&, Gecode::IntVarArray&,
00348 Gecode::BoolVar) {}
00349
00350 bool
00351 Test::run(void) {
00352 using namespace Gecode;
00353 const char* test = "NONE";
00354 const char* problem = "NONE";
00355
00356
00357 Assignment* ap = assignment();
00358 Assignment& a = *ap;
00359
00360
00361 TestSpace* search_s = new TestSpace(arity,dom,false,this,false);
00362 post(*search_s,search_s->x);
00363 branch(*search_s,search_s->x,INT_VAR_NONE,INT_VAL_MIN);
00364 Search::Options search_o;
00365 search_o.threads = 1;
00366 DFS<TestSpace> e_s(search_s,search_o);
00367 delete search_s;
00368
00369 while (a()) {
00370 bool sol = solution(a);
00371 if (opt.log) {
00372 olog << ind(1) << "Assignment: " << a
00373 << (sol ? " (solution)" : " (no solution)")
00374 << std::endl;
00375 }
00376
00377 START_TEST("Assignment (after posting)");
00378 {
00379 TestSpace* s = new TestSpace(arity,dom,false,this);
00380 TestSpace* sc = NULL;
00381 s->post();
00382 switch (Base::rand(3)) {
00383 case 0:
00384 if (opt.log)
00385 olog << ind(3) << "No copy" << std::endl;
00386 sc = s;
00387 s = NULL;
00388 break;
00389 case 1:
00390 if (opt.log)
00391 olog << ind(3) << "Unshared copy" << std::endl;
00392 if (s->status() != SS_FAILED) {
00393 sc = static_cast<TestSpace*>(s->clone(false));
00394 } else {
00395 sc = s; s = NULL;
00396 }
00397 break;
00398 case 2:
00399 if (opt.log)
00400 olog << ind(3) << "Shared copy" << std::endl;
00401 if (s->status() != SS_FAILED) {
00402 sc = static_cast<TestSpace*>(s->clone(true));
00403 } else {
00404 sc = s; s = NULL;
00405 }
00406 break;
00407 default: assert(false);
00408 }
00409 sc->assign(a);
00410 if (sol) {
00411 CHECK_TEST(!sc->failed(), "Failed on solution");
00412 CHECK_TEST(sc->propagators()==0, "No subsumption");
00413 } else {
00414 CHECK_TEST(sc->failed(), "Solved on non-solution");
00415 }
00416 delete s; delete sc;
00417 }
00418 START_TEST("Partial assignment (after posting)");
00419 {
00420 TestSpace* s = new TestSpace(arity,dom,false,this);
00421 s->post();
00422 s->assign(a,true);
00423 (void) s->failed();
00424 s->assign(a);
00425 if (sol) {
00426 CHECK_TEST(!s->failed(), "Failed on solution");
00427 CHECK_TEST(s->propagators()==0, "No subsumption");
00428 } else {
00429 CHECK_TEST(s->failed(), "Solved on non-solution");
00430 }
00431 delete s;
00432 }
00433 START_TEST("Assignment (before posting)");
00434 {
00435 TestSpace* s = new TestSpace(arity,dom,false,this);
00436 s->assign(a);
00437 s->post();
00438 if (sol) {
00439 CHECK_TEST(!s->failed(), "Failed on solution");
00440 CHECK_TEST(s->propagators()==0, "No subsumption");
00441 } else {
00442 CHECK_TEST(s->failed(), "Solved on non-solution");
00443 }
00444 delete s;
00445 }
00446 START_TEST("Partial assignment (before posting)");
00447 {
00448 TestSpace* s = new TestSpace(arity,dom,false,this);
00449 s->assign(a,true);
00450 s->post();
00451 (void) s->failed();
00452 s->assign(a);
00453 if (sol) {
00454 CHECK_TEST(!s->failed(), "Failed on solution");
00455 CHECK_TEST(s->propagators()==0, "No subsumption");
00456 } else {
00457 CHECK_TEST(s->failed(), "Solved on non-solution");
00458 }
00459 delete s;
00460 }
00461 START_TEST("Prune");
00462 {
00463 TestSpace* s = new TestSpace(arity,dom,false,this);
00464 s->post();
00465 while (!s->failed() && !s->assigned())
00466 if (!s->prune(a)) {
00467 problem = "No fixpoint";
00468 delete s;
00469 goto failed;
00470 }
00471 s->assign(a);
00472 if (sol) {
00473 CHECK_TEST(!s->failed(), "Failed on solution");
00474 CHECK_TEST(s->propagators()==0, "No subsumption");
00475 } else {
00476 CHECK_TEST(s->failed(), "Solved on non-solution");
00477 }
00478 delete s;
00479 }
00480
00481 if (reified && !ignore(a)) {
00482 START_TEST("Assignment reified (rewrite after post)");
00483 {
00484 TestSpace* s = new TestSpace(arity,dom,true,this);
00485 s->post();
00486 s->rel(sol);
00487 s->assign(a);
00488 CHECK_TEST(!s->failed(), "Failed");
00489 CHECK_TEST(s->propagators()==0, "No subsumption");
00490 delete s;
00491 }
00492 START_TEST("Assignment reified (immediate rewrite)");
00493 {
00494 TestSpace* s = new TestSpace(arity,dom,true,this);
00495 s->rel(sol);
00496 s->post();
00497 s->assign(a);
00498 CHECK_TEST(!s->failed(), "Failed");
00499 CHECK_TEST(s->propagators()==0, "No subsumption");
00500 delete s;
00501 }
00502 START_TEST("Assignment reified (before posting)");
00503 {
00504 TestSpace* s = new TestSpace(arity,dom,true,this);
00505 s->assign(a);
00506 s->post();
00507 CHECK_TEST(!s->failed(), "Failed");
00508 CHECK_TEST(s->propagators()==0, "No subsumption");
00509 CHECK_TEST(s->b.assigned(), "Control variable unassigned");
00510 if (sol) {
00511 CHECK_TEST(s->b.val()==1, "Zero on solution");
00512 } else {
00513 CHECK_TEST(s->b.val()==0, "One on non-solution");
00514 }
00515 delete s;
00516 }
00517 START_TEST("Assignment reified (after posting)");
00518 {
00519 TestSpace* s = new TestSpace(arity,dom,true,this);
00520 s->post();
00521 s->assign(a);
00522 CHECK_TEST(!s->failed(), "Failed");
00523 CHECK_TEST(s->propagators()==0, "No subsumption");
00524 CHECK_TEST(s->b.assigned(), "Control variable unassigned");
00525 if (sol) {
00526 CHECK_TEST(s->b.val()==1, "Zero on solution");
00527 } else {
00528 CHECK_TEST(s->b.val()==0, "One on non-solution");
00529 }
00530 delete s;
00531 }
00532 START_TEST("Prune reified");
00533 {
00534 TestSpace* s = new TestSpace(arity,dom,true,this);
00535 s->post();
00536 while (!s->failed() && (!s->assigned() || !s->b.assigned()))
00537 if (!s->prune(a)) {
00538 problem = "No fixpoint";
00539 delete s;
00540 goto failed;
00541 }
00542 CHECK_TEST(!s->failed(), "Failed");
00543 CHECK_TEST(s->propagators()==0, "No subsumption");
00544 CHECK_TEST(s->b.assigned(), "Control variable unassigned");
00545 if (sol) {
00546 CHECK_TEST(s->b.val()==1, "Zero on solution");
00547 } else {
00548 CHECK_TEST(s->b.val()==0, "One on non-solution");
00549 }
00550 delete s;
00551 }
00552 }
00553
00554 if (testsearch) {
00555 if (sol) {
00556 START_TEST("Search");
00557 TestSpace* s = e_s.next();
00558 CHECK_TEST(s != NULL, "Solutions exhausted");
00559 CHECK_TEST(s->propagators()==0, "No subsumption");
00560 for (int i=a.size(); i--; ) {
00561 CHECK_TEST(s->x[i].assigned(), "Unassigned variable");
00562 CHECK_TEST(a[i] == s->x[i].val(), "Wrong value in solution");
00563 }
00564 delete s;
00565 }
00566 }
00567
00568 ++a;
00569 }
00570
00571 if (testsearch) {
00572 test = "Search";
00573 if (e_s.next() != NULL) {
00574 problem = "Excess solutions";
00575 goto failed;
00576 }
00577 }
00578
00579 switch (contest) {
00580 case CTL_NONE: break;
00581 case CTL_DOMAIN: {
00582 START_TEST("Full domain consistency");
00583 TestSpace* s = new TestSpace(arity,dom,false,this);
00584 s->post();
00585 if (!s->failed()) {
00586 while (!s->failed() && !s->assigned())
00587 s->prune();
00588 CHECK_TEST(!s->failed(), "Failed");
00589 CHECK_TEST(s->propagators()==0, "No subsumption");
00590 }
00591 delete s;
00592
00593 }
00594 case CTL_BOUNDS_D: {
00595 START_TEST("Bounds(D)-consistency");
00596 TestSpace* s = new TestSpace(arity,dom,false,this);
00597 s->post();
00598 for (int i = s->x.size(); i--; )
00599 s->prune(i, false);
00600 if (!s->failed()) {
00601 while (!s->failed() && !s->assigned())
00602 s->bound();
00603 CHECK_TEST(!s->failed(), "Failed");
00604 CHECK_TEST(s->propagators()==0, "No subsumption");
00605 }
00606 delete s;
00607
00608 }
00609 case CTL_BOUNDS_Z: {
00610 START_TEST("Bounds(Z)-consistency");
00611 TestSpace* s = new TestSpace(arity,dom,false,this);
00612 s->post();
00613 for (int i = s->x.size(); i--; )
00614 s->prune(i, true);
00615 if (!s->failed()) {
00616 while (!s->failed() && !s->assigned())
00617 s->bound();
00618 CHECK_TEST(!s->failed(), "Failed");
00619 CHECK_TEST(s->propagators()==0, "No subsumption");
00620 }
00621 delete s;
00622 break;
00623 }
00624 }
00625
00626 delete ap;
00627 return true;
00628
00629 failed:
00630 if (opt.log)
00631 olog << "FAILURE" << std::endl
00632 << ind(1) << "Test: " << test << std::endl
00633 << ind(1) << "Problem: " << problem << std::endl;
00634 if (a() && opt.log)
00635 olog << ind(1) << "Assignment: " << a << std::endl;
00636 delete ap;
00637
00638 return false;
00639 }
00640
00641 }}
00642
00643 #undef START_TEST
00644 #undef CHECK_TEST
00645
00646