Generated on Fri Mar 20 15:56:12 2015 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  *  Last modified:
00010  *     $Date: 2012-10-22 21:13:52 +0200 (Mon, 22 Oct 2012) $ by $Author: schulte $
00011  *     $Revision: 13163 $
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 #include <climits>
00042 
00043 namespace Test { namespace Int {
00044   
00046   namespace NoOverlap {
00047 
00053 
00054     class Int2 : public Test {
00055     protected:
00057       Gecode::IntArgs w;
00059       Gecode::IntArgs h;
00060     public:
00062       Int2(int m, const Gecode::IntArgs& w0, const Gecode::IntArgs& h0) 
00063         : Test("NoOverlap::Int::2::"+str(m)+"::"+str(w0)+"::"+str(h0),
00064                2*w0.size(), 0, m-1), 
00065           w(w0), h(h0) {
00066       }
00068       virtual bool solution(const Assignment& xy) const {
00069         int n = xy.size() / 2;
00070         for (int i=0; i<n; i++) {
00071           int xi=xy[2*i+0], yi=xy[2*i+1];
00072           for (int j=i+1; j<n; j++) {
00073             int xj=xy[2*j+0], yj=xy[2*j+1];
00074             if (!((xi + w[i] <= xj) || (xj + w[j] <= xi) ||
00075                   (yi + h[i] <= yj) || (yj + h[j] <= yi)))
00076               return false;
00077           }
00078         }
00079         return true;
00080       }
00082       virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
00083         using namespace Gecode;
00084         int n = xy.size() / 2;
00085         IntVarArgs x(n), y(n);
00086         for (int i=0; i<n; i++) {
00087           x[i]=xy[2*i+0]; y[i]=xy[2*i+1];
00088         }
00089         nooverlap(home, x, w, y, h);
00090       }
00091     };
00093     class IntOpt2 : public Test {
00094     protected:
00096       Gecode::IntArgs w;
00098       Gecode::IntArgs h;
00099     public:
00101       IntOpt2(int m, const Gecode::IntArgs& w0, const Gecode::IntArgs& h0) 
00102         : Test("NoOverlap::Int::Opt::2::"+str(m)+"::"+str(w0)+"::"+str(h0), 
00103                3*w0.size(), 0, m-1), w(w0), h(h0) {}
00105       virtual bool solution(const Assignment& xyo) const {
00106         int n = xyo.size() / 3;
00107         for (int i=0; i<n; i++) {
00108           int xi=xyo[3*i+0], yi=xyo[3*i+1];
00109           int oi=xyo[3*i+2];
00110           for (int j=i+1; j<n; j++) {
00111             int xj=xyo[3*j+0], yj=xyo[3*j+1];
00112             int oj=xyo[3*j+2];
00113             if ((oi > 0) && (oj > 0) &&
00114                 !((xi + w[i] <= xj) || (xj + w[j] <= xi) ||
00115                   (yi + h[i] <= yj) || (yj + h[j] <= yi)))
00116               return false;
00117           }
00118         }
00119         return true;
00120       }
00122       virtual void post(Gecode::Space& home, Gecode::IntVarArray& xyo) {
00123         using namespace Gecode;
00124         int n = xyo.size() / 3;
00125         IntVarArgs x(n), y(n);
00126         BoolVarArgs o(n);
00127         for (int i=0; i<n; i++) {
00128           x[i]=xyo[3*i+0]; y[i]=xyo[3*i+1];
00129           o[i]=expr(home, xyo[3*i+2] > 0);
00130         }
00131         nooverlap(home, x, w, y, h, o);
00132       }
00133     };
00134     
00136     class Var2 : public Test {
00137     public:
00139       Var2(int m, int n)
00140         : Test("NoOverlap::Var::2::"+str(m)+"::"+str(n), 4*n, 0, m) {}
00142       virtual bool solution(const Assignment& xwyh) const {
00143         int n = xwyh.size() / 4;
00144         for (int i=0; i<n; i++) {
00145           int xi=xwyh[4*i+0], yi=xwyh[4*i+2];
00146           int wi=xwyh[4*i+1], hi=xwyh[4*i+3];
00147           for (int j=i+1; j<n; j++) {
00148             int xj=xwyh[4*j+0], yj=xwyh[4*j+2];
00149             int wj=xwyh[4*j+1], hj=xwyh[4*j+3];
00150             if (!((xi + wi <= xj) || (xj + wj <= xi) ||
00151                   (yi + hi <= yj) || (yj + hj <= yi)))
00152               return false;
00153           }
00154         }
00155         return true;
00156       }
00158       virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyh) {
00159         using namespace Gecode;
00160         int n = xwyh.size() / 4;
00161         IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
00162         for (int i=0; i<n; i++) {
00163           x0[i]=xwyh[4*i+0]; w[i]=xwyh[4*i+1];
00164           x1[i]=expr(home, x0[i] + w[i]);
00165           y0[i]=xwyh[4*i+2]; h[i]=xwyh[4*i+3];
00166           y1[i]=expr(home, y0[i] + h[i]);
00167         }
00168         nooverlap(home, x0, w, x1, y0, h, y1);
00169       }
00170     };
00171     
00173     class VarOpt2 : public Test {
00174     public:
00176       VarOpt2(int m, int n)
00177         : Test("NoOverlap::Var::Opt::2::"+str(m)+"::"+str(n), 5*n, 0, m) {
00178         testfix = false;
00179       }
00181       virtual bool solution(const Assignment& xwyho) const {
00182         int n = xwyho.size() / 5;
00183         for (int i=0; i<n; i++) {
00184           int xi=xwyho[5*i+0], yi=xwyho[5*i+2];
00185           int wi=xwyho[5*i+1], hi=xwyho[5*i+3];
00186           int oi=xwyho[5*i+4];
00187           for (int j=i+1; j<n; j++) {
00188             int xj=xwyho[5*j+0], yj=xwyho[5*j+2];
00189             int wj=xwyho[5*j+1], hj=xwyho[5*j+3];
00190             int oj=xwyho[5*j+4];
00191             if ((oi > 0) && (oj > 0) &&
00192                 !((xi + wi <= xj) || (xj + wj <= xi) ||
00193                   (yi + hi <= yj) || (yj + hj <= yi)))
00194               return false;
00195           }
00196         }
00197         return true;
00198       }
00200       virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyho) {
00201         using namespace Gecode;
00202         int n = xwyho.size() / 5;
00203         IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
00204         BoolVarArgs o(n);
00205         for (int i=0; i<n; i++) {
00206           x0[i]=xwyho[5*i+0]; w[i]=xwyho[5*i+1];
00207           x1[i]=expr(home, x0[i] + w[i]);
00208           y0[i]=xwyho[5*i+2]; h[i]=xwyho[5*i+3];
00209           y1[i]=expr(home, y0[i] + h[i]);
00210           o[i]=expr(home, xwyho[5*i+4] > 0);
00211         }
00212         nooverlap(home, x0, w, x1, y0, h, y1, o);
00213       }
00214     };
00215     
00217     class VarOptShared2 : public Test {
00218     public:
00220       VarOptShared2(int m, int n)
00221         : Test("NoOverlap::Var::Opt::Shared::2::"+
00222                str(m)+"::"+str(n), 2*n+2, 0, m) {
00223         testfix = false;
00224       }
00226       virtual bool solution(const Assignment& xwyho) const {
00227         int n = (xwyho.size() - 2) / 2;
00228         for (int i=0; i<n; i++) {
00229           int xi=xwyho[2*i+0], yi=xwyho[2*i+0];
00230           int wi=xwyho[2*i+1], hi=xwyho[2*i+1];
00231           int oi=xwyho[2*n + (i % 2)];
00232           for (int j=i+1; j<n; j++) {
00233             int xj=xwyho[2*j+0], yj=xwyho[2*j+0];
00234             int wj=xwyho[2*j+1], hj=xwyho[2*j+1];
00235             int oj=xwyho[2*n + (j % 2)];
00236             if ((oi > 0) && (oj > 0) &&
00237                 !((xi + wi <= xj) || (xj + wj <= xi) ||
00238                   (yi + hi <= yj) || (yj + hj <= yi)))
00239               return false;
00240           }
00241         }
00242         return true;
00243       }
00245       virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyho) {
00246         using namespace Gecode;
00247         int n = (xwyho.size() - 2) / 2;
00248         IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
00249         BoolVarArgs o(n);
00250         for (int i=0; i<n; i++) {
00251           x0[i]=xwyho[2*i+0]; w[i]=xwyho[2*i+1];
00252           x1[i]=expr(home, x0[i] + w[i]);
00253           y0[i]=xwyho[2*i+0]; h[i]=xwyho[2*i+1];
00254           y1[i]=expr(home, y0[i] + h[i]);
00255           o[i]=expr(home, xwyho[2*n + (i % 2)] > 0);
00256         }
00257         nooverlap(home, x0, w, x1, y0, h, y1, o);
00258       }
00259     };
00260     
00261     
00263     class Create {
00264     public:
00266       Create(void) {
00267         using namespace Gecode;
00268 
00269         IntArgs s1(3, 2,1,1);
00270         IntArgs s2(4, 1,2,3,4);
00271         IntArgs s3(4, 4,3,2,1);
00272         IntArgs s4(4, 1,1,1,1);
00273 
00274         for (int m=2; m<3; m++) {
00275           (void) new Int2(m, s1, s1);
00276           (void) new Int2(m, s2, s2);
00277           (void) new Int2(m, s3, s3);
00278           (void) new Int2(m, s2, s3);
00279           (void) new Int2(m, s4, s4);
00280           (void) new Int2(m, s4, s2);
00281           (void) new IntOpt2(m, s2, s3);
00282           (void) new IntOpt2(m, s4, s3);
00283         }
00284 
00285         (void) new Var2(2, 2);
00286         (void) new Var2(3, 2);
00287         (void) new Var2(1, 3);
00288         (void) new VarOpt2(2, 2);
00289         (void) new VarOpt2(3, 2);
00290         (void) new VarOptShared2(2, 2);
00291         (void) new VarOptShared2(3, 2);
00292         (void) new VarOptShared2(4, 2);
00293 
00294       }
00295     };
00296     
00297     Create c;
00298     
00300     
00301   }
00302 
00303 }}
00304 
00305 
00306 // STATISTICS: test-int
00307