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 * Mikael Lagerkvist <lagerkvist@gecode.org>
6 *
7 * Copyright:
8 * Christian Schulte, 2005
9 * Mikael Lagerkvist, 2006
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#ifndef GECODE_TEST_INT_HH
37#define GECODE_TEST_INT_HH
38
39#include "test/test.hh"
40
41#include <gecode/int.hh>
42
43namespace Test {
44
45 /// Testing finite domain integers
46 namespace Int {
47
48 /**
49 * \defgroup TaskTestInt Testing finite domain integers
50 * \ingroup TaskTest
51 */
52
53 /**
54 * \defgroup TaskTestIntInt General test support
55 * \ingroup TaskTestInt
56 */
57 //@{
58 /// %Base class for assignments
59 class Assignment {
60 protected:
61 int n; ///< Number of variables
62 Gecode::IntSet d; ///< Domain for each variable
63 public:
64 /// Initialize assignments for \a n0 variables and values \a d0
65 Assignment(int n0, const Gecode::IntSet& d0);
66 /// Test whether all assignments have been iterated
67 virtual bool has_more(void) const = 0;
68 /// Move to next assignment
69 virtual void next(Gecode::Support::RandomGenerator& rand) = 0;
70 /// Return value for variable \a i
71 virtual int operator[](int i) const = 0;
72 /// Return number of variables
73 int size(void) const;
74 /// Destructor
75 virtual ~Assignment(void);
76 };
77
78 /// Generate all assignments
79 class CpltAssignment : public Assignment {
80 protected:
81 Gecode::IntSetValues* dsv; ///< Iterator for each variable
82 public:
83 /// Initialize assignments for \a n0 variables and values \a d0
84 CpltAssignment(int n, const Gecode::IntSet& d);
85 /// Test whether all assignments have been iterated
86 virtual bool has_more(void) const;
87 /// Move to next assignment
88 virtual void next(Gecode::Support::RandomGenerator& rand);
89 /// Return value for variable \a i
90 virtual int operator[](int i) const;
91 /// Destructor
92 virtual ~CpltAssignment(void);
93 };
94
95 /// Generate random selection of assignments
96 class RandomAssignment : public Assignment {
97 protected:
98 int* vals; ///< The current values for the variables
99 int a; ///< How many assigments still to be generated
100 /// Generate new value according to domain
101 int randval(Gecode::Support::RandomGenerator& rand);
102 public:
103 /// Initialize for \a a assignments for \a n0 variables and values \a d0
104 RandomAssignment(int n, const Gecode::IntSet& d, int a0, Gecode::Support::RandomGenerator& rand);
105 /// Test whether all assignments have been iterated
106 virtual bool has_more(void) const;
107 /// Move to next assignment
108 virtual void next(Gecode::Support::RandomGenerator& rand);
109 /// Return value for variable \a i
110 virtual int operator[](int i) const;
111 /// Destructor
112 virtual ~RandomAssignment(void);
113 };
114
115 /// Generate random selection of assignments
116 class RandomMixAssignment : public Assignment {
117 protected:
118 int* vals; ///< The current values for the variables
119 int a; ///< How many assigments still to be generated
120 int _n1; ///< How many variables in the second set
121 Gecode::IntSet _d1; ///< Domain for second set of variables
122 /// Generate new value according to domain \a d
123 int randval(const Gecode::IntSet& d, Gecode::Support::RandomGenerator& rand);
124 public:
125 /// Initialize for \a a assignments for \a n0 variables and values \a d0
126 RandomMixAssignment(int n0, const Gecode::IntSet& d0, int n1, const Gecode::IntSet& d1, int a0,
127 Gecode::Support::RandomGenerator& rand);
128 /// Test whether all assignments have been iterated
129 virtual bool has_more(void) const;
130 /// Move to next assignment
131 virtual void next(Gecode::Support::RandomGenerator& rand);
132 /// Return value for variable \a i
133 virtual int operator[](int i) const;
134 /// Destructor
135 virtual ~RandomMixAssignment(void);
136 };
137
138 /// Level of consistency to test for
139 enum ConTestLevel {
140 CTL_NONE, ///< No consistency-test
141 CTL_DOMAIN, ///< Test for domain-consistency
142 CTL_BOUNDS_D, ///< Test for bounds(d)-consistency
143 CTL_BOUNDS_Z, ///< Test for bounds(z)-consistency
144 };
145
146 class Test;
147
148 /// Space for executing tests
149 class TestSpace : public Gecode::Space {
150 public:
151 /// Initial domain
152 Gecode::IntSet d;
153 /// Variables to be tested
154 Gecode::IntVarArray x;
155 /// Reification information
156 Gecode::Reify r;
157 /// The test currently run
158 Test* test;
159 /// Whether the test is for a reified propagator
160 bool reified;
161
162 /**
163 * \brief Create test space without reification
164 *
165 * Creates \a n variables with domain \a d for test \a t.
166 *
167 */
168 TestSpace(int n, Gecode::IntSet& d, Test* t);
169 /**
170 * \brief Create test space with reification
171 *
172 * Creates \a n variables with domain \a d for test \a t and stores
173 * the reification mode \a rm.
174 *
175 */
176 TestSpace(int n, Gecode::IntSet& d, Test* t, Gecode::ReifyMode rm);
177 /// Constructor for cloning \a s
178 TestSpace(TestSpace& s);
179 /// Copy space during cloning
180 virtual Gecode::Space* copy(void);
181 /// Test whether all variables are assigned
182 bool assigned(void) const;
183 /// Post propagator
184 void post(void);
185 /// Compute a fixpoint and check for failure
186 bool failed(void);
187 /// Randomly select an unassigned variable
188 int rndvar(Gecode::Support::RandomGenerator& rand);
189 /// Randomly select a pruning rel for variable \a i
190 void rndrel(const Assignment& a, int i, Gecode::IntRelType& irt, int& v, Gecode::Support::RandomGenerator& rand);
191 /// Perform integer tell operation on \a x[i]
192 void rel(int i, Gecode::IntRelType irt, int n);
193 /// Perform Boolean tell on \a b
194 void rel(bool sol);
195 /// Assign all (or all but one, if \a skip is true) variables to values in \a a
196 void assign(const Assignment& a, bool skip, Gecode::Support::RandomGenerator& rand);
197 /// Assing a random variable to a random bound
198 void bound(Gecode::Support::RandomGenerator& rand);
199 /** \brief Prune some random values from variable \a i
200 *
201 * If \a bounds_only is true, then the pruning is only done on the
202 * bounds of the variable.
203 */
204 void prune(int i, bool bounds_only, Gecode::Support::RandomGenerator& rand);
205 /// Prune some random values for some random variable
206 void prune(Gecode::Support::RandomGenerator& rand);
207 /// Prune values but not those in assignment \a a
208 bool prune(const Assignment& a, bool testfix, Gecode::Support::RandomGenerator& rand);
209 /// Disable propagators in space and compute fixpoint (make all idle)
210 void disable(void);
211 /// Enable propagators in space
212 void enable(void);
213 /// Prune values also in a space \a c with disabled propagators, but not those in assignment \a a
214 bool disabled(const Assignment& a, TestSpace& c, bool testfix, Gecode::Support::RandomGenerator& rand);
215 /// Return the number of propagators
216 unsigned int propagators(void);
217 };
218
219 /**
220 * \brief %Base class for tests with integer constraints
221 *
222 */
223 class Test : public Base {
224 protected:
225 /// Number of variables
226 int arity;
227 /// Domain of variables
228 Gecode::IntSet dom;
229 /// Does the constraint also exist as reified constraint
230 bool reified;
231 /// Which reification modes are supported
232 int rms;
233 /// Propagation level
234 Gecode::IntPropLevel ipl;
235 /// Whether to test for certain consistency
236 ConTestLevel contest;
237 /// Whether to perform search test
238 bool testsearch;
239 /// Whether to perform fixpoint test
240 bool testfix;
241 /// \name Test for reification modes
242 //@{
243 /// Test whether equivalence as reification mode is supported
244 bool eqv(void) const;
245 /// Test whether implication as reification mode is supported
246 bool imp(void) const;
247 /// Test whether reverse implication as reification mode is supported
248 bool pmi(void) const;
249 //@}
250 public:
251 /**
252 * \brief Constructor
253 *
254 * Constructs a test with prefix \a p, name \a s, arity \a a,
255 * and variable domain \a d. Also tests for a reified
256 * constraint, if \a r is true. The propagation level is
257 * maintained for convenience.
258 */
259 Test(const std::string& p, const std::string& s,
260 int a, const Gecode::IntSet& d, bool r=false,
261 Gecode::IntPropLevel i=Gecode::IPL_DEF);
262 /**
263 * \brief Constructor
264 *
265 * Constructs a test with name \a s, arity \a a, and variable
266 * domain \a d. Also tests for a reified constraint,
267 * if \a r is true. The propagation level is
268 * maintained for convenience.
269 */
270 Test(const std::string& s,
271 int a, const Gecode::IntSet& d, bool r=false,
272 Gecode::IntPropLevel i=Gecode::IPL_DEF);
273 /**
274 * \brief Constructor
275 *
276 * Constructs a test with prefix \a p, name \a s, arity \a a,
277 * and variable domain \a min ... \a max. Also tests for
278 * a reified constraint, if \a r is true. The propagation
279 * level is maintained for convenience.
280 */
281 Test(const std::string& p, const std::string& s,
282 int a, int min, int max, bool r=false,
283 Gecode::IntPropLevel i=Gecode::IPL_DEF);
284 /**
285 * \brief Constructor
286 *
287 * Constructs a test with name \a s, arity \a a, variable
288 * domain \a min ... \a max. Also tests for a reified constraint,
289 * if \a r is true. The propagation level is
290 * maintained for convenience.
291 */
292 Test(const std::string& s,
293 int a, int min, int max, bool r=false,
294 Gecode::IntPropLevel i=Gecode::IPL_DEF);
295 /// Create assignment
296 virtual Assignment* assignment(void) const;
297 /// Check for solution
298 virtual bool solution(const Assignment&) const = 0;
299 /// Whether to ignore assignment for reification
300 virtual bool ignore(const Assignment&) const;
301 /// Post constraint
302 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) = 0;
303 /// Post reified constraint
304 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
305 Gecode::Reify r);
306 /// Perform test
307 virtual bool run(void);
308 /// \name Mapping scalar values to strings
309 //@{
310 /// Map bool to string
311 static std::string str(bool b);
312 /// Map integer to string
313 static std::string str(int i);
314 /// Map integer array to string
315 static std::string str(const Gecode::IntArgs& i);
316 /// Map integer propagation level to string
317 static std::string str(Gecode::IntPropLevel ipl);
318 /// Map integer relation to string
319 static std::string str(Gecode::IntRelType irl);
320 /// Map Boolean operation to string
321 static std::string str(Gecode::BoolOpType bot);
322 //@}
323 /// \name General support
324 //@{
325 /// Compare \a x and \a y with respect to \a r
326 template<class T> static bool cmp(T x, Gecode::IntRelType r, T y);
327 //@}
328 };
329 //@}
330
331 /// Iterator for simple integer propagation levels
332 class IntPropLevels {
333 private:
334 /// Array of propagation levels
335 static const Gecode::IntPropLevel ipls[3];
336 /// Current position in level array
337 int i;
338 public:
339 /// Initialize iterator
340 IntPropLevels(void);
341 /// Test whether iterator is done
342 bool operator()(void) const;
343 /// Increment to next level
344 void operator++(void);
345 /// Return current level
346 Gecode::IntPropLevel ipl(void) const;
347 };
348
349 /// Iterator for basic and advanced integer propagation levels
350 class IntPropBasicAdvanced {
351 private:
352 /// Array of propagation levels
353 static const Gecode::IntPropLevel ipls[3];
354 /// Current position in level array
355 int i;
356 public:
357 /// Initialize iterator
358 IntPropBasicAdvanced(void);
359 /// Test whether iterator is done
360 bool operator()(void) const;
361 /// Increment to next level
362 void operator++(void);
363 /// Return current level
364 Gecode::IntPropLevel ipl(void) const;
365 };
366
367 /// Iterator for integer relation types
368 class IntRelTypes {
369 private:
370 /// Array of relation types
371 static const Gecode::IntRelType irts[6];
372 /// Current position in relation type array
373 int i;
374 public:
375 /// Initialize iterator
376 IntRelTypes(void);
377 /// Reset iterator
378 void reset(void);
379 /// Test whether iterator is done
380 bool operator()(void) const;
381 /// Increment to next relation type
382 void operator++(void);
383 /// Return current relation type
384 Gecode::IntRelType irt(void) const;
385 };
386
387 /// Iterator for Boolean operation types
388 class BoolOpTypes {
389 private:
390 /// Array of operation types
391 static const Gecode::BoolOpType bots[5];
392 /// Current position in operation type array
393 int i;
394 public:
395 /// Initialize iterator
396 BoolOpTypes(void);
397 /// Test whether iterator is done
398 bool operator()(void) const;
399 /// Increment to next operation type
400 void operator++(void);
401 /// Return current operation type
402 Gecode::BoolOpType bot(void) const;
403 };
404
405 }
406}
407
408/**
409 * \brief Print assignment \a
410 * \relates Assignment
411 */
412std::ostream& operator<<(std::ostream& os, const Test::Int::Assignment& a);
413
414#include "test/int.hpp"
415
416#endif
417
418// STATISTICS: test-int
419