rel.cpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2005
00008  *
00009  *  Last modified:
00010  *     $Date: 2011-07-06 21:56:28 +0200 (Wed, 06 Jul 2011) $ by $Author: schulte $
00011  *     $Revision: 12151 $
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/int.hh"
00039 
00040 #include <gecode/minimodel.hh>
00041 
00042 namespace Test { namespace Int {
00043 
00045    namespace Rel {
00046 
00052 
00053      class IntVarXY : public Test {
00054      protected:
00056        Gecode::IntRelType irt;
00057      public:
00059        IntVarXY(Gecode::IntRelType irt0, int n, Gecode::IntConLevel icl)
00060          : Test("Rel::Int::Var::XY::"+str(irt0)+"::"+str(icl)+"::"+str(n),
00061                 n+1,-3,3,n==1,icl),
00062            irt(irt0) {}
00064        virtual bool solution(const Assignment& x) const {
00065          if (x.size() == 2) {
00066            return cmp(x[0],irt,x[1]);
00067          } else {
00068            return cmp(x[0],irt,x[2]) && cmp(x[1],irt,x[2]);
00069          }
00070        }
00072        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00073          using namespace Gecode;
00074          if (x.size() == 2) {
00075            rel(home, x[0], irt, x[1], icl);
00076          } else {
00077            IntVarArgs y(2);
00078            y[0]=x[0]; y[1]=x[1];
00079            rel(home, y, irt, x[2], icl);
00080          }
00081        }
00083        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00084                          Gecode::BoolVar b) {
00085          assert(x.size() == 2);
00086          Gecode::rel(home, x[0], irt, x[1], b, icl);
00087        }
00088      };
00089 
00091      class IntVarXX : public Test {
00092      protected:
00094        Gecode::IntRelType irt;
00095      public:
00097        IntVarXX(Gecode::IntRelType irt0, Gecode::IntConLevel icl)
00098          : Test("Rel::Int::Var::XX::"+str(irt0)+"::"+str(icl),
00099                 1,-3,3,true,icl),
00100            irt(irt0) {
00101          contest = ((irt != Gecode::IRT_LE) &&
00102                     (irt != Gecode::IRT_GR) &&
00103                     (irt != Gecode::IRT_NQ))
00104            ? CTL_DOMAIN : CTL_NONE;
00105        }
00107        virtual bool solution(const Assignment& x) const {
00108          return cmp(x[0],irt,x[0]);
00109        }
00111        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00112          Gecode::rel(home, x[0], irt, x[0], icl);
00113        }
00115        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00116                          Gecode::BoolVar b) {
00117          Gecode::rel(home, x[0], irt, x[0], b, icl);
00118        }
00119      };
00120 
00122      class BoolVarXY : public Test {
00123      protected:
00125        Gecode::IntRelType irt;
00126      public:
00128        BoolVarXY(Gecode::IntRelType irt0, int n)
00129          : Test("Rel::Bool::Var::XY::"+str(irt0)+"::"+str(n),n+1,0,1,
00130                 n==1),
00131            irt(irt0) {}
00133        virtual bool solution(const Assignment& x) const {
00134          if (x.size() == 2) {
00135            return cmp(x[0],irt,x[1]);
00136          } else {
00137            return cmp(x[0],irt,x[2]) && cmp(x[1],irt,x[2]);
00138          }
00139        }
00141        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00142          using namespace Gecode;
00143          if (x.size() == 2) {
00144            rel(home, channel(home,x[0]), irt, channel(home,x[1]));
00145          } else {
00146            BoolVarArgs y(2);
00147            y[0]=channel(home,x[0]); y[1]=channel(home,x[1]);
00148            rel(home, y, irt, channel(home,x[2]));
00149          }
00150        }
00152        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00153                          Gecode::BoolVar b) {
00154          assert(x.size() == 2);
00155          using namespace Gecode;
00156          rel(home,
00157              channel(home,x[0]), irt, channel(home,x[1]),
00158              b);
00159        }
00160      };
00161 
00163      class BoolVarXX : public Test {
00164      protected:
00166        Gecode::IntRelType irt;
00167      public:
00169        BoolVarXX(Gecode::IntRelType irt0)
00170          : Test("Rel::Bool::Var::XX::"+str(irt0),1,0,1),
00171            irt(irt0) {
00172          contest = ((irt != Gecode::IRT_LE) &&
00173                     (irt != Gecode::IRT_GR) &&
00174                     (irt != Gecode::IRT_NQ))
00175            ? CTL_DOMAIN : CTL_NONE;
00176        }
00178        virtual bool solution(const Assignment& x) const {
00179          return cmp(x[0],irt,x[0]);
00180        }
00182        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00183          Gecode::BoolVar b = Gecode::channel(home,x[0]);
00184          Gecode::rel(home, b, irt, b);
00185        }
00186      };
00187 
00189      class IntInt : public Test {
00190      protected:
00192        Gecode::IntRelType irt;
00194        int c;
00195      public:
00197        IntInt(Gecode::IntRelType irt0, int n, int c0)
00198          : Test("Rel::Int::Int::"+str(irt0)+"::"+str(n)+"::"+str(c0),
00199                 n,-3,3,n==1),
00200            irt(irt0), c(c0) {}
00202        virtual bool solution(const Assignment& x) const {
00203          if (x.size() == 1)
00204            return cmp(x[0],irt,c);
00205          else
00206            return cmp(x[0],irt,c) && cmp(x[1],irt,c);
00207        }
00209        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00210          using namespace Gecode;
00211          if (x.size() == 1)
00212            rel(home, x[0], irt, c);
00213          else
00214            rel(home, x, irt, c);
00215        }
00217        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00218                          Gecode::BoolVar b) {
00219          assert(x.size() == 1);
00220          Gecode::rel(home, x[0], irt, c, b);
00221        }
00222      };
00223 
00225      class BoolInt : public Test {
00226      protected:
00228        Gecode::IntRelType irt;
00230        int c;
00231      public:
00233        BoolInt(Gecode::IntRelType irt0, int n, int c0)
00234          : Test("Rel::Bool::Int::"+str(irt0)+"::"+str(n)+"::"+str(c0),n,0,1,
00235                 n==1),
00236            irt(irt0), c(c0) {}
00238        virtual bool solution(const Assignment& x) const {
00239          if (x.size() == 1)
00240            return cmp(x[0],irt,c);
00241          else
00242            return cmp(x[0],irt,c) && cmp(x[1],irt,c);
00243        }
00245        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00246          using namespace Gecode;
00247          if (x.size() == 1) {
00248            rel(home, channel(home,x[0]), irt, c);
00249          } else {
00250            BoolVarArgs y(2);
00251            y[0]=channel(home,x[0]); y[1]=channel(home,x[1]);
00252            rel(home, y, irt, c);
00253          }
00254        }
00256        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00257                          Gecode::BoolVar b) {
00258          assert(x.size() == 1);
00259          using namespace Gecode;
00260          rel(home, channel(home,x[0]), irt, c, b);
00261        }
00262      };
00263 
00265      class IntSeq : public Test {
00266      protected:
00268        Gecode::IntRelType irt;
00269      public:
00271        IntSeq(int n, Gecode::IntRelType irt0, Gecode::IntConLevel icl)
00272          : Test("Rel::Int::Seq::"+str(n)+"::"+str(irt0)+"::"+str(icl),
00273                 n,-3,3,false,icl),
00274            irt(irt0) {}
00276        virtual bool solution(const Assignment& x) const {
00277          if (irt == Gecode::IRT_NQ) {
00278            if (x.size() < 2)
00279              return false;
00280            for (int i=0; i<x.size()-1; i++)
00281              if (x[i] != x[i+1])
00282                return true;
00283            return false;
00284          } else {
00285            for (int i=0; i<x.size()-1; i++)
00286              if (!cmp(x[i],irt,x[i+1]))
00287                return false;
00288            return true;
00289          }
00290        }
00292        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00293          Gecode::rel(home, x, irt, icl);
00294        }
00295      };
00296 
00298      class IntSharedSeq : public Test {
00299      protected:
00301        Gecode::IntRelType irt;
00302      public:
00304        IntSharedSeq(int n, Gecode::IntRelType irt0, Gecode::IntConLevel icl)
00305          : Test("Rel::Int::Seq::Shared::"+str(n)+"::"+str(irt0)+"::"+str(icl),
00306                 n,-3,3,false,icl),
00307            irt(irt0) {}
00309        virtual bool solution(const Assignment& x) const {
00310          if (irt == Gecode::IRT_NQ) {
00311            if (x.size() < 2)
00312              return false;
00313            for (int i=0; i<x.size()-1; i++)
00314              if (x[i] != x[i+1])
00315                return true;
00316            return false;
00317          } else {
00318            int n = x.size();
00319            for (int i=0; i<2*n-1; i++)
00320              if (!cmp(x[i % n],irt,x[(i+1) % n]))
00321                return false;
00322            return true;
00323          }
00324        }
00326        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00327          using namespace Gecode;
00328          int n = x.size();
00329          IntVarArgs y(2*n);
00330          for (int i=n; i--; ) 
00331            y[i] = y[n+i] = x[i];
00332          rel(home, y, irt, icl);
00333        }
00334      };
00335 
00337      class BoolSeq : public Test {
00338      protected:
00340        Gecode::IntRelType irt;
00341      public:
00343        BoolSeq(int n, Gecode::IntRelType irt0)
00344          : Test("Rel::Bool::Seq::"+str(n)+"::"+str(irt0),n,0,1),
00345            irt(irt0) {}
00347        virtual bool solution(const Assignment& x) const {
00348          if (irt == Gecode::IRT_NQ) {
00349            if (x.size() < 2)
00350              return false;
00351            for (int i=0; i<x.size()-1; i++)
00352              if (x[i] != x[i+1])
00353                return true;
00354            return false;
00355          } else {
00356            for (int i=0; i<x.size()-1; i++)
00357              if (!cmp(x[i],irt,x[i+1]))
00358                return false;
00359            return true;
00360          }
00361        }
00363        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00364          using namespace Gecode;
00365          BoolVarArgs b(x.size());
00366          for (int i=x.size(); i--; )
00367            b[i]=channel(home,x[i]);
00368          rel(home, b, irt);
00369        }
00370      };
00371 
00373      class BoolSharedSeq : public Test {
00374      protected:
00376        Gecode::IntRelType irt;
00377      public:
00379        BoolSharedSeq(int n, Gecode::IntRelType irt0)
00380          : Test("Rel::Bool::Seq::Shared::"+str(n)+"::"+str(irt0),n,0,1),
00381            irt(irt0) {}
00383        virtual bool solution(const Assignment& x) const {
00384          if (irt == Gecode::IRT_NQ) {
00385            if (x.size() < 2)
00386              return false;
00387            for (int i=0; i<x.size()-1; i++)
00388              if (x[i] != x[i+1])
00389                return true;
00390            return false;
00391          } else {
00392            int n = x.size();
00393            for (int i=0; i<2*n-1; i++)
00394              if (!cmp(x[i % n],irt,x[(i+1) % n]))
00395                return false;
00396            return true;
00397          }
00398        }
00400        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00401          using namespace Gecode;
00402          int n = x.size();
00403          BoolVarArgs b(2*n);
00404          for (int i=n; i--; )
00405            b[i]=b[n+i]=channel(home,x[i]);
00406          rel(home, b, irt);
00407        }
00408      };
00409 
00411      class IntArray : public Test {
00412      protected:
00414        Gecode::IntRelType irt;
00415      public:
00417        IntArray(Gecode::IntRelType irt0)
00418          : Test("Rel::Int::Array::"+str(irt0),6,-2,2), irt(irt0) {}
00420        virtual bool solution(const Assignment& x) const {
00421          int n=x.size() >> 1;
00422          for (int i=0; i<n; i++)
00423            if (x[i] != x[n+i])
00424              return cmp(x[i],irt,x[n+i]);
00425          return ((irt == Gecode::IRT_LQ) || (irt == Gecode::IRT_GQ) ||
00426                  (irt == Gecode::IRT_EQ));
00427          GECODE_NEVER;
00428          return false;
00429        }
00431        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00432          using namespace Gecode;
00433          int n=x.size() >> 1;
00434          IntVarArgs y(n); IntVarArgs z(n);
00435          for (int i=0; i<n; i++) {
00436            y[i]=x[i]; z[i]=x[n+i];
00437          }
00438          rel(home, y, irt, z);
00439        }
00440      };
00441 
00443      class IntArrayDiff : public Test {
00444      protected:
00446        Gecode::IntRelType irt;
00448        static const int n = 4;
00450        int n_fst;
00451      public:
00453        IntArrayDiff(Gecode::IntRelType irt0, int m)
00454          : Test("Rel::Int::Array::"+str(irt0)+"::"+str(m)+"::"+str(n-m),
00455                 n,-2,2), 
00456            irt(irt0), n_fst(m) {
00457          assert(n_fst <= n);
00458        }
00460        virtual bool solution(const Assignment& x) const {
00461          int n_snd = n - n_fst;
00462          for (int i=0; i<std::min(n_fst,n_snd); i++)
00463            if (x[i] != x[n_fst+i])
00464              return cmp(x[i],irt,x[n_fst+i]);
00465          return cmp(n_fst,irt,n_snd);
00466        }
00468        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00469          using namespace Gecode;
00470          int n_snd = n - n_fst;
00471          IntVarArgs y(n_fst); IntVarArgs z(n_snd);
00472          for (int i=0; i<n_fst; i++) {
00473            y[i]=x[i];
00474          }
00475          for (int i=0; i<n_snd; i++) {
00476            z[i]=x[n_fst + i];
00477          }
00478          rel(home, y, irt, z);
00479        }
00480      };
00481 
00483      class BoolArray : public Test {
00484      protected:
00486        Gecode::IntRelType irt;
00487      public:
00489        BoolArray(Gecode::IntRelType irt0)
00490          : Test("Rel::Bool::Array::"+str(irt0),10,0,1), irt(irt0) {}
00492        virtual bool solution(const Assignment& x) const {
00493          int n=x.size() >> 1;
00494          for (int i=0; i<n; i++)
00495            if (x[i] != x[n+i])
00496              return cmp(x[i],irt,x[n+i]);
00497          return ((irt == Gecode::IRT_LQ) || (irt == Gecode::IRT_GQ) ||
00498                  (irt == Gecode::IRT_EQ));
00499          GECODE_NEVER;
00500          return false;
00501        }
00503        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00504          using namespace Gecode;
00505          int n=x.size() >> 1;
00506          BoolVarArgs y(n); BoolVarArgs z(n);
00507          for (int i=0; i<n; i++) {
00508            y[i]=channel(home,x[i]); z[i]=channel(home,x[n+i]);
00509          }
00510          rel(home, y, irt, z);
00511        }
00512      };
00513 
00515      class Create {
00516      public:
00518        Create(void) {
00519          using namespace Gecode;
00520          for (IntRelTypes irts; irts(); ++irts) {
00521            for (IntConLevels icls; icls(); ++icls) {
00522              (void) new IntVarXY(irts.irt(),1,icls.icl());
00523              (void) new IntVarXY(irts.irt(),2,icls.icl());
00524              (void) new IntVarXX(irts.irt(),icls.icl());
00525              (void) new IntSeq(1,irts.irt(),icls.icl());
00526              (void) new IntSeq(2,irts.irt(),icls.icl());
00527              (void) new IntSeq(3,irts.irt(),icls.icl());
00528              (void) new IntSeq(5,irts.irt(),icls.icl());
00529              (void) new IntSharedSeq(1,irts.irt(),icls.icl());
00530              (void) new IntSharedSeq(2,irts.irt(),icls.icl());
00531              (void) new IntSharedSeq(3,irts.irt(),icls.icl());
00532              (void) new IntSharedSeq(4,irts.irt(),icls.icl());
00533            }
00534            (void) new BoolVarXY(irts.irt(),1);
00535            (void) new BoolVarXY(irts.irt(),2);
00536            (void) new BoolVarXX(irts.irt());
00537            (void) new BoolSeq(1,irts.irt());
00538            (void) new BoolSeq(2,irts.irt());
00539            (void) new BoolSeq(3,irts.irt());
00540            (void) new BoolSeq(10,irts.irt());
00541            (void) new BoolSharedSeq(1,irts.irt());
00542            (void) new BoolSharedSeq(2,irts.irt());
00543            (void) new BoolSharedSeq(3,irts.irt());
00544            (void) new BoolSharedSeq(4,irts.irt());
00545            (void) new BoolSharedSeq(8,irts.irt());
00546            for (int c=-4; c<=4; c++) {
00547              (void) new IntInt(irts.irt(),1,c);
00548              (void) new IntInt(irts.irt(),2,c);
00549            }
00550            for (int c=0; c<=1; c++) {
00551              (void) new BoolInt(irts.irt(),1,c);
00552              (void) new BoolInt(irts.irt(),2,c);
00553            }
00554            (void) new IntArray(irts.irt());
00555            for (int n_fst=0; n_fst<=4; n_fst++)
00556              (void) new IntArrayDiff(irts.irt(),n_fst);
00557            (void) new BoolArray(irts.irt());
00558          }
00559        }
00560      };
00561 
00562      Create c;
00564 
00565    }
00566 }}
00567 
00568 // STATISTICS: test-int