int-dom.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2006 00008 * 00009 * Last modified: 00010 * $Date: 2010-06-03 13:46:55 +0200 (Thu, 03 Jun 2010) $ by $Author: schulte $ 00011 * $Revision: 11014 $ 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 namespace Gecode { namespace Int { namespace Linear { 00039 00047 class SupportSet { 00048 private: 00050 Support::BitSetBase bs; 00051 public: 00053 SupportSet(void); 00055 void init(Region& r, unsigned int n); 00057 void support(unsigned int i); 00059 bool supported(unsigned int i) const; 00060 00061 private: 00063 class ResultIter : public ViewValues<IntView> { 00064 protected: 00066 const SupportSet& s; 00068 unsigned int p; 00069 public: 00071 ResultIter(const SupportSet& s0, const IntView& x); 00073 void operator ++(void); 00074 }; 00075 00076 public: 00078 ModEvent tell(Space& home, IntView& x) const; 00079 }; 00080 00085 template<class Val> 00086 class SupportIter { 00087 protected: 00089 int a; 00091 IntView x; 00093 SupportSet s; 00095 int c; 00097 unsigned int p; 00099 Val l; 00101 Val u; 00102 public: 00104 void init(Region& r, int a, const IntView& x, Val l, Val u); 00106 void support(void); 00108 ModEvent tell(Space& home); 00109 }; 00110 00111 00116 template<class Val> 00117 class PosSupportIter : public SupportIter<Val> { 00118 private: 00120 IntVarImpFwd i; 00121 // Using-declarations for dependant names 00122 using SupportIter<Val>::a; 00123 using SupportIter<Val>::x; 00124 using SupportIter<Val>::s; 00125 using SupportIter<Val>::c; 00126 using SupportIter<Val>::p; 00127 using SupportIter<Val>::l; 00128 using SupportIter<Val>::u; 00129 public: 00131 bool reset(Val& d); 00133 bool adjust(Val& d); 00134 }; 00135 00136 00141 template<class Val> 00142 class NegSupportIter : public SupportIter<Val> { 00143 private: 00145 IntVarImpBwd i; 00146 // Using-declarations for dependant names 00147 using SupportIter<Val>::a; 00148 using SupportIter<Val>::x; 00149 using SupportIter<Val>::s; 00150 using SupportIter<Val>::c; 00151 using SupportIter<Val>::p; 00152 using SupportIter<Val>::l; 00153 using SupportIter<Val>::u; 00154 public: 00156 bool reset(Val& d); 00158 bool adjust(Val& d); 00159 }; 00160 00161 00162 /* 00163 * Support set 00164 * 00165 */ 00166 forceinline 00167 SupportSet::SupportSet(void) {} 00168 forceinline void 00169 SupportSet::init(Region& r, unsigned int n) { 00170 bs.init(r,n); 00171 } 00172 forceinline void 00173 SupportSet::support(unsigned int i) { 00174 bs.set(i); 00175 } 00176 forceinline bool 00177 SupportSet::supported(unsigned int i) const { 00178 return bs.get(i); 00179 } 00180 00181 forceinline 00182 SupportSet::ResultIter::ResultIter(const SupportSet& s0, const IntView& x) 00183 : ViewValues<IntView>(x), s(s0), p(0) { 00184 while (ViewValues<IntView>::operator ()() && s.supported(p)) { 00185 ViewValues<IntView>::operator ++(); ++p; 00186 } 00187 } 00188 forceinline void 00189 SupportSet::ResultIter::operator ++(void) { 00190 do { 00191 ViewValues<IntView>::operator ++(); ++p; 00192 } while (ViewValues<IntView>::operator ()() && s.supported(p)); 00193 } 00194 00195 00196 forceinline ModEvent 00197 SupportSet::tell(Space& home, IntView& x) const { 00198 switch (bs.status()) { 00199 case Support::BSS_NONE: 00200 return ME_INT_FAILED; 00201 case Support::BSS_ALL: 00202 return ME_INT_NONE; 00203 case Support::BSS_SOME: 00204 { 00205 ResultIter i(*this,x); 00206 return x.minus_v(home,i); 00207 } 00208 default: 00209 GECODE_NEVER; 00210 } 00211 return ME_INT_NONE; 00212 } 00213 00214 00215 /* 00216 * Base-class for support-based iterator 00217 * 00218 */ 00219 template<class Val> 00220 forceinline void 00221 SupportIter<Val>::init(Region& r, 00222 int a0, const IntView& x0, Val l0, Val u0) { 00223 a=a0; x=x0; l=l0; u=u0; 00224 s.init(r,x.size()); 00225 } 00226 template<class Val> 00227 forceinline void 00228 SupportIter<Val>::support(void) { 00229 s.support(p); 00230 } 00231 template<class Val> 00232 forceinline ModEvent 00233 SupportIter<Val>::tell(Space& home) { 00234 return s.tell(home,x); 00235 } 00236 00237 00238 /* 00239 * Support-based iterator for positive view 00240 * 00241 */ 00242 template<class Val> 00243 forceinline bool 00244 PosSupportIter<Val>::reset(Val& d) { 00245 // Way too small, no value can make it big enough 00246 if (d + static_cast<Val>(a)*x.max() < u) 00247 return false; 00248 // Restart iterator and position of values 00249 i.init(x.varimp()); p = 0; 00250 // Skip all ranges which are too small 00251 while (d + static_cast<Val>(a)*i.max() < u) { 00252 p += i.width(); ++i; 00253 } 00254 // There is at least one range left (check of max) 00255 assert(i()); 00256 // Initialize current range and adjust value 00257 c = i.min(); 00258 // Skip all values which are too small 00259 while (d + static_cast<Val>(a)*c < u) { 00260 p++; c++; 00261 } 00262 // Adjust to new value 00263 d += static_cast<Val>(a) * c; 00264 return true; 00265 } 00266 template<class Val> 00267 forceinline bool 00268 PosSupportIter<Val>::adjust(Val& d) { 00269 // Current value 00270 Val v = static_cast<Val>(a) * c; 00271 // Subtract current value from d 00272 d -= v; 00273 // Move to next position (number of value) 00274 p++; 00275 // Still in the same range 00276 if (c < i.max()) { 00277 // Decrement current values 00278 c += 1; v += a; 00279 } else { 00280 // Go to next range 00281 ++i; 00282 if (!i()) 00283 return false; 00284 c = i.min(); v = static_cast<Val>(a) * c; 00285 } 00286 // Is d with the current value too large? 00287 if (d + v > l) 00288 return false; 00289 // Update d 00290 d += v; 00291 return true; 00292 } 00293 00294 00295 /* 00296 * Support-based iterator for negative view 00297 * 00298 */ 00299 template<class Val> 00300 forceinline bool 00301 NegSupportIter<Val>::reset(Val& d) { 00302 // Way too small, no value can make it big enough 00303 if (d + static_cast<Val>(a)*x.min() < u) 00304 return false; 00305 // Restart iterator and position of values 00306 i.init(x.varimp()); p = x.size()-1; 00307 // Skip all ranges which are too small 00308 while (d + static_cast<Val>(a)*i.min() < u) { 00309 p -= i.width(); ++i; 00310 } 00311 // There is at least one range left (check of max) 00312 assert(i()); 00313 // Initialize current range 00314 c = i.max(); 00315 // Skip all values which are too small 00316 while (d + static_cast<Val>(a)*c < u) { 00317 p--; c--; 00318 } 00319 // Adjust to new value 00320 d += static_cast<Val>(a) * c; 00321 return true; 00322 } 00323 template<class Val> 00324 forceinline bool 00325 NegSupportIter<Val>::adjust(Val& d) { 00326 // Current value 00327 Val v = static_cast<Val>(a) * c; 00328 // Subtract current value from d 00329 d -= v; 00330 // Move to next position (number of value) 00331 p--; 00332 // Still in the same range 00333 if (c > i.min()) { 00334 // Decrement current values 00335 c -= 1; v -= a; 00336 } else { 00337 // Go to next range 00338 ++i; 00339 if (!i()) 00340 return false; 00341 c = i.max(); v = static_cast<Val>(a) * c; 00342 } 00343 // Is d with the current value too large? 00344 if (d + v > l) 00345 return false; 00346 // Update d 00347 d += v; 00348 return true; 00349 } 00350 00351 00352 00353 /* 00354 * The domain consisten equality propagator 00355 * 00356 */ 00357 template<class Val, class View> 00358 forceinline 00359 DomEq<Val,View>::DomEq(Home home, 00360 ViewArray<View >& x, ViewArray<View >& y, 00361 Val c) 00362 : Lin<Val,View,View,PC_INT_DOM>(home,x,y,c) {} 00363 00364 template<class Val, class View> 00365 ExecStatus 00366 DomEq<Val,View>::post(Home home, 00367 ViewArray<View>& x, ViewArray<View>& y, 00368 Val c) { 00369 (void) new (home) DomEq<Val,View>(home,x,y,c); 00370 return ES_OK; 00371 } 00372 00373 template<class Val, class View> 00374 forceinline 00375 DomEq<Val,View>::DomEq(Space& home, bool share, DomEq<Val,View>& p) 00376 : Lin<Val,View,View,PC_INT_DOM>(home,share,p) {} 00377 00378 template<class Val, class View> 00379 Actor* 00380 DomEq<Val,View>::copy(Space& home, bool share) { 00381 return new (home) DomEq<Val,View>(home,share,*this); 00382 } 00383 00384 template<class Val, class View> 00385 PropCost 00386 DomEq<Val,View>::cost(const Space&, const ModEventDelta& med) const { 00387 if (View::me(med) != ME_INT_DOM) 00388 return PropCost::linear(PropCost::LO, x.size()+y.size()); 00389 else 00390 return PropCost::crazy(PropCost::HI, x.size()+y.size()); 00391 } 00392 00393 template<class Val, class View> 00394 ExecStatus 00395 DomEq<Val,View>::propagate(Space& home, const ModEventDelta& med) { 00396 if (View::me(med) != ME_INT_DOM) { 00397 ExecStatus es = prop_bnd<Val,View,View>(home,med,*this,x,y,c); 00398 GECODE_ES_CHECK(es); 00399 return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM)); 00400 } 00401 00402 // Value of equation for partial assignment 00403 Val d = -c; 00404 00405 int n = x.size(); 00406 int m = y.size(); 00407 00408 Region r(home); 00409 // Create support-base iterators 00410 PosSupportIter<Val>* xp = r.alloc<PosSupportIter<Val> >(n); 00411 NegSupportIter<Val>* yp = r.alloc<NegSupportIter<Val> >(m); 00412 00413 // Initialize views for assignments 00414 { 00415 Val l = 0; 00416 Val u = 0; 00417 for (int j=m; j--; ) { 00418 yp[j].init(r,-y[j].scale(),y[j].base(),l,u); 00419 l += y[j].max(); u += y[j].min(); 00420 } 00421 for (int i=n; i--; ) { 00422 xp[i].init(r,x[i].scale(),x[i].base(),l,u); 00423 l -= x[i].min(); u -= x[i].max(); 00424 } 00425 } 00426 00427 // Collect support information by iterating assignments 00428 { 00429 // Force reset of all iterators in first round 00430 int i = 0; 00431 int j = 0; 00432 00433 next_i: 00434 // Reset all iterators for positive views and update d 00435 while (i<n) { 00436 if (!xp[i].reset(d)) goto prev_i; 00437 i++; 00438 } 00439 next_j: 00440 // Reset all iterators for negative views and update d 00441 while (j<m) { 00442 if (!yp[j].reset(d)) goto prev_j; 00443 j++; 00444 } 00445 // Check whether current assignment is solution 00446 if (d == 0) { 00447 // Record support 00448 for (int is=n; is--; ) xp[is].support(); 00449 for (int js=m; js--; ) yp[js].support(); 00450 } 00451 prev_j: 00452 // Try iterating to next assignment: negative views 00453 while (j>0) { 00454 if (yp[j-1].adjust(d)) goto next_j; 00455 j--; 00456 } 00457 prev_i: 00458 // Try iterating to next assignment: positive views 00459 while (i>0) { 00460 if (xp[i-1].adjust(d)) goto next_i; 00461 i--; 00462 } 00463 } 00464 00465 // Tell back new variable domains 00466 bool assigned = true; 00467 for (int i=n; i--; ) { 00468 GECODE_ME_CHECK(xp[i].tell(home)); 00469 if (!x[i].assigned()) 00470 assigned = false; 00471 } 00472 for (int j=m; j--; ) { 00473 GECODE_ME_CHECK(yp[j].tell(home)); 00474 if (!y[j].assigned()) 00475 assigned = false; 00476 } 00477 if (assigned) 00478 return home.ES_SUBSUMED(*this); 00479 return ES_FIX; 00480 } 00481 00482 }}} 00483 00484 // STATISTICS: int-prop