Generated on Mon May 10 06:46:46 2010 for Gecode by doxygen 1.6.3

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