Generated on Wed Jan 4 17:49:11 2006 for Gecode by doxygen 1.4.6

propagator.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2002
00008  *     Guido Tack, 2004
00009  *
00010  *  Last modified:
00011  *     $Date: 2005-07-31 21:42:01 +0200 (Sun, 31 Jul 2005) $ by $Author: schulte $
00012  *     $Revision: 2097 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
00021  *
00022  */
00023 
00024 namespace Gecode {
00025 
00032   PropCost cost_lo(int n, PropCost pc);
00039   PropCost cost_hi(int n, PropCost pc);
00040 
00041 
00056   template <class View, PropCond pc>
00057   class UnaryPropagator : public Propagator {
00058   protected:
00060     View x0;
00062     UnaryPropagator(Space* home, bool share, UnaryPropagator& p);
00064     UnaryPropagator(Space* home, View x0, bool fd=false);
00065   public:
00067     virtual PropCost cost(void) const;
00069     virtual ~UnaryPropagator(void);
00070   };
00071 
00077   template <class View, PropCond pc>
00078   class BinaryPropagator : public Propagator {
00079   protected:
00081     View x0, x1;
00083     BinaryPropagator(Space* home, bool share, BinaryPropagator& p);
00085     BinaryPropagator(Space* home, View x0, View x1, bool fd=false);
00086   public:
00088     virtual PropCost cost(void) const;
00090     virtual ~BinaryPropagator(void);
00091   };
00092 
00098   template <class View, PropCond pc>
00099   class TernaryPropagator : public Propagator {
00100   protected:
00102     View x0, x1, x2;
00104     TernaryPropagator(Space* home, bool share, TernaryPropagator& p);
00106     TernaryPropagator(Space* home, View x0, View x1, View x2, bool fd=false);
00107   public:
00109     virtual PropCost cost(void) const;
00111     virtual ~TernaryPropagator(void);
00112   };
00113 
00119   template <class View, PropCond pc>
00120   class NaryPropagator : public Propagator {
00121   protected:
00123     ViewArray<View> x;
00125     NaryPropagator(Space* home, bool share, NaryPropagator& p);
00127     NaryPropagator(Space* home, ViewArray<View>& x, bool fd=false);
00128   public:
00130     virtual PropCost cost(void) const;
00132     virtual ~NaryPropagator(void);
00133   };
00134 
00141   template <class View, PropCond pc>
00142   class NaryOnePropagator : public Propagator {
00143   protected:
00145     ViewArray<View> x; 
00147     View y;
00149     NaryOnePropagator(Space* home, bool share, NaryOnePropagator& p);
00151     NaryOnePropagator(Space* home, ViewArray<View>& x, View y, bool fd=false);
00152   public:
00154     virtual PropCost cost(void) const;
00156     virtual ~NaryOnePropagator(void);
00157   };
00159 
00160 
00161 
00162 
00163 
00164 
00165   /*
00166    * Dynamic cost computation
00167    *
00168    */
00169 
00170   forceinline PropCost
00171   cost_lo(int n, PropCost c) {
00172     if (n > 3) return c;
00173     if (n < 2) return PC_UNARY_LO;
00174     return (n > 2) ? PC_TERNARY_LO : PC_BINARY_LO;
00175   }
00176 
00177   forceinline PropCost
00178   cost_hi(int n, PropCost c) {
00179     if (n > 3) return c;
00180     if (n < 2) return PC_UNARY_HI;
00181     return (n > 2) ? PC_TERNARY_HI : PC_BINARY_HI;
00182   }
00183 
00184   /*
00185    * Unary propagators
00186    *
00187    */
00188 
00189   template <class View, PropCond pc>
00190   UnaryPropagator<View,pc>::UnaryPropagator
00191   (Space* home, View y0, bool fd)
00192     : Propagator(home,fd), x0(y0) {
00193     x0.subscribe(home,this,pc);
00194   }
00195 
00196   template <class View, PropCond pc>
00197   forceinline
00198   UnaryPropagator<View,pc>::UnaryPropagator
00199   (Space* home, bool share, UnaryPropagator<View,pc>& p)
00200     : Propagator(home,share,p) {
00201     x0.update(home,share,p.x0);
00202   }
00203 
00204   template <class View, PropCond pc>
00205   PropCost
00206   UnaryPropagator<View,pc>::cost(void) const {
00207     return PC_UNARY_LO;
00208   }
00209 
00210   template <class View, PropCond pc>
00211   UnaryPropagator<View,pc>::~UnaryPropagator(void) {
00212     x0.cancel(this,pc);
00213   }
00214 
00215 
00216   /*
00217    * Binary propagators
00218    *
00219    */
00220 
00221   template <class View, PropCond pc>
00222   BinaryPropagator<View,pc>::BinaryPropagator
00223   (Space* home, View y0, View y1, bool fd)
00224     : Propagator(home,fd), x0(y0), x1(y1) {
00225     x0.subscribe(home,this,pc);
00226     x1.subscribe(home,this,pc);
00227   }
00228 
00229   template <class View, PropCond pc>
00230   forceinline
00231   BinaryPropagator<View,pc>::BinaryPropagator
00232   (Space* home, bool share, BinaryPropagator<View,pc>& p)
00233     : Propagator(home,share,p) {
00234     x0.update(home,share,p.x0);
00235     x1.update(home,share,p.x1);
00236   }
00237 
00238   template <class View, PropCond pc>
00239   PropCost
00240   BinaryPropagator<View,pc>::cost(void) const {
00241     return PC_BINARY_LO;
00242   }
00243 
00244   template <class View, PropCond pc>
00245   BinaryPropagator<View,pc>::~BinaryPropagator(void) {
00246     x0.cancel(this,pc);
00247     x1.cancel(this,pc);
00248   }
00249 
00250 
00251   /*
00252    * Ternary propagators
00253    *
00254    */
00255 
00256   template <class View, PropCond pc>
00257   TernaryPropagator<View,pc>::TernaryPropagator
00258   (Space* home, View y0, View y1, View y2, bool fd)
00259     : Propagator(home,fd), x0(y0), x1(y1), x2(y2) {
00260     x0.subscribe(home,this,pc);
00261     x1.subscribe(home,this,pc);
00262     x2.subscribe(home,this,pc);
00263   }
00264 
00265   template <class View, PropCond pc>
00266   forceinline
00267   TernaryPropagator<View,pc>::TernaryPropagator
00268   (Space* home, bool share, TernaryPropagator<View,pc>& p)
00269     : Propagator(home,share,p) {
00270     x0.update(home,share,p.x0);
00271     x1.update(home,share,p.x1);
00272     x2.update(home,share,p.x2);
00273   }
00274 
00275   template <class View, PropCond pc>
00276   PropCost
00277   TernaryPropagator<View,pc>::cost(void) const {
00278     return PC_TERNARY_LO;
00279   }
00280 
00281   template <class View, PropCond pc>
00282   TernaryPropagator<View,pc>::~TernaryPropagator(void) {
00283     x0.cancel(this,pc);
00284     x1.cancel(this,pc);
00285     x2.cancel(this,pc);
00286   }
00287 
00288 
00289   /*
00290    * Nary propagators
00291    *
00292    */
00293 
00294   template <class View, PropCond pc>
00295   NaryPropagator<View,pc>::NaryPropagator
00296   (Space* home, ViewArray<View>& y, bool fd)
00297     : Propagator(home,fd), x(y) {
00298     x.subscribe(home,this,pc);
00299   }
00300 
00301   template <class View, PropCond pc>
00302   forceinline
00303   NaryPropagator<View,pc>::NaryPropagator
00304   (Space* home, bool share, NaryPropagator<View,pc>& p)
00305     : Propagator(home,share,p) {
00306     x.update(home,share,p.x);
00307   }
00308 
00309   template <class View, PropCond pc>
00310   PropCost
00311   NaryPropagator<View,pc>::cost(void) const {
00312     return cost_lo(x.size(), PC_LINEAR_LO);
00313   }
00314 
00315   template <class View, PropCond pc>
00316   NaryPropagator<View,pc>::~NaryPropagator(void) {
00317     x.cancel(this,pc);
00318   }
00319 
00320 
00321   /*
00322    * NaryOne (one additional variable) propagators
00323    *
00324    */
00325 
00326   template <class View, PropCond pc>
00327   NaryOnePropagator<View,pc>::NaryOnePropagator
00328   (Space* home, ViewArray<View>& x0, View y0, bool fd)
00329     : Propagator(home,fd), x(x0), y(y0) {
00330     x.subscribe(home,this,pc);
00331     y.subscribe(home,this,pc);
00332   }
00333 
00334   template <class View, PropCond pc>
00335   forceinline
00336   NaryOnePropagator<View,pc>::NaryOnePropagator
00337   (Space* home, bool share, NaryOnePropagator<View,pc>& p)
00338     : Propagator(home,share,p) {
00339     x.update(home,share,p.x);
00340     y.update(home,share,p.y);
00341   }
00342 
00343   template <class View, PropCond pc>
00344   PropCost
00345   NaryOnePropagator<View,pc>::cost(void) const {
00346     return cost_lo(x.size()+1, PC_LINEAR_LO);
00347   }
00348 
00349   template <class View, PropCond pc>
00350   NaryOnePropagator<View,pc>::~NaryOnePropagator(void) {
00351     x.cancel(this,pc);
00352     y.cancel(this,pc);
00353   }
00354 
00355 }
00356 
00357 // STATISTICS: kernel-other