Generated on Mon May 10 06:46:41 2010 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  *  Last modified:
00012  *     $Date: 2009-05-08 13:44:41 +0200 (Fri, 08 May 2009) $ by $Author: schulte $
00013  *     $Revision: 9034 $
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 }}
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     // Select variable to be assigned
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     // Prune values
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     // Select variable to be pruned
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     // Select variable to be pruned
00237     int i = Base::rand(x.size());
00238     while (x[i].assigned())
00239       i = (i+1) % x.size();
00240     // Select mode for pruning
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     // Set up assignments
00357     Assignment* ap = assignment();
00358     Assignment& a = *ap;
00359 
00360     // Set up space for all solution search
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       // Fall-through -- domain implies bounds(d) and bounds(z)
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       // Fall-through -- bounds(d) implies bounds(z)
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 // STATISTICS: test-int