gcc.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Patrick Pekczynski <pekczynski@ps.uni-sb.de> 00005 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * 00009 * Copyright: 00010 * Patrick Pekczynski, 2005 00011 * Christian Schulte, 2007 00012 * 00013 * Last modified: 00014 * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $ 00015 * $Revision: 10684 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00039 * 00040 */ 00041 00042 #include "test/int.hh" 00043 00044 namespace Test { namespace Int { 00045 00047 namespace GCC { 00048 00054 00055 class IntAllMinMax : public Test { 00056 public: 00058 IntAllMinMax(Gecode::IntConLevel icl) 00059 : Test("GCC::Int::All::MinMax::"+str(icl),4,-1,3,false,icl) {} 00061 virtual bool solution(const Assignment& x) const { 00062 int n[5]; 00063 for (int i=5; i--; ) 00064 n[i]=0; 00065 for (int i=x.size(); i--; ) 00066 n[x[i]+1]++; 00067 if (n[2] > 0) 00068 return false; 00069 for (int i=5; i--;) 00070 if (n[i]>2) 00071 return false; 00072 return true; 00073 } 00075 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00076 using namespace Gecode; 00077 IntArgs values(5); 00078 IntSet fixed(0,2); 00079 IntSetArgs cards(5); 00080 for (int i=0; i<5; i++) { 00081 values[i] = i-1; cards[i] = fixed; 00082 } 00083 cards[2] = IntSet(0,0); 00084 count(home, x, cards, values, icl); 00085 } 00086 }; 00087 00089 class IntAllMinMaxDef : public Test { 00090 public: 00092 IntAllMinMaxDef(Gecode::IntConLevel icl) 00093 : Test("GCC::Int::All::MinMaxDef::"+str(icl),4,0,3,false,icl) {} 00095 virtual bool solution(const Assignment& x) const { 00096 int n[4]; 00097 for (int i=4; i--; ) 00098 n[i]=0; 00099 for (int i=x.size(); i--; ) 00100 n[x[i]]++; 00101 if (n[2] > 0) 00102 return false; 00103 for (int i=4; i--;) 00104 if (n[i]>2) 00105 return false; 00106 return true; 00107 } 00109 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00110 using namespace Gecode; 00111 IntSet fixed(0,2); 00112 IntSetArgs cards(4); 00113 for (int i=0; i<4; i++) { 00114 cards[i] = fixed; 00115 } 00116 cards[2] = IntSet(0,0); 00117 count(home, x, cards, icl); 00118 } 00119 }; 00120 00122 class IntAllMax : public Test { 00123 public: 00125 IntAllMax(Gecode::IntConLevel icl) 00126 : Test("GCC::Int::All::Max::"+str(icl), 4, 1,2, false, icl) {} 00128 virtual bool solution(const Assignment& x) const { 00129 int n[2]; 00130 for (int i=2; i--; ) 00131 n[i] = 0; 00132 for (int i=x.size(); i--; ) 00133 n[x[i] - 1]++; 00134 if (n[0] != 2 || n[1] != 2) 00135 return false; 00136 return true; 00137 } 00139 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00140 Gecode::IntArgs values(2, 1,2); 00141 Gecode::count(home, x, Gecode::IntSet(2,2), values, icl); 00142 } 00143 }; 00144 00145 00147 template<bool hole> 00148 class IntSome : public Test { 00149 public: 00151 IntSome(Gecode::IntConLevel icl) 00152 : Test(std::string("GCC::Int::Some::")+ 00153 (hole ? "::Hole" : "::Full")+str(icl),4,1,4,false,icl) {} 00155 virtual bool solution(const Assignment& x) const { 00156 int n[4]; 00157 for (int i=4; i--; ) 00158 n[i]=0; 00159 for (int i=x.size(); i--; ) 00160 n[x[i]-1]++; 00161 if ((n[0] < 2) || (n[1] < 2) || (n[2] > 0) || (n[3] > 0)) 00162 return false; 00163 return true; 00164 } 00166 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00167 using namespace Gecode; 00168 IntArgs values(2, 1,2); 00169 Gecode::IntSet fixed; 00170 if (!hole) { 00171 fixed = IntSet(0,2); 00172 } else { 00173 int ish[] = {0,2}; 00174 fixed = IntSet(ish,2); 00175 } 00176 Gecode::IntSetArgs cards(2); 00177 cards[0]=fixed; cards[1]=fixed; 00178 count(home, x, cards, values, icl); 00179 } 00180 }; 00181 00183 class VarAll : public Test { 00184 protected: 00186 static const int n = 4; 00187 public: 00189 VarAll(Gecode::IntConLevel icl) 00190 : Test("GCC::Var::All::"+str(icl),7,0,2,false,icl) {} 00192 virtual bool solution(const Assignment& x) const { 00193 // Number of cardinality variables 00194 int m = x.size()-n; 00195 for (int i=0; i<n; i++) 00196 if ((x[i] < 0) || (x[i] > 2)) 00197 return false; 00198 int* card = new int[m]; 00199 for (int i=0; i<m; i++) { 00200 card[i] = 0; 00201 if ((x[n+i] < 0) || (x[n+i] > 2)) { 00202 delete [] card; 00203 return false; 00204 } 00205 } 00206 for (int i=0; i<n; i++) 00207 card[x[i]]++; 00208 for (int i=0; i<m; i++) 00209 if (card[i] != x[n+i]) { 00210 delete [] card; 00211 return false; 00212 } 00213 delete [] card; 00214 return true; 00215 } 00217 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) { 00218 using namespace Gecode; 00219 // Number of cardinality variables 00220 int m = xy.size()-n; 00221 00222 IntVarArgs x(n), y(m); 00223 for (int i=0; i<n; i++) 00224 x[i]=xy[i]; 00225 for (int i=0; i<m; i++) 00226 y[i]=xy[n+i]; 00227 count(home, x, y, icl); 00228 } 00229 }; 00230 00232 class VarSome : public Test { 00233 protected: 00235 int n; 00237 static const int randomArity = 7; 00238 public: 00240 VarSome(std::string s, int n0, int min, int max, 00241 Gecode::IntConLevel icl) 00242 : Test("GCC::Var::Some::"+s+"::"+str(icl), 00243 n0+(max-min)+1,min,max,false,icl) 00244 , n(n0) 00245 { 00246 contest = CTL_NONE; 00247 if (arity>randomArity) 00248 testsearch = false; 00249 } 00251 virtual bool solution(const Assignment& x) const { 00252 // Number of cardinality variables 00253 int m = x.size()-n; 00254 int* card = new int[m]; 00255 for (int i=0; i<m; i++) { 00256 card[i] = 0; 00257 if ((x[n+i] < 0) || (x[n+i] > n)) { 00258 delete [] card; 00259 return false; 00260 } 00261 } 00262 for (int i=0; i<n; i++) 00263 card[x[i]-dom.min()]++; 00264 for (int i=0; i<m; i++) 00265 if (card[i] != x[n+i]) { 00266 delete [] card; 00267 return false; 00268 } 00269 delete [] card; 00270 return true; 00271 } 00273 virtual Assignment* assignment(void) const { 00274 if (arity > randomArity) 00275 return new RandomAssignment(arity,dom,4000); 00276 else 00277 return new CpltAssignment(arity,dom); 00278 } 00280 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) { 00281 using namespace Gecode; 00282 // Number of cardinality variables 00283 int m = xy.size()-n; 00284 IntVarArgs x(n), y(m); 00285 for (int i=0; i<n; i++) 00286 x[i]=xy[i]; 00287 for (int i=0; i<m; i++) 00288 y[i]=xy[n+i]; 00289 IntArgs values(m); 00290 for (int i=m; i--;) 00291 values[i] = i+dom.min(); 00292 count(home,x,y,values,icl); 00293 } 00294 }; 00295 00297 class Create { 00298 public: 00300 Create(void) { 00301 for (IntConLevels icls; icls(); ++icls) { 00302 (void) new IntAllMinMax(icls.icl()); 00303 (void) new IntAllMinMaxDef(icls.icl()); 00304 (void) new IntAllMax(icls.icl()); 00305 (void) new IntSome<false>(icls.icl()); 00306 (void) new IntSome<true>(icls.icl()); 00307 (void) new VarAll(icls.icl()); 00308 (void) new VarSome("Small",2,-1,3,icls.icl()); 00309 (void) new VarSome("Large",3,-1,4,icls.icl()); 00310 } 00311 } 00312 }; 00313 00314 Create c; 00316 00317 } 00318 }} 00319 00320 // STATISTICS: test-int