Generated on Mon Jul 27 2020 00:00:00 for Gecode by doxygen 1.8.18
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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include "test/int.hh"
35 
36 #include <gecode/minimodel.hh>
37 #include <climits>
38 
39 namespace Test { namespace Int {
40 
42  namespace NoOverlap {
43 
49  class Int2 : public Test {
51  protected:
56  public:
58  Int2(int m, const Gecode::IntArgs& w0, const Gecode::IntArgs& h0)
59  : Test("NoOverlap::Int::2::"+str(m)+"::"+str(w0)+"::"+str(h0),
60  2*w0.size(), 0, m-1),
61  w(w0), h(h0) {
62  }
64  virtual bool solution(const Assignment& xy) const {
65  int n = xy.size() / 2;
66  for (int i=0; i<n; i++) {
67  int xi=xy[2*i+0], yi=xy[2*i+1];
68  for (int j=i+1; j<n; j++) {
69  int xj=xy[2*j+0], yj=xy[2*j+1];
70  if (!((xi + w[i] <= xj) || (xj + w[j] <= xi) ||
71  (yi + h[i] <= yj) || (yj + h[j] <= yi)))
72  return false;
73  }
74  }
75  return true;
76  }
78  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
79  using namespace Gecode;
80  int n = xy.size() / 2;
81  IntVarArgs x(n), y(n);
82  for (int i=0; i<n; i++) {
83  x[i]=xy[2*i+0]; y[i]=xy[2*i+1];
84  }
85  nooverlap(home, x, w, y, h);
86  }
87  };
89  class IntOpt2 : public Test {
90  protected:
95  public:
97  IntOpt2(int m, const Gecode::IntArgs& w0, const Gecode::IntArgs& h0)
98  : Test("NoOverlap::Int::Opt::2::"+str(m)+"::"+str(w0)+"::"+str(h0),
99  3*w0.size(), 0, m-1), w(w0), h(h0) {}
101  virtual bool solution(const Assignment& xyo) const {
102  int n = xyo.size() / 3;
103  for (int i=0; i<n; i++) {
104  int xi=xyo[3*i+0], yi=xyo[3*i+1];
105  int oi=xyo[3*i+2];
106  for (int j=i+1; j<n; j++) {
107  int xj=xyo[3*j+0], yj=xyo[3*j+1];
108  int oj=xyo[3*j+2];
109  if ((oi > 0) && (oj > 0) &&
110  !((xi + w[i] <= xj) || (xj + w[j] <= xi) ||
111  (yi + h[i] <= yj) || (yj + h[j] <= yi)))
112  return false;
113  }
114  }
115  return true;
116  }
118  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xyo) {
119  using namespace Gecode;
120  int n = xyo.size() / 3;
121  IntVarArgs x(n), y(n);
122  BoolVarArgs o(n);
123  for (int i=0; i<n; i++) {
124  x[i]=xyo[3*i+0]; y[i]=xyo[3*i+1];
125  o[i]=expr(home, xyo[3*i+2] > 0);
126  }
127  nooverlap(home, x, w, y, h, o);
128  }
129  };
130 
132  class Var2 : public Test {
133  public:
135  Var2(int m, int n)
136  : Test("NoOverlap::Var::2::"+str(m)+"::"+str(n), 4*n, 0, m) {}
138  virtual bool solution(const Assignment& xwyh) const {
139  int n = xwyh.size() / 4;
140  for (int i=0; i<n; i++) {
141  int xi=xwyh[4*i+0], yi=xwyh[4*i+2];
142  int wi=xwyh[4*i+1], hi=xwyh[4*i+3];
143  for (int j=i+1; j<n; j++) {
144  int xj=xwyh[4*j+0], yj=xwyh[4*j+2];
145  int wj=xwyh[4*j+1], hj=xwyh[4*j+3];
146  if (!((xi + wi <= xj) || (xj + wj <= xi) ||
147  (yi + hi <= yj) || (yj + hj <= yi)))
148  return false;
149  }
150  }
151  return true;
152  }
154  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyh) {
155  using namespace Gecode;
156  int n = xwyh.size() / 4;
157  IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
158  for (int i=0; i<n; i++) {
159  x0[i]=xwyh[4*i+0]; w[i]=xwyh[4*i+1];
160  x1[i]=expr(home, x0[i] + w[i]);
161  y0[i]=xwyh[4*i+2]; h[i]=xwyh[4*i+3];
162  y1[i]=expr(home, y0[i] + h[i]);
163  }
164  nooverlap(home, x0, w, x1, y0, h, y1);
165  }
166  };
167 
169  class VarOpt2 : public Test {
170  public:
172  VarOpt2(int m, int n)
173  : Test("NoOverlap::Var::Opt::2::"+str(m)+"::"+str(n), 5*n, 0, m) {
174  testfix = false;
175  }
177  virtual bool solution(const Assignment& xwyho) const {
178  int n = xwyho.size() / 5;
179  for (int i=0; i<n; i++) {
180  int xi=xwyho[5*i+0], yi=xwyho[5*i+2];
181  int wi=xwyho[5*i+1], hi=xwyho[5*i+3];
182  int oi=xwyho[5*i+4];
183  for (int j=i+1; j<n; j++) {
184  int xj=xwyho[5*j+0], yj=xwyho[5*j+2];
185  int wj=xwyho[5*j+1], hj=xwyho[5*j+3];
186  int oj=xwyho[5*j+4];
187  if ((oi > 0) && (oj > 0) &&
188  !((xi + wi <= xj) || (xj + wj <= xi) ||
189  (yi + hi <= yj) || (yj + hj <= yi)))
190  return false;
191  }
192  }
193  return true;
194  }
196  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyho) {
197  using namespace Gecode;
198  int n = xwyho.size() / 5;
199  IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
200  BoolVarArgs o(n);
201  for (int i=0; i<n; i++) {
202  x0[i]=xwyho[5*i+0]; w[i]=xwyho[5*i+1];
203  x1[i]=expr(home, x0[i] + w[i]);
204  y0[i]=xwyho[5*i+2]; h[i]=xwyho[5*i+3];
205  y1[i]=expr(home, y0[i] + h[i]);
206  o[i]=expr(home, xwyho[5*i+4] > 0);
207  }
208  nooverlap(home, x0, w, x1, y0, h, y1, o);
209  }
210  };
211 
213  class VarOptShared2 : public Test {
214  public:
216  VarOptShared2(int m, int n)
217  : Test("NoOverlap::Var::Opt::Shared::2::"+
218  str(m)+"::"+str(n), 2*n+2, 0, m) {
219  testfix = false;
220  }
222  virtual bool solution(const Assignment& xwyho) const {
223  int n = (xwyho.size() - 2) / 2;
224  for (int i=0; i<n; i++) {
225  int xi=xwyho[2*i+0], yi=xwyho[2*i+0];
226  int wi=xwyho[2*i+1], hi=xwyho[2*i+1];
227  int oi=xwyho[2*n + (i % 2)];
228  for (int j=i+1; j<n; j++) {
229  int xj=xwyho[2*j+0], yj=xwyho[2*j+0];
230  int wj=xwyho[2*j+1], hj=xwyho[2*j+1];
231  int oj=xwyho[2*n + (j % 2)];
232  if ((oi > 0) && (oj > 0) &&
233  !((xi + wi <= xj) || (xj + wj <= xi) ||
234  (yi + hi <= yj) || (yj + hj <= yi)))
235  return false;
236  }
237  }
238  return true;
239  }
241  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyho) {
242  using namespace Gecode;
243  int n = (xwyho.size() - 2) / 2;
244  IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
245  BoolVarArgs o(n);
246  for (int i=0; i<n; i++) {
247  x0[i]=xwyho[2*i+0]; w[i]=xwyho[2*i+1];
248  x1[i]=expr(home, x0[i] + w[i]);
249  y0[i]=xwyho[2*i+0]; h[i]=xwyho[2*i+1];
250  y1[i]=expr(home, y0[i] + h[i]);
251  o[i]=expr(home, xwyho[2*n + (i % 2)] > 0);
252  }
253  nooverlap(home, x0, w, x1, y0, h, y1, o);
254  }
255  };
256 
257 
259  class Create {
260  public:
262  Create(void) {
263  using namespace Gecode;
264 
265  IntArgs s1({2,1,1});
266  IntArgs s2({1,2,3,4});
267  IntArgs s3({4,3,2,1});
268  IntArgs s4({1,1,1,1});
269 
270  for (int m=2; m<3; m++) {
271  (void) new Int2(m, s1, s1);
272  (void) new Int2(m, s2, s2);
273  (void) new Int2(m, s3, s3);
274  (void) new Int2(m, s2, s3);
275  (void) new Int2(m, s4, s4);
276  (void) new Int2(m, s4, s2);
277  (void) new IntOpt2(m, s2, s3);
278  (void) new IntOpt2(m, s4, s3);
279  }
280 
281  (void) new Var2(2, 2);
282  (void) new Var2(3, 2);
283  (void) new Var2(1, 3);
284  (void) new VarOpt2(2, 2);
285  (void) new VarOpt2(3, 2);
286  (void) new VarOptShared2(2, 2);
287  (void) new VarOptShared2(3, 2);
288  (void) new VarOptShared2(4, 2);
289 
290  }
291  };
292 
294 
296 
297  }
298 
299 }}
300 
301 
302 // STATISTICS: test-int
303 
VarOpt2(int m, int n)
Create and register test with maximal value m and n rectangles.
Definition: no-overlap.cpp:172
virtual bool solution(const Assignment &xwyh) const
Test whether xwyh is solution
Definition: no-overlap.cpp:138
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
virtual bool solution(const Assignment &xy) const
Test whether xy is solution
Definition: no-overlap.cpp:64
Int2(int m, const Gecode::IntArgs &w0, const Gecode::IntArgs &h0)
Create and register test with maximal coordinate value m.
Definition: no-overlap.cpp:58
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xwyho)
Post constraint on xwyho.
Definition: no-overlap.cpp:196
Gecode::IntArgs h
Height.
Definition: no-overlap.cpp:94
Test for no-overlap with optional rectangles and shared variables
Definition: no-overlap.cpp:213
Passing integer variables.
Definition: int.hh:656
unsigned int size(I &i)
Size of all ranges of range iterator i.
Computation spaces.
Definition: core.hpp:1742
virtual bool solution(const Assignment &xyo) const
Test whether xyo is solution
Definition: no-overlap.cpp:101
Gecode::IntArgs w
Width.
Definition: no-overlap.cpp:53
Integer variable array.
Definition: int.hh:763
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:926
Test for no-overlap with integer dimensions (rectangles)
Definition: no-overlap.cpp:50
int size(void) const
Return number of variables.
Definition: int.hpp:46
Create(void)
Perform creation and registration.
Definition: no-overlap.cpp:262
virtual bool solution(const Assignment &xwyho) const
Test whether xwyho is solution
Definition: no-overlap.cpp:222
Gecode toplevel namespace
bool testfix
Whether to perform fixpoint test.
Definition: int.hh:240
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
Test for no-overlap with variable dimensions (rectangles)
Definition: no-overlap.cpp:132
BoolVar expr(Home home, const BoolExpr &e, const IntPropLevels &ipls)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:629
Passing Boolean variables.
Definition: int.hh:712
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
Definition: no-overlap.cpp:78
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xwyho)
Post constraint on xwyho.
Definition: no-overlap.cpp:241
Test for no-overlap with optional rectangles
Definition: no-overlap.cpp:169
Test for no-overlap with optional rectangles
Definition: no-overlap.cpp:89
virtual bool solution(const Assignment &xwyho) const
Test whether xwyho is solution
Definition: no-overlap.cpp:177
Base class for assignments
Definition: int.hh:59
Help class to create and register tests.
Definition: no-overlap.cpp:259
Create c
Definition: no-overlap.cpp:293
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:97
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xwyh)
Post constraint on xwyh.
Definition: no-overlap.cpp:154
General test support.
Definition: afc.cpp:39
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, IntPropLevel)
Post propagator for rectangle packing.
Definition: no-overlap.cpp:164
Gecode::IntArgs h
Height.
Definition: no-overlap.cpp:55
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xyo)
Post constraint on xwyho.
Definition: no-overlap.cpp:118
Gecode::IntArgs w
Width.
Definition: no-overlap.cpp:92
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
VarOptShared2(int m, int n)
Create and register test with maximal value m and n rectangles.
Definition: no-overlap.cpp:216
Passing integer arguments.
Definition: int.hh:628
Gecode::IntArgs i({1, 2, 3, 4})
Var2(int m, int n)
Create and register test with maximal value m and n rectangles.
Definition: no-overlap.cpp:135
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition: int.hpp:209