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