Generated on for Gecode by doxygen 1.17.0
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.dev>
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.dev
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
39namespace Test { namespace Int {
40
42 namespace NoOverlap {
43
49
50 class Int2 : public Test {
51 protected:
56 public:
59 const Gecode::IntArgs& w0, const Gecode::IntArgs& h0)
60 : Test(tags,
61 "NoOverlap::Int::2::"+str(m)+"::"+str(w0)+"::"+str(h0),
62 2*w0.size(), 0, m-1),
63 w(w0), h(h0) {
64 }
65
66 virtual bool solution(const Assignment& xy) const {
67 int n = xy.size() / 2;
68 for (int i=0; i<n; i++) {
69 int xi=xy[2*i+0], yi=xy[2*i+1];
70 for (int j=i+1; j<n; j++) {
71 int xj=xy[2*j+0], yj=xy[2*j+1];
72 if (!((xi + w[i] <= xj) || (xj + w[j] <= xi) ||
73 (yi + h[i] <= yj) || (yj + h[j] <= yi)))
74 return false;
75 }
76 }
77 return true;
78 }
79
80 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
81 using namespace Gecode;
82 int n = xy.size() / 2;
83 IntVarArgs x(n), y(n);
84 for (int i=0; i<n; i++) {
85 x[i]=xy[2*i+0]; y[i]=xy[2*i+1];
86 }
87 nooverlap(home, x, w, y, h);
88 }
89 };
90
91 class IntOpt2 : public Test {
92 protected:
97 public:
99 IntOpt2(int m, const Gecode::IntArgs& w0, const Gecode::IntArgs& h0)
100 : Test(TestTags::sweep(),"NoOverlap::Int::Opt::2::"+str(m)+"::"+str(w0)+"::"+str(h0),
101 3*w0.size(), 0, m-1), w(w0), h(h0) {}
102
103 virtual bool solution(const Assignment& xyo) const {
104 int n = xyo.size() / 3;
105 for (int i=0; i<n; i++) {
106 int xi=xyo[3*i+0], yi=xyo[3*i+1];
107 int oi=xyo[3*i+2];
108 for (int j=i+1; j<n; j++) {
109 int xj=xyo[3*j+0], yj=xyo[3*j+1];
110 int oj=xyo[3*j+2];
111 if ((oi > 0) && (oj > 0) &&
112 !((xi + w[i] <= xj) || (xj + w[j] <= xi) ||
113 (yi + h[i] <= yj) || (yj + h[j] <= yi)))
114 return false;
115 }
116 }
117 return true;
118 }
119
120 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xyo) {
121 using namespace Gecode;
122 int n = xyo.size() / 3;
123 IntVarArgs x(n), y(n);
124 BoolVarArgs o(n);
125 for (int i=0; i<n; i++) {
126 x[i]=xyo[3*i+0]; y[i]=xyo[3*i+1];
127 o[i]=expr(home, xyo[3*i+2] > 0);
128 }
129 nooverlap(home, x, w, y, h, o);
130 }
131 };
132
134 class Var2 : public Test {
135 public:
137 Var2(int m, int n)
138 : Test(TestTags::sweep(),"NoOverlap::Var::2::"+str(m)+"::"+str(n), 4*n, 0, m) {}
139
140 virtual bool solution(const Assignment& xwyh) const {
141 int n = xwyh.size() / 4;
142 for (int i=0; i<n; i++) {
143 int xi=xwyh[4*i+0], yi=xwyh[4*i+2];
144 int wi=xwyh[4*i+1], hi=xwyh[4*i+3];
145 for (int j=i+1; j<n; j++) {
146 int xj=xwyh[4*j+0], yj=xwyh[4*j+2];
147 int wj=xwyh[4*j+1], hj=xwyh[4*j+3];
148 if (!((xi + wi <= xj) || (xj + wj <= xi) ||
149 (yi + hi <= yj) || (yj + hj <= yi)))
150 return false;
151 }
152 }
153 return true;
154 }
155
156 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyh) {
157 using namespace Gecode;
158 int n = xwyh.size() / 4;
159 IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
160 for (int i=0; i<n; i++) {
161 x0[i]=xwyh[4*i+0]; w[i]=xwyh[4*i+1];
162 x1[i]=expr(home, x0[i] + w[i]);
163 y0[i]=xwyh[4*i+2]; h[i]=xwyh[4*i+3];
164 y1[i]=expr(home, y0[i] + h[i]);
165 }
166 nooverlap(home, x0, w, x1, y0, h, y1);
167 }
168 };
169
171 class VarOpt2 : public Test {
172 public:
174 VarOpt2(int m, int n)
175 : Test(TestTags::sweep(),"NoOverlap::Var::Opt::2::"+str(m)+"::"+str(n), 5*n, 0, m) {
176 testfix = false;
177 }
178
179 virtual bool solution(const Assignment& xwyho) const {
180 int n = xwyho.size() / 5;
181 for (int i=0; i<n; i++) {
182 int xi=xwyho[5*i+0], yi=xwyho[5*i+2];
183 int wi=xwyho[5*i+1], hi=xwyho[5*i+3];
184 int oi=xwyho[5*i+4];
185 for (int j=i+1; j<n; j++) {
186 int xj=xwyho[5*j+0], yj=xwyho[5*j+2];
187 int wj=xwyho[5*j+1], hj=xwyho[5*j+3];
188 int oj=xwyho[5*j+4];
189 if ((oi > 0) && (oj > 0) &&
190 !((xi + wi <= xj) || (xj + wj <= xi) ||
191 (yi + hi <= yj) || (yj + hj <= yi)))
192 return false;
193 }
194 }
195 return true;
196 }
197
198 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyho) {
199 using namespace Gecode;
200 int n = xwyho.size() / 5;
201 IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
202 BoolVarArgs o(n);
203 for (int i=0; i<n; i++) {
204 x0[i]=xwyho[5*i+0]; w[i]=xwyho[5*i+1];
205 x1[i]=expr(home, x0[i] + w[i]);
206 y0[i]=xwyho[5*i+2]; h[i]=xwyho[5*i+3];
207 y1[i]=expr(home, y0[i] + h[i]);
208 o[i]=expr(home, xwyho[5*i+4] > 0);
209 }
210 nooverlap(home, x0, w, x1, y0, h, y1, o);
211 }
212 };
213
215 class VarOptShared2 : public Test {
216 public:
218 VarOptShared2(int m, int n)
219 : Test(TestTags::sweep(),"NoOverlap::Var::Opt::Shared::2::"+
220 str(m)+"::"+str(n), 2*n+2, 0, m) {
221 testfix = false;
222 }
223
224 virtual bool solution(const Assignment& xwyho) const {
225 int n = (xwyho.size() - 2) / 2;
226 for (int i=0; i<n; i++) {
227 int xi=xwyho[2*i+0], yi=xwyho[2*i+0];
228 int wi=xwyho[2*i+1], hi=xwyho[2*i+1];
229 int oi=xwyho[2*n + (i % 2)];
230 for (int j=i+1; j<n; j++) {
231 int xj=xwyho[2*j+0], yj=xwyho[2*j+0];
232 int wj=xwyho[2*j+1], hj=xwyho[2*j+1];
233 int oj=xwyho[2*n + (j % 2)];
234 if ((oi > 0) && (oj > 0) &&
235 !((xi + wi <= xj) || (xj + wj <= xi) ||
236 (yi + hi <= yj) || (yj + hj <= yi)))
237 return false;
238 }
239 }
240 return true;
241 }
242
243 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xwyho) {
244 using namespace Gecode;
245 int n = (xwyho.size() - 2) / 2;
246 IntVarArgs x0(n), w(n), x1(n), y0(n), h(n), y1(n);
247 BoolVarArgs o(n);
248 for (int i=0; i<n; i++) {
249 x0[i]=xwyho[2*i+0]; w[i]=xwyho[2*i+1];
250 x1[i]=expr(home, x0[i] + w[i]);
251 y0[i]=xwyho[2*i+0]; h[i]=xwyho[2*i+1];
252 y1[i]=expr(home, y0[i] + h[i]);
253 o[i]=expr(home, xwyho[2*n + (i % 2)] > 0);
254 }
255 nooverlap(home, x0, w, x1, y0, h, y1, o);
256 }
257 };
258
259
261 class Create {
262 public:
264 Create(void) {
265 using namespace Gecode;
266
267 IntArgs s1({2,1,1});
268 IntArgs s2({1,2,3,4});
269 IntArgs s3({4,3,2,1});
270 IntArgs s4({1,1,1,1});
271
272 for (int m=2; m<3; m++) {
273 (void) new Int2(TestTags::sweep(),m,s1,s1);
274 (void) new Int2(TestTags::sweep(),m,s2,s2);
275 (void) new Int2(TestTags::sweep(),m,s3,s3);
276 (void) new Int2(TestTags::sweep(),m,s2,s3);
277 (void) new Int2(TestTags::standard(),m,s4,s4);
278 (void) new Int2(TestTags::sweep(),m,s4,s2);
279 (void) new IntOpt2(m, s2, s3);
280 (void) new IntOpt2(m, s4, s3);
281 }
282
283 (void) new Var2(2, 2);
284 (void) new Var2(3, 2);
285 (void) new Var2(1, 3);
286 (void) new VarOpt2(2, 2);
287 (void) new VarOpt2(3, 2);
288 (void) new VarOptShared2(2, 2);
289 (void) new VarOptShared2(3, 2);
290 (void) new VarOptShared2(4, 2);
291
292 }
293 };
294
296
298
299 }
300
301}}
302
303
304// STATISTICS: test-int
Passing Boolean variables.
Definition int.hh:739
Passing integer arguments.
Definition int.hh:653
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Computation spaces.
Definition core.hpp:1787
int size(void) const
Return size of array (number of elements).
Definition array.hpp:945
TestTags tags(void) const
Return tags for test.
Definition test.hpp:95
Base class for assignments
Definition int.hh:73
int size(void) const
Return number of variables.
Definition int.hpp:46
Help class to create and register tests.
Create(void)
Perform creation and registration.
Test for no-overlap with integer dimensions (rectangles)
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
virtual bool solution(const Assignment &xy) const
Test whether xy is solution
Int2(TestTags tags, int m, const Gecode::IntArgs &w0, const Gecode::IntArgs &h0)
Create and register test with maximal coordinate value m.
Gecode::IntArgs h
Height.
Gecode::IntArgs w
Width.
Test for no-overlap with optional rectangles
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xyo)
Post constraint on xwyho.
IntOpt2(int m, const Gecode::IntArgs &w0, const Gecode::IntArgs &h0)
Create and register test with maximal value m and n rectangles.
virtual bool solution(const Assignment &xyo) const
Test whether xyo is solution
Gecode::IntArgs w
Width.
Gecode::IntArgs h
Height.
Test for no-overlap with variable dimensions (rectangles)
Var2(int m, int n)
Create and register test with maximal value m and n rectangles.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xwyh)
Post constraint on xwyh.
virtual bool solution(const Assignment &xwyh) const
Test whether xwyh is solution
Test for no-overlap with optional rectangles
virtual bool solution(const Assignment &xwyho) const
Test whether xwyho is solution
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xwyho)
Post constraint on xwyho.
VarOpt2(int m, int n)
Create and register test with maximal value m and n rectangles.
Test for no-overlap with optional rectangles and shared variables
VarOptShared2(int m, int n)
Create and register test with maximal value m and n rectangles.
virtual bool solution(const Assignment &xwyho) const
Test whether xwyho is solution
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xwyho)
Post constraint on xwyho.
static std::string str(bool b)
Map bool to string.
Definition int.hpp:278
bool testfix
Whether to perform fixpoint test.
Definition int.hh:287
Set of test tags.
Definition test.hh:105
static TestTags sweep(void)
Expensive parameter sweeps.
Definition test.hpp:59
static TestTags standard(void)
Standard suite without expensive sweeps.
Definition test.hpp:55
void nooverlap(Home home, const IntVarArgs &x, const IntArgs &w, const IntVarArgs &y, const IntArgs &h, IntPropLevel ipl=IPL_DEF)
Post propagator for rectangle packing.
Gecode toplevel namespace
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:988
Tests for no-overlap constraint
Testing finite domain integers.
Definition int.cpp:41
General test support.
Definition afc.cpp:41
@ sweep
Really heavy sweep tests.
Definition test.hh:101