rel-op-const.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 "test/set.hh"
00035 
00036 using namespace Gecode;
00037 
00038 namespace Test { namespace Set {
00039 
00041   namespace RelOpConst {
00042 
00048 
00049     static IntSet ds_33(-3,3);
00050     static IntSet ds_22(-2,2);
00051     static IntSet ds_12(-1,2);
00052 
00053     static IntSet iss[] = {IntSet(-1,1), IntSet(-4,-4), IntSet(0,2)};
00054 
00056     class RelSIS : public SetTest {
00057     private:
00058       IntSet is;
00059       Gecode::SetOpType sot;
00060       Gecode::SetRelType srt;
00061       bool inverse;
00062 
00063       template<class I, class J>
00064       bool
00065       sol(I& i, J& j) const {
00066         switch (srt) {
00067         case SRT_EQ: return Iter::Ranges::equal(i,j);
00068         case SRT_NQ: return !Iter::Ranges::equal(i,j);
00069         case SRT_SUB: return Iter::Ranges::subset(i,j);
00070         case SRT_SUP: return Iter::Ranges::subset(j,i);
00071         case SRT_DISJ:
00072           {
00073             Gecode::Iter::Ranges::Inter<I,J> inter(i,j);
00074             return !inter();
00075           }
00076         case SRT_CMPL:
00077           {
00078             Gecode::Set::RangesCompl<J> jc(j);
00079             return Iter::Ranges::equal(i,jc);
00080           }
00081         }
00082         GECODE_NEVER;
00083         return false;
00084       }
00085 
00086     public:
00088       RelSIS(Gecode::SetOpType sot0, Gecode::SetRelType srt0,
00089              int intSet, bool inverse0)
00090        : SetTest("RelOp::ConstSIS::"+str(sot0)+"::"+str(srt0)+"::"+
00091                  str(intSet)+(inverse0 ? "i" :""),2,ds_22,false)
00092        , is(iss[intSet]), sot(sot0), srt(srt0), inverse(inverse0) {}
00094       bool solution(const SetAssignment& x) const {
00095         IntSetRanges isr(is);
00096         CountableSetRanges xr0(x.lub, x[0]);
00097         CountableSetRanges xr1(x.lub, x[1]);
00098         switch (sot) {
00099         case SOT_UNION:
00100           {
00101             Iter::Ranges::Union<IntSetRanges, CountableSetRanges>
00102               u(isr, xr0);
00103             return sol(u,xr1);
00104           }
00105           break;
00106         case SOT_DUNION:
00107           {
00108             Iter::Ranges::Inter<IntSetRanges, CountableSetRanges>
00109               inter(isr, xr0);
00110             if (inter())
00111               return false;
00112             Iter::Ranges::Union<IntSetRanges, CountableSetRanges>
00113               u(isr,xr0);
00114             return sol(u,xr1);
00115           }
00116           break;
00117         case SOT_INTER:
00118           {
00119             Iter::Ranges::Inter<IntSetRanges, CountableSetRanges>
00120               u(isr,xr0);
00121             return sol(u,xr1);
00122           }
00123           break;
00124         case SOT_MINUS:
00125           {
00126             if (!inverse) {
00127               Iter::Ranges::Diff<IntSetRanges, CountableSetRanges>
00128                 u(isr,xr0);
00129               return sol(u,xr1);
00130             } else {
00131               Iter::Ranges::Diff<CountableSetRanges, IntSetRanges>
00132                 u(xr0,isr);
00133               return sol(u,xr1);
00134 
00135             }
00136           }
00137           break;
00138         }
00139         GECODE_NEVER;
00140         return false;
00141       }
00143       void post(Space& home, SetVarArray& x, IntVarArray&) {
00144         if (!inverse)
00145           Gecode::rel(home, is, sot, x[0], srt, x[1]);
00146         else
00147           Gecode::rel(home, x[0], sot, is, srt, x[1]);
00148       }
00149     };
00150 
00152     class RelSSI : public SetTest {
00153     private:
00154       IntSet is;
00155       Gecode::SetOpType sot;
00156       Gecode::SetRelType srt;
00157 
00158       template<class I, class J>
00159       bool
00160       sol(I& i, J& j) const {
00161         switch (srt) {
00162         case SRT_EQ: return Iter::Ranges::equal(i,j);
00163         case SRT_NQ: return !Iter::Ranges::equal(i,j);
00164         case SRT_SUB: return Iter::Ranges::subset(i,j);
00165         case SRT_SUP: return Iter::Ranges::subset(j,i);
00166         case SRT_DISJ:
00167           {
00168             Gecode::Iter::Ranges::Inter<I,J> inter(i,j);
00169             return !inter();
00170           }
00171         case SRT_CMPL:
00172           {
00173             Gecode::Set::RangesCompl<J> jc(j);
00174             return Iter::Ranges::equal(i,jc);
00175           }
00176         }
00177         GECODE_NEVER;
00178         return false;
00179       }
00180 
00181     public:
00183       RelSSI(Gecode::SetOpType sot0, Gecode::SetRelType srt0,
00184              int intSet)
00185        : SetTest("RelOp::ConstSSI::"+str(sot0)+"::"+str(srt0)+"::"+
00186                  str(intSet),2,ds_22,false)
00187        , is(iss[intSet]), sot(sot0), srt(srt0) {}
00189       bool solution(const SetAssignment& x) const {
00190         CountableSetRanges xr0(x.lub, x[0]);
00191         CountableSetRanges xr1(x.lub, x[1]);
00192         IntSetRanges isr(is);
00193         switch (sot) {
00194         case SOT_UNION:
00195           {
00196             Iter::Ranges::Union<CountableSetRanges, CountableSetRanges>
00197               u(xr0, xr1);
00198             return sol(u,isr);
00199           }
00200           break;
00201         case SOT_DUNION:
00202           {
00203             Iter::Ranges::Inter<CountableSetRanges, CountableSetRanges>
00204               inter(xr0, xr1);
00205             if (inter())
00206               return false;
00207             Iter::Ranges::Union<CountableSetRanges, CountableSetRanges>
00208               u(xr0, xr1);
00209             return sol(u,isr);
00210           }
00211           break;
00212         case SOT_INTER:
00213           {
00214             Iter::Ranges::Inter<CountableSetRanges, CountableSetRanges>
00215               u(xr0,xr1);
00216             return sol(u,isr);
00217           }
00218           break;
00219         case SOT_MINUS:
00220           {
00221             Iter::Ranges::Diff<CountableSetRanges, CountableSetRanges>
00222               u(xr0,xr1);
00223             return sol(u,isr);
00224           }
00225           break;
00226         }
00227         GECODE_NEVER;
00228         return false;
00229       }
00231       void post(Space& home, SetVarArray& x, IntVarArray&) {
00232         Gecode::rel(home, x[0], sot, x[1], srt, is);
00233       }
00234     };
00235 
00237     class RelISI : public SetTest {
00238     private:
00239       IntSet is0;
00240       IntSet is1;
00241       Gecode::SetOpType sot;
00242       Gecode::SetRelType srt;
00243       bool inverse;
00244 
00245       template<class I, class J>
00246       bool
00247       sol(I& i, J& j) const {
00248         switch (srt) {
00249         case SRT_EQ: return Iter::Ranges::equal(i,j);
00250         case SRT_NQ: return !Iter::Ranges::equal(i,j);
00251         case SRT_SUB: return Iter::Ranges::subset(i,j);
00252         case SRT_SUP: return Iter::Ranges::subset(j,i);
00253         case SRT_DISJ:
00254           {
00255             Gecode::Iter::Ranges::Inter<I,J> inter(i,j);
00256             return !inter();
00257           }
00258         case SRT_CMPL:
00259           {
00260             Gecode::Set::RangesCompl<J> jc(j);
00261             return Iter::Ranges::equal(i,jc);
00262           }
00263         }
00264         GECODE_NEVER;
00265         return false;
00266       }
00267 
00268     public:
00270       RelISI(Gecode::SetOpType sot0, Gecode::SetRelType srt0,
00271              int intSet0, int intSet1, bool inverse0)
00272        : SetTest("RelOp::ConstISI::"+str(sot0)+"::"+str(srt0)+"::"+
00273                  str(intSet0)+"::"+str(intSet1)+
00274                  (inverse0 ? "i" : ""),1,ds_33,false)
00275        , is0(iss[intSet0]), is1(iss[intSet1]), sot(sot0), srt(srt0)
00276        , inverse(inverse0) {}
00278       bool solution(const SetAssignment& x) const {
00279         CountableSetRanges xr0(x.lub, x[0]);
00280         IntSetRanges isr0(is0);
00281         IntSetRanges isr1(is1);
00282         switch (sot) {
00283         case SOT_UNION:
00284           {
00285             Iter::Ranges::Union<IntSetRanges, CountableSetRanges>
00286               u(isr0, xr0);
00287             return sol(u,isr1);
00288           }
00289           break;
00290         case SOT_DUNION:
00291           {
00292             Iter::Ranges::Inter<IntSetRanges, CountableSetRanges>
00293               inter(isr0, xr0);
00294             if (inter())
00295               return false;
00296             Iter::Ranges::Union<IntSetRanges, CountableSetRanges>
00297               u(isr0, xr0);
00298             return sol(u,isr1);
00299           }
00300           break;
00301         case SOT_INTER:
00302           {
00303             Iter::Ranges::Inter<IntSetRanges, CountableSetRanges>
00304               u(isr0,xr0);
00305             return sol(u,isr1);
00306           }
00307           break;
00308         case SOT_MINUS:
00309           {
00310             if (!inverse) {
00311               Iter::Ranges::Diff<IntSetRanges, CountableSetRanges>
00312                 u(isr0,xr0);
00313               return sol(u,isr1);
00314             } else {
00315               Iter::Ranges::Diff<CountableSetRanges, IntSetRanges>
00316                 u(xr0,isr0);
00317               return sol(u,isr1);
00318             }
00319           }
00320           break;
00321         }
00322         GECODE_NEVER;
00323         return false;
00324       }
00326       void post(Space& home, SetVarArray& x, IntVarArray&) {
00327         if (!inverse)
00328           Gecode::rel(home, is0, sot, x[0], srt, is1);
00329         else
00330           Gecode::rel(home, x[0], sot, is0, srt, is1);
00331       }
00332     };
00333 
00335     class Create {
00336     public:
00338       Create(void) {
00339         using namespace Gecode;
00340         for (SetRelTypes srts; srts(); ++srts) {
00341           for (SetOpTypes sots; sots(); ++sots) {
00342             for (int i=0; i<=2; i++) {
00343               (void) new RelSIS(sots.sot(),srts.srt(),i,false);
00344               (void) new RelSIS(sots.sot(),srts.srt(),i,true);
00345               (void) new RelSSI(sots.sot(),srts.srt(),i);
00346               (void) new RelISI(sots.sot(),srts.srt(),i,0,false);
00347               (void) new RelISI(sots.sot(),srts.srt(),i,1,false);
00348               (void) new RelISI(sots.sot(),srts.srt(),i,2,false);
00349               (void) new RelISI(sots.sot(),srts.srt(),i,0,true);
00350               (void) new RelISI(sots.sot(),srts.srt(),i,1,true);
00351               (void) new RelISI(sots.sot(),srts.srt(),i,2,true);
00352             }
00353           }
00354         }
00355       }
00356     };
00357 
00358     Create c;
00359 
00361 
00362 }}}
00363 
00364 // STATISTICS: test-set