Generated on Thu Mar 13 2014 04:39:32 for Gecode by doxygen 1.8.1.2
no-overlap.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2011
8  *
9  * Last modified:
10  * $Date: 2011-07-14 02:16:57 +1000 (Thu, 14 Jul 2011) $ by $Author: schulte $
11  * $Revision: 12192 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include "test/int.hh"
39 
40 #include <gecode/minimodel.hh>
41 #include <climits>
42 
43 namespace Test { namespace Int {
44 
46  namespace NoOverlap {
47 
53 
54  class Int2 : public Test {
55  protected:
60  public:
62  Int2(int m, const Gecode::IntArgs& w0, const Gecode::IntArgs& h0)
63  : Test("NoOverlap::Int::2::"+str(m)+"::"+str(w0)+"::"+str(h0),
64  2*w0.size(), 0, m-1),
65  w(w0), h(h0) {
66  }
68  virtual bool solution(const Assignment& xy) const {
69  int n = xy.size() / 2;
70  for (int i=0; i<n; i++) {
71  int xi=xy[2*i+0], yi=xy[2*i+1];
72  for (int j=i+1; j<n; j++) {
73  int xj=xy[2*j+0], yj=xy[2*j+1];
74  if (!((xi + w[i] <= xj) || (xj + w[j] <= xi) ||
75  (yi + h[i] <= yj) || (yj + h[j] <= yi)))
76  return false;
77  }
78  }
79  return true;
80  }
82  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
83  using namespace Gecode;
84  int n = xy.size() / 2;
85  IntVarArgs x(n), y(n);
86  for (int i=0; i<n; i++) {
87  x[i]=xy[2*i+0]; y[i]=xy[2*i+1];
88  }
89  nooverlap(home, x, w, y, h);
90  }
91  };
93  class IntOpt2 : public Test {
94  protected:
99  public:
101  IntOpt2(int m, const Gecode::IntArgs& w0, const Gecode::IntArgs& h0)
102  : Test("NoOverlap::Int::Opt::2::"+str(m)+"::"+str(w0)+"::"+str(h0),
103  3*w0.size(), 0, m-1), w(w0), h(h0) {}
105  virtual bool solution(const Assignment& xyo) const {
106  int n = xyo.size() / 3;
107  for (int i=0; i<n; i++) {
108  int xi=xyo[3*i+0], yi=xyo[3*i+1];
109  int oi=xyo[3*i+2];
110  for (int j=i+1; j<n; j++) {
111  int xj=xyo[3*j+0], yj=xyo[3*j+1];
112  int oj=xyo[3*j+2];
113  if ((oi > 0) && (oj > 0) &&
114  !((xi + w[i] <= xj) || (xj + w[j] <= xi) ||
115  (yi + h[i] <= yj) || (yj + h[j] <= yi)))
116  return false;
117  }
118  }
119  return true;
120  }
122  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xyo) {
123  using namespace Gecode;
124  int n = xyo.size() / 3;
125  IntVarArgs x(n), y(n);
126  BoolVarArgs o(n);
127  for (int i=0; i<n; i++) {
128  x[i]=xyo[3*i+0]; y[i]=xyo[3*i+1];
129  o[i]=expr(home, xyo[3*i+2] > 0);
130  }
131  nooverlap(home, x, w, y, h, o);
132  }
133  };
134 
136  class Var2 : public Test {
137  public:
139  Var2(int m, int n)
140  : Test("NoOverlap::Var::2::"+str(m)+"::"+str(n), 4*n, 0, m) {}
142  virtual bool solution(const Assignment& xwyh) const {
143  int n = xwyh.size() / 4;
144  for (int i=0; i<n; i++) {
145  int xi=xwyh[4*i+0], yi=xwyh[4*i+2];
146  int wi=xwyh[4*i+1], hi=xwyh[4*i+3];
147  for (int j=i+1; j<n; j++) {
148  int xj=xwyh[4*j+0], yj=xwyh[4*j+2];
149  int wj=xwyh[4*j+1], hj=xwyh[4*j+3];
150  if (!((xi + wi <= xj) || (xj + wj <= xi) ||
151  (yi + hi <= yj) || (yj + hj <= yi)))
152  return false;
153  }
154  }
155  return true;
156  }
158  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyh) {
159  using namespace Gecode;
160  int n = xwyh.size() / 4;
161  IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
162  for (int i=0; i<n; i++) {
163  x0[i]=xwyh[4*i+0]; w[i]=xwyh[4*i+1];
164  x1[i]=expr(home, x0[i] + w[i]);
165  y0[i]=xwyh[4*i+2]; h[i]=xwyh[4*i+3];
166  y1[i]=expr(home, y0[i] + h[i]);
167  }
168  nooverlap(home, x0, w, x1, y0, h, y1);
169  }
170  };
171 
173  class VarOpt2 : public Test {
174  public:
176  VarOpt2(int m, int n)
177  : Test("NoOverlap::Var::Opt::2::"+str(m)+"::"+str(n), 5*n, 0, m) {
178  testfix = false;
179  }
181  virtual bool solution(const Assignment& xwyho) const {
182  int n = xwyho.size() / 5;
183  for (int i=0; i<n; i++) {
184  int xi=xwyho[5*i+0], yi=xwyho[5*i+2];
185  int wi=xwyho[5*i+1], hi=xwyho[5*i+3];
186  int oi=xwyho[5*i+4];
187  for (int j=i+1; j<n; j++) {
188  int xj=xwyho[5*j+0], yj=xwyho[5*j+2];
189  int wj=xwyho[5*j+1], hj=xwyho[5*j+3];
190  int oj=xwyho[5*j+4];
191  if ((oi > 0) && (oj > 0) &&
192  !((xi + wi <= xj) || (xj + wj <= xi) ||
193  (yi + hi <= yj) || (yj + hj <= yi)))
194  return false;
195  }
196  }
197  return true;
198  }
200  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyho) {
201  using namespace Gecode;
202  int n = xwyho.size() / 5;
203  IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
204  BoolVarArgs o(n);
205  for (int i=0; i<n; i++) {
206  x0[i]=xwyho[5*i+0]; w[i]=xwyho[5*i+1];
207  x1[i]=expr(home, x0[i] + w[i]);
208  y0[i]=xwyho[5*i+2]; h[i]=xwyho[5*i+3];
209  y1[i]=expr(home, y0[i] + h[i]);
210  o[i]=expr(home, xwyho[5*i+4] > 0);
211  }
212  nooverlap(home, x0, w, x1, y0, h, y1, o);
213  }
214  };
215 
216 
218  class Create {
219  public:
221  Create(void) {
222  using namespace Gecode;
223 
224  IntArgs s1(3, 2,1,1);
225  IntArgs s2(4, 1,2,3,4);
226  IntArgs s3(4, 4,3,2,1);
227  IntArgs s4(4, 1,1,1,1);
228 
229  for (int m=2; m<3; m++) {
230  (void) new Int2(m, s1, s1);
231  (void) new Int2(m, s2, s2);
232  (void) new Int2(m, s3, s3);
233  (void) new Int2(m, s2, s3);
234  (void) new Int2(m, s4, s4);
235  (void) new Int2(m, s4, s2);
236  (void) new IntOpt2(m, s2, s3);
237  (void) new IntOpt2(m, s4, s3);
238  }
239 
240  (void) new Var2(2, 2);
241  (void) new Var2(3, 2);
242  (void) new Var2(1, 3);
243  (void) new VarOpt2(2, 2);
244  (void) new VarOpt2(3, 2);
245 
246  }
247  };
248 
250 
252 
253  }
254 
255 }}
256 
257 
258 // STATISTICS: test-int
259