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 
43 namespace 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  */
412 std::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 
420