Generated on Tue May 22 09:40:03 2018 for Gecode by doxygen 1.6.3

no-overlap.cpp

Go to the documentation of this file.
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, 2011
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 #include <climits>
00038 
00039 namespace Test { namespace Int {
00040 
00042   namespace NoOverlap {
00043 
00049 
00050     class Int2 : public Test {
00051     protected:
00053       Gecode::IntArgs w;
00055       Gecode::IntArgs h;
00056     public:
00058       Int2(int m, const Gecode::IntArgs& w0, const Gecode::IntArgs& h0)
00059         : Test("NoOverlap::Int::2::"+str(m)+"::"+str(w0)+"::"+str(h0),
00060                2*w0.size(), 0, m-1),
00061           w(w0), h(h0) {
00062       }
00064       virtual bool solution(const Assignment& xy) const {
00065         int n = xy.size() / 2;
00066         for (int i=0; i<n; i++) {
00067           int xi=xy[2*i+0], yi=xy[2*i+1];
00068           for (int j=i+1; j<n; j++) {
00069             int xj=xy[2*j+0], yj=xy[2*j+1];
00070             if (!((xi + w[i] <= xj) || (xj + w[j] <= xi) ||
00071                   (yi + h[i] <= yj) || (yj + h[j] <= yi)))
00072               return false;
00073           }
00074         }
00075         return true;
00076       }
00078       virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
00079         using namespace Gecode;
00080         int n = xy.size() / 2;
00081         IntVarArgs x(n), y(n);
00082         for (int i=0; i<n; i++) {
00083           x[i]=xy[2*i+0]; y[i]=xy[2*i+1];
00084         }
00085         nooverlap(home, x, w, y, h);
00086       }
00087     };
00089     class IntOpt2 : public Test {
00090     protected:
00092       Gecode::IntArgs w;
00094       Gecode::IntArgs h;
00095     public:
00097       IntOpt2(int m, const Gecode::IntArgs& w0, const Gecode::IntArgs& h0)
00098         : Test("NoOverlap::Int::Opt::2::"+str(m)+"::"+str(w0)+"::"+str(h0),
00099                3*w0.size(), 0, m-1), w(w0), h(h0) {}
00101       virtual bool solution(const Assignment& xyo) const {
00102         int n = xyo.size() / 3;
00103         for (int i=0; i<n; i++) {
00104           int xi=xyo[3*i+0], yi=xyo[3*i+1];
00105           int oi=xyo[3*i+2];
00106           for (int j=i+1; j<n; j++) {
00107             int xj=xyo[3*j+0], yj=xyo[3*j+1];
00108             int oj=xyo[3*j+2];
00109             if ((oi > 0) && (oj > 0) &&
00110                 !((xi + w[i] <= xj) || (xj + w[j] <= xi) ||
00111                   (yi + h[i] <= yj) || (yj + h[j] <= yi)))
00112               return false;
00113           }
00114         }
00115         return true;
00116       }
00118       virtual void post(Gecode::Space& home, Gecode::IntVarArray& xyo) {
00119         using namespace Gecode;
00120         int n = xyo.size() / 3;
00121         IntVarArgs x(n), y(n);
00122         BoolVarArgs o(n);
00123         for (int i=0; i<n; i++) {
00124           x[i]=xyo[3*i+0]; y[i]=xyo[3*i+1];
00125           o[i]=expr(home, xyo[3*i+2] > 0);
00126         }
00127         nooverlap(home, x, w, y, h, o);
00128       }
00129     };
00130 
00132     class Var2 : public Test {
00133     public:
00135       Var2(int m, int n)
00136         : Test("NoOverlap::Var::2::"+str(m)+"::"+str(n), 4*n, 0, m) {}
00138       virtual bool solution(const Assignment& xwyh) const {
00139         int n = xwyh.size() / 4;
00140         for (int i=0; i<n; i++) {
00141           int xi=xwyh[4*i+0], yi=xwyh[4*i+2];
00142           int wi=xwyh[4*i+1], hi=xwyh[4*i+3];
00143           for (int j=i+1; j<n; j++) {
00144             int xj=xwyh[4*j+0], yj=xwyh[4*j+2];
00145             int wj=xwyh[4*j+1], hj=xwyh[4*j+3];
00146             if (!((xi + wi <= xj) || (xj + wj <= xi) ||
00147                   (yi + hi <= yj) || (yj + hj <= yi)))
00148               return false;
00149           }
00150         }
00151         return true;
00152       }
00154       virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyh) {
00155         using namespace Gecode;
00156         int n = xwyh.size() / 4;
00157         IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
00158         for (int i=0; i<n; i++) {
00159           x0[i]=xwyh[4*i+0]; w[i]=xwyh[4*i+1];
00160           x1[i]=expr(home, x0[i] + w[i]);
00161           y0[i]=xwyh[4*i+2]; h[i]=xwyh[4*i+3];
00162           y1[i]=expr(home, y0[i] + h[i]);
00163         }
00164         nooverlap(home, x0, w, x1, y0, h, y1);
00165       }
00166     };
00167 
00169     class VarOpt2 : public Test {
00170     public:
00172       VarOpt2(int m, int n)
00173         : Test("NoOverlap::Var::Opt::2::"+str(m)+"::"+str(n), 5*n, 0, m) {
00174         testfix = false;
00175       }
00177       virtual bool solution(const Assignment& xwyho) const {
00178         int n = xwyho.size() / 5;
00179         for (int i=0; i<n; i++) {
00180           int xi=xwyho[5*i+0], yi=xwyho[5*i+2];
00181           int wi=xwyho[5*i+1], hi=xwyho[5*i+3];
00182           int oi=xwyho[5*i+4];
00183           for (int j=i+1; j<n; j++) {
00184             int xj=xwyho[5*j+0], yj=xwyho[5*j+2];
00185             int wj=xwyho[5*j+1], hj=xwyho[5*j+3];
00186             int oj=xwyho[5*j+4];
00187             if ((oi > 0) && (oj > 0) &&
00188                 !((xi + wi <= xj) || (xj + wj <= xi) ||
00189                   (yi + hi <= yj) || (yj + hj <= yi)))
00190               return false;
00191           }
00192         }
00193         return true;
00194       }
00196       virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyho) {
00197         using namespace Gecode;
00198         int n = xwyho.size() / 5;
00199         IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
00200         BoolVarArgs o(n);
00201         for (int i=0; i<n; i++) {
00202           x0[i]=xwyho[5*i+0]; w[i]=xwyho[5*i+1];
00203           x1[i]=expr(home, x0[i] + w[i]);
00204           y0[i]=xwyho[5*i+2]; h[i]=xwyho[5*i+3];
00205           y1[i]=expr(home, y0[i] + h[i]);
00206           o[i]=expr(home, xwyho[5*i+4] > 0);
00207         }
00208         nooverlap(home, x0, w, x1, y0, h, y1, o);
00209       }
00210     };
00211 
00213     class VarOptShared2 : public Test {
00214     public:
00216       VarOptShared2(int m, int n)
00217         : Test("NoOverlap::Var::Opt::Shared::2::"+
00218                str(m)+"::"+str(n), 2*n+2, 0, m) {
00219         testfix = false;
00220       }
00222       virtual bool solution(const Assignment& xwyho) const {
00223         int n = (xwyho.size() - 2) / 2;
00224         for (int i=0; i<n; i++) {
00225           int xi=xwyho[2*i+0], yi=xwyho[2*i+0];
00226           int wi=xwyho[2*i+1], hi=xwyho[2*i+1];
00227           int oi=xwyho[2*n + (i % 2)];
00228           for (int j=i+1; j<n; j++) {
00229             int xj=xwyho[2*j+0], yj=xwyho[2*j+0];
00230             int wj=xwyho[2*j+1], hj=xwyho[2*j+1];
00231             int oj=xwyho[2*n + (j % 2)];
00232             if ((oi > 0) && (oj > 0) &&
00233                 !((xi + wi <= xj) || (xj + wj <= xi) ||
00234                   (yi + hi <= yj) || (yj + hj <= yi)))
00235               return false;
00236           }
00237         }
00238         return true;
00239       }
00241       virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyho) {
00242         using namespace Gecode;
00243         int n = (xwyho.size() - 2) / 2;
00244         IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
00245         BoolVarArgs o(n);
00246         for (int i=0; i<n; i++) {
00247           x0[i]=xwyho[2*i+0]; w[i]=xwyho[2*i+1];
00248           x1[i]=expr(home, x0[i] + w[i]);
00249           y0[i]=xwyho[2*i+0]; h[i]=xwyho[2*i+1];
00250           y1[i]=expr(home, y0[i] + h[i]);
00251           o[i]=expr(home, xwyho[2*n + (i % 2)] > 0);
00252         }
00253         nooverlap(home, x0, w, x1, y0, h, y1, o);
00254       }
00255     };
00256 
00257 
00259     class Create {
00260     public:
00262       Create(void) {
00263         using namespace Gecode;
00264 
00265         IntArgs s1(3, 2,1,1);
00266         IntArgs s2(4, 1,2,3,4);
00267         IntArgs s3(4, 4,3,2,1);
00268         IntArgs s4(4, 1,1,1,1);
00269 
00270         for (int m=2; m<3; m++) {
00271           (void) new Int2(m, s1, s1);
00272           (void) new Int2(m, s2, s2);
00273           (void) new Int2(m, s3, s3);
00274           (void) new Int2(m, s2, s3);
00275           (void) new Int2(m, s4, s4);
00276           (void) new Int2(m, s4, s2);
00277           (void) new IntOpt2(m, s2, s3);
00278           (void) new IntOpt2(m, s4, s3);
00279         }
00280 
00281         (void) new Var2(2, 2);
00282         (void) new Var2(3, 2);
00283         (void) new Var2(1, 3);
00284         (void) new VarOpt2(2, 2);
00285         (void) new VarOpt2(3, 2);
00286         (void) new VarOptShared2(2, 2);
00287         (void) new VarOptShared2(3, 2);
00288         (void) new VarOptShared2(4, 2);
00289 
00290       }
00291     };
00292 
00293     Create c;
00294 
00296 
00297   }
00298 
00299 }}
00300 
00301 
00302 // STATISTICS: test-int
00303