dom.cpp

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           default: GECODE_NEVER;
00156           }
00157         }
00158         return true;
00159       }
00161       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00162         if (x.size() == 1)
00163           Gecode::dom(home, x[0], srt, is);
00164         else
00165           Gecode::dom(home, x, srt, is);
00166       }
00168       virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00169         assert(x.size() == 1);
00170         if (Base::rand(2) != 0) {
00171           Gecode::dom(home, x[0], srt, is, r);
00172         } else {
00173            switch (r.mode()) {
00174            case Gecode::RM_EQV:
00175              Gecode::rel(home, Gecode::dom(x[0], srt, is) == r.var()); break;
00176            case Gecode::RM_IMP:
00177              Gecode::rel(home, Gecode::dom(x[0], srt, is) << r.var()); break;
00178            case Gecode::RM_PMI:
00179              Gecode::rel(home, Gecode::dom(x[0], srt, is) >> r.var()); break;
00180            default: GECODE_NEVER;
00181            }
00182         }
00183       }
00184     };
00185 
00187     class DomIntRange : public SetTest {
00188     private:
00189       Gecode::SetRelType srt;
00190     public:
00192       DomIntRange(Gecode::SetRelType srt0, int n)
00193         : SetTest("Dom::IntRange::"+str(srt0)+"::"+str(n),1,ds_33,n==1),
00194           srt(srt0) {}
00196       virtual bool solution(const SetAssignment& x) const {
00197         for (int i=x.size(); i--; ) {
00198           CountableSetRanges xr(x.lub, x[i]);
00199           IntSet is(-3,-1);
00200           IntSetRanges dr(is);
00201           switch (srt) {
00202           case SRT_EQ:
00203             if (!Iter::Ranges::equal(xr, dr))
00204               return false;
00205             break;
00206           case SRT_LQ:
00207             if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00208               return false;
00209             break;
00210           case SRT_LE:
00211             if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00212               return false;
00213             break;
00214           case SRT_GQ:
00215             if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00216               return false;
00217             break;
00218           case SRT_GR:
00219             if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00220               return false;
00221             break;
00222           case SRT_NQ:
00223             if (!(!Iter::Ranges::equal(xr, dr)))
00224               return false;
00225             break;
00226           case SRT_SUB:
00227             if (!(Iter::Ranges::subset(xr, dr)))
00228               return false;
00229             break;
00230           case SRT_SUP:
00231             if (!(Iter::Ranges::subset(dr, xr)))
00232               return false;
00233             break;
00234           case SRT_DISJ:
00235             {
00236               Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00237                 inter(xr, dr);
00238               if (inter())
00239                 return false;
00240             }
00241             break;
00242           case SRT_CMPL:
00243             {
00244               Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00245               if (!Iter::Ranges::equal(xr,drc))
00246                 return false;
00247             }
00248             break;
00249           default: GECODE_NEVER;
00250           }
00251         }
00252         return true;
00253       }
00255       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00256         if (x.size() == 1)
00257           Gecode::dom(home, x[0], srt, -3, -1);
00258         else
00259           Gecode::dom(home, x, srt, -3, -1);
00260       }
00262       virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00263         assert(x.size() == 1);
00264         if (Base::rand(2) != 0) {
00265           Gecode::dom(home, x[0], srt, -3, -1, r);
00266         } else {
00267            switch (r.mode()) {
00268            case Gecode::RM_EQV:
00269              Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) == r.var()); break;
00270            case Gecode::RM_IMP:
00271              Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) << r.var()); break;
00272            case Gecode::RM_PMI:
00273              Gecode::rel(home, Gecode::dom(x[0], srt, -3, -1) >> r.var()); break;
00274            default: GECODE_NEVER;
00275            }
00276         }
00277       }
00278     };
00279 
00281     class DomInt : public SetTest {
00282     private:
00283       Gecode::SetRelType srt;
00284     public:
00286       DomInt(Gecode::SetRelType srt0, int n) :
00287         SetTest("Dom::Int::"+str(srt0)+"::"+str(n),n,ds_33,n==1),
00288         srt(srt0) {}
00290       virtual bool solution(const SetAssignment& x) const {
00291         IntSet is(-3,-3);
00292         for (int i=x.size(); i--; ) {
00293           CountableSetRanges xr(x.lub, x[i]);
00294           IntSetRanges dr(is);
00295           switch (srt) {
00296           case SRT_EQ:
00297             if (!Iter::Ranges::equal(xr, dr))
00298               return false;
00299             break;
00300           case SRT_LQ:
00301             if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00302               return false;
00303             break;
00304           case SRT_LE:
00305             if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00306               return false;
00307             break;
00308           case SRT_GQ:
00309             if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00310               return false;
00311             break;
00312           case SRT_GR:
00313             if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00314               return false;
00315             break;
00316           case SRT_NQ:
00317             if (Iter::Ranges::equal(xr, dr))
00318               return false;
00319             break;
00320           case SRT_SUB:
00321             if (!(Iter::Ranges::subset(xr, dr)))
00322               return false;
00323             break;
00324           case SRT_SUP:
00325             if (!(Iter::Ranges::subset(dr, xr)))
00326               return false;
00327             break;
00328           case SRT_DISJ:
00329             {
00330               Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00331                 inter(xr, dr);
00332 
00333               if (inter())
00334                 return false;
00335               break;
00336             }
00337           case SRT_CMPL:
00338             {
00339               Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00340 
00341               if (!Iter::Ranges::equal(xr,drc))
00342                 return false;
00343               break;
00344             }
00345           default: GECODE_NEVER;
00346           }
00347         }
00348         return true;
00349       }
00351       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00352         if (x.size() == 1)
00353           Gecode::dom(home, x[0], srt, -3);
00354         else
00355           Gecode::dom(home, x, srt, -3);
00356       }
00358       virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00359         assert(x.size() == 1);
00360         if (Base::rand(2) != 0) {
00361           Gecode::dom(home, x[0], srt, -3, r);
00362         } else {
00363            switch (r.mode()) {
00364            case Gecode::RM_EQV:
00365              Gecode::rel(home, Gecode::dom(x[0], srt, -3) == r.var()); break;
00366            case Gecode::RM_IMP:
00367              Gecode::rel(home, Gecode::dom(x[0], srt, -3) << r.var()); break;
00368            case Gecode::RM_PMI:
00369              Gecode::rel(home, Gecode::dom(x[0], srt, -3) >> r.var()); break;
00370            default: GECODE_NEVER;
00371            }
00372         }
00373       }
00374     };
00375 
00377     class DomDom : public SetTest {
00378     private:
00379       Gecode::SetRelType srt;
00380       Gecode::IntSet is;
00381     public:
00383       DomDom(Gecode::SetRelType srt0, int n) :
00384         SetTest("Dom::Dom::"+str(srt0)+"::"+str(n),n,d1,(n == 1)),
00385         srt(srt0), is(srt == Gecode::SRT_CMPL ? d1c: d1) {}
00387       virtual bool solution(const SetAssignment& x) const {
00388         for (int i=x.size(); i--; ) {
00389           CountableSetRanges xr(x.lub, x[i]);
00390           IntSetRanges dr(is);
00391           switch (srt) {
00392           case SRT_EQ:
00393             if (!Iter::Ranges::equal(xr, dr))
00394               return false;
00395             break;
00396           case SRT_LQ:
00397             if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00398               return false;
00399             break;
00400           case SRT_LE:
00401             if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00402               return false;
00403             break;
00404           case SRT_GQ:
00405             if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00406               return false;
00407             break;
00408           case SRT_GR:
00409             if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00410               return false;
00411             break;
00412           case SRT_NQ:
00413             if (Iter::Ranges::equal(xr, dr))
00414               return false;
00415             break;
00416           case SRT_SUB:
00417             if (!Iter::Ranges::subset(xr, dr))
00418               return false;
00419             break;
00420           case SRT_SUP:
00421             if (!Iter::Ranges::subset(dr, xr))
00422               return false;
00423             break;
00424           case SRT_DISJ:
00425             {
00426               Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00427                 inter(xr, dr);
00428               if (inter())
00429                 return false;
00430             }
00431             break;
00432           case SRT_CMPL:
00433             {
00434               Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00435               if (!Iter::Ranges::equal(xr,drc))
00436                 return false;
00437             }
00438             break;
00439           default: GECODE_NEVER;
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