int.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * 00006 * Copyright: 00007 * Guido Tack, 2005 00008 * 00009 * Last modified: 00010 * $Date: 2010-05-08 12:56:03 +0200 (Sat, 08 May 2010) $ by $Author: tack $ 00011 * $Revision: 10906 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include "test/set.hh" 00039 #include "test/int.hh" 00040 #include <gecode/minimodel.hh> 00041 00042 using namespace Gecode; 00043 00044 namespace Test { namespace Set { 00045 00047 namespace Int { 00048 00054 00055 static const int d1r[4][2] = { 00056 {-4,-3},{-1,-1},{1,1},{3,5} 00057 }; 00058 static IntSet d1(d1r,4); 00059 00060 static IntSet d2(-1,3); 00061 static IntSet d3(0,3); 00062 00063 static IntSet d4(0,4); 00064 00065 static IntSet ds_33(-3,3); 00066 00068 class Card : public SetTest { 00069 public: 00071 Card(const char* t) 00072 : SetTest(t,1,ds_33,false,1) {} 00074 virtual bool solution(const SetAssignment& x) const { 00075 unsigned int s = 0; 00076 for (CountableSetRanges xr(x.lub, x[0]);xr();++xr) s+= xr.width(); 00077 if (x.intval() < 0) 00078 return false; 00079 return s==(unsigned int)x.intval(); 00080 } 00082 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00083 Gecode::cardinality(home, x[0], y[0]); 00084 } 00085 }; 00086 Card _card("Int::Card"); 00087 00089 class Min : public SetTest { 00090 public: 00092 Min(const char* t) 00093 : SetTest(t,1,ds_33,true,1) {} 00095 virtual bool solution(const SetAssignment& x) const { 00096 CountableSetRanges xr0(x.lub, x[0]); 00097 return xr0() && xr0.min()==x.intval(); 00098 } 00100 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00101 Gecode::min(home, x[0], y[0]); 00102 } 00104 virtual void post(Space& home, SetVarArray& x, IntVarArray& y, 00105 BoolVar b) { 00106 Gecode::min(home, x[0], y[0], b); 00107 } 00108 }; 00109 Min _min("Int::Min"); 00110 00112 class NotMin : public SetTest { 00113 public: 00115 NotMin(const char* t) 00116 : SetTest(t,1,ds_33,false,1) {} 00118 virtual bool solution(const SetAssignment& x) const { 00119 CountableSetRanges xr0(x.lub, x[0]); 00120 return !(xr0() && xr0.min()==x.intval()); 00121 } 00123 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00124 Gecode::notMin(home, x[0], y[0]); 00125 } 00126 }; 00127 NotMin _notmin("Int::NotMin"); 00128 00130 class Max : public SetTest { 00131 public: 00133 Max(const char* t) 00134 : SetTest(t,1,ds_33,true,1) {} 00136 virtual bool solution(const SetAssignment& x) const { 00137 CountableSetRanges xr0(x.lub, x[0]); 00138 IntSet x0(xr0); 00139 return x0.ranges() > 0 && x0.max()==x.intval(); 00140 } 00142 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00143 Gecode::max(home, x[0], y[0]); 00144 } 00146 virtual void post(Space& home, SetVarArray& x, IntVarArray& y, 00147 BoolVar b) { 00148 Gecode::max(home, x[0], y[0], b); 00149 } 00150 }; 00151 Max _max("Int::Max"); 00152 00154 class NotMax : public SetTest { 00155 public: 00157 NotMax(const char* t) 00158 : SetTest(t,1,ds_33,false,1) {} 00160 virtual bool solution(const SetAssignment& x) const { 00161 CountableSetRanges xr0(x.lub, x[0]); 00162 IntSet x0(xr0); 00163 return !(x0.ranges() > 0 && x0.max()==x.intval()); 00164 } 00166 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00167 Gecode::notMax(home, x[0], y[0]); 00168 } 00169 }; 00170 NotMax _notmax("Int::NotMax"); 00171 00173 class Elem : public SetTest { 00174 public: 00176 Elem(const char* t) 00177 : SetTest(t,1,ds_33,true,1) {} 00179 virtual bool solution(const SetAssignment& x) const { 00180 for (CountableSetValues xr(x.lub, x[0]);xr();++xr) 00181 if (xr.val()==x.intval()) 00182 return true; 00183 return false; 00184 } 00186 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00187 Gecode::rel(home, x[0], SRT_SUP, y[0]); 00188 } 00190 virtual void post(Space& home, SetVarArray& x, IntVarArray& y, BoolVar b) { 00191 Gecode::rel(home, x[0], SRT_SUP, y[0], b); 00192 } 00193 }; 00194 Elem _elem("Int::Elem"); 00195 00197 class NoElem : public SetTest { 00198 public: 00200 NoElem(const char* t) 00201 : SetTest(t,1,ds_33,false,1) {} 00203 virtual bool solution(const SetAssignment& x) const { 00204 for (CountableSetValues xr(x.lub, x[0]);xr();++xr) 00205 if (xr.val()==x.intval()) 00206 return false; 00207 return true; 00208 } 00210 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00211 Gecode::rel(home, x[0], SRT_DISJ, y[0]); 00212 } 00213 }; 00214 NoElem _noelem("Int::NoElem"); 00215 00217 class Rel : public SetTest { 00218 private: 00219 Gecode::SetRelType srt; 00220 bool inverse; 00221 public: 00223 Rel(Gecode::SetRelType srt0, bool inverse0) 00224 : SetTest("Int::Rel::"+str(srt0)+(inverse0 ? "::i" : ""), 00225 1,ds_33,true,1) 00226 , srt(srt0) 00227 , inverse(inverse0) {} 00229 virtual bool solution(const SetAssignment& x) const { 00230 CountableSetRanges xr(x.lub, x[0]); 00231 IntSet is(x.intval(), x.intval()); 00232 IntSetRanges dr(is); 00233 Gecode::SetRelType rsrt = srt; 00234 if (inverse) { 00235 switch (srt) { 00236 case SRT_SUB: rsrt = SRT_SUP; break; 00237 case SRT_SUP: rsrt = SRT_SUB; break; 00238 default: break; 00239 } 00240 } 00241 switch (rsrt) { 00242 case SRT_EQ: return Iter::Ranges::equal(xr, dr); 00243 case SRT_NQ: return !Iter::Ranges::equal(xr, dr); 00244 case SRT_SUB: return Iter::Ranges::subset(xr, dr); 00245 case SRT_SUP: return Iter::Ranges::subset(dr, xr); 00246 case SRT_DISJ: 00247 { 00248 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges> 00249 inter(xr, dr); 00250 return !inter(); 00251 } 00252 case SRT_CMPL: 00253 { 00254 Gecode::Set::RangesCompl<IntSetRanges> drc(dr); 00255 return Iter::Ranges::equal(xr,drc); 00256 } 00257 } 00258 GECODE_NEVER; 00259 return false; 00260 } 00262 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00263 if (!inverse) 00264 Gecode::rel(home, x[0], srt, y[0]); 00265 else 00266 Gecode::rel(home, y[0], srt, x[0]); 00267 } 00269 virtual void post(Space& home, SetVarArray& x, IntVarArray& y, 00270 BoolVar b) { 00271 if (!inverse) 00272 Gecode::rel(home, x[0], srt, y[0], b); 00273 else 00274 Gecode::rel(home, y[0], srt, x[0], b); 00275 } 00276 }; 00277 Rel _rel_eq(Gecode::SRT_EQ,false); 00278 Rel _rel_nq(Gecode::SRT_NQ,false); 00279 Rel _rel_sub(Gecode::SRT_SUB,false); 00280 Rel _rel_sup(Gecode::SRT_SUP,false); 00281 Rel _rel_disj(Gecode::SRT_DISJ,false); 00282 Rel _rel_cmpl(Gecode::SRT_CMPL,false); 00283 Rel _rel_eqi(Gecode::SRT_EQ,true); 00284 Rel _rel_nqi(Gecode::SRT_NQ,true); 00285 Rel _rel_subi(Gecode::SRT_SUB,true); 00286 Rel _rel_supi(Gecode::SRT_SUP,true); 00287 Rel _rel_disji(Gecode::SRT_DISJ,true); 00288 Rel _rel_cmpli(Gecode::SRT_CMPL,true); 00289 00291 class IntRel : public SetTest { 00292 private: 00293 Gecode::IntRelType irt; 00294 bool inverse; 00295 public: 00297 IntRel(Gecode::IntRelType irt0, bool inverse0) 00298 : SetTest("Int::IntRel::"+Test::Int::Test::str(irt0)+ 00299 (inverse0 ? "::i" : ""),1,ds_33,false,1) 00300 , irt(irt0) 00301 , inverse(inverse0) {} 00303 virtual bool solution(const SetAssignment& x) const { 00304 CountableSetValues xr(x.lub, x[0]); 00305 if (!xr()) 00306 return false; 00307 for (; xr(); ++xr) { 00308 switch (irt) { 00309 case Gecode::IRT_EQ: 00310 if (xr.val() != x.intval()) return false; 00311 break; 00312 case Gecode::IRT_NQ: 00313 if (xr.val() == x.intval()) return false; 00314 break; 00315 case Gecode::IRT_GR: 00316 if (!inverse && xr.val() <= x.intval()) return false; 00317 if (inverse && xr.val() >= x.intval()) return false; 00318 break; 00319 case Gecode::IRT_GQ: 00320 if (!inverse && xr.val() < x.intval()) return false; 00321 if (inverse && xr.val() > x.intval()) return false; 00322 break; 00323 case Gecode::IRT_LE: 00324 if (!inverse && xr.val() >= x.intval()) return false; 00325 if (inverse && xr.val() <= x.intval()) return false; 00326 break; 00327 case Gecode::IRT_LQ: 00328 if (!inverse && xr.val() > x.intval()) return false; 00329 if (inverse && xr.val() < x.intval()) return false; 00330 break; 00331 default: 00332 GECODE_NEVER; 00333 return false; 00334 } 00335 } 00336 return true; 00337 } 00339 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00340 if (!inverse) 00341 Gecode::rel(home, x[0], irt, y[0]); 00342 else 00343 Gecode::rel(home, y[0], irt, x[0]); 00344 } 00345 }; 00346 IntRel _intrel_eq(Gecode::IRT_EQ,false); 00347 IntRel _intrel_nq(Gecode::IRT_NQ,false); 00348 IntRel _intrel_gr(Gecode::IRT_GR,false); 00349 IntRel _intrel_gq(Gecode::IRT_GQ,false); 00350 IntRel _intrel_le(Gecode::IRT_LE,false); 00351 IntRel _intrel_lq(Gecode::IRT_LQ,false); 00352 IntRel _intrel_eqi(Gecode::IRT_EQ,true); 00353 IntRel _intrel_nqi(Gecode::IRT_NQ,true); 00354 IntRel _intrel_gri(Gecode::IRT_GR,true); 00355 IntRel _intrel_gqi(Gecode::IRT_GQ,true); 00356 IntRel _intrel_lei(Gecode::IRT_LE,true); 00357 IntRel _intrel_lqi(Gecode::IRT_LQ,true); 00358 00359 00360 template<class I> 00361 int weightI(const IntArgs& elements, 00362 const IntArgs& weights, 00363 I& iter) { 00364 Iter::Ranges::IsRangeIter<I>(); 00365 int sum = 0; 00366 int i = 0; 00367 for (Iter::Ranges::ToValues<I> v(iter); v(); ++v) { 00368 // Skip all elements below the current 00369 while (elements[i]<v.val()) i++; 00370 assert(elements[i] == v.val()); 00371 sum += weights[i]; 00372 } 00373 return sum; 00374 } 00375 00377 class Weights : public SetTest { 00378 public: 00379 IntArgs elements; 00380 IntArgs weights; 00381 int minWeight; 00382 int maxWeight; 00384 Weights(const char* t, IntArgs& el, IntArgs& w, 00385 int min = -10000, int max = 10000) 00386 : SetTest(t,1,ds_33,false,1), 00387 elements(el), weights(w), minWeight(min), maxWeight(max) {} 00389 virtual bool solution(const SetAssignment& x) const { 00390 CountableSetRanges x0(x.lub, x[0]); 00391 return x.intval()==weightI(elements,weights,x0) && 00392 x.intval() >= minWeight && x.intval() <= maxWeight; 00393 } 00395 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00396 Gecode::rel(home, minWeight <= y[0]); 00397 Gecode::rel(home, maxWeight >= y[0]); 00398 Gecode::weights(home, elements, weights, x[0], y[0]); 00399 } 00400 }; 00401 00402 const int el1v[] = {-3,-2,-1,0,1,2,3}; 00403 IntArgs el1(7,el1v); 00404 const int w1v[] = {1,-2,1,1,1,6,1}; 00405 IntArgs w1(7,w1v); 00406 Weights _weights1("Int::Weights::1", el1, w1); 00407 00408 const int w2v[] = {-1,-1,-1,10,-1,-1,-1}; 00409 IntArgs w2(7,w2v); 00410 Weights _weights2("Int::Weights::2", el1, w2); 00411 Weights _weights3("Int::Weights::3", el1, w2, 3); 00412 00413 const int w4v[] = {1,1,0,0,0,0,0}; 00414 IntArgs w4(7,w4v); 00415 Weights _weights4("Int::Weights::4", el1, w4); 00416 00418 class Match : public SetTest { 00419 public: 00421 Match(const char* t) 00422 : SetTest(t,1,ds_33,false,3) {} 00424 virtual bool solution(const SetAssignment& x) const { 00425 if (x.ints()[0]>=x.ints()[1] || 00426 x.ints()[1]>=x.ints()[2]) 00427 return false; 00428 CountableSetValues xr(x.lub, x[0]); 00429 if (!xr()) 00430 return false; 00431 if (xr.val() != x.ints()[0]) 00432 return false; 00433 ++xr; 00434 if (!xr()) 00435 return false; 00436 if (xr.val() != x.ints()[1]) 00437 return false; 00438 ++xr; 00439 if (!xr()) 00440 return false; 00441 if (xr.val() != x.ints()[2]) 00442 return false; 00443 ++xr; 00444 if (xr()) 00445 return false; 00446 return true; 00447 } 00449 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00450 Gecode::channel(home, y, x[0]); 00451 } 00452 }; 00453 Match _match("Int::Match"); 00454 00456 class ChannelInt : public SetTest { 00457 private: 00458 int ssize, isize; 00459 public: 00461 ChannelInt(const char* t, const IntSet& d, int _ssize, int _isize) 00462 : SetTest(t,_ssize,d,false,_isize), ssize(_ssize), isize(_isize) {} 00464 virtual bool solution(const SetAssignment& x) const { 00465 for (int i=0; i<isize; i++) { 00466 if (x.ints()[i] < 0 || x.ints()[i] >= ssize) 00467 return false; 00468 Iter::Ranges::Singleton single(i,i); 00469 CountableSetRanges csr(x.lub, x[x.ints()[i]]); 00470 if (!Iter::Ranges::subset(single, csr)) 00471 return false; 00472 } 00473 for (int i=0; i<ssize; i++) { 00474 int size = 0; 00475 for (CountableSetValues csv(x.lub, x[i]); csv(); ++csv) { 00476 if (csv.val() < 0 || csv.val() >= isize) return false; 00477 if (x.ints()[csv.val()] != i) return false; 00478 size++; 00479 } 00480 } 00481 return true; 00482 } 00484 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00485 Gecode::channel(home, y, x); 00486 } 00487 }; 00488 00489 ChannelInt _channelint1("Int::Channel::Int::1", d2, 2, 3); 00490 ChannelInt _channelint2("Int::Channel::Int::2", d3, 3, 3); 00491 00493 class ChannelBool : public SetTest { 00494 private: 00495 int isize; 00496 public: 00498 ChannelBool(const char* t, const IntSet& d, int _isize) 00499 : SetTest(t,1,d,false,_isize), isize(_isize) {} 00501 virtual bool solution(const SetAssignment& x) const { 00502 for (int i=0; i<isize; i++) { 00503 if (x.ints()[i] < 0 || x.ints()[i] > 1) 00504 return false; 00505 } 00506 int cur = 0; 00507 for (CountableSetValues csv(x.lub, x[0]); csv(); ++csv) { 00508 if (csv.val() < 0 || csv.val() >= isize) return false; 00509 if (x.ints()[csv.val()] != 1) return false; 00510 for (; cur<csv.val(); cur++) 00511 if (x.ints()[cur] != 0) return false; 00512 cur = csv.val() + 1; 00513 } 00514 for (; cur<isize; cur++) 00515 if (x.ints()[cur] != 0) return false; 00516 return true; 00517 } 00519 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) { 00520 BoolVarArgs b(y.size()); 00521 for (int i=y.size(); i--;) 00522 b[i] = channel(home, y[i]); 00523 Gecode::channel(home, b, x[0]); 00524 } 00525 }; 00526 00527 ChannelBool _channelbool1("Int::Channel::Bool::1", d2, 3); 00528 ChannelBool _channelbool2("Int::Channel::Bool::2", d3, 3); 00529 ChannelBool _channelbool3("Int::Channel::Bool::3", d4, 5); 00530 00531 }}} 00532 00533 // STATISTICS: test-set