1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Christian Schulte <schulte@gecode.org> 5 * 6 * Contributing authors: 7 * Guido Tack <tack@gecode.org> 8 * 9 * Copyright: 10 * Christian Schulte, 2004 11 * Guido Tack, 2004 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 <algorithm> 39 40 namespace Gecode { namespace Int { namespace Element { 41 42 /** 43 * \brief Class for bounds-equality test 44 * 45 */ 46 template<class VA, class VC> 47 class RelTestBnd { 48 public: 49 RelTest operator ()(VA,VC); 50 }; 51 /** 52 * \brief Class for bounds-equality test (specialized) 53 * 54 */ 55 template<class VA> 56 class RelTestBnd<VA,ConstIntView> { 57 public: 58 RelTest operator ()(VA,ConstIntView); 59 }; 60 61 /** 62 * \brief Class for domain-equality test 63 * 64 */ 65 template<class VA, class VC> 66 class RelTestDom { 67 public: 68 RelTest operator ()(VA,VC); 69 }; 70 /** 71 * \brief Class for domain-equality test (specialized) 72 * 73 */ 74 template<class VA> 75 class RelTestDom<VA,ConstIntView> { 76 public: 77 RelTest operator ()(VA,ConstIntView); 78 }; 79 80 81 template<class VA, class VC> 82 forceinline RelTest operator ()(VA x,VC y)83 RelTestBnd<VA,VC>::operator ()(VA x, VC y) { 84 return rtest_eq_bnd(x,y); 85 } 86 template<class VA> 87 forceinline RelTest operator ()(VA x,ConstIntView y)88 RelTestBnd<VA,ConstIntView>::operator ()(VA x, ConstIntView y) { 89 return rtest_eq_bnd(x,y.val()); 90 } 91 92 template<class VA, class VC> 93 forceinline RelTest operator ()(VA x,VC y)94 RelTestDom<VA,VC>::operator ()(VA x, VC y) { 95 return rtest_eq_dom(x,y); 96 } 97 template<class VA> 98 forceinline RelTest operator ()(VA x,ConstIntView y)99 RelTestDom<VA,ConstIntView>::operator ()(VA x, ConstIntView y) { 100 return rtest_eq_dom(x,y.val()); 101 } 102 103 104 105 106 /* 107 * Base class 108 * 109 */ 110 111 template<class VA, class VB, class VC, PropCond pc_ac> View(Home home,IdxViewArray<VA> & iv0,VB y0,VC y1)112 View<VA,VB,VC,pc_ac>::View(Home home, IdxViewArray<VA>& iv0, 113 VB y0, VC y1) 114 : Propagator(home), iv(iv0), x0(y0), x1(y1) { 115 x0.subscribe(home,*this,PC_INT_DOM); 116 x1.subscribe(home,*this,pc_ac); 117 iv.subscribe(home,*this,pc_ac); 118 } 119 120 template<class VA, class VB, class VC, PropCond pc_ac> 121 forceinline View(Space & home,View & p)122 View<VA,VB,VC,pc_ac>::View(Space& home, View& p) 123 : Propagator(home,p) { 124 x0.update(home,p.x0); 125 x1.update(home,p.x1); 126 iv.update(home,p.iv); 127 } 128 129 template<class VA, class VB, class VC, PropCond pc_ac> 130 PropCost cost(const Space &,const ModEventDelta &) const131 View<VA,VB,VC,pc_ac>::cost(const Space&, const ModEventDelta&) const { 132 // This is required for subscribing to variables in the 133 // above constructor, but this is then the only time this 134 // virtual function is ever used! 135 return PropCost::linear(PropCost::LO,iv.size()+2); 136 } 137 138 template<class VA, class VB, class VC, PropCond pc_ac> 139 void reschedule(Space & home)140 View<VA,VB,VC,pc_ac>::reschedule(Space& home) { 141 x0.reschedule(home,*this,PC_INT_DOM); 142 x1.reschedule(home,*this,pc_ac); 143 iv.reschedule(home,*this,pc_ac); 144 } 145 146 template<class VA, class VB, class VC, PropCond pc_ac> 147 forceinline size_t dispose(Space & home)148 View<VA,VB,VC,pc_ac>::dispose(Space& home) { 149 x0.cancel(home,*this,PC_INT_DOM); 150 x1.cancel(home,*this,pc_ac); 151 iv.cancel(home,*this,pc_ac); 152 (void) Propagator::dispose(home); 153 return sizeof(*this); 154 } 155 156 157 158 159 /** 160 * \brief Value iterator for indices in index-view map 161 * 162 */ 163 template<class View> 164 class IterIdxView { 165 private: 166 const IdxView<View> *cur, *end; 167 public: 168 IterIdxView(void); 169 IterIdxView(const IdxView<View>*, const IdxView<View>*); 170 void init(const IdxView<View>*, const IdxView<View>*); 171 bool operator ()(void) const; 172 void operator ++(void); 173 int val(void) const; 174 }; 175 176 template<class View> 177 forceinline IterIdxView(void)178 IterIdxView<View>::IterIdxView(void) {} 179 template<class View> 180 forceinline IterIdxView(const IdxView<View> * b,const IdxView<View> * e)181 IterIdxView<View>::IterIdxView(const IdxView<View>* b, 182 const IdxView<View>* e) 183 : cur(b), end(e) {} 184 template<class View> 185 forceinline void init(const IdxView<View> * b,const IdxView<View> * e)186 IterIdxView<View>::init(const IdxView<View>* b, 187 const IdxView<View>* e) { 188 cur=b; end=e; 189 } 190 template<class View> 191 forceinline bool operator ()(void) const192 IterIdxView<View>::operator ()(void) const { 193 return cur < end; 194 } 195 template<class View> 196 forceinline void operator ++(void)197 IterIdxView<View>::operator ++(void) { 198 cur++; 199 } 200 template<class View> 201 forceinline int val(void) const202 IterIdxView<View>::val(void) const { 203 return cur->idx; 204 } 205 206 207 208 209 /* 210 * Generic scanning: does all but computing new domain for result 211 * (which is specific to bounds/domain version) 212 * 213 */ 214 215 template<class VA, class VB, class VC, PropCond pc_ac, class RelTest> 216 ExecStatus scan(Space & home,IdxViewArray<VA> & iv,VB x0,VC x1,Propagator & p,RelTest rt)217 scan(Space& home, IdxViewArray<VA>& iv, 218 VB x0, VC x1, Propagator& p, RelTest rt) { 219 assert(iv.size() > 1); 220 /* 221 * Prunes pairs of index, variable 222 * - checks for idx value removed 223 * - checks for disequal variables 224 * 225 */ 226 ViewValues<VB> vx0(x0); 227 int i = 0; 228 int j = 0; 229 while (vx0() && (i < iv.size())) { 230 if (iv[i].idx < vx0.val()) { 231 iv[i].view.cancel(home,p,pc_ac); 232 ++i; 233 } else if (iv[i].idx > vx0.val()) { 234 ++vx0; 235 } else { 236 assert(iv[i].idx == vx0.val()); 237 switch (rt(iv[i].view,x1)) { 238 case RT_FALSE: 239 iv[i].view.cancel(home,p,pc_ac); 240 break; 241 case RT_TRUE: 242 case RT_MAYBE: 243 iv[j++] = iv[i]; 244 break; 245 default: GECODE_NEVER; 246 } 247 ++vx0; ++i; 248 } 249 } 250 while (i < iv.size()) 251 iv[i++].view.cancel(home,p,pc_ac); 252 bool adjust = (j<iv.size()); 253 iv.size(j); 254 255 if (iv.size() == 0) 256 return ES_FAILED; 257 258 if (iv.size() == 1) { 259 GECODE_ME_CHECK(x0.eq(home,iv[0].idx)); 260 } else if (adjust) { 261 IterIdxView<VA> v(&iv[0],&iv[0]+iv.size()); 262 GECODE_ME_CHECK(x0.narrow_v(home,v,false)); 263 assert(x0.size() == static_cast<unsigned int>(iv.size())); 264 } 265 return ES_OK; 266 } 267 268 269 270 271 /* 272 * Bounds consistent propagator 273 * 274 */ 275 276 template<class VA, class VB, class VC> 277 forceinline ViewBnd(Home home,IdxViewArray<VA> & iv,VB x0,VC x1)278 ViewBnd<VA,VB,VC>::ViewBnd(Home home, 279 IdxViewArray<VA>& iv, VB x0, VC x1) 280 : View<VA,VB,VC,PC_INT_BND>(home,iv,x0,x1) {} 281 282 template<class VA, class VB, class VC> 283 ExecStatus post(Home home,IdxViewArray<VA> & iv,VB x0,VC x1)284 ViewBnd<VA,VB,VC>::post(Home home, 285 IdxViewArray<VA>& iv, VB x0, VC x1) { 286 GECODE_ME_CHECK(x0.gq(home,0)); 287 GECODE_ME_CHECK(x0.le(home,iv.size())); 288 if (x0.assigned()) { 289 (void) new (home) Rel::EqBnd<VA,VC>(home,iv[x0.val()].view,x1); 290 return ES_OK; 291 } else { 292 assert(iv.size()>1); 293 (void) new (home) ViewBnd<VA,VB,VC>(home,iv,x0,x1); 294 } 295 return ES_OK; 296 } 297 298 299 template<class VA, class VB, class VC> 300 forceinline ViewBnd(Space & home,ViewBnd & p)301 ViewBnd<VA,VB,VC>::ViewBnd(Space& home, ViewBnd& p) 302 : View<VA,VB,VC,PC_INT_BND>(home,p) {} 303 304 template<class VA, class VB, class VC> 305 Actor* copy(Space & home)306 ViewBnd<VA,VB,VC>::copy(Space& home) { 307 return new (home) ViewBnd<VA,VB,VC>(home,*this); 308 } 309 310 template<class VA, class VB, class VC> 311 ExecStatus propagate(Space & home,const ModEventDelta &)312 ViewBnd<VA,VB,VC>::propagate(Space& home, const ModEventDelta&) { 313 assert(iv.size() > 1); 314 RelTestBnd<VA,VC> rt; 315 GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_BND,RelTestBnd<VA,VC> > 316 (home,iv,x0,x1,*this,rt))); 317 if (iv.size() == 1) { 318 ExecStatus es = home.ES_SUBSUMED(*this); 319 (void) new (home) Rel::EqBnd<VA,VC>(home(*this),iv[0].view,x1); 320 return es; 321 } 322 assert(iv.size() > 1); 323 // Compute new result 324 int min = iv[0].view.min(); 325 int max = iv[0].view.max(); 326 for (int i=1; i<iv.size(); i++) { 327 min = std::min(iv[i].view.min(),min); 328 max = std::max(iv[i].view.max(),max); 329 } 330 ExecStatus es = shared(x0,x1) ? ES_NOFIX : ES_FIX; 331 { 332 ModEvent me = x1.lq(home,max); 333 if (me_failed(me)) 334 return ES_FAILED; 335 if (me_modified(me) && (x1.max() != max)) 336 es = ES_NOFIX; 337 } 338 { 339 ModEvent me = x1.gq(home,min); 340 if (me_failed(me)) 341 return ES_FAILED; 342 if (me_modified(me) && (x1.min() != min)) 343 es = ES_NOFIX; 344 } 345 return (x1.assigned() && (min == max)) ? 346 home.ES_SUBSUMED(*this) : es; 347 } 348 349 350 351 352 353 /* 354 * Domain consistent propagator 355 * 356 */ 357 358 template<class VA, class VB, class VC> 359 forceinline ViewDom(Home home,IdxViewArray<VA> & iv,VB x0,VC x1)360 ViewDom<VA,VB,VC>::ViewDom(Home home, 361 IdxViewArray<VA>& iv, VB x0, VC x1) 362 : View<VA,VB,VC,PC_INT_DOM>(home,iv,x0,x1) {} 363 364 template<class VA, class VB, class VC> 365 ExecStatus post(Home home,IdxViewArray<VA> & iv,VB x0,VC x1)366 ViewDom<VA,VB,VC>::post(Home home, 367 IdxViewArray<VA>& iv, VB x0, VC x1){ 368 GECODE_ME_CHECK(x0.gq(home,0)); 369 GECODE_ME_CHECK(x0.le(home,iv.size())); 370 if (x0.assigned()) { 371 (void) new (home) Rel::EqDom<VA,VC>(home,iv[x0.val()].view,x1); 372 return ES_OK; 373 } else { 374 assert(iv.size()>1); 375 (void) new (home) ViewDom<VA,VB,VC>(home,iv,x0,x1); 376 } 377 return ES_OK; 378 } 379 380 381 template<class VA, class VB, class VC> 382 forceinline ViewDom(Space & home,ViewDom & p)383 ViewDom<VA,VB,VC>::ViewDom(Space& home, ViewDom& p) 384 : View<VA,VB,VC,PC_INT_DOM>(home,p) {} 385 386 template<class VA, class VB, class VC> 387 Actor* copy(Space & home)388 ViewDom<VA,VB,VC>::copy(Space& home) { 389 return new (home) ViewDom<VA,VB,VC>(home,*this); 390 } 391 392 393 template<class VA, class VB, class VC> 394 PropCost cost(const Space &,const ModEventDelta & med) const395 ViewDom<VA,VB,VC>::cost(const Space&, const ModEventDelta& med) const { 396 return PropCost::linear((VA::me(med) != ME_INT_DOM) ? 397 PropCost::LO : PropCost::HI, iv.size()+2); 398 } 399 400 template<class VA, class VB, class VC> 401 ExecStatus propagate(Space & home,const ModEventDelta & med)402 ViewDom<VA,VB,VC>::propagate(Space& home, const ModEventDelta& med) { 403 assert(iv.size() > 1); 404 if (VA::me(med) != ME_INT_DOM) { 405 RelTestBnd<VA,VC> rt; 406 GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestBnd<VA,VC> > 407 (home,iv,x0,x1,*this,rt))); 408 if (iv.size() == 1) { 409 ExecStatus es = home.ES_SUBSUMED(*this); 410 (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1); 411 return es; 412 } 413 // Compute new result 414 int min = iv[0].view.min(); 415 int max = iv[0].view.max(); 416 for (int i=1; i<iv.size(); i++) { 417 min = std::min(iv[i].view.min(),min); 418 max = std::max(iv[i].view.max(),max); 419 } 420 GECODE_ME_CHECK(x1.lq(home,max)); 421 GECODE_ME_CHECK(x1.gq(home,min)); 422 return (x1.assigned() && (min == max)) ? 423 home.ES_SUBSUMED(*this) : 424 home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM)); 425 } 426 RelTestDom<VA,VC> rt; 427 GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestDom<VA,VC> > 428 (home,iv,x0,x1,*this,rt))); 429 if (iv.size() == 1) { 430 ExecStatus es = home.ES_SUBSUMED(*this); 431 (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1); 432 return es; 433 } 434 assert(iv.size() > 1); 435 436 if (x1.assigned()) { 437 for (int i=0; i<iv.size(); i++) 438 if (iv[i].view.in(x1.val())) 439 return shared(x0,x1) ? ES_NOFIX : ES_FIX; 440 return ES_FAILED; 441 } else { 442 Region r; 443 ViewRanges<VA>* i_view = r.alloc<ViewRanges<VA> >(iv.size()); 444 for (int i=0; i<iv.size(); i++) 445 i_view[i].init(iv[i].view); 446 Iter::Ranges::NaryUnion i_val(r, i_view, iv.size()); 447 ModEvent me = x1.inter_r(home,i_val); 448 r.free<ViewRanges<VA> >(i_view,iv.size()); 449 GECODE_ME_CHECK(me); 450 return (shared(x0,x1) || me_modified(me)) ? ES_NOFIX : ES_FIX; 451 } 452 } 453 454 }}} 455 456 // STATISTICS: int-prop 457 458