int.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * Mikael Lagerkvist <lagerkvist@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2005 00009 * Mikael Lagerkvist, 2005 00010 * 00011 * Last modified: 00012 * $Date: 2010-06-03 13:11:11 +0200 (Thu, 03 Jun 2010) $ by $Author: tack $ 00013 * $Revision: 11013 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 #include "test/int.hh" 00041 00042 #include <algorithm> 00043 00044 namespace Test { namespace Int { 00045 00046 00047 /* 00048 * Complete assignments 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 * Random assignments 00064 * 00065 */ 00066 void 00067 RandomAssignment::operator++(void) { 00068 for (int i = n; i--; ) 00069 vals[i]=randval(); 00070 a--; 00071 } 00072 00073 void 00074 RandomMixAssignment::operator++(void) { 00075 for (int i=n-_n1; i--; ) 00076 vals[i] = randval(d); 00077 for (int i=_n1; i--; ) 00078 vals[n-_n1+i] = randval(_d1); 00079 a--; 00080 } 00081 00082 }} 00083 00084 std::ostream& 00085 operator<<(std::ostream& os, const Test::Int::Assignment& a) { 00086 int n = a.size(); 00087 os << "{"; 00088 for (int i=0; i<n; i++) 00089 os << a[i] << ((i!=n-1) ? "," : "}"); 00090 return os; 00091 } 00092 00093 namespace Test { namespace Int { 00094 00095 TestSpace::TestSpace(int n, Gecode::IntSet& d0, bool r, Test* t, bool log) 00096 : d(d0), x(*this,n,d), b(*this,0,1), reified(r), test(t) { 00097 if (opt.log && log) { 00098 olog << ind(2) << "Initial: x[]=" << x; 00099 if (reified) 00100 olog << " b=" << b; 00101 olog << std::endl; 00102 } 00103 } 00104 00105 TestSpace::TestSpace(bool share, TestSpace& s) 00106 : Gecode::Space(share,s), d(s.d), reified(s.reified), test(s.test) { 00107 x.update(*this, share, s.x); 00108 b.update(*this, share, s.b); 00109 } 00110 00111 Gecode::Space* 00112 TestSpace::copy(bool share) { 00113 return new TestSpace(share,*this); 00114 } 00115 00116 bool 00117 TestSpace::assigned(void) const { 00118 for (int i=x.size(); i--; ) 00119 if (!x[i].assigned()) 00120 return false; 00121 return true; 00122 } 00123 00124 void 00125 TestSpace::post(void) { 00126 if (reified){ 00127 test->post(*this,x,b); 00128 if (opt.log) 00129 olog << ind(3) << "Posting reified propagator" << std::endl; 00130 } else { 00131 test->post(*this,x); 00132 if (opt.log) 00133 olog << ind(3) << "Posting propagator" << std::endl; 00134 } 00135 } 00136 00137 bool 00138 TestSpace::failed(void) { 00139 if (opt.log) { 00140 olog << ind(3) << "Fixpoint: " << x; 00141 bool f=(status() == Gecode::SS_FAILED); 00142 olog << std::endl << ind(3) << " --> " << x << std::endl; 00143 return f; 00144 } else { 00145 return status() == Gecode::SS_FAILED; 00146 } 00147 } 00148 00149 void 00150 TestSpace::rel(int i, Gecode::IntRelType irt, int n) { 00151 if (opt.log) { 00152 olog << ind(4) << "x[" << i << "] "; 00153 switch (irt) { 00154 case Gecode::IRT_EQ: olog << "="; break; 00155 case Gecode::IRT_NQ: olog << "!="; break; 00156 case Gecode::IRT_LQ: olog << "<="; break; 00157 case Gecode::IRT_LE: olog << "<"; break; 00158 case Gecode::IRT_GQ: olog << ">="; break; 00159 case Gecode::IRT_GR: olog << ">"; break; 00160 } 00161 olog << " " << n << std::endl; 00162 } 00163 Gecode::rel(*this, x[i], irt, n); 00164 } 00165 00166 void 00167 TestSpace::rel(bool sol) { 00168 int n = sol ? 1 : 0; 00169 assert(reified); 00170 if (opt.log) 00171 olog << ind(4) << "b = " << n << std::endl; 00172 Gecode::rel(*this, b, Gecode::IRT_EQ, n); 00173 } 00174 00175 void 00176 TestSpace::assign(const Assignment& a, bool skip) { 00177 using namespace Gecode; 00178 int i = skip ? static_cast<int>(Base::rand(a.size())) : -1; 00179 for (int j=a.size(); j--; ) 00180 if (i != j) { 00181 rel(j, IRT_EQ, a[j]); 00182 if (Base::fixpoint() && failed()) 00183 return; 00184 } 00185 } 00186 00187 void 00188 TestSpace::bound(void) { 00189 using namespace Gecode; 00190 // Select variable to be assigned 00191 int i = Base::rand(x.size()); 00192 while (x[i].assigned()) { 00193 i = (i+1) % x.size(); 00194 } 00195 bool min = Base::rand(2); 00196 rel(i, IRT_EQ, min ? x[i].min() : x[i].max()); 00197 } 00198 00199 void 00200 TestSpace::prune(int i, bool bounds_only) { 00201 using namespace Gecode; 00202 // Prune values 00203 if (bounds_only) { 00204 if (Base::rand(2) && !x[i].assigned()) { 00205 int v=x[i].min()+1+Base::rand(static_cast 00206 <unsigned int>(x[i].max()-x[i].min())); 00207 assert((v > x[i].min()) && (v <= x[i].max())); 00208 rel(i, Gecode::IRT_LE, v); 00209 } 00210 if (Base::rand(2) && !x[i].assigned()) { 00211 int v=x[i].min()+Base::rand(static_cast 00212 <unsigned int>(x[i].max()-x[i].min())); 00213 assert((v < x[i].max()) && (v >= x[i].min())); 00214 rel(i, Gecode::IRT_GR, v); 00215 } 00216 } else { 00217 for (int vals = Base::rand(x[i].size()-1)+1; vals--; ) { 00218 int v; 00219 Gecode::Int::ViewRanges<Gecode::Int::IntView> it(x[i]); 00220 unsigned int skip = Base::rand(x[i].size()-1); 00221 while (true) { 00222 if (it.width() > skip) { 00223 v = it.min() + skip; break; 00224 } 00225 skip -= it.width(); ++it; 00226 } 00227 rel(i, IRT_NQ, v); 00228 } 00229 } 00230 } 00231 00232 void 00233 TestSpace::prune(void) { 00234 using namespace Gecode; 00235 // Select variable to be pruned 00236 int i = Base::rand(x.size()); 00237 while (x[i].assigned()) { 00238 i = (i+1) % x.size(); 00239 } 00240 prune(i, false); 00241 } 00242 00243 bool 00244 TestSpace::prune(const Assignment& a, bool testfix) { 00245 // Select variable to be pruned 00246 int i = Base::rand(x.size()); 00247 while (x[i].assigned()) 00248 i = (i+1) % x.size(); 00249 // Select mode for pruning 00250 switch (Base::rand(3)) { 00251 case 0: 00252 if (a[i] < x[i].max()) { 00253 int v=a[i]+1+Base::rand(static_cast 00254 <unsigned int>(x[i].max()-a[i])); 00255 assert((v > a[i]) && (v <= x[i].max())); 00256 rel(i, Gecode::IRT_LE, v); 00257 } 00258 break; 00259 case 1: 00260 if (a[i] > x[i].min()) { 00261 int v=x[i].min()+Base::rand(static_cast 00262 <unsigned int>(a[i]-x[i].min())); 00263 assert((v < a[i]) && (v >= x[i].min())); 00264 rel(i, Gecode::IRT_GR, v); 00265 } 00266 break; 00267 default: 00268 { 00269 int v; 00270 Gecode::Int::ViewRanges<Gecode::Int::IntView> it(x[i]); 00271 unsigned int skip = Base::rand(x[i].size()-1); 00272 while (true) { 00273 if (it.width() > skip) { 00274 v = it.min() + skip; 00275 if (v == a[i]) { 00276 if (it.width() == 1) { 00277 ++it; v = it.min(); 00278 } else if (v < it.max()) { 00279 ++v; 00280 } else { 00281 --v; 00282 } 00283 } 00284 break; 00285 } 00286 skip -= it.width(); ++it; 00287 } 00288 rel(i, Gecode::IRT_NQ, v); 00289 break; 00290 } 00291 } 00292 if (Base::fixpoint()) { 00293 if (failed() || !testfix) 00294 return true; 00295 TestSpace* c = static_cast<TestSpace*>(clone()); 00296 if (opt.log) 00297 olog << ind(3) << "Testing fixpoint on copy" << std::endl; 00298 c->post(); 00299 if (c->failed()) { 00300 delete c; return false; 00301 } 00302 for (int i=x.size(); i--; ) 00303 if (x[i].size() != c->x[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 } 00313 return true; 00314 } 00315 00316 00317 const Gecode::IntConLevel IntConLevels::icls[] = 00318 {Gecode::ICL_DOM,Gecode::ICL_BND,Gecode::ICL_VAL}; 00319 00320 const Gecode::IntRelType IntRelTypes::irts[] = 00321 {Gecode::IRT_EQ,Gecode::IRT_NQ,Gecode::IRT_LQ, 00322 Gecode::IRT_LE,Gecode::IRT_GQ,Gecode::IRT_GR}; 00323 00324 const Gecode::BoolOpType BoolOpTypes::bots[] = 00325 {Gecode::BOT_AND,Gecode::BOT_OR,Gecode::BOT_IMP, 00326 Gecode::BOT_EQV,Gecode::BOT_XOR}; 00327 00328 Assignment* 00329 Test::assignment(void) const { 00330 return new CpltAssignment(arity,dom); 00331 } 00332 00333 00335 #define CHECK_TEST(T,M) \ 00336 if (opt.log) \ 00337 olog << ind(3) << "Check: " << (M) << std::endl; \ 00338 if (!(T)) { \ 00339 problem = (M); delete s; goto failed; \ 00340 } 00341 00343 #define START_TEST(T) \ 00344 if (opt.log) { \ 00345 olog.str(""); \ 00346 olog << ind(2) << "Testing: " << (T) << std::endl; \ 00347 } \ 00348 test = (T); 00349 00350 bool 00351 Test::ignore(const Assignment&) const { 00352 return false; 00353 } 00354 00355 void 00356 Test::post(Gecode::Space&, Gecode::IntVarArray&, 00357 Gecode::BoolVar) {} 00358 00359 bool 00360 Test::run(void) { 00361 using namespace Gecode; 00362 const char* test = "NONE"; 00363 const char* problem = "NONE"; 00364 00365 // Set up assignments 00366 Assignment* ap = assignment(); 00367 Assignment& a = *ap; 00368 00369 // Set up space for all solution search 00370 TestSpace* search_s = new TestSpace(arity,dom,false,this,false); 00371 post(*search_s,search_s->x); 00372 branch(*search_s,search_s->x,INT_VAR_NONE,INT_VAL_MIN); 00373 Search::Options search_o; 00374 search_o.threads = 1; 00375 DFS<TestSpace> e_s(search_s,search_o); 00376 delete search_s; 00377 00378 while (a()) { 00379 bool sol = solution(a); 00380 if (opt.log) { 00381 olog << ind(1) << "Assignment: " << a 00382 << (sol ? " (solution)" : " (no solution)") 00383 << std::endl; 00384 } 00385 00386 START_TEST("Assignment (after posting)"); 00387 { 00388 TestSpace* s = new TestSpace(arity,dom,false,this); 00389 TestSpace* sc = NULL; 00390 s->post(); 00391 switch (Base::rand(3)) { 00392 case 0: 00393 if (opt.log) 00394 olog << ind(3) << "No copy" << std::endl; 00395 sc = s; 00396 s = NULL; 00397 break; 00398 case 1: 00399 if (opt.log) 00400 olog << ind(3) << "Unshared copy" << std::endl; 00401 if (s->status() != SS_FAILED) { 00402 sc = static_cast<TestSpace*>(s->clone(false)); 00403 } else { 00404 sc = s; s = NULL; 00405 } 00406 break; 00407 case 2: 00408 if (opt.log) 00409 olog << ind(3) << "Shared copy" << std::endl; 00410 if (s->status() != SS_FAILED) { 00411 sc = static_cast<TestSpace*>(s->clone(true)); 00412 } else { 00413 sc = s; s = NULL; 00414 } 00415 break; 00416 default: assert(false); 00417 } 00418 sc->assign(a); 00419 if (sol) { 00420 CHECK_TEST(!sc->failed(), "Failed on solution"); 00421 CHECK_TEST(sc->propagators()==0, "No subsumption"); 00422 } else { 00423 CHECK_TEST(sc->failed(), "Solved on non-solution"); 00424 } 00425 delete s; delete sc; 00426 } 00427 START_TEST("Partial assignment (after posting)"); 00428 { 00429 TestSpace* s = new TestSpace(arity,dom,false,this); 00430 s->post(); 00431 s->assign(a,true); 00432 (void) s->failed(); 00433 s->assign(a); 00434 if (sol) { 00435 CHECK_TEST(!s->failed(), "Failed on solution"); 00436 CHECK_TEST(s->propagators()==0, "No subsumption"); 00437 } else { 00438 CHECK_TEST(s->failed(), "Solved on non-solution"); 00439 } 00440 delete s; 00441 } 00442 START_TEST("Assignment (before posting)"); 00443 { 00444 TestSpace* s = new TestSpace(arity,dom,false,this); 00445 s->assign(a); 00446 s->post(); 00447 if (sol) { 00448 CHECK_TEST(!s->failed(), "Failed on solution"); 00449 CHECK_TEST(s->propagators()==0, "No subsumption"); 00450 } else { 00451 CHECK_TEST(s->failed(), "Solved on non-solution"); 00452 } 00453 delete s; 00454 } 00455 START_TEST("Partial assignment (before posting)"); 00456 { 00457 TestSpace* s = new TestSpace(arity,dom,false,this); 00458 s->assign(a,true); 00459 s->post(); 00460 (void) s->failed(); 00461 s->assign(a); 00462 if (sol) { 00463 CHECK_TEST(!s->failed(), "Failed on solution"); 00464 CHECK_TEST(s->propagators()==0, "No subsumption"); 00465 } else { 00466 CHECK_TEST(s->failed(), "Solved on non-solution"); 00467 } 00468 delete s; 00469 } 00470 START_TEST("Prune"); 00471 { 00472 TestSpace* s = new TestSpace(arity,dom,false,this); 00473 s->post(); 00474 while (!s->failed() && !s->assigned()) 00475 if (!s->prune(a,testfix)) { 00476 problem = "No fixpoint"; 00477 delete s; 00478 goto failed; 00479 } 00480 s->assign(a); 00481 if (sol) { 00482 CHECK_TEST(!s->failed(), "Failed on solution"); 00483 CHECK_TEST(s->propagators()==0, "No subsumption"); 00484 } else { 00485 CHECK_TEST(s->failed(), "Solved on non-solution"); 00486 } 00487 delete s; 00488 } 00489 00490 if (reified && !ignore(a)) { 00491 START_TEST("Assignment reified (rewrite after post)"); 00492 { 00493 TestSpace* s = new TestSpace(arity,dom,true,this); 00494 s->post(); 00495 s->rel(sol); 00496 s->assign(a); 00497 CHECK_TEST(!s->failed(), "Failed"); 00498 CHECK_TEST(s->propagators()==0, "No subsumption"); 00499 delete s; 00500 } 00501 START_TEST("Assignment reified (immediate rewrite)"); 00502 { 00503 TestSpace* s = new TestSpace(arity,dom,true,this); 00504 s->rel(sol); 00505 s->post(); 00506 s->assign(a); 00507 CHECK_TEST(!s->failed(), "Failed"); 00508 CHECK_TEST(s->propagators()==0, "No subsumption"); 00509 delete s; 00510 } 00511 START_TEST("Assignment reified (before posting)"); 00512 { 00513 TestSpace* s = new TestSpace(arity,dom,true,this); 00514 s->assign(a); 00515 s->post(); 00516 CHECK_TEST(!s->failed(), "Failed"); 00517 CHECK_TEST(s->propagators()==0, "No subsumption"); 00518 CHECK_TEST(s->b.assigned(), "Control variable unassigned"); 00519 if (sol) { 00520 CHECK_TEST(s->b.val()==1, "Zero on solution"); 00521 } else { 00522 CHECK_TEST(s->b.val()==0, "One on non-solution"); 00523 } 00524 delete s; 00525 } 00526 START_TEST("Assignment reified (after posting)"); 00527 { 00528 TestSpace* s = new TestSpace(arity,dom,true,this); 00529 s->post(); 00530 s->assign(a); 00531 CHECK_TEST(!s->failed(), "Failed"); 00532 CHECK_TEST(s->propagators()==0, "No subsumption"); 00533 CHECK_TEST(s->b.assigned(), "Control variable unassigned"); 00534 if (sol) { 00535 CHECK_TEST(s->b.val()==1, "Zero on solution"); 00536 } else { 00537 CHECK_TEST(s->b.val()==0, "One on non-solution"); 00538 } 00539 delete s; 00540 } 00541 START_TEST("Prune reified"); 00542 { 00543 TestSpace* s = new TestSpace(arity,dom,true,this); 00544 s->post(); 00545 while (!s->failed() && (!s->assigned() || !s->b.assigned())) 00546 if (!s->prune(a,testfix)) { 00547 problem = "No fixpoint"; 00548 delete s; 00549 goto failed; 00550 } 00551 CHECK_TEST(!s->failed(), "Failed"); 00552 CHECK_TEST(s->propagators()==0, "No subsumption"); 00553 CHECK_TEST(s->b.assigned(), "Control variable unassigned"); 00554 if (sol) { 00555 CHECK_TEST(s->b.val()==1, "Zero on solution"); 00556 } else { 00557 CHECK_TEST(s->b.val()==0, "One on non-solution"); 00558 } 00559 delete s; 00560 } 00561 } 00562 00563 if (testsearch) { 00564 if (sol) { 00565 START_TEST("Search"); 00566 TestSpace* s = e_s.next(); 00567 CHECK_TEST(s != NULL, "Solutions exhausted"); 00568 CHECK_TEST(s->propagators()==0, "No subsumption"); 00569 for (int i=a.size(); i--; ) { 00570 CHECK_TEST(s->x[i].assigned(), "Unassigned variable"); 00571 CHECK_TEST(a[i] == s->x[i].val(), "Wrong value in solution"); 00572 } 00573 delete s; 00574 } 00575 } 00576 00577 ++a; 00578 } 00579 00580 if (testsearch) { 00581 test = "Search"; 00582 if (e_s.next() != NULL) { 00583 problem = "Excess solutions"; 00584 goto failed; 00585 } 00586 } 00587 00588 switch (contest) { 00589 case CTL_NONE: break; 00590 case CTL_DOMAIN: { 00591 START_TEST("Full domain consistency"); 00592 TestSpace* s = new TestSpace(arity,dom,false,this); 00593 s->post(); 00594 if (!s->failed()) { 00595 while (!s->failed() && !s->assigned()) 00596 s->prune(); 00597 CHECK_TEST(!s->failed(), "Failed"); 00598 CHECK_TEST(s->propagators()==0, "No subsumption"); 00599 } 00600 delete s; 00601 // Fall-through -- domain implies bounds(d) and bounds(z) 00602 } 00603 case CTL_BOUNDS_D: { 00604 START_TEST("Bounds(D)-consistency"); 00605 TestSpace* s = new TestSpace(arity,dom,false,this); 00606 s->post(); 00607 for (int i = s->x.size(); i--; ) 00608 s->prune(i, false); 00609 if (!s->failed()) { 00610 while (!s->failed() && !s->assigned()) 00611 s->bound(); 00612 CHECK_TEST(!s->failed(), "Failed"); 00613 CHECK_TEST(s->propagators()==0, "No subsumption"); 00614 } 00615 delete s; 00616 // Fall-through -- bounds(d) implies bounds(z) 00617 } 00618 case CTL_BOUNDS_Z: { 00619 START_TEST("Bounds(Z)-consistency"); 00620 TestSpace* s = new TestSpace(arity,dom,false,this); 00621 s->post(); 00622 for (int i = s->x.size(); i--; ) 00623 s->prune(i, true); 00624 if (!s->failed()) { 00625 while (!s->failed() && !s->assigned()) 00626 s->bound(); 00627 CHECK_TEST(!s->failed(), "Failed"); 00628 CHECK_TEST(s->propagators()==0, "No subsumption"); 00629 } 00630 delete s; 00631 break; 00632 } 00633 } 00634 00635 delete ap; 00636 return true; 00637 00638 failed: 00639 if (opt.log) 00640 olog << "FAILURE" << std::endl 00641 << ind(1) << "Test: " << test << std::endl 00642 << ind(1) << "Problem: " << problem << std::endl; 00643 if (a() && opt.log) 00644 olog << ind(1) << "Assignment: " << a << std::endl; 00645 delete ap; 00646 00647 return false; 00648 } 00649 00650 }} 00651 00652 #undef START_TEST 00653 #undef CHECK_TEST 00654 00655 // STATISTICS: test-int