this repo has no description
dekker.one
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
41 /// %Tests for no-overlap constraint
42 namespace NoOverlap {
43
44 /**
45 * \defgroup TaskTestIntNoOverlap No-overlap constraints
46 * \ingroup TaskTestInt
47 */
48 //@{
49 /// %Test for no-overlap with integer dimensions (rectangles)
50 class Int2 : public Test {
51 protected:
52 /// Width
53 Gecode::IntArgs w;
54 /// Height
55 Gecode::IntArgs h;
56 public:
57 /// Create and register test with maximal coordinate value \a m
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 /// %Test whether \a xy is solution
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 /// Post constraint on \a xy
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 /// %Test for no-overlap with optional rectangles
89 class IntOpt2 : public Test {
90 protected:
91 /// Width
92 Gecode::IntArgs w;
93 /// Height
94 Gecode::IntArgs h;
95 public:
96 /// Create and register test with maximal value \a m and \a n rectangles
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 /// %Test whether \a xyo is solution
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 /// Post constraint on \a xwyho
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
131 /// %Test for no-overlap with variable dimensions (rectangles)
132 class Var2 : public Test {
133 public:
134 /// Create and register test with maximal value \a m and \a n rectangles
135 Var2(int m, int n)
136 : Test("NoOverlap::Var::2::"+str(m)+"::"+str(n), 4*n, 0, m) {}
137 /// %Test whether \a xwyh is solution
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 /// Post constraint on \a xwyh
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
168 /// %Test for no-overlap with optional rectangles
169 class VarOpt2 : public Test {
170 public:
171 /// Create and register test with maximal value \a m and \a n rectangles
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 /// %Test whether \a xwyho is solution
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 /// Post constraint on \a xwyho
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
212 /// %Test for no-overlap with optional rectangles and shared variables
213 class VarOptShared2 : public Test {
214 public:
215 /// Create and register test with maximal value \a m and \a n rectangles
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 /// %Test whether \a xwyho is solution
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 /// Post constraint on \a xwyho
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
258 /// Help class to create and register tests
259 class Create {
260 public:
261 /// Perform creation and registration
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
293 Create c;
294
295 //@}
296
297 }
298
299}}
300
301
302// STATISTICS: test-int
303