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