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  *  Last modified:
00010  *     $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
00011  *     $Revision: 14967 $
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 "test/set.hh"
00039 
00040 using namespace Gecode;
00041 
00042 namespace Test { namespace Set {
00043 
00045   namespace Dom {
00046 
00052 
00053     static const int d1r[4][2] = {
00054       {-4,-3},{-1,-1},{1,1},{3,5}
00055     };
00056     static IntSet d1(d1r,4);
00057 
00058     static const int d1cr[5][2] = {
00059       {Gecode::Set::Limits::min,-5},
00060       {-2,-2},{0,0},{2,2},
00061       {6,Gecode::Set::Limits::max}
00062     };
00063     static IntSet d1c(d1cr,5);
00064 
00065     static IntSet ds_33(-3,3);
00066 
00067     static const int d2r[2][2] = {
00068       {Gecode::Set::Limits::min,-4}, {4,Gecode::Set::Limits::max}
00069     };
00070     static IntSet ds_33c(d2r,2);
00071 
00072     namespace {
00073       static int minSymDiff(const SetAssignment& x, int i, const IntSet& is) {
00074         typedef Iter::Ranges::Diff<CountableSetRanges,IntSetRanges> DiffA;
00075         CountableSetRanges xr00(x.lub, x[i]);
00076         IntSetRanges xr10(is);
00077         DiffA a(xr00,xr10);
00078         typedef Iter::Ranges::Diff<IntSetRanges,CountableSetRanges> DiffB;
00079         CountableSetRanges xr01(x.lub, x[i]);
00080         IntSetRanges xr11(is);
00081         DiffB b(xr11,xr01);
00082         Iter::Ranges::Union<DiffA,DiffB> u(a,b);
00083         return u() ? u.min() : Gecode::Set::Limits::max+1;
00084       }
00085       template<class I>
00086       static bool in(int i, I& c, bool eq=false) {
00087         if (eq && i==Gecode::Set::Limits::max+1)
00088           return true;
00089         Iter::Ranges::Singleton s(i,i);
00090         return Iter::Ranges::subset(s,c);
00091       }
00092     }
00093 
00095     class DomRange : public SetTest {
00096     private:
00097       Gecode::SetRelType srt;
00098       IntSet is;
00099     public:
00101       DomRange(SetRelType srt0, int n) :
00102         SetTest("Dom::Range::"+str(srt0)+"::"+str(n),n,ds_33,(n == 1)),
00103         srt(srt0), is(srt == Gecode::SRT_CMPL ? ds_33c: ds_33) {}
00105       virtual bool solution(const SetAssignment& x) const {
00106         for (int i=x.size(); i--; ) {
00107           CountableSetRanges xr(x.lub, x[i]);
00108           IntSetRanges dr(is);
00109           switch (srt) {
00110           case SRT_EQ:
00111             if (!Iter::Ranges::equal(xr, dr))
00112               return false;
00113             break;
00114           case SRT_LQ:
00115             if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00116               return false;
00117             break;
00118           case SRT_LE:
00119             if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00120               return false;
00121             break;
00122           case SRT_GQ:
00123             if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00124               return false;
00125             break;
00126           case SRT_GR:
00127             if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00128               return false;
00129             break;
00130           case SRT_NQ:
00131             if (Iter::Ranges::equal(xr, dr))
00132               return false;
00133             break;
00134           case SRT_SUB:
00135             if (!Iter::Ranges::subset(xr, dr))
00136               return false;
00137             break;
00138           case SRT_SUP:
00139             if (!Iter::Ranges::subset(dr, xr))
00140               return false;
00141             break;
00142           case SRT_DISJ:
00143             {
00144               Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00145                 inter(xr, dr);
00146               if (inter())
00147                 return false;
00148             }
00149             break;
00150           case SRT_CMPL:
00151             {
00152               Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00153               if (!Iter::Ranges::equal(xr,drc))
00154                 return false;
00155             }
00156             break;
00157           }
00158         }
00159         return true;
00160       }
00162       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00163         if (x.size() == 1)
00164           Gecode::dom(home, x[0], srt, is);
00165         else
00166           Gecode::dom(home, x, srt, is);
00167       }
00169       virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00170         assert(x.size() == 1);
00171         Gecode::dom(home, x[0], srt, is, r);
00172       }
00173     };
00174 
00176     class DomIntRange : public SetTest {
00177     private:
00178       Gecode::SetRelType srt;
00179     public:
00181       DomIntRange(Gecode::SetRelType srt0, int n)
00182         : SetTest("Dom::IntRange::"+str(srt0)+"::"+str(n),1,ds_33,n==1),
00183           srt(srt0) {}
00185       virtual bool solution(const SetAssignment& x) const {
00186         for (int i=x.size(); i--; ) {
00187           CountableSetRanges xr(x.lub, x[i]);
00188           IntSet is(-3,-1);
00189           IntSetRanges dr(is);
00190           switch (srt) {
00191           case SRT_EQ:
00192             if (!Iter::Ranges::equal(xr, dr))
00193               return false;
00194             break;
00195           case SRT_LQ:
00196             if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00197               return false;
00198             break;
00199           case SRT_LE:
00200             if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00201               return false;
00202             break;
00203           case SRT_GQ:
00204             if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00205               return false;
00206             break;
00207           case SRT_GR:
00208             if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00209               return false;
00210             break;
00211           case SRT_NQ:
00212             if (!(!Iter::Ranges::equal(xr, dr)))
00213               return false;
00214             break;
00215           case SRT_SUB:
00216             if (!(Iter::Ranges::subset(xr, dr)))
00217               return false;
00218             break;
00219           case SRT_SUP:
00220             if (!(Iter::Ranges::subset(dr, xr)))
00221               return false;
00222             break;
00223           case SRT_DISJ:
00224             {
00225               Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00226                 inter(xr, dr);
00227               if (inter())
00228                 return false;
00229             }
00230             break;
00231           case SRT_CMPL:
00232             {
00233               Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00234               if (!Iter::Ranges::equal(xr,drc))
00235                 return false;
00236             }
00237             break;
00238           }
00239         }
00240         return true;
00241       }
00243       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00244         if (x.size() == 1)
00245           Gecode::dom(home, x[0], srt, -3, -1);
00246         else
00247           Gecode::dom(home, x, srt, -3, -1);
00248       }
00250       virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00251         assert(x.size() == 1);
00252         Gecode::dom(home, x[0], srt, -3, -1, r);
00253       }
00254     };
00255 
00257     class DomInt : public SetTest {
00258     private:
00259       Gecode::SetRelType srt;
00260     public:
00262       DomInt(Gecode::SetRelType srt0, int n) :
00263         SetTest("Dom::Int::"+str(srt0)+"::"+str(n),n,ds_33,n==1),
00264         srt(srt0) {}
00266       virtual bool solution(const SetAssignment& x) const {
00267         IntSet is(-3,-3);
00268         for (int i=x.size(); i--; ) {
00269           CountableSetRanges xr(x.lub, x[i]);
00270           IntSetRanges dr(is);
00271           switch (srt) {
00272           case SRT_EQ:
00273             if (!Iter::Ranges::equal(xr, dr))
00274               return false;
00275             break;
00276           case SRT_LQ:
00277             if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00278               return false;
00279             break;
00280           case SRT_LE:
00281             if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00282               return false;
00283             break;
00284           case SRT_GQ:
00285             if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00286               return false;
00287             break;
00288           case SRT_GR:
00289             if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00290               return false;
00291             break;
00292           case SRT_NQ:
00293             if (Iter::Ranges::equal(xr, dr))
00294               return false;
00295             break;
00296           case SRT_SUB:
00297             if (!(Iter::Ranges::subset(xr, dr)))
00298               return false;
00299             break;
00300           case SRT_SUP:
00301             if (!(Iter::Ranges::subset(dr, xr)))
00302               return false;
00303             break;
00304           case SRT_DISJ:
00305             {
00306               Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00307                 inter(xr, dr);
00308 
00309               if (inter())
00310                 return false;
00311               break;
00312             }
00313           case SRT_CMPL:
00314             {
00315               Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00316 
00317               if (!Iter::Ranges::equal(xr,drc))
00318                 return false;
00319               break;
00320             }
00321           }
00322         }
00323         return true;
00324       }
00326       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00327         if (x.size() == 1)
00328           Gecode::dom(home, x[0], srt, -3);
00329         else
00330           Gecode::dom(home, x, srt, -3);
00331       }
00333       virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00334         assert(x.size() == 1);
00335         Gecode::dom(home, x[0], srt, -3, r);
00336       }
00337     };
00338 
00340     class DomDom : public SetTest {
00341     private:
00342       Gecode::SetRelType srt;
00343       Gecode::IntSet is;
00344     public:
00346       DomDom(Gecode::SetRelType srt0, int n) :
00347         SetTest("Dom::Dom::"+str(srt0)+"::"+str(n),n,d1,(n == 1)),
00348         srt(srt0), is(srt == Gecode::SRT_CMPL ? d1c: d1) {}
00350       virtual bool solution(const SetAssignment& x) const {
00351         for (int i=x.size(); i--; ) {
00352           CountableSetRanges xr(x.lub, x[i]);
00353           IntSetRanges dr(is);
00354           switch (srt) {
00355           case SRT_EQ:
00356             if (!Iter::Ranges::equal(xr, dr))
00357               return false;
00358             break;
00359           case SRT_LQ:
00360             if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
00361               return false;
00362             break;
00363           case SRT_LE:
00364             if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
00365               return false;
00366             break;
00367           case SRT_GQ:
00368             if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
00369               return false;
00370             break;
00371           case SRT_GR:
00372             if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
00373               return false;
00374             break;
00375           case SRT_NQ:
00376             if (Iter::Ranges::equal(xr, dr))
00377               return false;
00378             break;
00379           case SRT_SUB:
00380             if (!Iter::Ranges::subset(xr, dr))
00381               return false;
00382             break;
00383           case SRT_SUP:
00384             if (!Iter::Ranges::subset(dr, xr))
00385               return false;
00386             break;
00387           case SRT_DISJ:
00388             {
00389               Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00390                 inter(xr, dr);
00391               if (inter())
00392                 return false;
00393             }
00394             break;
00395           case SRT_CMPL:
00396             {
00397               Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00398               if (!Iter::Ranges::equal(xr,drc))
00399                 return false;
00400             }
00401             break;
00402           }
00403         }
00404         return true;
00405       }
00407       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00408         if (x.size() == 1)
00409           Gecode::dom(home, x[0], srt, is);
00410         else
00411           Gecode::dom(home, x, srt, is);
00412       }
00414       virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00415         assert(x.size() == 1);
00416         Gecode::dom(home, x[0], srt, is, r);
00417       }
00418     };
00419 
00421     class CardRange : public SetTest {
00422     public:
00424       CardRange(int n)
00425         : SetTest("Dom::CardRange::"+str(n),n,d1,false) {}
00427       virtual bool solution(const SetAssignment& x) const {
00428         for (int i=x.size(); i--; ) {
00429           CountableSetRanges xr(x.lub, x[i]);
00430           unsigned int card = Iter::Ranges::size(xr);
00431           if ((card < 2) || (card > 3))
00432             return false;
00433         }
00434         return true;
00435       }
00437       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00438         if (x.size() == 1)
00439           Gecode::cardinality(home, x[0], 2, 3);
00440         else
00441           Gecode::cardinality(home, x, 2, 3);
00442       }
00443     };
00444 
00445     DomRange _domrange_eq1(SRT_EQ,1);
00446     DomRange _domrange_lq1(SRT_LQ,1);
00447     DomRange _domrange_le1(SRT_LE,1);
00448     DomRange _domrange_gq1(SRT_GQ,1);
00449     DomRange _domrange_gr1(SRT_GR,1);
00450     DomRange _domrange_nq1(SRT_NQ,1);
00451     DomRange _domrange_sub1(SRT_SUB,1);
00452     DomRange _domrange_sup1(SRT_SUP,1);
00453     DomRange _domrange_disj1(SRT_DISJ,1);
00454     DomRange _domrange_cmpl1(SRT_CMPL,1);
00455     DomRange _domrange_eq2(SRT_EQ,2);
00456     DomRange _domrange_lq2(SRT_LQ,2);
00457     DomRange _domrange_le2(SRT_LE,2);
00458     DomRange _domrange_gq2(SRT_GQ,2);
00459     DomRange _domrange_gr2(SRT_GR,2);
00460     DomRange _domrange_nq2(SRT_NQ,2);
00461     DomRange _domrange_sub2(SRT_SUB,2);
00462     DomRange _domrange_sup2(SRT_SUP,2);
00463     DomRange _domrange_disj2(SRT_DISJ,2);
00464     DomRange _domrange_cmpl2(SRT_CMPL,2);
00465 
00466     DomIntRange _domintrange_eq1(SRT_EQ,1);
00467     DomIntRange _domintrange_lq1(SRT_LQ,1);
00468     DomIntRange _domintrange_le1(SRT_LE,1);
00469     DomIntRange _domintrange_gq1(SRT_GQ,1);
00470     DomIntRange _domintrange_gr1(SRT_GR,1);
00471     DomIntRange _domintrange_nq1(SRT_NQ,1);
00472     DomIntRange _domintrange_sub1(SRT_SUB,1);
00473     DomIntRange _domintrange_sup1(SRT_SUP,1);
00474     DomIntRange _domintrange_disj1(SRT_DISJ,1);
00475     DomIntRange _domintrange_cmpl1(SRT_CMPL,1);
00476     DomIntRange _domintrange_eq2(SRT_EQ,2);
00477     DomIntRange _domintrange_lq2(SRT_LQ,2);
00478     DomIntRange _domintrange_le2(SRT_LE,2);
00479     DomIntRange _domintrange_gq2(SRT_GQ,2);
00480     DomIntRange _domintrange_gr2(SRT_GR,2);
00481     DomIntRange _domintrange_nq2(SRT_NQ,2);
00482     DomIntRange _domintrange_sub2(SRT_SUB,2);
00483     DomIntRange _domintrange_sup2(SRT_SUP,2);
00484     DomIntRange _domintrange_disj2(SRT_DISJ,2);
00485     DomIntRange _domintrange_cmpl2(SRT_CMPL,2);
00486 
00487     DomInt _domint_eq1(SRT_EQ,1);
00488     DomInt _domint_lq1(SRT_LQ,1);
00489     DomInt _domint_le1(SRT_LE,1);
00490     DomInt _domint_gq1(SRT_GQ,1);
00491     DomInt _domint_gr1(SRT_GR,1);
00492     DomInt _domint_nq1(SRT_NQ,1);
00493     DomInt _domint_sub1(SRT_SUB,1);
00494     DomInt _domint_sup1(SRT_SUP,1);
00495     DomInt _domint_disj1(SRT_DISJ,1);
00496     DomInt _domint_cmpl1(SRT_CMPL,1);
00497     DomInt _domint_eq2(SRT_EQ,2);
00498     DomInt _domint_lq2(SRT_LQ,2);
00499     DomInt _domint_le2(SRT_LE,2);
00500     DomInt _domint_gq2(SRT_GQ,2);
00501     DomInt _domint_gr2(SRT_GR,2);
00502     DomInt _domint_nq2(SRT_NQ,2);
00503     DomInt _domint_sub2(SRT_SUB,2);
00504     DomInt _domint_sup2(SRT_SUP,2);
00505     DomInt _domint_disj2(SRT_DISJ,2);
00506     DomInt _domint_cmpl2(SRT_CMPL,2);
00507 
00508     DomDom _domdom_eq1(SRT_EQ,1);
00509     DomDom _domdom_lq1(SRT_LQ,1);
00510     DomDom _domdom_le1(SRT_LE,1);
00511     DomDom _domdom_gq1(SRT_GQ,1);
00512     DomDom _domdom_gr1(SRT_GR,1);
00513     DomDom _domdom_nq1(SRT_NQ,1);
00514     DomDom _domdom_sub1(SRT_SUB,1);
00515     DomDom _domdom_sup1(SRT_SUP,1);
00516     DomDom _domdom_disj1(SRT_DISJ,1);
00517     DomDom _domdom_cmpl1(SRT_CMPL,1);
00518     DomDom _domdom_eq2(SRT_EQ,2);
00519     DomDom _domdom_lq2(SRT_LQ,2);
00520     DomDom _domdom_le2(SRT_LE,2);
00521     DomDom _domdom_gq2(SRT_GQ,2);
00522     DomDom _domdom_gr2(SRT_GR,2);
00523     DomDom _domdom_nq2(SRT_NQ,2);
00524     DomDom _domdom_sub2(SRT_SUB,2);
00525     DomDom _domdom_sup2(SRT_SUP,2);
00526     DomDom _domdom_disj2(SRT_DISJ,2);
00527     DomDom _domdom_cmpl2(SRT_CMPL,2);
00528 
00529     CardRange _cr1(1);
00530     CardRange _cr2(2);
00531 
00532 }}}
00533 
00534 // STATISTICS: test-set