Generated on Thu Mar 22 10:39:41 2012 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: 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