Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.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.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
39namespace Test { namespace Int {
40
42 namespace NoOverlap {
43
49
50 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 }
63
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 }
77
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 };
88
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) {}
100
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 }
117
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) {}
137
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 }
153
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 }
176
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 }
195
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 }
221
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 }
240
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
Passing Boolean variables.
Definition int.hh:721
Passing integer arguments.
Definition int.hh:634
Passing integer variables.
Definition int.hh:662
Integer variable array.
Definition int.hh:772
Computation spaces.
Definition core.hpp:1744
int size(void) const
Return size of array (number of elements)
Definition array.hpp:932
Base class for assignments
Definition int.hh:59
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)
Int2(int m, const Gecode::IntArgs &w0, const Gecode::IntArgs &h0)
Create and register test with maximal coordinate value m.
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
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.
bool testfix
Whether to perform fixpoint test.
Definition int.hh:240
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition int.hpp:209
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:915
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
Post propagator for SetVar x
Definition set.hh:773
Tests for no-overlap constraint
Testing finite domain integers.
Definition int.cpp:40
General test support.
Definition afc.cpp:39