Generated on Thu Mar 22 10:39:45 2012 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: 2011-08-24 16:34:16 +0200 (Wed, 24 Aug 2011) $ by $Author: tack $
00015  *     $Revision: 12346 $
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_LQ: olog << "<="; break;
00184       case Gecode::SRT_LE: olog << "<"; break;
00185       case Gecode::SRT_GQ: olog << ">="; break;
00186       case Gecode::SRT_GR: olog << ">"; break;
00187       case Gecode::SRT_NQ: olog << "!="; break;
00188       case Gecode::SRT_SUB: olog << "sub"; break;
00189       case Gecode::SRT_SUP: olog << "sup"; break;
00190       case Gecode::SRT_DISJ: olog << "||"; break;
00191       case Gecode::SRT_CMPL: olog << "^-1 = "; break;
00192       }
00193       olog << is << std::endl;
00194     }
00195     Gecode::dom(*this, x[i], srt, is);
00196   }
00197 
00198   void 
00199   SetTestSpace::cardinality(int i, int cmin, int cmax) {
00200     if (opt.log) {
00201       olog << ind(4) << cmin << " <= #(x[" << i << "]) <= " << cmax
00202            << std::endl;
00203     }
00204     Gecode::cardinality(*this, x[i], cmin, cmax);
00205   }
00206 
00207   void 
00208   SetTestSpace::rel(int i, Gecode::IntRelType irt, int n) {
00209     if (opt.log) {
00210       olog << ind(4) << "y[" << i << "] ";
00211       switch (irt) {
00212       case Gecode::IRT_EQ: olog << "="; break;
00213       case Gecode::IRT_NQ: olog << "!="; break;
00214       case Gecode::IRT_LQ: olog << "<="; break;
00215       case Gecode::IRT_LE: olog << "<"; break;
00216       case Gecode::IRT_GQ: olog << ">="; break;
00217       case Gecode::IRT_GR: olog << ">"; break;
00218       }
00219       olog << " " << n << std::endl;
00220     }
00221     Gecode::rel(*this, y[i], irt, n);
00222   }
00223 
00224   void 
00225   SetTestSpace::rel(bool sol) {
00226     int n = sol ? 1 : 0;
00227     assert(reified);
00228     if (opt.log)
00229       olog << ind(4) << "b = " << n << std::endl;
00230     Gecode::rel(*this, b, Gecode::IRT_EQ, n);
00231   }
00232   
00233   void 
00234   SetTestSpace::assign(const SetAssignment& a) {
00235     for (int i=a.size(); i--; ) {
00236       CountableSetRanges csv(a.lub, a[i]);
00237       Gecode::IntSet ai(csv);
00238       rel(i, Gecode::SRT_EQ, ai);
00239       if (Base::fixpoint() && failed())
00240         return;
00241     }
00242     for (int i=withInt; i--; ) {
00243       rel(i, Gecode::IRT_EQ, a.ints()[i]);
00244       if (Base::fixpoint() && failed())
00245         return;
00246     }
00247   }
00248   
00249   bool 
00250   SetTestSpace::assigned(void) const {
00251     for (int i=x.size(); i--; )
00252       if (!x[i].assigned())
00253         return false;
00254     for (int i=y.size(); i--; )
00255       if (!y[i].assigned())
00256         return false;
00257     return true;
00258   }
00259 
00260   void 
00261   SetTestSpace::removeFromLub(int v, int i, const SetAssignment& a) {
00262     using namespace Gecode;
00263     SetVarUnknownRanges ur(x[i]);
00264     CountableSetRanges air(a.lub, a[i]);
00265     Gecode::Iter::Ranges::Diff<Gecode::SetVarUnknownRanges,
00266       CountableSetRanges> diff(ur, air);
00267     Gecode::Iter::Ranges::ToValues<Gecode::Iter::Ranges::Diff
00268       <Gecode::SetVarUnknownRanges, CountableSetRanges> > diffV(diff);
00269     for (int j=0; j<v; j++, ++diffV) {}
00270     rel(i, Gecode::SRT_DISJ, Gecode::IntSet(diffV.val(), diffV.val()));
00271   }
00272 
00273   void 
00274   SetTestSpace::addToGlb(int v, int i, const SetAssignment& a) {
00275     using namespace Gecode;
00276     SetVarUnknownRanges ur(x[i]);
00277     CountableSetRanges air(a.lub, a[i]);
00278     Gecode::Iter::Ranges::Inter<Gecode::SetVarUnknownRanges,
00279       CountableSetRanges> inter(ur, air);
00280     Gecode::Iter::Ranges::ToValues<Gecode::Iter::Ranges::Inter
00281       <Gecode::SetVarUnknownRanges, CountableSetRanges> > interV(inter);
00282     for (int j=0; j<v; j++, ++interV) {}
00283     rel(i, Gecode::SRT_SUP, Gecode::IntSet(interV.val(), interV.val()));
00284   }
00285 
00286   bool 
00287   SetTestSpace::fixprob(void) {
00288     if (failed())
00289       return true;
00290     SetTestSpace* c = static_cast<SetTestSpace*>(clone());
00291     if (opt.log)
00292       olog << ind(3) << "Testing fixpoint on copy" << std::endl;
00293     c->post();
00294     if (c->failed()) {
00295       delete c; return false;
00296     }
00297     
00298     for (int i=x.size(); i--; )
00299       if (x[i].glbSize() != c->x[i].glbSize() ||
00300           x[i].lubSize() != c->x[i].lubSize() ||
00301           x[i].cardMin() != c->x[i].cardMin() ||
00302           x[i].cardMax() != c->x[i].cardMax()) {
00303         delete c;
00304         return false;
00305       }
00306     for (int i=y.size(); i--; )
00307       if (y[i].size() != c->y[i].size()) {
00308         delete c; return false;
00309       }
00310     if (reified && (b.size() != c->b.size())) {
00311       delete c; return false;
00312     }
00313     if (opt.log)
00314       olog << ind(3) << "Finished testing fixpoint on copy" << std::endl;
00315     delete c;
00316     return true;
00317   }
00318 
00319   bool 
00320   SetTestSpace::prune(const SetAssignment& a) {
00321     using namespace Gecode;
00322     bool setsAssigned = true;
00323     for (int j=x.size(); j--; )
00324       if (!x[j].assigned()) {
00325         setsAssigned = false;
00326         break;
00327       }
00328     bool intsAssigned = true;
00329     for (int j=y.size(); j--; )
00330       if (!y[j].assigned()) {
00331         intsAssigned = false;
00332         break;
00333       }
00334     
00335     // Select variable to be pruned
00336     int i;
00337     if (intsAssigned) {
00338       i = Base::rand(x.size());
00339     } else if (setsAssigned) {
00340       i = Base::rand(y.size());
00341     } else {
00342       i = Base::rand(x.size()+y.size());
00343     }
00344     
00345     if (setsAssigned || i>=x.size()) {
00346       if (i>=x.size())
00347         i = i-x.size();
00348       while (y[i].assigned()) {
00349         i = (i+1) % y.size();
00350       }
00351       // Prune int var
00352       
00353       // Select mode for pruning
00354       switch (Base::rand(3)) {
00355       case 0:
00356         if (a.ints()[i] < y[i].max()) {
00357           int v=a.ints()[i]+1+
00358             Base::rand(static_cast<unsigned int>(y[i].max()-a.ints()[i]));
00359           assert((v > a.ints()[i]) && (v <= y[i].max()));
00360           rel(i, Gecode::IRT_LE, v);
00361         }
00362         break;
00363       case 1:
00364         if (a.ints()[i] > y[i].min()) {
00365           int v=y[i].min()+
00366             Base::rand(static_cast<unsigned int>(a.ints()[i]-y[i].min()));
00367           assert((v < a.ints()[i]) && (v >= y[i].min()));
00368           rel(i, Gecode::IRT_GR, v);
00369         }
00370         break;
00371       default:
00372         int v;
00373         Gecode::Int::ViewRanges<Gecode::Int::IntView> it(y[i]);
00374         unsigned int skip = Base::rand(y[i].size()-1);
00375         while (true) {
00376           if (it.width() > skip) {
00377             v = it.min() + skip;
00378             if (v == a.ints()[i]) {
00379               if (it.width() == 1) {
00380                 ++it; v = it.min();
00381               } else if (v < it.max()) {
00382                 ++v;
00383               } else {
00384                 --v;
00385               }
00386             }
00387             break;
00388           }
00389           skip -= it.width();
00390           ++it;
00391         }
00392         rel(i, Gecode::IRT_NQ, v);
00393       }
00394       return (!Base::fixpoint() || fixprob());
00395     }
00396     while (x[i].assigned()) {
00397       i = (i+1) % x.size();
00398     }
00399     Gecode::SetVarUnknownRanges ur1(x[i]);
00400     CountableSetRanges air1(a.lub, a[i]);
00401     Gecode::Iter::Ranges::Diff<Gecode::SetVarUnknownRanges,
00402       CountableSetRanges> diff(ur1, air1);
00403     Gecode::SetVarUnknownRanges ur2(x[i]);
00404     CountableSetRanges air2(a.lub, a[i]);
00405     Gecode::Iter::Ranges::Inter<Gecode::SetVarUnknownRanges,
00406       CountableSetRanges> inter(ur2, air2);
00407     
00408     CountableSetRanges aisizer(a.lub, a[i]);
00409     unsigned int aisize = Gecode::Iter::Ranges::size(aisizer);
00410     
00411     // Select mode for pruning
00412     switch (Base::rand(5)) {
00413     case 0:
00414       if (inter()) {
00415         int v = Base::rand(Gecode::Iter::Ranges::size(inter));
00416         addToGlb(v, i, a);
00417       }
00418       break;
00419     case 1:
00420       if (diff()) {
00421         int v = Base::rand(Gecode::Iter::Ranges::size(diff));
00422         removeFromLub(v, i, a);
00423       }
00424       break;
00425     case 2:
00426       if (x[i].cardMin() < aisize) {
00427         unsigned int newc = x[i].cardMin() + 1 +
00428           Base::rand(aisize - x[i].cardMin());
00429         assert( newc > x[i].cardMin() );
00430         assert( newc <= aisize );
00431         cardinality(i, newc, Gecode::Set::Limits::card);
00432       }
00433       break;
00434     case 3:
00435       if (x[i].cardMax() > aisize) {
00436         unsigned int newc = x[i].cardMax() - 1 -
00437           Base::rand(x[i].cardMax() - aisize);
00438         assert( newc < x[i].cardMax() );
00439         assert( newc >= aisize );
00440         cardinality(i, 0, newc);
00441       }
00442       break;
00443     default:
00444       if (inter()) {
00445         int v = Base::rand(Gecode::Iter::Ranges::size(inter));
00446         addToGlb(v, i, a);
00447       } else {
00448         int v = Base::rand(Gecode::Iter::Ranges::size(diff));
00449         removeFromLub(v, i, a);
00450       }
00451     }
00452     return (!Base::fixpoint() || fixprob());
00453   }
00454 
00455 
00457 #define CHECK_TEST(T,M)                                         \
00458 if (opt.log)                                                    \
00459   olog << ind(3) << "Check: " << (M) << std::endl;              \
00460 if (!(T)) {                                                     \
00461   problem = (M); delete s; goto failed;                         \
00462 }
00463 
00465 #define START_TEST(T)                                           \
00466   if (opt.log) {                                                \
00467      olog.str("");                                              \
00468      olog << ind(2) << "Testing: " << (T) << std::endl;         \
00469   }                                                             \
00470   test = (T);
00471 
00472   bool
00473   SetTest::run(void) {
00474     const char* test    = "NONE";
00475     const char* problem = "NONE";
00476 
00477     SetAssignment* ap = new SetAssignment(arity,lub,withInt);
00478     SetAssignment& a = *ap;
00479     while (a()) {
00480       bool is_sol = solution(a);
00481       if (opt.log)
00482         olog << ind(1) << "Assignment: " << a
00483              << (is_sol ? " (solution)" : " (no solution)")
00484              << std::endl;
00485 
00486       START_TEST("Assignment (after posting)");
00487       {
00488         SetTestSpace* s = new SetTestSpace(arity,lub,withInt,false,this);
00489         SetTestSpace* sc = NULL;
00490         s->post();
00491         switch (Base::rand(3)) {
00492           case 0:
00493             if (opt.log)
00494               olog << ind(3) << "No copy" << std::endl;
00495             sc = s;
00496             s = NULL;
00497             break;
00498           case 1:
00499             if (opt.log)
00500               olog << ind(3) << "Unshared copy" << std::endl;
00501             if (s->status() != Gecode::SS_FAILED) {
00502               sc = static_cast<SetTestSpace*>(s->clone(true));
00503             } else {
00504               sc = s; s = NULL;
00505             }
00506             break;
00507           case 2:
00508             if (opt.log)
00509               olog << ind(3) << "Unshared copy" << std::endl;
00510             if (s->status() != Gecode::SS_FAILED) {
00511               sc = static_cast<SetTestSpace*>(s->clone(false));
00512             } else {
00513               sc = s; s = NULL;
00514             }
00515             break;
00516           default: assert(false);
00517         }
00518         sc->assign(a);
00519         if (is_sol) {
00520           CHECK_TEST(!sc->failed(), "Failed on solution");
00521           CHECK_TEST(sc->propagators()==0, "No subsumption");
00522         } else {
00523           CHECK_TEST(sc->failed(), "Solved on non-solution");
00524         }
00525         delete s; delete sc;
00526       }
00527       START_TEST("Assignment (before posting)");
00528       {
00529         SetTestSpace* s = new SetTestSpace(arity,lub,withInt,false,this);
00530         s->assign(a);
00531         s->post();
00532         if (is_sol) {
00533           CHECK_TEST(!s->failed(), "Failed on solution");
00534           CHECK_TEST(s->propagators()==0, "No subsumption");
00535         } else {
00536           CHECK_TEST(s->failed(), "Solved on non-solution");
00537         }
00538         delete s;
00539       }
00540       if (reified) {
00541         START_TEST("Assignment reified (before posting)");
00542         SetTestSpace* s = new SetTestSpace(arity,lub,withInt,true,this);
00543         s->assign(a);
00544         s->post();
00545         CHECK_TEST(!s->failed(), "Failed");
00546         CHECK_TEST(s->propagators()==0, "No subsumption");
00547         CHECK_TEST(s->b.assigned(), "Control variable unassigned");
00548         if (is_sol) {
00549           CHECK_TEST(s->b.val()==1, "Zero on solution");
00550         } else {
00551           CHECK_TEST(s->b.val()==0, "One on non-solution");
00552         }
00553         delete s;
00554       }
00555       if (reified) {
00556         START_TEST("Assignment reified (after posting)");
00557         SetTestSpace* s = new SetTestSpace(arity,lub,withInt,true,this);
00558         s->post();
00559         s->assign(a);
00560         CHECK_TEST(!s->failed(), "Failed");
00561         CHECK_TEST(s->propagators()==0, "No subsumption");
00562         CHECK_TEST(s->b.assigned(), "Control variable unassigned");
00563         if (is_sol) {
00564           CHECK_TEST(s->b.val()==1, "Zero on solution");
00565         } else {
00566           CHECK_TEST(s->b.val()==0, "One on non-solution");
00567         }
00568         delete s;
00569       }
00570       START_TEST("Prune");
00571       {
00572         SetTestSpace* s = new SetTestSpace(arity,lub,withInt,false,this);
00573         s->post();
00574         while (!s->failed() && !s->assigned())
00575            if (!s->prune(a)) {
00576              problem = "No fixpoint";
00577              delete s;
00578              goto failed;
00579            }
00580         s->assign(a);
00581         if (is_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       if (reified) {
00590         START_TEST("Prune reified");
00591         SetTestSpace* s = new SetTestSpace(arity,lub,withInt,true,this);
00592         s->post();
00593         while (!s->assigned() && !s->b.assigned())
00594            if (!s->prune(a)) {
00595              problem = "No fixpoint";
00596              delete s;
00597              goto failed;
00598            }
00599         CHECK_TEST(!s->failed(), "Failed");
00600         CHECK_TEST(s->propagators()==0, "No subsumption");
00601         CHECK_TEST(s->b.assigned(), "Control variable unassigned");
00602         if (is_sol) {
00603           CHECK_TEST(s->b.val()==1, "Zero on solution");
00604         } else {
00605           CHECK_TEST(s->b.val()==0, "One on non-solution");
00606         }
00607         delete s;
00608       }
00609       ++a;
00610     }
00611     delete ap;
00612     return true;
00613    failed:
00614         if (opt.log)
00615           olog << "FAILURE" << std::endl
00616                << ind(1) << "Test:       " << test << std::endl
00617                << ind(1) << "Problem:    " << problem << std::endl;
00618         if (a() && opt.log)
00619           olog << ind(1) << "Assignment: " << a << std::endl;
00620      delete ap;
00621 
00622      return false;
00623   }
00624 
00625   const Gecode::SetRelType SetRelTypes::srts[] =
00626     {Gecode::SRT_EQ,Gecode::SRT_NQ,Gecode::SRT_SUB,
00627      Gecode::SRT_SUP,Gecode::SRT_DISJ,Gecode::SRT_CMPL};
00628 
00629   const Gecode::SetOpType SetOpTypes::sots[] =
00630     {Gecode::SOT_UNION, Gecode::SOT_DUNION,
00631      Gecode::SOT_INTER, Gecode::SOT_MINUS};
00632 
00633 }}
00634 
00635 #undef START_TEST
00636 #undef CHECK_TEST
00637 
00638 // STATISTICS: test-set