Generated on Sat Feb 7 2015 02:01:24 for Gecode by doxygen 1.8.9.1
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: 2012-10-22 21:13:52 +0200 (Mon, 22 Oct 2012) $ by $Author: schulte $
11  * $Revision: 13163 $
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  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 
217  class VarOptShared2 : public Test {
218  public:
220  VarOptShared2(int m, int n)
221  : Test("NoOverlap::Var::Opt::Shared::2::"+
222  str(m)+"::"+str(n), 2*n+2, 0, m) {
223  testfix = false;
224  }
226  virtual bool solution(const Assignment& xwyho) const {
227  int n = (xwyho.size() - 2) / 2;
228  for (int i=0; i<n; i++) {
229  int xi=xwyho[2*i+0], yi=xwyho[2*i+0];
230  int wi=xwyho[2*i+1], hi=xwyho[2*i+1];
231  int oi=xwyho[2*n + (i % 2)];
232  for (int j=i+1; j<n; j++) {
233  int xj=xwyho[2*j+0], yj=xwyho[2*j+0];
234  int wj=xwyho[2*j+1], hj=xwyho[2*j+1];
235  int oj=xwyho[2*n + (j % 2)];
236  if ((oi > 0) && (oj > 0) &&
237  !((xi + wi <= xj) || (xj + wj <= xi) ||
238  (yi + hi <= yj) || (yj + hj <= yi)))
239  return false;
240  }
241  }
242  return true;
243  }
245  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyho) {
246  using namespace Gecode;
247  int n = (xwyho.size() - 2) / 2;
248  IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
249  BoolVarArgs o(n);
250  for (int i=0; i<n; i++) {
251  x0[i]=xwyho[2*i+0]; w[i]=xwyho[2*i+1];
252  x1[i]=expr(home, x0[i] + w[i]);
253  y0[i]=xwyho[2*i+0]; h[i]=xwyho[2*i+1];
254  y1[i]=expr(home, y0[i] + h[i]);
255  o[i]=expr(home, xwyho[2*n + (i % 2)] > 0);
256  }
257  nooverlap(home, x0, w, x1, y0, h, y1, o);
258  }
259  };
260 
261 
263  class Create {
264  public:
266  Create(void) {
267  using namespace Gecode;
268 
269  IntArgs s1(3, 2,1,1);
270  IntArgs s2(4, 1,2,3,4);
271  IntArgs s3(4, 4,3,2,1);
272  IntArgs s4(4, 1,1,1,1);
273 
274  for (int m=2; m<3; m++) {
275  (void) new Int2(m, s1, s1);
276  (void) new Int2(m, s2, s2);
277  (void) new Int2(m, s3, s3);
278  (void) new Int2(m, s2, s3);
279  (void) new Int2(m, s4, s4);
280  (void) new Int2(m, s4, s2);
281  (void) new IntOpt2(m, s2, s3);
282  (void) new IntOpt2(m, s4, s3);
283  }
284 
285  (void) new Var2(2, 2);
286  (void) new Var2(3, 2);
287  (void) new Var2(1, 3);
288  (void) new VarOpt2(2, 2);
289  (void) new VarOpt2(3, 2);
290  (void) new VarOptShared2(2, 2);
291  (void) new VarOptShared2(3, 2);
292  (void) new VarOptShared2(4, 2);
293 
294  }
295  };
296 
298 
300 
301  }
302 
303 }}
304 
305 
306 // STATISTICS: test-int
307 
virtual bool solution(const Assignment &xyo) const
Test whether xyo is solution
Definition: no-overlap.cpp:105
Gecode::IntArgs w
Width.
Definition: no-overlap.cpp:96
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
Definition: no-overlap.cpp:82
Gecode::IntArgs h
Height.
Definition: no-overlap.cpp:59
Integer variable array.
Definition: int.hh:741
Help class to create and register tests.
Definition: no-overlap.cpp:263
Computation spaces.
Definition: core.hpp:1362
virtual bool solution(const Assignment &xwyh) const
Test whether xwyh is solution
Definition: no-overlap.cpp:142
static std::string str(Gecode::ExtensionalPropKind epk)
Map extensional propagation kind to string.
Definition: int.hpp:212
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xwyh)
Post constraint on xwyh.
Definition: no-overlap.cpp:158
unsigned int size(I &i)
Size of all ranges of range iterator i.
virtual bool solution(const Assignment &xwyho) const
Test whether xwyho is solution
Definition: no-overlap.cpp:226
Int2(int m, const Gecode::IntArgs &w0, const Gecode::IntArgs &h0)
Create and register test with maximal coordinate value m.
Definition: no-overlap.cpp:62
Passing integer variables.
Definition: int.hh:636
Passing integer arguments.
Definition: int.hh:607
Passing Boolean variables.
Definition: int.hh:690
IntOpt2(int m, const Gecode::IntArgs &w0, const Gecode::IntArgs &h0)
Create and register test with maximal value m and n rectangles.
Definition: no-overlap.cpp:101
Test for no-overlap with optional rectangles and shared variables
Definition: no-overlap.cpp:217
Test for no-overlap with optional rectangles
Definition: no-overlap.cpp:93
bool testfix
Whether to perform fixpoint test.
Definition: int.hh:232
General test support.
Definition: afc.cpp:43
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
Test for no-overlap with integer dimensions (rectangles)
Definition: no-overlap.cpp:54
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xwyho)
Post constraint on xwyho.
Definition: no-overlap.cpp:245
Base class for assignments
Definition: int.hh:63
void nooverlap(Home home, const IntVarArgs &x0, const IntVarArgs &w, const IntVarArgs &x1, const IntVarArgs &y0, const IntVarArgs &h, const IntVarArgs &y1, const BoolVarArgs &m, IntConLevel)
Post propagator for rectangle packing.
Definition: no-overlap.cpp:168
Gecode toplevel namespace
Test for no-overlap with optional rectangles
Definition: no-overlap.cpp:173
VarOptShared2(int m, int n)
Create and register test with maximal value m and n rectangles.
Definition: no-overlap.cpp:220
Create(void)
Perform creation and registration.
Definition: no-overlap.cpp:266
Var2(int m, int n)
Create and register test with maximal value m and n rectangles.
Definition: no-overlap.cpp:139
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xwyho)
Post constraint on xwyho.
Definition: no-overlap.cpp:200
int size(void) const
Return number of variables.
Definition: int.hpp:50
virtual bool solution(const Assignment &xwyho) const
Test whether xwyho is solution
Definition: no-overlap.cpp:181
Gecode::IntArgs h
Height.
Definition: no-overlap.cpp:98
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xyo)
Post constraint on xwyho.
Definition: no-overlap.cpp:122
VarOpt2(int m, int n)
Create and register test with maximal value m and n rectangles.
Definition: no-overlap.cpp:176
Gecode::IntArgs w
Width.
Definition: no-overlap.cpp:57
Test for no-overlap with variable dimensions (rectangles)
Definition: no-overlap.cpp:136
virtual bool solution(const Assignment &xy) const
Test whether xy is solution
Definition: no-overlap.cpp:68