unary.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, 2009
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/int.hh"
00035 
00036 #include <gecode/minimodel.hh>
00037 
00038 namespace Test { namespace Int {
00040    namespace Unary {}
00041 }}
00042 
00043 namespace Test { namespace Int { namespace Unary {
00044 
00050 
00051   class ManFixPUnary : public Test {
00052   protected:
00054     Gecode::IntArgs p;
00056     static int st(const Gecode::IntArgs& p) {
00057       int t = 0;
00058       for (int i=p.size(); i--; )
00059         t += p[i];
00060       return t;
00061     }
00062   public:
00064     ManFixPUnary(const Gecode::IntArgs& p0, int o, Gecode::IntPropLevel ipl0)
00065       : Test("Unary::Man::Fix::"+str(o)+"::"+str(p0)+"::"+str(ipl0),
00066              p0.size(),o,o+st(p0),false,ipl0),
00067         p(p0) {
00068       testsearch = false;
00069       contest = CTL_NONE;
00070     }
00072     virtual Assignment* assignment(void) const {
00073       return new RandomAssignment(arity,dom,500);
00074     }
00076     virtual bool solution(const Assignment& x) const {
00077       for (int i=0; i<x.size(); i++)
00078         for (int j=i+1; j<x.size(); j++)
00079           if ((x[i]+p[i] > x[j]) && (x[j]+p[j] > x[i]))
00080             return false;
00081       return true;
00082     }
00084     virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00085       Gecode::unary(home, x, p, ipl);
00086     }
00087   };
00088 
00090   class OptFixPUnary : public Test {
00091   protected:
00093     Gecode::IntArgs p;
00095     int l;
00097     static int st(const Gecode::IntArgs& p) {
00098       int t = 0;
00099       for (int i=p.size(); i--; )
00100         t += p[i];
00101       return t;
00102     }
00103   public:
00105     OptFixPUnary(const Gecode::IntArgs& p0, int o, Gecode::IntPropLevel ipl0)
00106       : Test("Unary::Opt::Fix::"+str(o)+"::"+str(p0)+"::"+str(ipl0),
00107              2*p0.size(),o,o+st(p0),false,ipl0), p(p0), l(o+st(p)/2) {
00108       testsearch = false;
00109       contest = CTL_NONE;
00110     }
00112     virtual Assignment* assignment(void) const {
00113       return new RandomAssignment(arity,dom,500);
00114     }
00116     virtual bool solution(const Assignment& x) const {
00117       int n = x.size() / 2;
00118       for (int i=0; i<n; i++)
00119         if (x[n+i] > l)
00120           for (int j=i+1; j<n; j++)
00121             if(x[n+j] > l)
00122               if ((x[i]+p[i] > x[j]) && (x[j]+p[j] > x[i]))
00123                 return false;
00124       return true;
00125     }
00127     virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00128       int n=x.size() / 2;
00129       Gecode::IntVarArgs s(n);
00130       Gecode::BoolVarArgs m(n);
00131       for (int i=0; i<n; i++) {
00132         s[i]=x[i];
00133         m[i]=Gecode::expr(home, (x[n+i] > l));
00134       }
00135       Gecode::unary(home, s, p, m, ipl);
00136     }
00137   };
00138 
00140   class ManFlexUnary : public Test {
00141   protected:
00143     int _minP;
00145     int _maxP;
00147     int off;
00148   public:
00150     ManFlexUnary(int n, int minP, int maxP, int o, Gecode::IntPropLevel ipl0)
00151       : Test("Unary::Man::Flex::"+str(o)+"::"+str(n)+"::"
00152              +str(minP)+"::"+str(maxP)+"::"+str(ipl0),
00153              2*n,0,n*maxP,false,ipl0), _minP(minP), _maxP(maxP), off(o) {
00154       testsearch = false;
00155       testfix = false;
00156       contest = CTL_NONE;
00157     }
00159     virtual Assignment* assignment(void) const {
00160       return new RandomMixAssignment(arity/2,dom,arity/2,
00161                                      Gecode::IntSet(_minP,_maxP),500);
00162     }
00164     virtual bool solution(const Assignment& x) const {
00165       int n = x.size()/2;
00166       for (int i=0; i<n; i++)
00167         for (int j=i+1; j<n; j++)
00168           if ((x[i]+x[n+i] > x[j]) && (x[j]+x[n+j] > x[i]))
00169             return false;
00170       return true;
00171     }
00173     virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00174       Gecode::IntVarArgs s(x.size()/2);
00175       Gecode::IntVarArgs px(x.slice(x.size()/2));
00176       Gecode::IntVarArgs e(home,x.size()/2,
00177                            Gecode::Int::Limits::min,
00178                            Gecode::Int::Limits::max);
00179       for (int i=s.size(); i--;) {
00180         s[i] = expr(home, off+x[i]);
00181         rel(home, s[i]+px[i] == e[i]);
00182         rel(home, _minP <= px[i]);
00183         rel(home, _maxP >= px[i]);
00184       }
00185       Gecode::unary(home, s, px, e, ipl);
00186     }
00187   };
00188 
00190   class OptFlexUnary : public Test {
00191   protected:
00193     int _minP;
00195     int _maxP;
00197     int off;
00199     int l;
00201     static int st(const Gecode::IntArgs& p) {
00202       int t = 0;
00203       for (int i=p.size(); i--; )
00204         t += p[i];
00205       return t;
00206     }
00207   public:
00209     OptFlexUnary(int n, int minP, int maxP, int o, Gecode::IntPropLevel ipl0)
00210       : Test("Unary::Opt::Flex::"+str(o)+"::"+str(n)+"::"
00211              +str(minP)+"::"+str(maxP)+"::"+str(ipl0),
00212              3*n,0,n*maxP,false,ipl0), _minP(minP), _maxP(maxP), off(o),
00213         l(n*maxP/2) {
00214       testsearch = false;
00215       testfix = false;
00216       contest = CTL_NONE;
00217     }
00219     virtual Assignment* assignment(void) const {
00220       return new RandomMixAssignment(2*(arity/3),dom,arity/3,
00221                                      Gecode::IntSet(_minP,_maxP),500);
00222     }
00224     virtual bool solution(const Assignment& x) const {
00225       int n = x.size() / 3;
00226       for (int i=0; i<n; i++)
00227         if (x[n+i] > l)
00228           for (int j=i+1; j<n; j++)
00229             if(x[n+j] > l)
00230               if ((x[i]+x[2*n+i] > x[j]) && (x[j]+x[2*n+j] > x[i]))
00231                 return false;
00232       return true;
00233     }
00235     virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00236       int n=x.size() / 3;
00237 
00238       Gecode::IntVarArgs s(n);
00239       Gecode::IntVarArgs px(n);
00240       Gecode::IntVarArgs e(home,n,
00241                            Gecode::Int::Limits::min,
00242                            Gecode::Int::Limits::max);
00243       for (int i=n; i--;) {
00244         s[i] = expr(home, off+x[i]);
00245         px[i] = x[2*n+i];
00246         rel(home, s[i]+px[i] == e[i]);
00247         rel(home, _minP <= px[i]);
00248         rel(home, _maxP >= px[i]);
00249       }
00250       Gecode::BoolVarArgs m(n);
00251       for (int i=0; i<n; i++)
00252         m[i]=Gecode::expr(home, (x[n+i] > l));
00253       Gecode::unary(home, s, px, e, m, ipl);
00254     }
00255   };
00256 
00258   class Create {
00259   public:
00261     Create(void) {
00262       using namespace Gecode;
00263       IntArgs p1(4, 2,2,2,2);
00264       IntArgs p10(5, 2,2,0,2,2);
00265       IntArgs p2(4, 4,3,3,5);
00266       IntArgs p20(6, 4,0,3,3,0,5);
00267       IntArgs p3(6, 4,2,9,3,7,5);
00268       IntArgs p30(8, 4,0,2,9,3,7,5,0);
00269 
00270       for (IntPropBasicAdvanced ipba; ipba(); ++ipba) {
00271         (void) new ManFixPUnary(p1,0,ipba.ipl());
00272         (void) new ManFixPUnary(p1,Gecode::Int::Limits::min,ipba.ipl());
00273         (void) new OptFixPUnary(p1,0,ipba.ipl());
00274         (void) new OptFixPUnary(p1,Gecode::Int::Limits::min,ipba.ipl());
00275         (void) new ManFlexUnary(4,0,2,0,ipba.ipl());
00276         (void) new ManFlexUnary(4,0,2,Gecode::Int::Limits::min,ipba.ipl());
00277         (void) new ManFlexUnary(4,1,3,0,ipba.ipl());
00278         (void) new ManFlexUnary(4,1,3,Gecode::Int::Limits::min,ipba.ipl());
00279         (void) new OptFlexUnary(4,0,2,0,ipba.ipl());
00280         (void) new OptFlexUnary(4,0,2,Gecode::Int::Limits::min,ipba.ipl());
00281 
00282         (void) new ManFixPUnary(p10,0,ipba.ipl());
00283         (void) new ManFixPUnary(p10,Gecode::Int::Limits::min,ipba.ipl());
00284         (void) new OptFixPUnary(p10,0,ipba.ipl());
00285         (void) new OptFixPUnary(p10,Gecode::Int::Limits::min,ipba.ipl());
00286         (void) new ManFlexUnary(5,0,2,0,ipba.ipl());
00287         (void) new ManFlexUnary(5,0,2,Gecode::Int::Limits::min,ipba.ipl());
00288         (void) new OptFlexUnary(5,0,2,0,ipba.ipl());
00289         (void) new OptFlexUnary(5,0,2,Gecode::Int::Limits::min,ipba.ipl());
00290 
00291         (void) new ManFixPUnary(p2,0,ipba.ipl());
00292         (void) new ManFixPUnary(p2,Gecode::Int::Limits::min,ipba.ipl());
00293         (void) new OptFixPUnary(p2,0,ipba.ipl());
00294         (void) new OptFixPUnary(p2,Gecode::Int::Limits::min,ipba.ipl());
00295         (void) new ManFlexUnary(4,3,5,0,ipba.ipl());
00296         (void) new ManFlexUnary(4,3,5,Gecode::Int::Limits::min,ipba.ipl());
00297         (void) new OptFlexUnary(4,3,5,0,ipba.ipl());
00298         (void) new OptFlexUnary(4,3,5,Gecode::Int::Limits::min,ipba.ipl());
00299 
00300         (void) new ManFixPUnary(p20,0,ipba.ipl());
00301         (void) new ManFixPUnary(p20,Gecode::Int::Limits::min,ipba.ipl());
00302         (void) new OptFixPUnary(p20,0,ipba.ipl());
00303         (void) new OptFixPUnary(p20,Gecode::Int::Limits::min,ipba.ipl());
00304         (void) new ManFlexUnary(6,0,5,0,ipba.ipl());
00305         (void) new ManFlexUnary(6,0,5,Gecode::Int::Limits::min,ipba.ipl());
00306         (void) new OptFlexUnary(6,0,5,0,ipba.ipl());
00307         (void) new OptFlexUnary(6,0,5,Gecode::Int::Limits::min,ipba.ipl());
00308 
00309         (void) new ManFixPUnary(p3,0,ipba.ipl());
00310         (void) new ManFixPUnary(p3,Gecode::Int::Limits::min,ipba.ipl());
00311         (void) new OptFixPUnary(p3,0,ipba.ipl());
00312         (void) new OptFixPUnary(p3,Gecode::Int::Limits::min,ipba.ipl());
00313         (void) new ManFlexUnary(6,2,7,0,ipba.ipl());
00314         (void) new ManFlexUnary(6,2,7,Gecode::Int::Limits::min,ipba.ipl());
00315         (void) new OptFlexUnary(6,2,7,0,ipba.ipl());
00316         (void) new OptFlexUnary(6,2,7,Gecode::Int::Limits::min,ipba.ipl());
00317 
00318         (void) new ManFixPUnary(p30,0,ipba.ipl());
00319         (void) new ManFixPUnary(p30,Gecode::Int::Limits::min,ipba.ipl());
00320         (void) new OptFixPUnary(p30,0,ipba.ipl());
00321         (void) new OptFixPUnary(p30,Gecode::Int::Limits::min,ipba.ipl());
00322         (void) new ManFlexUnary(8,0,9,0,ipba.ipl());
00323         (void) new ManFlexUnary(8,0,9,Gecode::Int::Limits::min,ipba.ipl());
00324         (void) new OptFlexUnary(8,0,9,0,ipba.ipl());
00325         (void) new OptFlexUnary(8,0,9,Gecode::Int::Limits::min,ipba.ipl());
00326       }
00327     }
00328   };
00329 
00330   Create c;
00332 
00333 
00334 }}}
00335 
00336 // STATISTICS: test-int