set.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * Christian Schulte <schulte@gecode.org> 00006 * Mikael Lagerkvist <lagerkvist@gecode.org> 00007 * 00008 * Copyright: 00009 * Guido Tack, 2005 00010 * Christian Schulte, 2005 00011 * Mikael Lagerkvist, 2005 00012 * 00013 * Last modified: 00014 * $Date: 2009-05-14 19:35:46 +0200 (Thu, 14 May 2009) $ by $Author: tack $ 00015 * $Revision: 9118 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 // Select variable to be pruned 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 // Prune int var 00348 00349 // Select mode for pruning 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 // Select mode for pruning 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 // STATISTICS: test-set