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: 2016-11-08 17:23:24 +0100 (Tue, 08 Nov 2016) $ by $Author: schulte $
00011  *     $Revision: 15253 $
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::IntPropLevel ipl)
00060          : Test("Rel::Int::Var::XY::"+str(irt0)+"::"+str(ipl)+"::"+str(n),
00061                 n+1,-3,3,n==1,ipl),
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], ipl);
00076          } else {
00077            IntVarArgs y(2);
00078            y[0]=x[0]; y[1]=x[1];
00079            rel(home, y, irt, x[2], ipl);
00080          }
00081        }
00083        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00084                          Gecode::Reify r) {
00085          assert(x.size() == 2);
00086          Gecode::rel(home, x[0], irt, x[1], r, ipl);
00087        }
00088      };
00089 
00091      class IntVarXX : public Test {
00092      protected:
00094        Gecode::IntRelType irt;
00095      public:
00097        IntVarXX(Gecode::IntRelType irt0, Gecode::IntPropLevel ipl)
00098          : Test("Rel::Int::Var::XX::"+str(irt0)+"::"+str(ipl),
00099                 1,-3,3,true,ipl),
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], ipl);
00113        }
00115        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00116                          Gecode::Reify r) {
00117          Gecode::rel(home, x[0], irt, x[0], r, ipl);
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::Reify r) {
00154          assert(x.size() == 2);
00155          using namespace Gecode;
00156          rel(home,
00157              channel(home,x[0]), irt, channel(home,x[1]),
00158              r);
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::Reify r) {
00219          assert(x.size() == 1);
00220          Gecode::rel(home, x[0], irt, c, r);
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::Reify r) {
00258          assert(x.size() == 1);
00259          using namespace Gecode;
00260          rel(home, channel(home,x[0]), irt, c, r);
00261        }
00262      };
00263 
00265      class IntSeq : public Test {
00266      protected:
00268        Gecode::IntRelType irt;
00269      public:
00271        IntSeq(int n, Gecode::IntRelType irt0, Gecode::IntPropLevel ipl)
00272          : Test("Rel::Int::Seq::"+str(n)+"::"+str(irt0)+"::"+str(ipl),
00273                 n,-3,3,false,ipl),
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, ipl);
00294        }
00295      };
00296 
00298      class IntSharedSeq : public Test {
00299      protected:
00301        Gecode::IntRelType irt;
00302      public:
00304        IntSharedSeq(int n, Gecode::IntRelType irt0, Gecode::IntPropLevel ipl)
00305          : Test("Rel::Int::Seq::Shared::"+str(n)+"::"+str(irt0)+"::"+str(ipl),
00306                 n,-3,3,false,ipl),
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, ipl);
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 IntArrayVar : public Test {
00412      protected:
00414        Gecode::IntRelType irt;
00415      public:
00417        IntArrayVar(Gecode::IntRelType irt0)
00418          : Test("Rel::Int::Array::Var::"+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 IntArrayInt : public Test {
00444      protected:
00446        Gecode::IntRelType irt;
00447      public:
00449        IntArrayInt(Gecode::IntRelType irt0)
00450          : Test("Rel::Int::Array::Int::"+str(irt0),3,-2,2), irt(irt0) {}
00452        virtual bool solution(const Assignment& x) const {
00453          Gecode::IntArgs y(3, 0,0,0);
00454          int n=x.size();
00455          for (int i=0; i<n; i++)
00456            if (x[i] != y[i])
00457              return cmp(x[i],irt,y[i]);
00458          return ((irt == Gecode::IRT_LQ) || (irt == Gecode::IRT_GQ) ||
00459                  (irt == Gecode::IRT_EQ));
00460          GECODE_NEVER;
00461          return false;
00462        }
00464        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00465          using namespace Gecode;
00466          IntArgs y(3, 0,0,0);
00467          rel(home, x, irt, y);
00468        }
00469      };
00470 
00472      class IntArrayDiff : public Test {
00473      protected:
00475        Gecode::IntRelType irt;
00477        static const int n = 4;
00479        int n_fst;
00480      public:
00482        IntArrayDiff(Gecode::IntRelType irt0, int m)
00483          : Test("Rel::Int::Array::"+str(irt0)+"::"+str(m)+"::"+str(n-m),
00484                 n,-2,2),
00485            irt(irt0), n_fst(m) {
00486          assert(n_fst <= n);
00487        }
00489        virtual bool solution(const Assignment& x) const {
00490          int n_snd = n - n_fst;
00491          for (int i=0; i<std::min(n_fst,n_snd); i++)
00492            if (x[i] != x[n_fst+i])
00493              return cmp(x[i],irt,x[n_fst+i]);
00494          return cmp(n_fst,irt,n_snd);
00495        }
00497        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00498          using namespace Gecode;
00499          int n_snd = n - n_fst;
00500          IntVarArgs y(n_fst); IntVarArgs z(n_snd);
00501          for (int i=0; i<n_fst; i++) {
00502            y[i]=x[i];
00503          }
00504          for (int i=0; i<n_snd; i++) {
00505            z[i]=x[n_fst + i];
00506          }
00507          rel(home, y, irt, z);
00508        }
00509      };
00510 
00512      class BoolArrayVar : public Test {
00513      protected:
00515        Gecode::IntRelType irt;
00516      public:
00518        BoolArrayVar(Gecode::IntRelType irt0)
00519          : Test("Rel::Bool::Array::Var::"+str(irt0),10,0,1), irt(irt0) {}
00521        virtual bool solution(const Assignment& x) const {
00522          int n=x.size() >> 1;
00523          for (int i=0; i<n; i++)
00524            if (x[i] != x[n+i])
00525              return cmp(x[i],irt,x[n+i]);
00526          return ((irt == Gecode::IRT_LQ) || (irt == Gecode::IRT_GQ) ||
00527                  (irt == Gecode::IRT_EQ));
00528          GECODE_NEVER;
00529          return false;
00530        }
00532        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00533          using namespace Gecode;
00534          int n=x.size() >> 1;
00535          BoolVarArgs y(n); BoolVarArgs z(n);
00536          for (int i=0; i<n; i++) {
00537            y[i]=channel(home,x[i]); z[i]=channel(home,x[n+i]);
00538          }
00539          rel(home, y, irt, z);
00540        }
00541      };
00542 
00544      class BoolArrayInt : public Test {
00545      protected:
00547        Gecode::IntRelType irt;
00548      public:
00550        BoolArrayInt(Gecode::IntRelType irt0)
00551          : Test("Rel::Bool::Array::Int::"+str(irt0),5,0,1), irt(irt0) {}
00553        virtual bool solution(const Assignment& x) const {
00554          Gecode::IntArgs y(5, 0,0,1,0,0);
00555          for (int i=0; i<5; i++)
00556            if (x[i] != y[i])
00557              return cmp(x[i],irt,y[i]);
00558          return ((irt == Gecode::IRT_LQ) || (irt == Gecode::IRT_GQ) ||
00559                  (irt == Gecode::IRT_EQ));
00560          GECODE_NEVER;
00561          return false;
00562        }
00564        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00565          using namespace Gecode;
00566          Gecode::IntArgs z(5, 0,0,1,0,0);
00567          int n=x.size();
00568          BoolVarArgs y(n);
00569          for (int i=0; i<n; i++)
00570            y[i]=channel(home,x[i]);
00571          rel(home, y, irt, z);
00572        }
00573      };
00574 
00576      class Create {
00577      public:
00579        Create(void) {
00580          using namespace Gecode;
00581          for (IntRelTypes irts; irts(); ++irts) {
00582            for (IntPropLevels ipls; ipls(); ++ipls) {
00583              (void) new IntVarXY(irts.irt(),1,ipls.ipl());
00584              (void) new IntVarXY(irts.irt(),2,ipls.ipl());
00585              (void) new IntVarXX(irts.irt(),ipls.ipl());
00586              (void) new IntSeq(1,irts.irt(),ipls.ipl());
00587              (void) new IntSeq(2,irts.irt(),ipls.ipl());
00588              (void) new IntSeq(3,irts.irt(),ipls.ipl());
00589              (void) new IntSeq(5,irts.irt(),ipls.ipl());
00590              (void) new IntSharedSeq(1,irts.irt(),ipls.ipl());
00591              (void) new IntSharedSeq(2,irts.irt(),ipls.ipl());
00592              (void) new IntSharedSeq(3,irts.irt(),ipls.ipl());
00593              (void) new IntSharedSeq(4,irts.irt(),ipls.ipl());
00594            }
00595            (void) new BoolVarXY(irts.irt(),1);
00596            (void) new BoolVarXY(irts.irt(),2);
00597            (void) new BoolVarXX(irts.irt());
00598            (void) new BoolSeq(1,irts.irt());
00599            (void) new BoolSeq(2,irts.irt());
00600            (void) new BoolSeq(3,irts.irt());
00601            (void) new BoolSeq(10,irts.irt());
00602            (void) new BoolSharedSeq(1,irts.irt());
00603            (void) new BoolSharedSeq(2,irts.irt());
00604            (void) new BoolSharedSeq(3,irts.irt());
00605            (void) new BoolSharedSeq(4,irts.irt());
00606            (void) new BoolSharedSeq(8,irts.irt());
00607            for (int c=-4; c<=4; c++) {
00608              (void) new IntInt(irts.irt(),1,c);
00609              (void) new IntInt(irts.irt(),2,c);
00610            }
00611            for (int c=0; c<=1; c++) {
00612              (void) new BoolInt(irts.irt(),1,c);
00613              (void) new BoolInt(irts.irt(),2,c);
00614            }
00615            (void) new IntArrayVar(irts.irt());
00616            (void) new IntArrayInt(irts.irt());
00617            for (int n_fst=0; n_fst<=4; n_fst++)
00618              (void) new IntArrayDiff(irts.irt(),n_fst);
00619            (void) new BoolArrayVar(irts.irt());
00620            (void) new BoolArrayInt(irts.irt());
00621          }
00622        }
00623      };
00624 
00625      Create c;
00627 
00628    }
00629 }}
00630 
00631 // STATISTICS: test-int