1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Patrick Pekczynski <pekczynski@ps.uni-sb.de> 5 * 6 * Contributing authors: 7 * Christian Schulte <schulte@gecode.org> 8 * 9 * Copyright: 10 * Patrick Pekczynski, 2005 11 * Christian Schulte, 2007 12 * 13 * This file is part of Gecode, the generic constraint 14 * development environment: 15 * http://www.gecode.org 16 * 17 * Permission is hereby granted, free of charge, to any person obtaining 18 * a copy of this software and associated documentation files (the 19 * "Software"), to deal in the Software without restriction, including 20 * without limitation the rights to use, copy, modify, merge, publish, 21 * distribute, sublicense, and/or sell copies of the Software, and to 22 * permit persons to whom the Software is furnished to do so, subject to 23 * the following conditions: 24 * 25 * The above copyright notice and this permission notice shall be 26 * included in all copies or substantial portions of the Software. 27 * 28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 35 * 36 */ 37 38 #include "test/int.hh" 39 40 namespace Test { namespace Int { 41 42 /// %Tests for counting constraints (global cardinality) 43 namespace GCC { 44 45 /** 46 * \defgroup TaskTestIntGCC Counting constraints (global cardinality) 47 * \ingroup TaskTestInt 48 */ 49 //@{ 50 /// %Test for integer cardinality with min and max for all variables 51 class IntAllMinMax : public Test { 52 public: 53 /// Create and register test IntAllMinMax(Gecode::IntPropLevel ipl)54 IntAllMinMax(Gecode::IntPropLevel ipl) 55 : Test("GCC::Int::All::MinMax::"+str(ipl),4,-1,3,false,ipl) {} 56 /// %Test whether \a x is solution solution(const Assignment & x) const57 virtual bool solution(const Assignment& x) const { 58 int n[5]; 59 for (int i=5; i--; ) 60 n[i]=0; 61 for (int i=x.size(); i--; ) 62 n[x[i]+1]++; 63 if (n[2] > 0) 64 return false; 65 for (int i=5; i--;) 66 if (n[i]>2) 67 return false; 68 return true; 69 } 70 /// Post constraint on \a x post(Gecode::Space & home,Gecode::IntVarArray & x)71 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 72 using namespace Gecode; 73 IntArgs values(5); 74 IntSet fixed(0,2); 75 IntSetArgs cards(5); 76 for (int i=0; i<5; i++) { 77 values[i] = i-1; cards[i] = fixed; 78 } 79 cards[2] = IntSet(0,0); 80 count(home, x, cards, values, ipl); 81 } 82 }; 83 84 /// %Test for integer cardinality with min and max for all variables 85 class IntAllMinMaxDef : public Test { 86 public: 87 /// Create and register test IntAllMinMaxDef(Gecode::IntPropLevel ipl)88 IntAllMinMaxDef(Gecode::IntPropLevel ipl) 89 : Test("GCC::Int::All::MinMaxDef::"+str(ipl),4,0,3,false,ipl) {} 90 /// %Test whether \a x is solution solution(const Assignment & x) const91 virtual bool solution(const Assignment& x) const { 92 int n[4]; 93 for (int i=4; i--; ) 94 n[i]=0; 95 for (int i=x.size(); i--; ) 96 n[x[i]]++; 97 if (n[2] > 0) 98 return false; 99 for (int i=4; i--;) 100 if (n[i]>2) 101 return false; 102 return true; 103 } 104 /// Post constraint on \a x post(Gecode::Space & home,Gecode::IntVarArray & x)105 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 106 using namespace Gecode; 107 IntSet fixed(0,2); 108 IntSetArgs cards(4); 109 for (int i=0; i<4; i++) { 110 cards[i] = fixed; 111 } 112 cards[2] = IntSet(0,0); 113 count(home, x, cards, ipl); 114 } 115 }; 116 117 /// %Test for integer cardinality with max cardinality for all variables 118 class IntAllMax : public Test { 119 public: 120 /// Create and register test IntAllMax(Gecode::IntPropLevel ipl)121 IntAllMax(Gecode::IntPropLevel ipl) 122 : Test("GCC::Int::All::Max::"+str(ipl), 4, 1,2, false, ipl) {} 123 /// %Test whether \a x is solution solution(const Assignment & x) const124 virtual bool solution(const Assignment& x) const { 125 int n[2]; 126 for (int i=2; i--; ) 127 n[i] = 0; 128 for (int i=x.size(); i--; ) 129 n[x[i] - 1]++; 130 if (n[0] != 2 || n[1] != 2) 131 return false; 132 return true; 133 } 134 /// Post constraint on \a x post(Gecode::Space & home,Gecode::IntVarArray & x)135 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 136 Gecode::IntArgs values({1,2}); 137 Gecode::count(home, x, Gecode::IntSet(2,2), values, ipl); 138 } 139 }; 140 141 142 /// %Test for integer cardinality for some variables 143 template<bool hole> 144 class IntSome : public Test { 145 public: 146 /// Create and register test IntSome(Gecode::IntPropLevel ipl)147 IntSome(Gecode::IntPropLevel ipl) 148 : Test(std::string("GCC::Int::Some::")+ 149 (hole ? "::Hole" : "::Full")+str(ipl),4,1,4,false,ipl) {} 150 /// %Test whether \a x is solution solution(const Assignment & x) const151 virtual bool solution(const Assignment& x) const { 152 int n[4]; 153 for (int i=4; i--; ) 154 n[i]=0; 155 for (int i=x.size(); i--; ) 156 n[x[i]-1]++; 157 if ((n[0] < 2) || (n[1] < 2) || (n[2] > 0) || (n[3] > 0)) 158 return false; 159 return true; 160 } 161 /// Post constraint on \a x post(Gecode::Space & home,Gecode::IntVarArray & x)162 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 163 using namespace Gecode; 164 IntArgs values({1,2}); 165 Gecode::IntSet fixed; 166 if (!hole) { 167 fixed = IntSet(0,2); 168 } else { 169 int ish[] = {0,2}; 170 fixed = IntSet(ish,2); 171 } 172 Gecode::IntSetArgs cards(2); 173 cards[0]=fixed; cards[1]=fixed; 174 count(home, x, cards, values, ipl); 175 } 176 }; 177 178 /// %Test for variable cardinality for all cardinality values 179 class VarAll : public Test { 180 protected: 181 /// Number of non-cardinality variables 182 static const int n = 4; 183 public: 184 /// Create and register test VarAll(Gecode::IntPropLevel ipl)185 VarAll(Gecode::IntPropLevel ipl) 186 : Test("GCC::Var::All::"+str(ipl),7,0,2,false,ipl) {} 187 /// %Test whether \a x is solution solution(const Assignment & x) const188 virtual bool solution(const Assignment& x) const { 189 // Number of cardinality variables 190 int m = x.size()-n; 191 for (int i=0; i<n; i++) 192 if ((x[i] < 0) || (x[i] > 2)) 193 return false; 194 int* card = new int[m]; 195 for (int i=0; i<m; i++) { 196 card[i] = 0; 197 if ((x[n+i] < 0) || (x[n+i] > 2)) { 198 delete [] card; 199 return false; 200 } 201 } 202 for (int i=0; i<n; i++) 203 card[x[i]]++; 204 for (int i=0; i<m; i++) 205 if (card[i] != x[n+i]) { 206 delete [] card; 207 return false; 208 } 209 delete [] card; 210 return true; 211 } 212 /// Post constraint on \a xy post(Gecode::Space & home,Gecode::IntVarArray & xy)213 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) { 214 using namespace Gecode; 215 // Number of cardinality variables 216 int m = xy.size()-n; 217 218 IntVarArgs x(n), y(m); 219 for (int i=0; i<n; i++) 220 x[i]=xy[i]; 221 for (int i=0; i<m; i++) 222 y[i]=xy[n+i]; 223 count(home, x, y, ipl); 224 } 225 }; 226 227 /// %Test for variable cardinality for some cardinality values 228 class VarSome : public Test { 229 protected: 230 /// Number of non-cardinality variables 231 int n; 232 /// Arity beyond which to use randomized tests 233 static const int randomArity = 7; 234 public: 235 /// Create and register test VarSome(std::string s,int n0,int min,int max,Gecode::IntPropLevel ipl)236 VarSome(std::string s, int n0, int min, int max, 237 Gecode::IntPropLevel ipl) 238 : Test("GCC::Var::Some::"+s+"::"+str(ipl), 239 n0+(max-min)+1,min,max,false,ipl) 240 , n(n0) 241 { 242 contest = CTL_NONE; 243 if (arity>randomArity) 244 testsearch = false; 245 } 246 /// %Test whether \a x is solution solution(const Assignment & x) const247 virtual bool solution(const Assignment& x) const { 248 // Number of cardinality variables 249 int m = x.size()-n; 250 int* card = new int[m]; 251 for (int i=0; i<m; i++) { 252 card[i] = 0; 253 if ((x[n+i] < 0) || (x[n+i] > n)) { 254 delete [] card; 255 return false; 256 } 257 } 258 for (int i=0; i<n; i++) 259 card[x[i]-dom.min()]++; 260 for (int i=0; i<m; i++) 261 if (card[i] != x[n+i]) { 262 delete [] card; 263 return false; 264 } 265 delete [] card; 266 return true; 267 } 268 /// Create and register initial assignment assignment(void) const269 virtual Assignment* assignment(void) const { 270 if (arity > randomArity) 271 return new RandomAssignment(arity, dom, 4000, _rand); 272 else 273 return new CpltAssignment(arity,dom); 274 } 275 /// Post constraint on \a xy post(Gecode::Space & home,Gecode::IntVarArray & xy)276 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) { 277 using namespace Gecode; 278 // Number of cardinality variables 279 int m = xy.size()-n; 280 IntVarArgs x(n), y(m); 281 for (int i=0; i<n; i++) 282 x[i]=xy[i]; 283 for (int i=0; i<m; i++) 284 y[i]=xy[n+i]; 285 IntArgs values(m); 286 for (int i=m; i--;) 287 values[i] = i+dom.min(); 288 count(home,x,y,values,ipl); 289 } 290 }; 291 292 /// Help class to create and register tests 293 class Create { 294 public: 295 /// Perform creation and registration Create(void)296 Create(void) { 297 for (IntPropLevels ipls; ipls(); ++ipls) { 298 (void) new IntAllMinMax(ipls.ipl()); 299 (void) new IntAllMinMaxDef(ipls.ipl()); 300 (void) new IntAllMax(ipls.ipl()); 301 (void) new IntSome<false>(ipls.ipl()); 302 (void) new IntSome<true>(ipls.ipl()); 303 (void) new VarAll(ipls.ipl()); 304 (void) new VarSome("Small",2,-1,3,ipls.ipl()); 305 (void) new VarSome("Large",3,-1,4,ipls.ipl()); 306 } 307 } 308 }; 309 310 Create c; 311 //@} 312 313 } 314 }} 315 316 // STATISTICS: test-int 317