propagator.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 * Guido Tack <tack@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2002 00009 * Guido Tack, 2004 00010 * 00011 * Last modified: 00012 * $Date: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $ 00013 * $Revision: 9878 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 namespace Gecode { 00041 00058 template<class View, PropCond pc> 00059 class UnaryPropagator : public Propagator { 00060 protected: 00062 View x0; 00064 UnaryPropagator(Space& home, bool share, UnaryPropagator& p); 00066 UnaryPropagator(Space& home, bool share, Propagator& p, 00067 View x0); 00069 UnaryPropagator(Home home, View x0); 00070 public: 00072 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00074 virtual size_t dispose(Space& home); 00075 }; 00076 00086 template<class View, PropCond pc> 00087 class BinaryPropagator : public Propagator { 00088 protected: 00090 View x0, x1; 00092 BinaryPropagator(Space& home, bool share, BinaryPropagator& p); 00094 BinaryPropagator(Home home, View x0, View x1); 00096 BinaryPropagator(Space& home, bool share, Propagator& p, 00097 View x0, View x1); 00098 public: 00100 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00102 virtual size_t dispose(Space& home); 00103 }; 00104 00114 template<class View, PropCond pc> 00115 class TernaryPropagator : public Propagator { 00116 protected: 00118 View x0, x1, x2; 00120 TernaryPropagator(Space& home, bool share, TernaryPropagator& p); 00122 TernaryPropagator(Home home, View x0, View x1, View x2); 00124 TernaryPropagator(Space& home, bool share, Propagator& p, 00125 View x0, View x1, View x2); 00126 public: 00128 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00130 virtual size_t dispose(Space& home); 00131 }; 00132 00142 template<class View, PropCond pc> 00143 class NaryPropagator : public Propagator { 00144 protected: 00146 ViewArray<View> x; 00148 NaryPropagator(Space& home, bool share, NaryPropagator& p); 00150 NaryPropagator(Space& home, bool share, Propagator& p, 00151 ViewArray<View>& x); 00153 NaryPropagator(Home home, ViewArray<View>& x); 00154 public: 00156 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00158 virtual size_t dispose(Space& home); 00159 }; 00160 00171 template<class View, PropCond pc> 00172 class NaryOnePropagator : public Propagator { 00173 protected: 00175 ViewArray<View> x; 00177 View y; 00179 NaryOnePropagator(Space& home, bool share, NaryOnePropagator& p); 00181 NaryOnePropagator(Space& home, bool share, Propagator& p, 00182 ViewArray<View>& x, View y); 00184 NaryOnePropagator(Home home, ViewArray<View>& x, View y); 00185 public: 00187 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00189 virtual size_t dispose(Space& home); 00190 }; 00191 00202 template<class View0, PropCond pc0, class View1, PropCond pc1> 00203 class MixBinaryPropagator : public Propagator { 00204 protected: 00206 View0 x0; 00208 View1 x1; 00210 MixBinaryPropagator(Space& home,bool,MixBinaryPropagator&); 00212 MixBinaryPropagator(Home home,View0,View1); 00214 MixBinaryPropagator(Space& home, bool share, Propagator& p, 00215 View0 x0, View1 x1); 00216 public: 00218 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00220 virtual size_t dispose(Space& home); 00221 }; 00222 00233 template<class View0, PropCond pc0, class View1, PropCond pc1, 00234 class View2, PropCond pc2> 00235 class MixTernaryPropagator : public Propagator { 00236 protected: 00238 View0 x0; 00240 View1 x1; 00242 View2 x2; 00244 MixTernaryPropagator(Space& home, bool share, MixTernaryPropagator& p); 00246 MixTernaryPropagator(Home home, View0 x0, View1 x1, View2 x2); 00248 MixTernaryPropagator(Space& home, bool share, Propagator& p, 00249 View0 x0, View1 x1, View2 x2); 00250 public: 00252 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00254 virtual size_t dispose(Space& home); 00255 }; 00256 00267 template<class View0, PropCond pc0, class View1, PropCond pc1> 00268 class MixNaryOnePropagator : public Propagator { 00269 protected: 00271 ViewArray<View0> x; 00273 View1 y; 00275 MixNaryOnePropagator(Space& home, bool share, MixNaryOnePropagator& p); 00277 MixNaryOnePropagator(Home home, ViewArray<View0>& x, View1 y); 00279 MixNaryOnePropagator(Space& home, bool share, Propagator& p, 00280 ViewArray<View0>& x, View1 y); 00281 public: 00283 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 00285 virtual size_t dispose(Space& home); 00286 }; 00288 00289 00290 /* 00291 * Unary propagators 00292 * 00293 */ 00294 00295 template<class View, PropCond pc> 00296 UnaryPropagator<View,pc>::UnaryPropagator(Home home, View y0) 00297 : Propagator(home), x0(y0) { 00298 if (pc != PC_GEN_NONE) 00299 x0.subscribe(home,*this,pc); 00300 } 00301 00302 template<class View, PropCond pc> 00303 forceinline 00304 UnaryPropagator<View,pc>::UnaryPropagator 00305 (Space& home, bool share, UnaryPropagator<View,pc>& p) 00306 : Propagator(home,share,p) { 00307 x0.update(home,share,p.x0); 00308 } 00309 00310 template<class View, PropCond pc> 00311 forceinline 00312 UnaryPropagator<View,pc>::UnaryPropagator 00313 (Space& home, bool share, Propagator& p, View y0) 00314 : Propagator(home,share,p) { 00315 x0.update(home,share,y0); 00316 } 00317 00318 template<class View, PropCond pc> 00319 PropCost 00320 UnaryPropagator<View,pc>::cost(const Space&, const ModEventDelta&) const { 00321 return PropCost::unary(PropCost::LO); 00322 } 00323 00324 template<class View, PropCond pc> 00325 forceinline size_t 00326 UnaryPropagator<View,pc>::dispose(Space& home) { 00327 if (pc != PC_GEN_NONE) 00328 x0.cancel(home,*this,pc); 00329 (void) Propagator::dispose(home); 00330 return sizeof(*this); 00331 } 00332 00333 00334 /* 00335 * Binary propagators 00336 * 00337 */ 00338 00339 template<class View, PropCond pc> 00340 BinaryPropagator<View,pc>::BinaryPropagator(Home home, View y0, View y1) 00341 : Propagator(home), x0(y0), x1(y1) { 00342 if (pc != PC_GEN_NONE) { 00343 x0.subscribe(home,*this,pc); 00344 x1.subscribe(home,*this,pc); 00345 } 00346 } 00347 00348 template<class View, PropCond pc> 00349 forceinline 00350 BinaryPropagator<View,pc>::BinaryPropagator 00351 (Space& home, bool share, BinaryPropagator<View,pc>& p) 00352 : Propagator(home,share,p) { 00353 x0.update(home,share,p.x0); 00354 x1.update(home,share,p.x1); 00355 } 00356 00357 template<class View, PropCond pc> 00358 forceinline 00359 BinaryPropagator<View,pc>::BinaryPropagator 00360 (Space& home, bool share, Propagator& p, View y0, View y1) 00361 : Propagator(home,share,p) { 00362 x0.update(home,share,y0); 00363 x1.update(home,share,y1); 00364 } 00365 00366 template<class View, PropCond pc> 00367 PropCost 00368 BinaryPropagator<View,pc>::cost(const Space&, const ModEventDelta&) const { 00369 return PropCost::binary(PropCost::LO); 00370 } 00371 00372 template<class View, PropCond pc> 00373 forceinline size_t 00374 BinaryPropagator<View,pc>::dispose(Space& home) { 00375 if (pc != PC_GEN_NONE) { 00376 x0.cancel(home,*this,pc); 00377 x1.cancel(home,*this,pc); 00378 } 00379 (void) Propagator::dispose(home); 00380 return sizeof(*this); 00381 } 00382 00383 /* 00384 * Ternary propagators 00385 * 00386 */ 00387 00388 template<class View, PropCond pc> 00389 TernaryPropagator<View,pc>::TernaryPropagator 00390 (Home home, View y0, View y1, View y2) 00391 : Propagator(home), x0(y0), x1(y1), x2(y2) { 00392 if (pc != PC_GEN_NONE) { 00393 x0.subscribe(home,*this,pc); 00394 x1.subscribe(home,*this,pc); 00395 x2.subscribe(home,*this,pc); 00396 } 00397 } 00398 00399 template<class View, PropCond pc> 00400 forceinline 00401 TernaryPropagator<View,pc>::TernaryPropagator 00402 (Space& home, bool share, TernaryPropagator<View,pc>& p) 00403 : Propagator(home,share,p) { 00404 x0.update(home,share,p.x0); 00405 x1.update(home,share,p.x1); 00406 x2.update(home,share,p.x2); 00407 } 00408 00409 template<class View, PropCond pc> 00410 forceinline 00411 TernaryPropagator<View,pc>::TernaryPropagator 00412 (Space& home, bool share, Propagator& p, View y0, View y1, View y2) 00413 : Propagator(home,share,p) { 00414 x0.update(home,share,y0); 00415 x1.update(home,share,y1); 00416 x2.update(home,share,y2); 00417 } 00418 00419 template<class View, PropCond pc> 00420 PropCost 00421 TernaryPropagator<View,pc>::cost(const Space&, const ModEventDelta&) const { 00422 return PropCost::ternary(PropCost::LO);; 00423 } 00424 00425 template<class View, PropCond pc> 00426 forceinline size_t 00427 TernaryPropagator<View,pc>::dispose(Space& home) { 00428 if (pc != PC_GEN_NONE) { 00429 x0.cancel(home,*this,pc); 00430 x1.cancel(home,*this,pc); 00431 x2.cancel(home,*this,pc); 00432 } 00433 (void) Propagator::dispose(home); 00434 return sizeof(*this); 00435 } 00436 00437 /* 00438 * Nary propagators 00439 * 00440 */ 00441 00442 template<class View, PropCond pc> 00443 NaryPropagator<View,pc>::NaryPropagator 00444 (Home home, ViewArray<View>& y) 00445 : Propagator(home), x(y) { 00446 if (pc != PC_GEN_NONE) 00447 x.subscribe(home,*this,pc); 00448 } 00449 00450 template<class View, PropCond pc> 00451 forceinline 00452 NaryPropagator<View,pc>::NaryPropagator 00453 (Space& home, bool share, NaryPropagator<View,pc>& p) 00454 : Propagator(home,share,p) { 00455 x.update(home,share,p.x); 00456 } 00457 00458 template<class View, PropCond pc> 00459 forceinline 00460 NaryPropagator<View,pc>::NaryPropagator 00461 (Space& home, bool share, Propagator& p, ViewArray<View>& x0) 00462 : Propagator(home,share,p) { 00463 x.update(home,share,x0); 00464 } 00465 00466 template<class View, PropCond pc> 00467 PropCost 00468 NaryPropagator<View,pc>::cost(const Space&, const ModEventDelta&) const { 00469 return PropCost::linear(PropCost::LO,x.size()); 00470 } 00471 00472 template<class View, PropCond pc> 00473 forceinline size_t 00474 NaryPropagator<View,pc>::dispose(Space& home) { 00475 if (pc != PC_GEN_NONE) 00476 x.cancel(home,*this,pc); 00477 (void) Propagator::dispose(home); 00478 return sizeof(*this); 00479 } 00480 00481 /* 00482 * NaryOne (one additional variable) propagators 00483 * 00484 */ 00485 00486 template<class View, PropCond pc> 00487 NaryOnePropagator<View,pc>::NaryOnePropagator 00488 (Home home, ViewArray<View>& x0, View y0) 00489 : Propagator(home), x(x0), y(y0) { 00490 if (pc != PC_GEN_NONE) { 00491 x.subscribe(home,*this,pc); 00492 y.subscribe(home,*this,pc); 00493 } 00494 } 00495 00496 template<class View, PropCond pc> 00497 forceinline 00498 NaryOnePropagator<View,pc>::NaryOnePropagator 00499 (Space& home, bool share, NaryOnePropagator<View,pc>& p) 00500 : Propagator(home,share,p) { 00501 x.update(home,share,p.x); 00502 y.update(home,share,p.y); 00503 } 00504 00505 template<class View, PropCond pc> 00506 forceinline 00507 NaryOnePropagator<View,pc>::NaryOnePropagator 00508 (Space& home, bool share, Propagator& p, ViewArray<View>& x0, View y0) 00509 : Propagator(home,share,p) { 00510 x.update(home,share,x0); 00511 y.update(home,share,y0); 00512 } 00513 00514 template<class View, PropCond pc> 00515 PropCost 00516 NaryOnePropagator<View,pc>::cost(const Space&, const ModEventDelta&) const { 00517 return PropCost::linear(PropCost::LO,x.size()+1); 00518 } 00519 00520 template<class View, PropCond pc> 00521 forceinline size_t 00522 NaryOnePropagator<View,pc>::dispose(Space& home) { 00523 if (pc != PC_GEN_NONE) { 00524 x.cancel(home,*this,pc); 00525 y.cancel(home,*this,pc); 00526 } 00527 (void) Propagator::dispose(home); 00528 return sizeof(*this); 00529 } 00530 00531 /* 00532 * Mixed binary propagators 00533 * 00534 */ 00535 00536 template<class View0, PropCond pc0, class View1, PropCond pc1> 00537 MixBinaryPropagator<View0,pc0,View1,pc1>::MixBinaryPropagator 00538 (Home home, View0 y0, View1 y1) 00539 : Propagator(home), x0(y0), x1(y1) { 00540 if (pc0 != PC_GEN_NONE) 00541 x0.subscribe(home,*this,pc0); 00542 if (pc1 != PC_GEN_NONE) 00543 x1.subscribe(home,*this,pc1); 00544 } 00545 00546 template<class View0, PropCond pc0, class View1, PropCond pc1> 00547 forceinline 00548 MixBinaryPropagator<View0,pc0,View1,pc1>::MixBinaryPropagator 00549 (Space& home, bool share, MixBinaryPropagator<View0,pc0,View1,pc1>& p) 00550 : Propagator(home,share,p) { 00551 x0.update(home,share,p.x0); 00552 x1.update(home,share,p.x1); 00553 } 00554 00555 template<class View0, PropCond pc0, class View1, PropCond pc1> 00556 forceinline 00557 MixBinaryPropagator<View0,pc0,View1,pc1>::MixBinaryPropagator 00558 (Space& home, bool share, Propagator& p, View0 y0, View1 y1) 00559 : Propagator(home,share,p) { 00560 x0.update(home,share,y0); 00561 x1.update(home,share,y1); 00562 } 00563 00564 template<class View0, PropCond pc0, class View1, PropCond pc1> 00565 PropCost 00566 MixBinaryPropagator<View0,pc0,View1,pc1>::cost(const Space&, 00567 const ModEventDelta&) const { 00568 return PropCost::binary(PropCost::LO); 00569 } 00570 00571 template<class View0, PropCond pc0, class View1, PropCond pc1> 00572 forceinline size_t 00573 MixBinaryPropagator<View0,pc0,View1,pc1>::dispose(Space& home) { 00574 if (pc0 != PC_GEN_NONE) 00575 x0.cancel(home,*this,pc0); 00576 if (pc1 != PC_GEN_NONE) 00577 x1.cancel(home,*this,pc1); 00578 (void) Propagator::dispose(home); 00579 return sizeof(*this); 00580 } 00581 00582 /* 00583 * Mixed ternary propagators 00584 * 00585 */ 00586 00587 template<class View0, PropCond pc0, class View1, PropCond pc1, 00588 class View2, PropCond pc2> 00589 MixTernaryPropagator<View0,pc0,View1,pc1,View2,pc2>:: 00590 MixTernaryPropagator(Home home, View0 y0, View1 y1, View2 y2) 00591 : Propagator(home), x0(y0), x1(y1), x2(y2) { 00592 if (pc0 != PC_GEN_NONE) 00593 x0.subscribe(home,*this,pc0); 00594 if (pc1 != PC_GEN_NONE) 00595 x1.subscribe(home,*this,pc1); 00596 if (pc2 != PC_GEN_NONE) 00597 x2.subscribe(home,*this,pc2); 00598 } 00599 00600 template<class View0, PropCond pc0, class View1, PropCond pc1, 00601 class View2, PropCond pc2> 00602 forceinline 00603 MixTernaryPropagator<View0,pc0,View1,pc1,View2,pc2>:: 00604 MixTernaryPropagator(Space& home, bool share, 00605 MixTernaryPropagator<View0,pc0,View1,pc1, 00606 View2,pc2>& p) 00607 : Propagator(home,share,p) { 00608 x0.update(home,share,p.x0); 00609 x1.update(home,share,p.x1); 00610 x2.update(home,share,p.x2); 00611 } 00612 00613 template<class View0, PropCond pc0, class View1, PropCond pc1, 00614 class View2, PropCond pc2> 00615 forceinline 00616 MixTernaryPropagator<View0,pc0,View1,pc1,View2,pc2>::MixTernaryPropagator 00617 (Space& home, bool share, Propagator& p, View0 y0, View1 y1, View2 y2) 00618 : Propagator(home,share,p) { 00619 x0.update(home,share,y0); 00620 x1.update(home,share,y1); 00621 x2.update(home,share,y2); 00622 } 00623 00624 template<class View0, PropCond pc0, class View1, PropCond pc1, 00625 class View2, PropCond pc2> 00626 PropCost 00627 MixTernaryPropagator<View0,pc0,View1,pc1,View2,pc2>:: 00628 cost(const Space&, const ModEventDelta&) const { 00629 return PropCost::ternary(PropCost::LO); 00630 } 00631 00632 template<class View0, PropCond pc0, class View1, PropCond pc1, 00633 class View2, PropCond pc2> 00634 forceinline size_t 00635 MixTernaryPropagator<View0,pc0,View1,pc1,View2,pc2>::dispose(Space& home) { 00636 if (pc0 != PC_GEN_NONE) 00637 x0.cancel(home,*this,pc0); 00638 if (pc1 != PC_GEN_NONE) 00639 x1.cancel(home,*this,pc1); 00640 if (pc2 != PC_GEN_NONE) 00641 x2.cancel(home,*this,pc2); 00642 (void) Propagator::dispose(home); 00643 return sizeof(*this); 00644 } 00645 00646 /* 00647 * MixNaryOne (one additional variable) propagators 00648 * 00649 */ 00650 00651 template<class View0, PropCond pc0, class View1, PropCond pc1> 00652 MixNaryOnePropagator<View0,pc0,View1,pc1>::MixNaryOnePropagator 00653 (Home home, ViewArray<View0>& x0, View1 y0) 00654 : Propagator(home), x(x0), y(y0) { 00655 if (pc0 != PC_GEN_NONE) 00656 x.subscribe(home,*this,pc0); 00657 if (pc1 != PC_GEN_NONE) 00658 y.subscribe(home,*this,pc1); 00659 } 00660 00661 template<class View0, PropCond pc0, class View1, PropCond pc1> 00662 forceinline 00663 MixNaryOnePropagator<View0,pc0,View1,pc1>::MixNaryOnePropagator 00664 (Space& home, bool share, MixNaryOnePropagator<View0,pc0,View1,pc1>& p) 00665 : Propagator(home,share,p) { 00666 x.update(home,share,p.x); 00667 y.update(home,share,p.y); 00668 } 00669 00670 template<class View0, PropCond pc0, class View1, PropCond pc1> 00671 forceinline 00672 MixNaryOnePropagator<View0,pc0,View1,pc1>::MixNaryOnePropagator 00673 (Space& home, bool share, Propagator& p, ViewArray<View0>& x0, View1 y0) 00674 : Propagator(home,share,p) { 00675 x.update(home,share,x0); 00676 y.update(home,share,y0); 00677 } 00678 00679 template<class View0, PropCond pc0, class View1, PropCond pc1> 00680 PropCost 00681 MixNaryOnePropagator<View0,pc0,View1,pc1>::cost(const Space&, 00682 const ModEventDelta&) const { 00683 return PropCost::linear(PropCost::LO,x.size()+1); 00684 } 00685 00686 template<class View0, PropCond pc0, class View1, PropCond pc1> 00687 forceinline size_t 00688 MixNaryOnePropagator<View0,pc0,View1,pc1>::dispose(Space& home) { 00689 if (pc0 != PC_GEN_NONE) 00690 x.cancel(home,*this,pc0); 00691 if (pc1 != PC_GEN_NONE) 00692 y.cancel(home,*this,pc1); 00693 (void) Propagator::dispose(home); 00694 return sizeof(*this); 00695 } 00696 00697 } 00698 00699 // STATISTICS: kernel-prop