propagator.hpp

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