Generated on for Gecode by doxygen 1.17.0
inter-distance.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
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 <algorithm>
37#include <limits>
38
39namespace Test { namespace Int { namespace InterDistance {
40
42 class Distance : public Test {
43 protected:
44 int p;
45 public:
46 Distance(int n, int p0, int min, int max,
48 : Test((n == 3 && p0 == 2 && min == -3)
50 "InterDistance::"+str(n)+"::"+str(p0)+"::"+str(min)+
51 "::"+str(ipl0),n,min,max,false,ipl0), p(p0) {
53 }
54 Distance(int n, int p0, const Gecode::IntSet& domain)
55 : Test(TestTags::standard(),"InterDistance::Holes::"+str(n)+"::"+str(p0),
56 n,domain,false,Gecode::IPL_DEF), p(p0) {
58 }
59 virtual bool solution(const Assignment& x) const {
60 for (int i=0; i<x.size(); i++)
61 for (int j=0; j<i; j++) {
62 long long int d = static_cast<long long int>(x[i])-x[j];
63 if ((-p < d) && (d < p))
64 return false;
65 }
66 return true;
67 }
68 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
70 }
71 };
72
74 class Variable : public Test {
75 public:
77 : Test(n == 3 ? TestTags::check() : TestTags::standard(),
78 "InterDistance::Variable::"+str(n)+"::"+str(ipl0),
79 n+1,-2,3,false,ipl0) {
81 }
82 virtual bool solution(const Assignment& x) const {
83 int p = x[x.size()-1];
84 if (p < 0)
85 return false;
86 for (int i=0; i<x.size()-1; i++)
87 for (int j=0; j<i; j++)
88 if (std::abs(x[i]-x[j]) < p)
89 return false;
90 return true;
91 }
92 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
93 Gecode::IntVarArgs a(x.size()-1);
94 for (int i=0; i<a.size(); i++)
95 a[i] = x[i];
96 Gecode::inter_distance(home,a,x[x.size()-1],ipl);
97 }
98 };
99
102 protected:
103 int p;
105 public:
106 DistanceAssignment(int n, const Gecode::IntSet& d, int p0, bool v,
108 : RandomAssignment(n,d,100,rand), p(p0), variable(v) {}
111 if (a % 2 == 0) {
112 int m = n - static_cast<int>(variable);
113 int distance = variable ? static_cast<int>(rand(p+1)) : p;
114 int slack = d.max()-d.min()-(m-1)*distance;
115 int value = d.min();
116 for (int i=0; i<m; i++) {
117 int extra = static_cast<int>(rand(slack+1));
118 slack -= extra;
119 value += extra;
120 vals[i] = value;
121 if (i+1 < m)
122 value += distance;
123 }
124 for (int i=m-1; i>0; i--) {
125 int j = static_cast<int>(rand(i+1));
126 std::swap(vals[i],vals[j]);
127 }
128 if (variable)
129 vals[m] = distance;
130 }
131 }
132 };
133
135 class Random : public Test {
136 protected:
137 int p;
139 public:
140 Random(int n, int p0, int slack, bool v, Gecode::IntPropLevel level)
141 : Test("InterDistance::Random::"+str(n)+"::"+str(p0)+"::"+
142 str(slack)+"::"+str(v)+"::"+str(level),
143 n+static_cast<int>(v),0,(n-1)*p0+slack,false,level),
144 p(p0), variable(v) {
145 testsearch = false;
146 }
147 virtual Assignment* assignment(void) const {
149 }
150 virtual bool solution(const Assignment& x) const {
151 int n = x.size()-static_cast<int>(variable);
152 int distance = variable ? x[n] : p;
153 for (int i=0; i<n; i++)
154 for (int j=0; j<i; j++)
155 if (std::abs(x[i]-x[j]) < distance)
156 return false;
157 return true;
158 }
159 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
160 Gecode::IntVarArgs y(x.size()-static_cast<int>(variable));
161 for (int i=0; i<y.size(); i++)
162 y[i] = x[i];
163 if (variable)
164 Gecode::inter_distance(home,y,x[y.size()],ipl);
165 else
167 }
168 };
169
172 Gecode::IntSet domains[6];
173 Gecode::IntSetValues values[6];
174 public:
176 : Assignment(n,Gecode::IntSet()) {
177 for (int i=0; i<n; i++) {
178 domains[i] = d[i];
179 values[i].init(domains[i]);
180 }
181 }
182 virtual bool has_more(void) const {
183 return values[0]();
184 }
186 int i = n-1;
187 while (true) {
188 ++values[i];
189 if (values[i]() || (i == 0))
190 return;
191 values[i--].init(domains[i]);
192 }
193 }
194 virtual int operator[](int i) const {
195 return values[i].val();
196 }
197 };
198
200 class Examples : public Test {
201 protected:
203 public:
204 Examples(const std::string& name, int n, const Gecode::IntSet& domain,
205 const Gecode::IntSet* d, Gecode::IntPropLevel level)
206 : Test(TestTags::check(),"InterDistance::"+name+"::"+str(level),
207 n,domain,false,level) {
208 for (int i=0; i<n; i++)
209 domains[i] = d[i];
210 testsearch = false;
211 }
212 virtual Assignment* assignment(void) const {
213 return new ExampleAssignment(arity,domains);
214 }
215 virtual bool solution(const Assignment& x) const {
216 for (int i=0; i<x.size(); i++)
217 if (!domains[i].in(x[i]))
218 return false;
219 int p = x[x.size()-1];
220 for (int i=0; i<x.size()-1; i++)
221 for (int j=0; j<i; j++) {
222 long long int d = static_cast<long long int>(x[i])-x[j];
223 if ((-p < d) && (d < p))
224 return false;
225 }
226 return true;
227 }
228 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
229 for (int i=0; i<x.size(); i++)
230 Gecode::dom(home,x[i],domains[i]);
231 Gecode::IntVarArgs y(x.size()-1);
232 for (int i=0; i<y.size(); i++)
233 y[i] = x[i];
234 Gecode::inter_distance(home,y,x[x.size()-1],ipl);
235 }
236 };
237
239 class Posting : public Base {
240 static bool constant_contracts(void) {
241 using namespace Gecode;
242 IntSet domain(-2,2);
243 TestSpace s(0,domain,nullptr);
244 IntVar v(s,-2,2);
245 IntVarArgs duplicate(2);
246 duplicate[0] = duplicate[1] = v;
247 inter_distance(s,duplicate,0);
248 bool same = false;
249 bool negative = false;
250 bool tooLarge = false;
251 try {
252 inter_distance(s,duplicate,2);
253 } catch (const Gecode::Int::ArgumentSame&) {
254 same = true;
255 }
256 try {
258 } catch (const Gecode::Int::OutOfLimits&) {
259 negative = true;
260 }
261 try {
262 inter_distance(s,IntVarArgs(),std::numeric_limits<int>::max());
263 } catch (const Gecode::Int::OutOfLimits&) {
264 tooLarge = true;
265 }
266
269 singleton[0] = v;
271 if (!same || !negative || !tooLarge || (s.status() == SS_FAILED))
272 return false;
273
274 TestSpace t(0,domain,nullptr);
275 IntVar assigned(t,3,3);
276 duplicate[0] = duplicate[1] = assigned;
277 inter_distance(t,duplicate,2);
278 if (t.status() != SS_FAILED)
279 return false;
280 return true;
281 }
282
283 static bool variable_contracts(void) {
284 using namespace Gecode;
285 IntSet domain(-3,9);
286 TestSpace empty(0,domain,nullptr);
287 IntVar distance(empty,-3,9);
288 inter_distance(empty,IntVarArgs(),distance);
289 if ((empty.status() == SS_FAILED) || (distance.min() != 0))
290 return false;
291
292 TestSpace negativeDistance(0,domain,nullptr);
293 IntVar negativeVar(negativeDistance,-3,-1);
294 inter_distance(negativeDistance,IntVarArgs(),negativeVar);
295 if (negativeDistance.status() != SS_FAILED)
296 return false;
297
298 TestSpace shared(0,domain,nullptr);
299 IntVar a(shared,0,9);
300 IntVar b(shared,0,9);
301 IntVar p(shared,0,9);
302 IntVarArgs pair(2);
303 pair[0] = a;
304 pair[1] = b;
305 bool alias = false;
306 bool repeated = false;
307 try {
308 inter_distance(shared,pair,a);
309 } catch (const Gecode::Int::ArgumentSame&) {
310 alias = true;
311 }
312 pair[1] = a;
313 try {
314 inter_distance(shared,pair,p);
315 } catch (const Gecode::Int::ArgumentSame&) {
316 repeated = true;
317 }
318 if (!alias || !repeated)
319 return false;
320 return true;
321 }
322
323 public:
324 Posting(void) : Base("Int::InterDistance::Posting",TestTags::check()) {}
325 virtual bool run(void) {
326 if (!constant_contracts()) {
327 olog << "Constant posting contracts failed" << std::endl;
328 return false;
329 }
330 if (!variable_contracts()) {
331 olog << "Variable posting contracts failed" << std::endl;
332 return false;
333 }
334 return true;
335 }
336 };
337
338 class Create {
339 public:
340 Create(void) {
341 using namespace Gecode;
343 for (int n : {8,24})
344 for (int slack : {0,8})
345 for (bool variable : {false,true})
346 (void) new Random(n,3,slack,variable,level);
347 const IntSet paper[] = {IntSet(2,6),IntSet(10,14),
348 IntSet(4,15),IntSet(0,8)};
349 (void) new Examples("Paper",4,IntSet(0,15),paper,level);
350 const IntSet adjacent[] = {IntSet(1,17),IntSet(5,8),
351 IntSet(2,14),IntSet(0,8)};
352 (void) new Examples("Adjacent",4,IntSet(0,17),adjacent,level);
353 const IntSet holes[] = {IntSet({0,2,6,7}),IntSet({-3,2}),
354 IntSet({10,11,14}),IntSet({1,2,3,6}),IntSet({-1,0,3,5,9}),
355 IntSet(4,4)};
356 (void) new Examples("HoleJump",6,IntSet(-3,14),holes,level);
357 const IntSet residue[] = {IntSet(2,11),IntSet(-10,-2),
358 IntSet(16,17),IntSet(13,14)};
359 (void) new Examples("Residue",4,IntSet(-10,17),residue,level);
360 }
361 const int limit = Gecode::Int::Limits::max;
362 const IntSet extremes[] = {IntSet(-limit,-limit+1),IntSet(0,1),
363 IntSet(limit-1,limit),IntSet(limit-1,limit)};
364 (void) new Examples("Limits",4,
365 IntSet({-limit,-limit+1,0,1,limit-1,limit}),
366 extremes,IPL_BASIC);
367 (void) new Distance(3,limit,IntSet({-limit,-limit+1,0,1,
368 limit-1,limit}));
369 for (int n=1; n<=4; n++)
370 for (int p=0; p<=4; p++)
371 (void) new Distance(n,p,-3,3);
372 (void) new Distance(3,2,Gecode::IntSet({-3,-1,0,2,3}));
373 (void) new Distance(3,2,Gecode::Int::Limits::min,
375 (void) new Distance(3,2,Gecode::Int::Limits::max-5,
379 (void) new Variable(2,ipl);
380 (void) new Variable(3,ipl);
381 }
382 (void) new Variable(0,Gecode::IPL_DEF);
383 (void) new Variable(1,Gecode::IPL_DEF);
386 (void) new Distance(3,2,-3,3,ipl);
387 (void) new Distance(3,2,-3,3,static_cast<Gecode::IntPropLevel>(
389 }
392
393}}}
394
395// STATISTICS: test-int
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
Value iterator for integer sets.
Definition int.hh:352
Integer sets.
Definition int.hh:179
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Integer variables.
Definition int.hh:390
int min(void) const
Return minimum of domain.
Definition int.hpp:62
Exception: Arguments contain same variable multiply
Definition exception.hpp:80
Exception: Value out of limits
Definition exception.hpp:44
Computation spaces.
Definition core.hpp:1787
int size(void) const
Return size of array (number of elements).
Definition array.hpp:945
Gecode::Support::RandomGenerator _rand
Random number generator.
Definition test.hh:238
Base(std::string s)
Create and register a standard test with name s.
Definition test.cpp:125
const std::string & name(void) const
Return name of test.
Definition test.hpp:91
Base class for assignments
Definition int.hh:73
Gecode::IntSet d
Domain for each variable.
Definition int.hh:76
int n
Number of variables.
Definition int.hh:75
Assignment(int n0, const Gecode::IntSet &d0)
Initialize assignments for n0 variables and values d0.
Definition int.hpp:43
int size(void) const
Return number of variables.
Definition int.hpp:46
Mix arbitrary assignments with sorted, separated values and shuffle them.
DistanceAssignment(int n, const Gecode::IntSet &d, int p0, bool v, Gecode::Support::RandomGenerator &rand)
virtual void next(Gecode::Support::RandomGenerator &rand)
Move to next assignment.
Exercise assignment, cloning, search, and bounds(Z) consistency.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
Distance(int n, int p0, int min, int max, Gecode::IntPropLevel ipl0=Gecode::IPL_DEF)
virtual bool solution(const Assignment &x) const
Check for solution.
Distance(int n, int p0, const Gecode::IntSet &domain)
Enumerate assignments within each example's individual variable domains.
ExampleAssignment(int n, const Gecode::IntSet *d)
virtual void next(Gecode::Support::RandomGenerator &)
Move to next assignment.
virtual bool has_more(void) const
Test whether all assignments have been iterated.
virtual int operator[](int i) const
Return value for variable i.
Hole-jump and residue examples use the same assignment checks.
Examples(const std::string &name, int n, const Gecode::IntSet &domain, const Gecode::IntSet *d, Gecode::IntPropLevel level)
virtual Assignment * assignment(void) const
Create the assignment generator (complete by default).
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
virtual bool solution(const Assignment &x) const
Check for solution.
Posting contracts, vacuous constraints, and shared variables.
virtual bool run(void)
Run test.
Larger instances with a bounded total slack.
Random(int n, int p0, int slack, bool v, Gecode::IntPropLevel level)
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
virtual bool solution(const Assignment &x) const
Check for solution.
virtual Assignment * assignment(void) const
Create the assignment generator (complete by default).
Variable distance, including propagation after distance assignments.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
Variable(int n, Gecode::IntPropLevel ipl0)
virtual bool solution(const Assignment &x) const
Check for solution.
int a
How many assignments still to be generated Generate new value according to domain.
Definition int.hh:113
int * vals
The current values for the variables.
Definition int.hh:112
RandomAssignment(int n, const Gecode::IntSet &d, int a0, Gecode::Support::RandomGenerator &rand)
Initialize for a assignments for n0 variables and values d0.
Definition int.hpp:88
virtual void next(Gecode::Support::RandomGenerator &rand)
Move to next assignment.
Definition int.cpp:63
Space for executing tests.
Definition int.hh:163
bool testsearch
Whether to perform search test.
Definition int.hh:285
static std::string str(bool b)
Map bool to string.
Definition int.hpp:278
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:281
int arity
Number of variables.
Definition int.hh:273
Gecode::IntSet dom
Domain of variables.
Definition int.hh:275
ConTestLevel contest
Whether to test for certain consistency.
Definition int.hh:283
Set of test tags.
Definition test.hh:105
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
Definition random.hpp:183
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IPL_BASIC
Use basic propagation algorithm.
Definition int.hh:1281
@ IPL_BASIC_ADVANCED
Use both.
Definition int.hh:1283
@ IPL_ADVANCED
Use advanced propagation algorithm.
Definition int.hh:1282
@ IPL_DEF
Simple propagation levels.
Definition int.hh:1276
@ IPL_BND
Bounds propagation.
Definition int.hh:1278
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ SS_FAILED
Space is failed
Definition core.hpp:1727
const int min
Smallest allowed integer value.
Definition int.hh:123
const int max
Largest allowed integer value.
Definition int.hh:121
Gecode toplevel namespace
IntPropLevel ba(IntPropLevel ipl)
Extract basic or advanced from propagation level.
Definition ipl.hpp:43
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition dom.cpp:40
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1936
void inter_distance(Home home, const IntVarArgs &x, int p, IntPropLevel ipl=IPL_DEF)
Post bounds-consistent propagator for for all .
SetExpr singleton(const LinIntExpr &)
Singleton expression.
Definition set-expr.cpp:691
bool shared(ViewArray< ViewX > x, ViewArray< ViewY > y)
Definition array.hpp:1464
class Test::Int::InterDistance::Create create
Testing finite domain integers.
Definition int.cpp:41
@ CTL_BOUNDS_Z
Test for bounds(z)-consistency.
Definition int.hh:157
@ CTL_NONE
No consistency-test.
Definition int.hh:154
General test support.
Definition afc.cpp:41
std::ostringstream olog
Stream used for logging.
Definition test.cpp:54
@ check
Basic integrity tests.
Definition test.hh:99
@ standard
Standard test suite.
Definition test.hh:100