Generated on Tue May 22 09:39:46 2018 for Gecode by doxygen 1.6.3

dom.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  *
00006  *  Copyright:
00007  *     Guido Tack, 2005
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/minimodel.hh>
00035 
00036 #include "test/set.hh"
00037 
00038 using namespace Gecode;
00039 
00040 namespace Test { namespace Set {
00041 
00043   namespace Dom {
00044 
00050 
00051     static const int d1r[4][2] = {
00052       {-4,-3},{-1,-1},{1,1},{3,5}
00053     };
00054     static IntSet d1(d1r,4);
00055 
00056     static const int d1cr[5][2] = {
00057       {Gecode::Set::Limits::min,-5},
00058       {-2,-2},{0,0},{2,2},
00059       {6,Gecode::Set::Limits::max}
00060     };
00061     static IntSet d1c(d1cr,5);
00062 
00063     static IntSet ds_33(-3,3);
00064 
00065     static const int d2r[2][2] = {
00066       {Gecode::Set::Limits::min,-4}, {4,Gecode::Set::Limits::max}
00067     };
00068     static IntSet ds_33c(d2r,2);
00069 
00070     namespace {
00071       static int minSymDiff(const SetAssignment& x, int i, const IntSet& is) {
00072         typedef Iter::Ranges::Diff<CountableSetRanges,IntSetRanges> DiffA;
00073         CountableSetRanges xr00(x.lub, x[i]);
00074         IntSetRanges xr10(is);
00075         DiffA a(xr00,xr10);
00076         typedef Iter::Ranges::Diff<IntSetRanges,CountableSetRanges> DiffB;
00077         CountableSetRanges xr01(x.lub, x[i]);
00078         IntSetRanges xr11(is);
00079         DiffB b(xr11,xr01);
00080         Iter::Ranges::Union<DiffA,DiffB> u(a,b);
00081         return u() ? u.min() : Gecode::Set::Limits::max+1;
00082       }
00083       template<class I>
00084       static bool in(int i, I& c, bool eq=false) {
00085         if (eq && i==Gecode::Set::Limits::max+1)
00086           return true;
00087         Iter::Ranges::Singleton s(i,i);
00088         return Iter::Ranges::subset(s,c);
00089       }
00090     }
00091 
00093     class DomRange : public SetTest {
00094     private:
00095       Gecode::SetRelType srt;
00096       IntSet is;
00097     public:
00099       DomRange(SetRelType srt0, int n) :
00100         SetTest("Dom::Range::"+str(srt0)+"::"+str(n),n,ds_33,(n == 1)),
00101         srt(srt0), is(srt == Gecode::SRT_CMPL ? ds_33c: ds_33) {}
00103       virtual bool solution(const SetAssignment& x) const {
00104         for (int i=x.size(); i--; ) {
00105           CountableSetRanges xr(x.lub, x[i]);
00106           IntSetRanges dr(is);
00107           switch (srt) {
00108           case SRT_EQ:
00109             if (!Iter::Ranges::equal(xr, dr))
00110               return false;
00111             break;
00112           case SRT_LQ:
00113             if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00114               return false;
00115             break;
00116           case SRT_LE:
00117             if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00118               return false;
00119             break;
00120           case SRT_GQ:
00121             if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00122               return false;
00123             break;
00124           case SRT_GR:
00125             if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00126               return false;
00127             break;
00128           case SRT_NQ:
00129             if (Iter::Ranges::equal(xr, dr))
00130               return false;
00131             break;
00132           case SRT_SUB:
00133             if (!Iter::Ranges::subset(xr, dr))
00134               return false;
00135             break;
00136           case SRT_SUP:
00137             if (!Iter::Ranges::subset(dr, xr))
00138               return false;
00139             break;
00140           case SRT_DISJ:
00141             {
00142               Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00143                 inter(xr, dr);
00144               if (inter())
00145                 return false;
00146             }
00147             break;
00148           case SRT_CMPL:
00149             {
00150               Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00151               if (!Iter::Ranges::equal(xr,drc))
00152                 return false;
00153             }
00154             break;
00155           }
00156         }
00157         return true;
00158       }
00160       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00161         if (x.size() == 1)
00162           Gecode::dom(home, x[0], srt, is);
00163         else
00164           Gecode::dom(home, x, srt, is);
00165       }
00167       virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00168         assert(x.size() == 1);
00169         if (Base::rand(2) != 0) {
00170           Gecode::dom(home, x[0], srt, is, r);
00171         } else {
00172            switch (r.mode()) {
00173            case Gecode::RM_EQV:
00174              Gecode::rel(home, Gecode::dom(x[0], srt, is) == r.var()); break;
00175            case Gecode::RM_IMP:
00176              Gecode::rel(home, Gecode::dom(x[0], srt, is) << r.var()); break;
00177            case Gecode::RM_PMI:
00178              Gecode::rel(home, Gecode::dom(x[0], srt, is) >> r.var()); break;
00179            default: GECODE_NEVER;
00180            }
00181         }
00182       }
00183     };
00184 
00186     class DomIntRange : public SetTest {
00187     private:
00188       Gecode::SetRelType srt;
00189     public:
00191       DomIntRange(Gecode::SetRelType srt0, int n)
00192         : SetTest("Dom::IntRange::"+str(srt0)+"::"+str(n),1,ds_33,n==1),
00193           srt(srt0) {}
00195       virtual bool solution(const SetAssignment& x) const {
00196         for (int i=x.size(); i--; ) {
00197           CountableSetRanges xr(x.lub, x[i]);
00198           IntSet is(-3,-1);
00199           IntSetRanges dr(is);
00200           switch (srt) {
00201           case SRT_EQ:
00202             if (!Iter::Ranges::equal(xr, dr))
00203               return false;
00204             break;
00205           case SRT_LQ:
00206             if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00207               return false;
00208             break;
00209           case SRT_LE:
00210             if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00211               return false;
00212             break;
00213           case SRT_GQ:
00214             if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00215               return false;
00216             break;
00217           case SRT_GR:
00218             if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00219               return false;
00220             break;
00221           case SRT_NQ:
00222             if (!(!Iter::Ranges::equal(xr, dr)))
00223               return false;
00224             break;
00225           case SRT_SUB:
00226             if (!(Iter::Ranges::subset(xr, dr)))
00227               return false;
00228             break;
00229           case SRT_SUP:
00230             if (!(Iter::Ranges::subset(dr, xr)))
00231               return false;
00232             break;
00233           case SRT_DISJ:
00234             {
00235               Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00236                 inter(xr, dr);
00237               if (inter())
00238                 return false;
00239             }
00240             break;
00241           case SRT_CMPL:
00242             {
00243               Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00244               if (!Iter::Ranges::equal(xr,drc))
00245                 return false;
00246             }
00247             break;
00248           }
00249         }
00250         return true;
00251       }
00253       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00254         if (x.size() == 1)
00255           Gecode::dom(home, x[0], srt, -3, -1);
00256         else
00257           Gecode::dom(home, x, srt, -3, -1);
00258       }
00260       virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00261         assert(x.size() == 1);
00262         if (Base::rand(2) != 0) {
00263           Gecode::dom(home, x[0], srt, -3, -1, r);
00264         } else {
00265            switch (r.mode()) {
00266            case Gecode::RM_EQV:
00267              Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) == r.var()); break;
00268            case Gecode::RM_IMP:
00269              Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) << r.var()); break;
00270            case Gecode::RM_PMI:
00271              Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) >> r.var()); break;
00272            default: GECODE_NEVER;
00273            }
00274         }
00275       }
00276     };
00277 
00279     class DomInt : public SetTest {
00280     private:
00281       Gecode::SetRelType srt;
00282     public:
00284       DomInt(Gecode::SetRelType srt0, int n) :
00285         SetTest("Dom::Int::"+str(srt0)+"::"+str(n),n,ds_33,n==1),
00286         srt(srt0) {}
00288       virtual bool solution(const SetAssignment& x) const {
00289         IntSet is(-3,-3);
00290         for (int i=x.size(); i--; ) {
00291           CountableSetRanges xr(x.lub, x[i]);
00292           IntSetRanges dr(is);
00293           switch (srt) {
00294           case SRT_EQ:
00295             if (!Iter::Ranges::equal(xr, dr))
00296               return false;
00297             break;
00298           case SRT_LQ:
00299             if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00300               return false;
00301             break;
00302           case SRT_LE:
00303             if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00304               return false;
00305             break;
00306           case SRT_GQ:
00307             if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00308               return false;
00309             break;
00310           case SRT_GR:
00311             if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00312               return false;
00313             break;
00314           case SRT_NQ:
00315             if (Iter::Ranges::equal(xr, dr))
00316               return false;
00317             break;
00318           case SRT_SUB:
00319             if (!(Iter::Ranges::subset(xr, dr)))
00320               return false;
00321             break;
00322           case SRT_SUP:
00323             if (!(Iter::Ranges::subset(dr, xr)))
00324               return false;
00325             break;
00326           case SRT_DISJ:
00327             {
00328               Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00329                 inter(xr, dr);
00330 
00331               if (inter())
00332                 return false;
00333               break;
00334             }
00335           case SRT_CMPL:
00336             {
00337               Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00338 
00339               if (!Iter::Ranges::equal(xr,drc))
00340                 return false;
00341               break;
00342             }
00343           }
00344         }
00345         return true;
00346       }
00348       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00349         if (x.size() == 1)
00350           Gecode::dom(home, x[0], srt, -3);
00351         else
00352           Gecode::dom(home, x, srt, -3);
00353       }
00355       virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00356         assert(x.size() == 1);
00357         if (Base::rand(2) != 0) {
00358           Gecode::dom(home, x[0], srt, -3, r);
00359         } else {
00360            switch (r.mode()) {
00361            case Gecode::RM_EQV:
00362              Gecode::rel(home, Gecode::dom(x[0], srt, -3) == r.var()); break;
00363            case Gecode::RM_IMP:
00364              Gecode::rel(home, Gecode::dom(x[0], srt, -3) << r.var()); break;
00365            case Gecode::RM_PMI:
00366              Gecode::rel(home, Gecode::dom(x[0], srt, -3) >> r.var()); break;
00367            default: GECODE_NEVER;
00368            }
00369         }
00370       }
00371     };
00372 
00374     class DomDom : public SetTest {
00375     private:
00376       Gecode::SetRelType srt;
00377       Gecode::IntSet is;
00378     public:
00380       DomDom(Gecode::SetRelType srt0, int n) :
00381         SetTest("Dom::Dom::"+str(srt0)+"::"+str(n),n,d1,(n == 1)),
00382         srt(srt0), is(srt == Gecode::SRT_CMPL ? d1c: d1) {}
00384       virtual bool solution(const SetAssignment& x) const {
00385         for (int i=x.size(); i--; ) {
00386           CountableSetRanges xr(x.lub, x[i]);
00387           IntSetRanges dr(is);
00388           switch (srt) {
00389           case SRT_EQ:
00390             if (!Iter::Ranges::equal(xr, dr))
00391               return false;
00392             break;
00393           case SRT_LQ:
00394             if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00395               return false;
00396             break;
00397           case SRT_LE:
00398             if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00399               return false;
00400             break;
00401           case SRT_GQ:
00402             if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00403               return false;
00404             break;
00405           case SRT_GR:
00406             if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00407               return false;
00408             break;
00409           case SRT_NQ:
00410             if (Iter::Ranges::equal(xr, dr))
00411               return false;
00412             break;
00413           case SRT_SUB:
00414             if (!Iter::Ranges::subset(xr, dr))
00415               return false;
00416             break;
00417           case SRT_SUP:
00418             if (!Iter::Ranges::subset(dr, xr))
00419               return false;
00420             break;
00421           case SRT_DISJ:
00422             {
00423               Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00424                 inter(xr, dr);
00425               if (inter())
00426                 return false;
00427             }
00428             break;
00429           case SRT_CMPL:
00430             {
00431               Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00432               if (!Iter::Ranges::equal(xr,drc))
00433                 return false;
00434             }
00435             break;
00436           }
00437         }
00438         return true;
00439       }
00441       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00442         if (x.size() == 1)
00443           Gecode::dom(home, x[0], srt, is);
00444         else
00445           Gecode::dom(home, x, srt, is);
00446       }
00448       virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00449         assert(x.size() == 1);
00450         Gecode::dom(home, x[0], srt, is, r);
00451       }
00452     };
00453 
00455     class CardRange : public SetTest {
00456     public:
00458       CardRange(int n)
00459         : SetTest("Dom::CardRange::"+str(n),n,d1,false) {}
00461       virtual bool solution(const SetAssignment& x) const {
00462         for (int i=x.size(); i--; ) {
00463           CountableSetRanges xr(x.lub, x[i]);
00464           unsigned int card = Iter::Ranges::size(xr);
00465           if ((card < 2) || (card > 3))
00466             return false;
00467         }
00468         return true;
00469       }
00471       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00472         if (x.size() == 1)
00473           Gecode::cardinality(home, x[0], 2, 3);
00474         else
00475           Gecode::cardinality(home, x, 2, 3);
00476       }
00477     };
00478 
00479     DomRange _domrange_eq1(SRT_EQ,1);
00480     DomRange _domrange_lq1(SRT_LQ,1);
00481     DomRange _domrange_le1(SRT_LE,1);
00482     DomRange _domrange_gq1(SRT_GQ,1);
00483     DomRange _domrange_gr1(SRT_GR,1);
00484     DomRange _domrange_nq1(SRT_NQ,1);
00485     DomRange _domrange_sub1(SRT_SUB,1);
00486     DomRange _domrange_sup1(SRT_SUP,1);
00487     DomRange _domrange_disj1(SRT_DISJ,1);
00488     DomRange _domrange_cmpl1(SRT_CMPL,1);
00489     DomRange _domrange_eq2(SRT_EQ,2);
00490     DomRange _domrange_lq2(SRT_LQ,2);
00491     DomRange _domrange_le2(SRT_LE,2);
00492     DomRange _domrange_gq2(SRT_GQ,2);
00493     DomRange _domrange_gr2(SRT_GR,2);
00494     DomRange _domrange_nq2(SRT_NQ,2);
00495     DomRange _domrange_sub2(SRT_SUB,2);
00496     DomRange _domrange_sup2(SRT_SUP,2);
00497     DomRange _domrange_disj2(SRT_DISJ,2);
00498     DomRange _domrange_cmpl2(SRT_CMPL,2);
00499 
00500     DomIntRange _domintrange_eq1(SRT_EQ,1);
00501     DomIntRange _domintrange_lq1(SRT_LQ,1);
00502     DomIntRange _domintrange_le1(SRT_LE,1);
00503     DomIntRange _domintrange_gq1(SRT_GQ,1);
00504     DomIntRange _domintrange_gr1(SRT_GR,1);
00505     DomIntRange _domintrange_nq1(SRT_NQ,1);
00506     DomIntRange _domintrange_sub1(SRT_SUB,1);
00507     DomIntRange _domintrange_sup1(SRT_SUP,1);
00508     DomIntRange _domintrange_disj1(SRT_DISJ,1);
00509     DomIntRange _domintrange_cmpl1(SRT_CMPL,1);
00510     DomIntRange _domintrange_eq2(SRT_EQ,2);
00511     DomIntRange _domintrange_lq2(SRT_LQ,2);
00512     DomIntRange _domintrange_le2(SRT_LE,2);
00513     DomIntRange _domintrange_gq2(SRT_GQ,2);
00514     DomIntRange _domintrange_gr2(SRT_GR,2);
00515     DomIntRange _domintrange_nq2(SRT_NQ,2);
00516     DomIntRange _domintrange_sub2(SRT_SUB,2);
00517     DomIntRange _domintrange_sup2(SRT_SUP,2);
00518     DomIntRange _domintrange_disj2(SRT_DISJ,2);
00519     DomIntRange _domintrange_cmpl2(SRT_CMPL,2);
00520 
00521     DomInt _domint_eq1(SRT_EQ,1);
00522     DomInt _domint_lq1(SRT_LQ,1);
00523     DomInt _domint_le1(SRT_LE,1);
00524     DomInt _domint_gq1(SRT_GQ,1);
00525     DomInt _domint_gr1(SRT_GR,1);
00526     DomInt _domint_nq1(SRT_NQ,1);
00527     DomInt _domint_sub1(SRT_SUB,1);
00528     DomInt _domint_sup1(SRT_SUP,1);
00529     DomInt _domint_disj1(SRT_DISJ,1);
00530     DomInt _domint_cmpl1(SRT_CMPL,1);
00531     DomInt _domint_eq2(SRT_EQ,2);
00532     DomInt _domint_lq2(SRT_LQ,2);
00533     DomInt _domint_le2(SRT_LE,2);
00534     DomInt _domint_gq2(SRT_GQ,2);
00535     DomInt _domint_gr2(SRT_GR,2);
00536     DomInt _domint_nq2(SRT_NQ,2);
00537     DomInt _domint_sub2(SRT_SUB,2);
00538     DomInt _domint_sup2(SRT_SUP,2);
00539     DomInt _domint_disj2(SRT_DISJ,2);
00540     DomInt _domint_cmpl2(SRT_CMPL,2);
00541 
00542     DomDom _domdom_eq1(SRT_EQ,1);
00543     DomDom _domdom_lq1(SRT_LQ,1);
00544     DomDom _domdom_le1(SRT_LE,1);
00545     DomDom _domdom_gq1(SRT_GQ,1);
00546     DomDom _domdom_gr1(SRT_GR,1);
00547     DomDom _domdom_nq1(SRT_NQ,1);
00548     DomDom _domdom_sub1(SRT_SUB,1);
00549     DomDom _domdom_sup1(SRT_SUP,1);
00550     DomDom _domdom_disj1(SRT_DISJ,1);
00551     DomDom _domdom_cmpl1(SRT_CMPL,1);
00552     DomDom _domdom_eq2(SRT_EQ,2);
00553     DomDom _domdom_lq2(SRT_LQ,2);
00554     DomDom _domdom_le2(SRT_LE,2);
00555     DomDom _domdom_gq2(SRT_GQ,2);
00556     DomDom _domdom_gr2(SRT_GR,2);
00557     DomDom _domdom_nq2(SRT_NQ,2);
00558     DomDom _domdom_sub2(SRT_SUB,2);
00559     DomDom _domdom_sup2(SRT_SUP,2);
00560     DomDom _domdom_disj2(SRT_DISJ,2);
00561     DomDom _domdom_cmpl2(SRT_CMPL,2);
00562 
00563     CardRange _cr1(1);
00564     CardRange _cr2(2);
00565 
00566 }}}
00567 
00568 // STATISTICS: test-set