view.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 * Contributing authors: 00007 * Guido Tack <tack@gecode.org> 00008 * 00009 * Copyright: 00010 * Christian Schulte, 2004 00011 * Guido Tack, 2004 00012 * 00013 * Last modified: 00014 * $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00015 * $Revision: 10364 $ 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 <algorithm> 00043 00044 namespace Gecode { namespace Int { namespace Element { 00045 00047 template<> 00048 class ViewToVarArg<IntView> { 00049 public: 00050 typedef IntVarArgs argtype; 00051 }; 00053 template<> 00054 class ViewToVarArg<BoolView> { 00055 public: 00056 typedef BoolVarArgs argtype; 00057 }; 00058 00063 template<class View> 00064 class IdxView { 00065 public: 00066 int idx; View view; 00067 00068 static IdxView* allocate(Space&, int); 00069 }; 00070 00071 template<class View> 00072 forceinline IdxView<View>* 00073 IdxView<View>::allocate(Space& home, int n) { 00074 return home.alloc<IdxView<View> >(n); 00075 } 00076 00077 template<class View> 00078 IdxViewArray<View>::IdxViewArray(void) : xs(NULL), n(0) {} 00079 00080 template<class View> 00081 IdxViewArray<View>::IdxViewArray(const IdxViewArray<View>& a) { 00082 n = a.n; xs = a.xs; 00083 } 00084 00085 template<class View> 00086 IdxViewArray<View>::IdxViewArray(Space& home, 00087 const typename ViewToVarArg<View>::argtype& xa) : xs(NULL) { 00088 n = xa.size(); 00089 if (n>0) { 00090 xs = IdxView<View>::allocate(home, n); 00091 for (int i = n; i--; ) { 00092 xs[i].idx = i; xs[i].view = xa[i]; 00093 } 00094 } 00095 } 00096 00097 template<class View> 00098 IdxViewArray<View>::IdxViewArray(Space& home, int n0) : xs(NULL) { 00099 n = n0; 00100 if (n>0) { 00101 xs = IdxView<View>::allocate(home, n); 00102 } 00103 } 00104 00105 template<class View> 00106 forceinline int 00107 IdxViewArray<View>::size(void) const { 00108 return n; 00109 } 00110 00111 template<class View> 00112 forceinline void 00113 IdxViewArray<View>::size(int n0) { 00114 n = n0; 00115 } 00116 00117 template<class View> 00118 forceinline IdxView<View>& 00119 IdxViewArray<View>::operator [](int i) { 00120 assert((i >= 0) && (i < size())); 00121 return xs[i]; 00122 } 00123 00124 template<class View> 00125 forceinline const IdxView<View>& 00126 IdxViewArray<View>::operator [](int i) const { 00127 assert((i >= 0) && (i < size())); 00128 return xs[i]; 00129 } 00130 00131 template<class View> 00132 void 00133 IdxViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc, 00134 bool process) { 00135 for (int i = n; i--; ) 00136 xs[i].view.subscribe(home,p,pc,process); 00137 } 00138 00139 template<class View> 00140 void 00141 IdxViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) { 00142 for (int i = n; i--; ) 00143 xs[i].view.cancel(home,p,pc); 00144 } 00145 00146 template<class View> 00147 void 00148 IdxViewArray<View>::update(Space& home, bool share, IdxViewArray<View>& a) { 00149 n = a.size(); 00150 if (n>0) { 00151 xs = IdxView<View>::allocate(home,n); 00152 for (int i=n; i--; ) { 00153 xs[i].idx = a[i].idx; 00154 xs[i].view.update(home,share,a[i].view); 00155 } 00156 } 00157 } 00158 00159 00164 template<class VA, class VC> 00165 class RelTestBnd { 00166 public: 00167 RelTest operator ()(VA,VC); 00168 }; 00173 template<class VA> 00174 class RelTestBnd<VA,ConstIntView> { 00175 public: 00176 RelTest operator ()(VA,ConstIntView); 00177 }; 00178 00183 template<class VA, class VC> 00184 class RelTestDom { 00185 public: 00186 RelTest operator ()(VA,VC); 00187 }; 00192 template<class VA> 00193 class RelTestDom<VA,ConstIntView> { 00194 public: 00195 RelTest operator ()(VA,ConstIntView); 00196 }; 00197 00198 00199 template<class VA, class VC> 00200 forceinline RelTest 00201 RelTestBnd<VA,VC>::operator ()(VA x, VC y) { 00202 return rtest_eq_bnd(x,y); 00203 } 00204 template<class VA> 00205 forceinline RelTest 00206 RelTestBnd<VA,ConstIntView>::operator ()(VA x, ConstIntView y) { 00207 return rtest_eq_bnd(x,y.val()); 00208 } 00209 00210 template<class VA, class VC> 00211 forceinline RelTest 00212 RelTestDom<VA,VC>::operator ()(VA x, VC y) { 00213 return rtest_eq_dom(x,y); 00214 } 00215 template<class VA> 00216 forceinline RelTest 00217 RelTestDom<VA,ConstIntView>::operator ()(VA x, ConstIntView y) { 00218 return rtest_eq_dom(x,y.val()); 00219 } 00220 00221 00222 00223 00224 /* 00225 * Base class 00226 * 00227 */ 00228 00229 template<class VA, class VB, class VC, PropCond pc_ac> 00230 View<VA,VB,VC,pc_ac>::View(Home home, IdxViewArray<VA>& iv0, 00231 VB y0, VC y1) 00232 : Propagator(home), iv(iv0), x0(y0), x1(y1) { 00233 x0.subscribe(home,*this,PC_INT_DOM); 00234 x1.subscribe(home,*this,pc_ac); 00235 iv.subscribe(home,*this,pc_ac); 00236 } 00237 00238 template<class VA, class VB, class VC, PropCond pc_ac> 00239 forceinline 00240 View<VA,VB,VC,pc_ac>::View(Space& home, bool share, View& p) 00241 : Propagator(home,share,p) { 00242 x0.update(home,share,p.x0); 00243 x1.update(home,share,p.x1); 00244 iv.update(home,share,p.iv); 00245 } 00246 00247 template<class VA, class VB, class VC, PropCond pc_ac> 00248 PropCost 00249 View<VA,VB,VC,pc_ac>::cost(const Space&, const ModEventDelta&) const { 00250 // This is required for subscribing to variables in the 00251 // above constructor, but this is then the only time this 00252 // virtual function is ever used! 00253 return PropCost::linear(PropCost::LO,iv.size()+2); 00254 } 00255 00256 template<class VA, class VB, class VC, PropCond pc_ac> 00257 forceinline size_t 00258 View<VA,VB,VC,pc_ac>::dispose(Space& home) { 00259 x0.cancel(home,*this,PC_INT_DOM); 00260 x1.cancel(home,*this,pc_ac); 00261 iv.cancel(home,*this,pc_ac); 00262 (void) Propagator::dispose(home); 00263 return sizeof(*this); 00264 } 00265 00266 00267 00268 00273 template<class View> 00274 class IterIdxView { 00275 private: 00276 const IdxView<View> *cur, *end; 00277 public: 00278 IterIdxView(void); 00279 IterIdxView(const IdxView<View>*, const IdxView<View>*); 00280 void init(const IdxView<View>*, const IdxView<View>*); 00281 bool operator ()(void) const; 00282 void operator ++(void); 00283 int val(void) const; 00284 }; 00285 00286 template<class View> 00287 forceinline 00288 IterIdxView<View>::IterIdxView(void) {} 00289 template<class View> 00290 forceinline 00291 IterIdxView<View>::IterIdxView(const IdxView<View>* b, 00292 const IdxView<View>* e) 00293 : cur(b), end(e) {} 00294 template<class View> 00295 forceinline void 00296 IterIdxView<View>::init(const IdxView<View>* b, 00297 const IdxView<View>* e) { 00298 cur=b; end=e; 00299 } 00300 template<class View> 00301 forceinline bool 00302 IterIdxView<View>::operator ()(void) const { 00303 return cur < end; 00304 } 00305 template<class View> 00306 forceinline void 00307 IterIdxView<View>::operator ++(void) { 00308 cur++; 00309 } 00310 template<class View> 00311 forceinline int 00312 IterIdxView<View>::val(void) const { 00313 return cur->idx; 00314 } 00315 00316 00317 00318 00319 /* 00320 * Generic scanning: does all but computing new domain for result 00321 * (which is specific to bounds/domain version) 00322 * 00323 */ 00324 00325 template<class VA, class VB, class VC, PropCond pc_ac, class RelTest> 00326 ExecStatus 00327 scan(Space& home, IdxViewArray<VA>& iv, 00328 VB x0, VC x1, Propagator& p, RelTest rt) { 00329 assert(iv.size() > 1); 00330 /* 00331 * Prunes pairs of index, variable 00332 * - checks for idx value removed 00333 * - checks for disequal variables 00334 * 00335 */ 00336 ViewValues<VB> vx0(x0); 00337 int i = 0; 00338 int j = 0; 00339 while (vx0() && (i < iv.size())) { 00340 if (iv[i].idx < vx0.val()) { 00341 iv[i].view.cancel(home,p,pc_ac); 00342 ++i; 00343 } else if (iv[i].idx > vx0.val()) { 00344 ++vx0; 00345 } else { 00346 assert(iv[i].idx == vx0.val()); 00347 switch (rt(iv[i].view,x1)) { 00348 case RT_FALSE: 00349 iv[i].view.cancel(home,p,pc_ac); 00350 break; 00351 case RT_TRUE: 00352 case RT_MAYBE: 00353 iv[j++] = iv[i]; 00354 break; 00355 default: GECODE_NEVER; 00356 } 00357 ++vx0; ++i; 00358 } 00359 } 00360 while (i < iv.size()) 00361 iv[i++].view.cancel(home,p,pc_ac); 00362 bool adjust = (j<iv.size()); 00363 iv.size(j); 00364 00365 if (iv.size() == 0) 00366 return ES_FAILED; 00367 00368 if (iv.size() == 1) { 00369 GECODE_ME_CHECK(x0.eq(home,iv[0].idx)); 00370 } else if (adjust) { 00371 IterIdxView<VA> v(&iv[0],&iv[0]+iv.size()); 00372 GECODE_ME_CHECK(x0.narrow_v(home,v,false)); 00373 assert(x0.size() == static_cast<unsigned int>(iv.size())); 00374 } 00375 return ES_OK; 00376 } 00377 00378 00379 00380 00381 /* 00382 * Bounds consistent propagator 00383 * 00384 */ 00385 00386 template<class VA, class VB, class VC> 00387 forceinline 00388 ViewBnd<VA,VB,VC>::ViewBnd(Home home, 00389 IdxViewArray<VA>& iv, VB x0, VC x1) 00390 : View<VA,VB,VC,PC_INT_BND>(home,iv,x0,x1) {} 00391 00392 template<class VA, class VB, class VC> 00393 ExecStatus 00394 ViewBnd<VA,VB,VC>::post(Home home, 00395 IdxViewArray<VA>& iv, VB x0, VC x1) { 00396 GECODE_ME_CHECK(x0.gq(home,0)); 00397 GECODE_ME_CHECK(x0.le(home,iv.size())); 00398 if (x0.assigned()) { 00399 (void) new (home) Rel::EqBnd<VA,VC>(home,iv[x0.val()].view,x1); 00400 return ES_OK; 00401 } else { 00402 assert(iv.size()>1); 00403 (void) new (home) ViewBnd<VA,VB,VC>(home,iv,x0,x1); 00404 } 00405 return ES_OK; 00406 } 00407 00408 00409 template<class VA, class VB, class VC> 00410 forceinline 00411 ViewBnd<VA,VB,VC>::ViewBnd(Space& home, bool share, ViewBnd& p) 00412 : View<VA,VB,VC,PC_INT_BND>(home,share,p) {} 00413 00414 template<class VA, class VB, class VC> 00415 Actor* 00416 ViewBnd<VA,VB,VC>::copy(Space& home, bool share) { 00417 return new (home) ViewBnd<VA,VB,VC>(home,share,*this); 00418 } 00419 00420 template<class VA, class VB, class VC> 00421 ExecStatus 00422 ViewBnd<VA,VB,VC>::propagate(Space& home, const ModEventDelta&) { 00423 assert(iv.size() > 1); 00424 RelTestBnd<VA,VC> rt; 00425 GECODE_ME_CHECK((scan<VA,VB,VC,PC_INT_BND,RelTestBnd<VA,VC> > 00426 (home,iv,x0,x1,*this,rt))); 00427 if (iv.size() == 1) { 00428 ExecStatus es = home.ES_SUBSUMED(*this); 00429 (void) new (home) Rel::EqBnd<VA,VC>(home,iv[0].view,x1); 00430 return es; 00431 } 00432 assert(iv.size() > 1); 00433 // Compute new result 00434 int min = iv[iv.size()-1].view.min(); 00435 int max = iv[iv.size()-1].view.max(); 00436 for (int i=iv.size()-1; i--; ) { 00437 min = std::min(iv[i].view.min(),min); 00438 max = std::max(iv[i].view.max(),max); 00439 } 00440 ExecStatus es = shared(x0,x1) ? ES_NOFIX : ES_FIX; 00441 { 00442 ModEvent me = x1.lq(home,max); 00443 if (me_failed(me)) 00444 return ES_FAILED; 00445 if (me_modified(me) && (x1.max() != max)) 00446 es = ES_NOFIX; 00447 } 00448 { 00449 ModEvent me = x1.gq(home,min); 00450 if (me_failed(me)) 00451 return ES_FAILED; 00452 if (me_modified(me) && (x1.min() != min)) 00453 es = ES_NOFIX; 00454 } 00455 return (x1.assigned() && (min == max)) ? 00456 home.ES_SUBSUMED(*this) : es; 00457 } 00458 00459 00460 00461 00462 00463 /* 00464 * Domain consistent propagator 00465 * 00466 */ 00467 00468 template<class VA, class VB, class VC> 00469 forceinline 00470 ViewDom<VA,VB,VC>::ViewDom(Home home, 00471 IdxViewArray<VA>& iv, VB x0, VC x1) 00472 : View<VA,VB,VC,PC_INT_DOM>(home,iv,x0,x1) {} 00473 00474 template<class VA, class VB, class VC> 00475 ExecStatus 00476 ViewDom<VA,VB,VC>::post(Home home, 00477 IdxViewArray<VA>& iv, VB x0, VC x1){ 00478 GECODE_ME_CHECK(x0.gq(home,0)); 00479 GECODE_ME_CHECK(x0.le(home,iv.size())); 00480 if (x0.assigned()) { 00481 (void) new (home) Rel::EqDom<VA,VC>(home,iv[x0.val()].view,x1); 00482 return ES_OK; 00483 } else { 00484 assert(iv.size()>1); 00485 (void) new (home) ViewDom<VA,VB,VC>(home,iv,x0,x1); 00486 } 00487 return ES_OK; 00488 } 00489 00490 00491 template<class VA, class VB, class VC> 00492 forceinline 00493 ViewDom<VA,VB,VC>::ViewDom(Space& home, bool share, ViewDom& p) 00494 : View<VA,VB,VC,PC_INT_DOM>(home,share,p) {} 00495 00496 template<class VA, class VB, class VC> 00497 Actor* 00498 ViewDom<VA,VB,VC>::copy(Space& home, bool share) { 00499 return new (home) ViewDom<VA,VB,VC>(home,share,*this); 00500 } 00501 00502 00503 template<class VA, class VB, class VC> 00504 PropCost 00505 ViewDom<VA,VB,VC>::cost(const Space&, const ModEventDelta& med) const { 00506 return PropCost::linear((VA::me(med) != ME_INT_DOM) ? 00507 PropCost::LO : PropCost::HI, iv.size()+2); 00508 } 00509 00510 template<class VA, class VB, class VC> 00511 ExecStatus 00512 ViewDom<VA,VB,VC>::propagate(Space& home, const ModEventDelta& med) { 00513 assert(iv.size() > 1); 00514 if (VA::me(med) != ME_INT_DOM) { 00515 RelTestBnd<VA,VC> rt; 00516 GECODE_ME_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestBnd<VA,VC> > 00517 (home,iv,x0,x1,*this,rt))); 00518 if (iv.size() == 1) { 00519 ExecStatus es = home.ES_SUBSUMED(*this); 00520 (void) new (home) Rel::EqDom<VA,VC>(home,iv[0].view,x1); 00521 return es; 00522 } 00523 // Compute new result 00524 int min = iv[iv.size()-1].view.min(); 00525 int max = iv[iv.size()-1].view.max(); 00526 for (int i=iv.size()-1; i--; ) { 00527 min = std::min(iv[i].view.min(),min); 00528 max = std::max(iv[i].view.max(),max); 00529 } 00530 GECODE_ME_CHECK(x1.lq(home,max)); 00531 GECODE_ME_CHECK(x1.gq(home,min)); 00532 return (x1.assigned() && (min == max)) ? 00533 home.ES_SUBSUMED(*this) : 00534 home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM)); 00535 } 00536 RelTestDom<VA,VC> rt; 00537 GECODE_ME_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestDom<VA,VC> > 00538 (home,iv,x0,x1,*this,rt))); 00539 if (iv.size() == 1) { 00540 ExecStatus es = home.ES_SUBSUMED(*this); 00541 (void) new (home) Rel::EqDom<VA,VC>(home,iv[0].view,x1); 00542 return es; 00543 } 00544 assert(iv.size() > 1); 00545 Region r(home); 00546 ViewRanges<VA>* i_view = r.alloc<ViewRanges<VA> >(iv.size()); 00547 for (int i = iv.size(); i--; ) 00548 i_view[i].init(iv[i].view); 00549 Iter::Ranges::NaryUnion<ViewRanges<VA> > i_val(i_view, iv.size()); 00550 ModEvent me = x1.inter_r(home,i_val); 00551 r.free<ViewRanges<VA> >(i_view,iv.size()); 00552 GECODE_ME_CHECK(me); 00553 return (shared(x0,x1) || me_modified(me)) ? ES_NOFIX : ES_FIX; 00554 } 00555 00556 }}} 00557 00558 // STATISTICS: int-prop 00559