Generated on Thu Apr 11 13:59:13 2019 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #include "test/int.hh"
00037 
00038 #include <algorithm>
00039 
00040 namespace Test { namespace Int {
00041 
00042 
00043   /*
00044    * Complete assignments
00045    *
00046    */
00047   void
00048   CpltAssignment::operator++(void) {
00049     int i = n-1;
00050     while (true) {
00051       ++dsv[i];
00052       if (dsv[i]() || (i == 0))
00053         return;
00054       dsv[i--].init(d);
00055     }
00056   }
00057 
00058   /*
00059    * Random assignments
00060    *
00061    */
00062   void
00063   RandomAssignment::operator++(void) {
00064     for (int i = n; i--; )
00065       vals[i]=randval();
00066     a--;
00067   }
00068 
00069   void
00070   RandomMixAssignment::operator++(void) {
00071     for (int i=n-_n1; i--; )
00072       vals[i] = randval(d);
00073     for (int i=_n1; i--; )
00074       vals[n-_n1+i] = randval(_d1);
00075     a--;
00076   }
00077 
00078 }}
00079 
00080 std::ostream&
00081 operator<<(std::ostream& os, const Test::Int::Assignment& a) {
00082   int n = a.size();
00083   os << "{";
00084   for (int i=0; i<n; i++)
00085     os << a[i] << ((i!=n-1) ? "," : "}");
00086   return os;
00087 }
00088 
00089 namespace Test { namespace Int {
00090 
00091   TestSpace::TestSpace(int n, Gecode::IntSet& d0, Test* t)
00092     : d(d0), x(*this,n,Gecode::Int::Limits::min,Gecode::Int::Limits::max),
00093       test(t), reified(false) {
00094     Gecode::IntVarArgs _x(*this,n,d);
00095     if (x.size() == 1)
00096       Gecode::dom(*this,x[0],_x[0]);
00097     else
00098       Gecode::dom(*this,x,_x);
00099     Gecode::BoolVar b(*this,0,1);
00100     r = Gecode::Reify(b,Gecode::RM_EQV);
00101     if (opt.log)
00102       olog << ind(2) << "Initial: x[]=" << x
00103            << std::endl;
00104   }
00105 
00106   TestSpace::TestSpace(int n, Gecode::IntSet& d0, Test* t,
00107                        Gecode::ReifyMode rm)
00108     : d(d0), x(*this,n,Gecode::Int::Limits::min,Gecode::Int::Limits::max),
00109       test(t), reified(true) {
00110     Gecode::IntVarArgs _x(*this,n,d);
00111     if (x.size() == 1)
00112       Gecode::dom(*this,x[0],_x[0]);
00113     else
00114       Gecode::dom(*this,x,_x);
00115     Gecode::BoolVar b(*this,0,1);
00116     r = Gecode::Reify(b,rm);
00117     if (opt.log)
00118       olog << ind(2) << "Initial: x[]=" << x
00119            << " b=" << r.var() << std::endl;
00120   }
00121 
00122   TestSpace::TestSpace(TestSpace& s)
00123     : Gecode::Space(s), d(s.d), test(s.test), reified(s.reified) {
00124     x.update(*this, s.x);
00125     Gecode::BoolVar b;
00126     Gecode::BoolVar sr(s.r.var());
00127     b.update(*this, sr);
00128     r.var(b); r.mode(s.r.mode());
00129   }
00130 
00131   Gecode::Space*
00132   TestSpace::copy(void) {
00133     return new TestSpace(*this);
00134   }
00135 
00136   bool
00137   TestSpace::assigned(void) const {
00138     for (int i=x.size(); i--; )
00139       if (!x[i].assigned())
00140         return false;
00141     return true;
00142   }
00143 
00144   void
00145   TestSpace::post(void) {
00146     if (reified){
00147       test->post(*this,x,r);
00148       if (opt.log)
00149         olog << ind(3) << "Posting reified propagator" << std::endl;
00150     } else {
00151       test->post(*this,x);
00152       if (opt.log)
00153         olog << ind(3) << "Posting propagator" << std::endl;
00154     }
00155   }
00156 
00157   bool
00158   TestSpace::failed(void) {
00159     if (opt.log) {
00160       olog << ind(3) << "Fixpoint: " << x;
00161       bool f=(status() == Gecode::SS_FAILED);
00162       olog << std::endl << ind(3) << "     -->  " << x << std::endl;
00163       return f;
00164     } else {
00165       return status() == Gecode::SS_FAILED;
00166     }
00167   }
00168 
00169   int
00170   TestSpace::rndvar(void) {
00171     assert(!assigned());
00172     // Select variable to be pruned
00173     int i = static_cast<int>(Base::rand(static_cast<unsigned int>(x.size())));
00174     while (x[i].assigned()) {
00175       i = (i+1) % x.size();
00176     }
00177     return i;
00178   }
00179 
00180   void
00181   TestSpace::rndrel(const Assignment& a, int i,
00182                     Gecode::IntRelType& irt, int& v) {
00183     using namespace Gecode;
00184     // Select mode for pruning
00185     irt = IRT_EQ; // Means do nothing!
00186     switch (Base::rand(3)) {
00187     case 0:
00188       if (a[i] < x[i].max()) {
00189         v=a[i]+1+
00190           static_cast<int>(Base::rand(static_cast
00191                                       <unsigned int>(x[i].max()-a[i])));
00192         assert((v > a[i]) && (v <= x[i].max()));
00193         irt = IRT_LE;
00194       }
00195       break;
00196     case 1:
00197       if (a[i] > x[i].min()) {
00198         v=x[i].min()+
00199           static_cast<int>(Base::rand(static_cast
00200                                       <unsigned int>(a[i]-x[i].min())));
00201         assert((v < a[i]) && (v >= x[i].min()));
00202         irt = IRT_GR;
00203       }
00204       break;
00205     default:
00206       {
00207         Gecode::Int::ViewRanges<Gecode::Int::IntView> it(x[i]);
00208         unsigned int skip = 
00209           Base::rand(static_cast<unsigned int>(x[i].size()-1));
00210         while (true) {
00211           if (it.width() > skip) {
00212             v = it.min() + static_cast<int>(skip);
00213             if (v == a[i]) {
00214               if (it.width() == 1) {
00215                 ++it; v = it.min();
00216               } else if (v < it.max()) {
00217                 ++v;
00218               } else {
00219                 --v;
00220               }
00221             }
00222             break;
00223           }
00224           skip -= it.width(); ++it;
00225         }
00226         irt = IRT_NQ;
00227         break;
00228       }
00229     }
00230   }
00231 
00232   void
00233   TestSpace::rel(int i, Gecode::IntRelType irt, int n) {
00234     if (opt.log) {
00235       olog << ind(4) << "x[" << i << "] ";
00236       switch (irt) {
00237       case Gecode::IRT_EQ: olog << "="; break;
00238       case Gecode::IRT_NQ: olog << "!="; break;
00239       case Gecode::IRT_LQ: olog << "<="; break;
00240       case Gecode::IRT_LE: olog << "<"; break;
00241       case Gecode::IRT_GQ: olog << ">="; break;
00242       case Gecode::IRT_GR: olog << ">"; break;
00243       }
00244       olog << " " << n << std::endl;
00245     }
00246     Gecode::rel(*this, x[i], irt, n);
00247   }
00248 
00249   void
00250   TestSpace::rel(bool sol) {
00251     int n = sol ? 1 : 0;
00252     assert(reified);
00253     if (opt.log)
00254       olog << ind(4) << "b = " << n << std::endl;
00255     Gecode::rel(*this, r.var(), Gecode::IRT_EQ, n);
00256   }
00257 
00258   void
00259   TestSpace::assign(const Assignment& a, bool skip) {
00260     using namespace Gecode;
00261     int i = skip ? 
00262       static_cast<int>(Base::rand(static_cast<unsigned int>(a.size()))) : -1;
00263     for (int j=a.size(); j--; )
00264       if (i != j) {
00265         rel(j, IRT_EQ, a[j]);
00266         if (Base::fixpoint() && failed())
00267           return;
00268       }
00269   }
00270 
00271   void
00272   TestSpace::bound(void) {
00273     using namespace Gecode;
00274     int i = rndvar();
00275     bool min = Base::rand(2);
00276     rel(i, IRT_EQ, min ? x[i].min() : x[i].max());
00277   }
00278 
00279   void
00280   TestSpace::prune(int i, bool bounds_only) {
00281     using namespace Gecode;
00282     // Prune values
00283     if (bounds_only) {
00284       if (Base::rand(2) && !x[i].assigned()) {
00285         int v=x[i].min()+1+
00286           static_cast<int>(Base::rand(static_cast
00287                                       <unsigned int>(x[i].max()-x[i].min())));
00288         assert((v > x[i].min()) && (v <= x[i].max()));
00289         rel(i, Gecode::IRT_LE, v);
00290       }
00291       if (Base::rand(2) && !x[i].assigned()) {
00292         int v=x[i].min()+
00293           static_cast<int>(Base::rand(static_cast
00294                                       <unsigned int>(x[i].max()-x[i].min())));
00295         assert((v < x[i].max()) && (v >= x[i].min()));
00296         rel(i, Gecode::IRT_GR, v);
00297       }
00298     } else {
00299       for (int vals = 
00300              static_cast<int>(Base::rand(static_cast<unsigned int>(x[i].size()-1))+1); vals--; ) {
00301         int v;
00302         Gecode::Int::ViewRanges<Gecode::Int::IntView> it(x[i]);
00303         unsigned int skip = Base::rand(x[i].size()-1);
00304         while (true) {
00305           if (it.width() > skip) {
00306             v = it.min() + static_cast<int>(skip); break;
00307           }
00308           skip -= it.width(); ++it;
00309         }
00310         rel(i, IRT_NQ, v);
00311       }
00312     }
00313   }
00314 
00315   void
00316   TestSpace::prune(void) {
00317     prune(rndvar(), false);
00318   }
00319 
00320   bool
00321   TestSpace::prune(const Assignment& a, bool testfix) {
00322     using namespace Gecode;
00323     // Select variable to be pruned
00324     int i = rndvar();
00325     // Select mode for pruning
00326     IntRelType irt;
00327     int v;
00328     rndrel(a,i,irt,v);
00329     if (irt != IRT_EQ)
00330       rel(i, irt, v);
00331     if (Base::fixpoint()) {
00332       if (failed() || !testfix)
00333         return true;
00334       TestSpace* c = static_cast<TestSpace*>(clone());
00335       if (opt.log)
00336         olog << ind(3) << "Testing fixpoint on copy" << std::endl;
00337       c->post();
00338       if (c->failed()) {
00339         if (opt.log)
00340           olog << ind(4) << "Copy failed after posting" << std::endl;
00341         delete c; return false;
00342       }
00343       for (int j=x.size(); j--; )
00344         if (x[j].size() != c->x[j].size()) {
00345           if (opt.log)
00346             olog << ind(4) << "Different domain size" << std::endl;
00347           delete c; return false;
00348         }
00349       if (reified && (r.var().size() != c->r.var().size())) {
00350         if (opt.log)
00351           olog << ind(4) << "Different control variable" << std::endl;
00352         delete c; return false;
00353       }
00354       if (opt.log)
00355         olog << ind(3) << "Finished testing fixpoint on copy" << std::endl;
00356       delete c;
00357     }
00358     return true;
00359   }
00360 
00361   void
00362   TestSpace::enable(void) {
00363     Gecode::PropagatorGroup::all.enable(*this);
00364   }
00365 
00366   void
00367   TestSpace::disable(void) {
00368     Gecode::PropagatorGroup::all.disable(*this);
00369     (void) status();
00370   }
00371 
00372   bool
00373   TestSpace::disabled(const Assignment& a, TestSpace& c,
00374                       bool testfix) {
00375     using namespace Gecode;
00376     // Disable propagators
00377     c.disable();
00378     // Select variable to be pruned
00379     int i = rndvar();
00380     // Select mode for pruning
00381     IntRelType irt;
00382     int v;
00383     rndrel(a,i,irt,v);
00384     if (irt != IRT_EQ) {
00385       rel(i, irt, v);
00386       c.rel(i, irt, v);
00387     }
00388     // Enable propagators
00389     c.enable();
00390     if (!testfix)
00391       return true;
00392     if (failed()) {
00393       if (!c.failed()) {
00394         if (opt.log)
00395           olog << ind(3) << "No failure on disabled copy" << std::endl;
00396         return false;
00397       }
00398       return true;
00399     }
00400     if (c.failed()) {
00401       if (opt.log)
00402         olog << ind(3) << "Failure on disabled copy" << std::endl;
00403       return false;
00404     }
00405     for (int j=x.size(); j--; ) {
00406       if (x[j].size() != c.x[j].size()) {
00407         if (opt.log)
00408           olog << ind(4) << "Different domain size" << std::endl;
00409         return false;
00410       }
00411       if (reified && (r.var().size() != c.r.var().size())) {
00412         if (opt.log)
00413           olog << ind(4) << "Different control variable" << std::endl;
00414         return false;
00415       }
00416     }
00417     return true;
00418   }
00419 
00420   unsigned int
00421   TestSpace::propagators(void) {
00422     return Gecode::PropagatorGroup::all.size(*this);
00423   }
00424 
00425   const Gecode::IntPropLevel IntPropLevels::ipls[] =
00426     {Gecode::IPL_DOM,Gecode::IPL_BND,Gecode::IPL_VAL};
00427 
00428   const Gecode::IntPropLevel IntPropBasicAdvanced::ipls[] =
00429     {Gecode::IPL_BASIC_ADVANCED,Gecode::IPL_ADVANCED,Gecode::IPL_BASIC};
00430 
00431   const Gecode::IntRelType IntRelTypes::irts[] =
00432     {Gecode::IRT_EQ,Gecode::IRT_NQ,Gecode::IRT_LQ,
00433      Gecode::IRT_LE,Gecode::IRT_GQ,Gecode::IRT_GR};
00434 
00435   const Gecode::BoolOpType BoolOpTypes::bots[] =
00436     {Gecode::BOT_AND,Gecode::BOT_OR,Gecode::BOT_IMP,
00437      Gecode::BOT_EQV,Gecode::BOT_XOR};
00438 
00439   Assignment*
00440   Test::assignment(void) const {
00441     return new CpltAssignment(arity,dom);
00442   }
00443 
00444 
00446 #define CHECK_TEST(T,M)                                         \
00447 if (opt.log)                                                    \
00448   olog << ind(3) << "Check: " << (M) << std::endl;              \
00449 if (!(T)) {                                                     \
00450   problem = (M); delete s; goto failed;                         \
00451 }
00452 
00454 #define START_TEST(T)                                           \
00455   if (opt.log) {                                                \
00456      olog.str("");                                              \
00457      olog << ind(2) << "Testing: " << (T) << std::endl;         \
00458   }                                                             \
00459   test = (T);
00460 
00461   bool
00462   Test::ignore(const Assignment&) const {
00463     return false;
00464   }
00465 
00466   void
00467   Test::post(Gecode::Space&, Gecode::IntVarArray&,
00468              Gecode::Reify) {}
00469 
00470   bool
00471   Test::run(void) {
00472     using namespace Gecode;
00473     const char* test    = "NONE";
00474     const char* problem = "NONE";
00475 
00476     // Set up assignments
00477     Assignment* ap = assignment();
00478     Assignment& a = *ap;
00479 
00480     // Set up space for all solution search
00481     TestSpace* search_s = new TestSpace(arity,dom,this);
00482     post(*search_s,search_s->x);
00483     branch(*search_s,search_s->x,INT_VAR_NONE(),INT_VAL_MIN());
00484     Search::Options search_o;
00485     search_o.threads = 1;
00486     DFS<TestSpace> e_s(search_s,search_o);
00487     delete search_s;
00488 
00489     while (a()) {
00490       bool sol = solution(a);
00491       if (opt.log) {
00492         olog << ind(1) << "Assignment: " << a
00493              << (sol ? " (solution)" : " (no solution)")
00494              << std::endl;
00495       }
00496 
00497       START_TEST("Assignment (after posting)");
00498       {
00499         TestSpace* s = new TestSpace(arity,dom,this);
00500         TestSpace* sc = NULL;
00501         s->post();
00502         switch (Base::rand(2)) {
00503           case 0:
00504             if (opt.log)
00505               olog << ind(3) << "No copy" << std::endl;
00506             sc = s;
00507             s = NULL;
00508             break;
00509           case 1:
00510             if (opt.log)
00511               olog << ind(3) << "Copy" << std::endl;
00512             if (s->status() != SS_FAILED) {
00513               sc = static_cast<TestSpace*>(s->clone());
00514             } else {
00515               sc = s; s = NULL;
00516             }
00517             break;
00518           default: assert(false);
00519         }
00520         sc->assign(a);
00521         if (sol) {
00522           CHECK_TEST(!sc->failed(), "Failed on solution");
00523           CHECK_TEST(sc->propagators()==0, "No subsumption");
00524         } else {
00525           CHECK_TEST(sc->failed(), "Solved on non-solution");
00526         }
00527         delete s; delete sc;
00528       }
00529       START_TEST("Partial assignment (after posting)");
00530       {
00531         TestSpace* s = new TestSpace(arity,dom,this);
00532         s->post();
00533         s->assign(a,true);
00534         (void) s->failed();
00535         s->assign(a);
00536         if (sol) {
00537           CHECK_TEST(!s->failed(), "Failed on solution");
00538           CHECK_TEST(s->propagators()==0, "No subsumption");
00539         } else {
00540           CHECK_TEST(s->failed(), "Solved on non-solution");
00541         }
00542         delete s;
00543       }
00544       START_TEST("Assignment (after posting, disable)");
00545       {
00546         TestSpace* s = new TestSpace(arity,dom,this);
00547         s->post();
00548         s->disable();
00549         s->assign(a);
00550         s->enable();
00551         if (sol) {
00552           CHECK_TEST(!s->failed(), "Failed on solution");
00553           CHECK_TEST(s->propagators()==0, "No subsumption");
00554         } else {
00555           CHECK_TEST(s->failed(), "Solved on non-solution");
00556         }
00557         delete s;
00558       }
00559       START_TEST("Partial assignment (after posting, disable)");
00560       {
00561         TestSpace* s = new TestSpace(arity,dom,this);
00562         s->post();
00563         s->assign(a,true);
00564         s->disable();
00565         (void) s->failed();
00566         s->assign(a);
00567         s->enable();
00568         if (sol) {
00569           CHECK_TEST(!s->failed(), "Failed on solution");
00570           CHECK_TEST(s->propagators()==0, "No subsumption");
00571         } else {
00572           CHECK_TEST(s->failed(), "Solved on non-solution");
00573         }
00574         delete s;
00575       }
00576       START_TEST("Assignment (before posting)");
00577       {
00578         TestSpace* s = new TestSpace(arity,dom,this);
00579         s->assign(a);
00580         s->post();
00581         if (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       START_TEST("Partial assignment (before posting)");
00590       {
00591         TestSpace* s = new TestSpace(arity,dom,this);
00592         s->assign(a,true);
00593         s->post();
00594         (void) s->failed();
00595         s->assign(a);
00596         if (sol) {
00597           CHECK_TEST(!s->failed(), "Failed on solution");
00598           CHECK_TEST(s->propagators()==0, "No subsumption");
00599         } else {
00600           CHECK_TEST(s->failed(), "Solved on non-solution");
00601         }
00602         delete s;
00603       }
00604       START_TEST("Prune");
00605       {
00606         TestSpace* s = new TestSpace(arity,dom,this);
00607         s->post();
00608         while (!s->failed() && !s->assigned())
00609           if (!s->prune(a,testfix)) {
00610             problem = "No fixpoint";
00611             delete s;
00612             goto failed;
00613           }
00614         s->assign(a);
00615         if (sol) {
00616           CHECK_TEST(!s->failed(), "Failed on solution");
00617           CHECK_TEST(s->propagators()==0, "No subsumption");
00618         } else {
00619           CHECK_TEST(s->failed(), "Solved on non-solution");
00620         }
00621         delete s;
00622       }
00623       START_TEST("Prune (disable)");
00624       {
00625         TestSpace* s = new TestSpace(arity,dom,this);
00626         TestSpace* c = static_cast<TestSpace*>(s->clone());
00627         s->post(); c->post();
00628         while (!s->failed() && !s->assigned())
00629           if (!s->disabled(a,*c,testfix)) {
00630             problem = "Different result after re-enable";
00631             delete s; delete c;
00632             goto failed;
00633           }
00634         if (testfix && (s->failed() != c->failed())) {
00635             problem = "Different failure after re-enable";
00636             delete s; delete c;
00637             goto failed;
00638         }
00639         delete s; delete c;
00640       }
00641       if (!ignore(a)) {
00642         if (eqv()) {
00643           {
00644             START_TEST("Assignment reified (rewrite after post, <=>)");
00645             TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
00646             s->post();
00647             s->rel(sol);
00648             s->assign(a);
00649             CHECK_TEST(!s->failed(), "Failed");
00650             CHECK_TEST(s->propagators()==0, "No subsumption");
00651             delete s;
00652           }
00653           {
00654             START_TEST("Assignment reified (rewrite failure, <=>)");
00655             TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
00656             s->post();
00657             s->rel(!sol);
00658             s->assign(a);
00659             CHECK_TEST(s->failed(), "Not failed");
00660             delete s;
00661           }
00662           {
00663             START_TEST("Assignment reified (immediate rewrite, <=>)");
00664             TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
00665             s->rel(sol);
00666             s->post();
00667             s->assign(a);
00668             CHECK_TEST(!s->failed(), "Failed");
00669             CHECK_TEST(s->propagators()==0, "No subsumption");
00670             delete s;
00671           }
00672           {
00673             START_TEST("Assignment reified (immediate failure, <=>)");
00674             TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
00675             s->rel(!sol);
00676             s->post();
00677             s->assign(a);
00678             CHECK_TEST(s->failed(), "Not failed");
00679             delete s;
00680           }
00681           {
00682             START_TEST("Assignment reified (before posting, <=>)");
00683             TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
00684             s->assign(a);
00685             s->post();
00686             CHECK_TEST(!s->failed(), "Failed");
00687             CHECK_TEST(s->propagators()==0, "No subsumption");
00688             CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00689             if (sol) {
00690               CHECK_TEST(s->r.var().val()==1, "Zero on solution");
00691             } else {
00692               CHECK_TEST(s->r.var().val()==0, "One on non-solution");
00693             }
00694             delete s;
00695           }
00696           {
00697             START_TEST("Assignment reified (after posting, <=>)");
00698             TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
00699             s->post();
00700             s->assign(a);
00701             CHECK_TEST(!s->failed(), "Failed");
00702             CHECK_TEST(s->propagators()==0, "No subsumption");
00703             CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00704             if (sol) {
00705               CHECK_TEST(s->r.var().val()==1, "Zero on solution");
00706             } else {
00707               CHECK_TEST(s->r.var().val()==0, "One on non-solution");
00708             }
00709             delete s;
00710           }
00711           {
00712             START_TEST("Assignment reified (after posting, <=>, disable)");
00713             TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
00714             s->post();
00715             s->disable();
00716             s->assign(a);
00717             s->enable();
00718             CHECK_TEST(!s->failed(), "Failed");
00719             CHECK_TEST(s->propagators()==0, "No subsumption");
00720             CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00721             if (sol) {
00722               CHECK_TEST(s->r.var().val()==1, "Zero on solution");
00723             } else {
00724               CHECK_TEST(s->r.var().val()==0, "One on non-solution");
00725             }
00726             delete s;
00727           }
00728           {
00729             START_TEST("Prune reified, <=>");
00730             TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
00731             s->post();
00732             while (!s->failed() &&
00733                    (!s->assigned() || !s->r.var().assigned()))
00734               if (!s->prune(a,testfix)) {
00735                 problem = "No fixpoint";
00736                 delete s;
00737                 goto failed;
00738               }
00739             CHECK_TEST(!s->failed(), "Failed");
00740             CHECK_TEST(s->propagators()==0, "No subsumption");
00741             CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00742             if (sol) {
00743               CHECK_TEST(s->r.var().val()==1, "Zero on solution");
00744             } else {
00745               CHECK_TEST(s->r.var().val()==0, "One on non-solution");
00746             }
00747             delete s;
00748           }
00749           {
00750             START_TEST("Prune reified, <=>, disable");
00751             TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
00752             TestSpace* c = static_cast<TestSpace*>(s->clone());
00753             s->post(); c->post();
00754             while (!s->failed() &&
00755                    (!s->assigned() || !s->r.var().assigned()))
00756               if (!s->disabled(a,*c,testfix)) {
00757                 problem = "No fixpoint";
00758                 delete s;
00759                 delete c;
00760                 goto failed;
00761               }
00762             CHECK_TEST(!c->failed(), "Failed");
00763             CHECK_TEST(c->propagators()==0, "No subsumption");
00764             CHECK_TEST(c->r.var().assigned(), "Control variable unassigned");
00765             if (sol) {
00766               CHECK_TEST(c->r.var().val()==1, "Zero on solution");
00767             } else {
00768               CHECK_TEST(c->r.var().val()==0, "One on non-solution");
00769             }
00770             delete s;
00771             delete c;
00772           }
00773         }
00774 
00775         if (imp()) {
00776           {
00777             START_TEST("Assignment reified (rewrite after post, =>)");
00778             TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
00779             s->post();
00780             s->rel(sol);
00781             s->assign(a);
00782             CHECK_TEST(!s->failed(), "Failed");
00783             CHECK_TEST(s->propagators()==0, "No subsumption");
00784             delete s;
00785           }
00786           {
00787             START_TEST("Assignment reified (rewrite failure, =>)");
00788             TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
00789             s->post();
00790             s->rel(!sol);
00791             s->assign(a);
00792             if (sol) {
00793               CHECK_TEST(!s->failed(), "Failed");
00794               CHECK_TEST(s->propagators()==0, "No subsumption");
00795             } else {
00796               CHECK_TEST(s->failed(), "Not failed");
00797             }
00798             delete s;
00799           }
00800           {
00801             START_TEST("Assignment reified (immediate rewrite, =>)");
00802             TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
00803             s->rel(sol);
00804             s->post();
00805             s->assign(a);
00806             CHECK_TEST(!s->failed(), "Failed");
00807             CHECK_TEST(s->propagators()==0, "No subsumption");
00808             delete s;
00809           }
00810           {
00811             START_TEST("Assignment reified (immediate failure, =>)");
00812             TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
00813             s->rel(!sol);
00814             s->post();
00815             s->assign(a);
00816             if (sol) {
00817               CHECK_TEST(!s->failed(), "Failed");
00818               CHECK_TEST(s->propagators()==0, "No subsumption");
00819             } else {
00820               CHECK_TEST(s->failed(), "Not failed");
00821             }
00822             delete s;
00823           }
00824           {
00825             START_TEST("Assignment reified (before posting, =>)");
00826             TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
00827             s->assign(a);
00828             s->post();
00829             CHECK_TEST(!s->failed(), "Failed");
00830             CHECK_TEST(s->propagators()==0, "No subsumption");
00831             if (sol) {
00832               CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
00833             } else {
00834               CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00835               CHECK_TEST(s->r.var().val()==0, "One on non-solution");
00836             }
00837             delete s;
00838           }
00839           {
00840             START_TEST("Assignment reified (after posting, =>)");
00841             TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
00842             s->post();
00843             s->assign(a);
00844             CHECK_TEST(!s->failed(), "Failed");
00845             CHECK_TEST(s->propagators()==0, "No subsumption");
00846             if (sol) {
00847               CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
00848             } else {
00849               CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00850               CHECK_TEST(s->r.var().val()==0, "One on non-solution");
00851             }
00852             delete s;
00853           }
00854           {
00855             START_TEST("Assignment reified (after posting, =>, disable)");
00856             TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
00857             s->post();
00858             s->disable();
00859             s->assign(a);
00860             s->enable();
00861             CHECK_TEST(!s->failed(), "Failed");
00862             CHECK_TEST(s->propagators()==0, "No subsumption");
00863             if (sol) {
00864               CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
00865             } else {
00866               CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00867               CHECK_TEST(s->r.var().val()==0, "One on non-solution");
00868             }
00869             delete s;
00870           }
00871           {
00872             START_TEST("Prune reified, =>");
00873             TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
00874             s->post();
00875             while (!s->failed() &&
00876                    (!s->assigned() || (!sol && !s->r.var().assigned())))
00877               if (!s->prune(a,testfix)) {
00878                 problem = "No fixpoint";
00879                 delete s;
00880                 goto failed;
00881               }
00882             CHECK_TEST(!s->failed(), "Failed");
00883             CHECK_TEST(s->propagators()==0, "No subsumption");
00884             if (sol) {
00885               CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
00886             } else {
00887               CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00888               CHECK_TEST(s->r.var().val()==0, "One on non-solution");
00889             }
00890             delete s;
00891           }
00892           {
00893             START_TEST("Prune reified, =>, disable");
00894             TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
00895             TestSpace* c = static_cast<TestSpace*>(s->clone());
00896             s->post(); c->post();
00897             while (!s->failed() &&
00898                    (!s->assigned() || (!sol && !s->r.var().assigned())))
00899               if (!s->disabled(a,*c,testfix)) {
00900                 problem = "No fixpoint";
00901                 delete s;
00902                 delete c;
00903                 goto failed;
00904               }
00905             CHECK_TEST(!c->failed(), "Failed");
00906             CHECK_TEST(c->propagators()==0, "No subsumption");
00907             if (sol) {
00908               CHECK_TEST(!c->r.var().assigned(), "Control variable assigned");
00909             } else {
00910               CHECK_TEST(c->r.var().assigned(), "Control variable unassigned");
00911               CHECK_TEST(c->r.var().val()==0, "One on non-solution");
00912             }
00913             delete s;
00914             delete c;
00915           }
00916         }
00917 
00918         if (pmi()) {
00919           {
00920             START_TEST("Assignment reified (rewrite after post, <=)");
00921             TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
00922             s->post();
00923             s->rel(sol);
00924             s->assign(a);
00925             CHECK_TEST(!s->failed(), "Failed");
00926             CHECK_TEST(s->propagators()==0, "No subsumption");
00927             delete s;
00928           }
00929           {
00930             START_TEST("Assignment reified (rewrite failure, <=)");
00931             TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
00932             s->post();
00933             s->rel(!sol);
00934             s->assign(a);
00935             if (sol) {
00936               CHECK_TEST(s->failed(), "Not failed");
00937             } else {
00938               CHECK_TEST(!s->failed(), "Failed");
00939               CHECK_TEST(s->propagators()==0, "No subsumption");
00940             }
00941             delete s;
00942           }
00943           {
00944             START_TEST("Assignment reified (immediate rewrite, <=)");
00945             TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
00946             s->rel(sol);
00947             s->post();
00948             s->assign(a);
00949             CHECK_TEST(!s->failed(), "Failed");
00950             CHECK_TEST(s->propagators()==0, "No subsumption");
00951             delete s;
00952           }
00953           {
00954             START_TEST("Assignment reified (immediate failure, <=)");
00955             TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
00956             s->rel(!sol);
00957             s->post();
00958             s->assign(a);
00959             if (sol) {
00960               CHECK_TEST(s->failed(), "Not failed");
00961             } else {
00962               CHECK_TEST(!s->failed(), "Failed");
00963               CHECK_TEST(s->propagators()==0, "No subsumption");
00964             }
00965             delete s;
00966           }
00967           {
00968             START_TEST("Assignment reified (before posting, <=)");
00969             TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
00970             s->assign(a);
00971             s->post();
00972             CHECK_TEST(!s->failed(), "Failed");
00973             CHECK_TEST(s->propagators()==0, "No subsumption");
00974             if (sol) {
00975               CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00976               CHECK_TEST(s->r.var().val()==1, "Zero on solution");
00977             } else {
00978               CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
00979             }
00980             delete s;
00981           }
00982           {
00983             START_TEST("Assignment reified (after posting, <=)");
00984             TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
00985             s->post();
00986             s->assign(a);
00987             CHECK_TEST(!s->failed(), "Failed");
00988             CHECK_TEST(s->propagators()==0, "No subsumption");
00989             if (sol) {
00990               CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
00991               CHECK_TEST(s->r.var().val()==1, "Zero on solution");
00992             } else {
00993               CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
00994             }
00995             delete s;
00996           }
00997           {
00998             START_TEST("Assignment reified (after posting, <=, disable)");
00999             TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
01000             s->post();
01001             s->disable();
01002             s->assign(a);
01003             s->enable();
01004             CHECK_TEST(!s->failed(), "Failed");
01005             CHECK_TEST(s->propagators()==0, "No subsumption");
01006             if (sol) {
01007               CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01008               CHECK_TEST(s->r.var().val()==1, "Zero on solution");
01009             } else {
01010               CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
01011             }
01012             delete s;
01013           }
01014           {
01015             START_TEST("Prune reified, <=");
01016             TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
01017             s->post();
01018             while (!s->failed() &&
01019                    (!s->assigned() || (sol && !s->r.var().assigned())))
01020               if (!s->prune(a,testfix)) {
01021                 problem = "No fixpoint";
01022                 delete s;
01023                 goto failed;
01024               }
01025             CHECK_TEST(!s->failed(), "Failed");
01026             CHECK_TEST(s->propagators()==0, "No subsumption");
01027             if (sol) {
01028               CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
01029               CHECK_TEST(s->r.var().val()==1, "Zero on solution");
01030             } else {
01031               CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
01032             }
01033             delete s;
01034           }
01035           {
01036             START_TEST("Prune reified, <=, disable");
01037             TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
01038             TestSpace* c = static_cast<TestSpace*>(s->clone());
01039             s->post(); c->post();
01040             while (!s->failed() &&
01041                    (!s->assigned() || (sol && !s->r.var().assigned())))
01042               if (!s->disabled(a,*c,testfix)) {
01043                 problem = "No fixpoint";
01044                 delete s;
01045                 delete c;
01046                 goto failed;
01047               }
01048             CHECK_TEST(!c->failed(), "Failed");
01049             CHECK_TEST(c->propagators()==0, "No subsumption");
01050             if (sol) {
01051               CHECK_TEST(c->r.var().assigned(), "Control variable unassigned");
01052               CHECK_TEST(c->r.var().val()==1, "Zero on solution");
01053             } else {
01054               CHECK_TEST(!c->r.var().assigned(), "Control variable assigned");
01055             }
01056             delete s;
01057             delete c;
01058           }
01059         }
01060       }
01061 
01062       if (testsearch) {
01063         if (sol) {
01064           START_TEST("Search");
01065           TestSpace* s = e_s.next();
01066           CHECK_TEST(s != NULL, "Solutions exhausted");
01067           CHECK_TEST(s->propagators()==0, "No subsumption");
01068           for (int i=a.size(); i--; ) {
01069             CHECK_TEST(s->x[i].assigned(), "Unassigned variable");
01070             CHECK_TEST(a[i] == s->x[i].val(), "Wrong value in solution");
01071           }
01072           delete s;
01073         }
01074       }
01075 
01076       ++a;
01077     }
01078 
01079     if (testsearch) {
01080       test = "Search";
01081       if (e_s.next() != NULL) {
01082         problem = "Excess solutions";
01083         goto failed;
01084       }
01085     }
01086 
01087     switch (contest) {
01088     case CTL_NONE: break;
01089     case CTL_DOMAIN: {
01090       START_TEST("Full domain consistency");
01091       TestSpace* s = new TestSpace(arity,dom,this);
01092       s->post();
01093       if (!s->failed()) {
01094         while (!s->failed() && !s->assigned())
01095           s->prune();
01096         CHECK_TEST(!s->failed(), "Failed");
01097         CHECK_TEST(s->propagators()==0, "No subsumption");
01098       }
01099       delete s;
01100       // Fall-through -- domain implies bounds(d) and bounds(z)
01101     }
01102     case CTL_BOUNDS_D: {
01103       START_TEST("Bounds(D)-consistency");
01104       TestSpace* s = new TestSpace(arity,dom,this);
01105       s->post();
01106       for (int i = s->x.size(); i--; )
01107         s->prune(i, false);
01108       if (!s->failed()) {
01109         while (!s->failed() && !s->assigned())
01110           s->bound();
01111         CHECK_TEST(!s->failed(), "Failed");
01112         CHECK_TEST(s->propagators()==0, "No subsumption");
01113       }
01114       delete s;
01115       // Fall-through -- bounds(d) implies bounds(z)
01116     }
01117     case CTL_BOUNDS_Z: {
01118       START_TEST("Bounds(Z)-consistency");
01119       TestSpace* s = new TestSpace(arity,dom,this);
01120       s->post();
01121       for (int i = s->x.size(); i--; )
01122         s->prune(i, true);
01123       if (!s->failed()) {
01124         while (!s->failed() && !s->assigned())
01125           s->bound();
01126         CHECK_TEST(!s->failed(), "Failed");
01127         CHECK_TEST(s->propagators()==0, "No subsumption");
01128       }
01129       delete s;
01130       break;
01131     }
01132     }
01133 
01134     delete ap;
01135     return true;
01136 
01137   failed:
01138     if (opt.log)
01139       olog << "FAILURE" << std::endl
01140            << ind(1) << "Test:       " << test << std::endl
01141            << ind(1) << "Problem:    " << problem << std::endl;
01142     if (a() && opt.log)
01143       olog << ind(1) << "Assignment: " << a << std::endl;
01144     delete ap;
01145 
01146     return false;
01147   }
01148 
01149 }}
01150 
01151 #undef START_TEST
01152 #undef CHECK_TEST
01153 
01154 // STATISTICS: test-int