propagator.icc

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: 2006-08-04 16:03:05 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
00012  *     $Revision: 3510 $
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 
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(Space* home, View x0, bool fd=false);
00070   public:
00072     virtual PropCost cost(void) const;
00074     virtual size_t dispose(Space* home);
00075   };
00076 
00082   template <class View, PropCond pc>
00083   class BinaryPropagator : public Propagator {
00084   protected:
00086     View x0, x1;
00088     BinaryPropagator(Space* home, bool share, BinaryPropagator& p);
00090     BinaryPropagator(Space* home, View x0, View x1, bool fd=false);
00092     BinaryPropagator(Space* home, bool share, Propagator& p,
00093                      View x0, View x1);
00094   public:
00096     virtual PropCost cost(void) const;
00098     virtual size_t dispose(Space* home);
00099   };
00100 
00106   template <class View, PropCond pc>
00107   class TernaryPropagator : public Propagator {
00108   protected:
00110     View x0, x1, x2;
00112     TernaryPropagator(Space* home, bool share, TernaryPropagator& p);
00114     TernaryPropagator(Space* home, View x0, View x1, View x2, bool fd=false);
00116     TernaryPropagator(Space* home, bool share, Propagator& p,
00117                       View x0, View x1, View x2);
00118   public:
00120     virtual PropCost cost(void) const;
00122     virtual size_t dispose(Space* home);
00123   };
00124 
00130   template <class View, PropCond pc>
00131   class NaryPropagator : public Propagator {
00132   protected:
00134     ViewArray<View> x;
00136     NaryPropagator(Space* home, bool share, NaryPropagator& p);
00138     NaryPropagator(Space* home, bool share, Propagator& p,
00139                    ViewArray<View>& x);
00141     NaryPropagator(Space* home, ViewArray<View>& x, bool fd=false);
00142   public:
00144     virtual PropCost cost(void) const;
00146     virtual size_t dispose(Space* home);
00147   };
00148 
00155   template <class View, PropCond pc>
00156   class NaryOnePropagator : public Propagator {
00157   protected:
00159     ViewArray<View> x;
00161     View y;
00163     NaryOnePropagator(Space* home, bool share, NaryOnePropagator& p);
00165     NaryOnePropagator(Space* home, bool share, Propagator& p,
00166                       ViewArray<View>& x, View y);
00168     NaryOnePropagator(Space* home, ViewArray<View>& x, View y, bool fd=false);
00169   public:
00171     virtual PropCost cost(void) const;
00173     virtual size_t dispose(Space* home);
00174   };
00175 
00182   template <class View0, PropCond pc0, class View1, PropCond pc1>
00183   class InhomBinaryPropagator : public Propagator {
00184   protected:
00185     View0 x0;
00186     View1 x1;
00188     InhomBinaryPropagator(Space* home,bool,InhomBinaryPropagator&);
00190     InhomBinaryPropagator(Space* home,View0,View1,bool=false);
00192     InhomBinaryPropagator(Space* home, bool share, Propagator& p,
00193                           View0 x0, View1 x1);
00194   public:
00196     virtual PropCost cost(void) const;
00198     virtual size_t dispose(Space* home);
00199   };
00200 
00207   template <class View0, PropCond pc0, class View1, PropCond pc1,
00208             class View2, PropCond pc2>
00209   class InhomTernaryPropagator : public Propagator {
00210   protected:
00211     View0 x0;
00212     View1 x1;
00213     View2 x2;
00215     InhomTernaryPropagator(Space* home,bool,InhomTernaryPropagator&);
00217     InhomTernaryPropagator(Space* home,View0,View1,View2,bool=false);
00219     InhomTernaryPropagator(Space* home, bool share, Propagator& p,
00220                            View0 x0, View1 x1, View2 x2);
00221   public:
00223     virtual PropCost cost(void) const;
00225     virtual size_t dispose(Space* home);
00226   };
00227 
00234   template <class View0, PropCond pc0, class View1, PropCond pc1>
00235   class InhomNaryOnePropagator : public Propagator {
00236   protected:
00238     ViewArray<View0> x;
00240     View1 y;
00242     InhomNaryOnePropagator(Space* home, bool share, InhomNaryOnePropagator& p);
00244     InhomNaryOnePropagator(Space* home, ViewArray<View0>& x, View1 y,
00245                            bool fd=false);
00247     InhomNaryOnePropagator(Space* home, bool share, Propagator& p,
00248                            ViewArray<View0>& x, View1 y);
00249   public:
00251     virtual PropCost cost(void) const;
00253     virtual size_t dispose(Space* home);
00254   };
00256 
00257 
00258 
00259 
00260 
00261 
00262   /*
00263    * Dynamic cost computation
00264    *
00265    */
00266 
00267   forceinline PropCost
00268   cost_lo(int n, PropCost c) {
00269     if (n > 3) return c;
00270     if (n < 2) return PC_UNARY_LO;
00271     return (n > 2) ? PC_TERNARY_LO : PC_BINARY_LO;
00272   }
00273 
00274   forceinline PropCost
00275   cost_hi(int n, PropCost c) {
00276     if (n > 3) return c;
00277     if (n < 2) return PC_UNARY_HI;
00278     return (n > 2) ? PC_TERNARY_HI : PC_BINARY_HI;
00279   }
00280 
00281   /*
00282    * Unary propagators
00283    *
00284    */
00285 
00286   template <class View, PropCond pc>
00287   UnaryPropagator<View,pc>::UnaryPropagator
00288   (Space* home, View y0, bool fd)
00289     : Propagator(home,fd), x0(y0) {
00290     x0.subscribe(home,this,pc);
00291   }
00292 
00293   template <class View, PropCond pc>
00294   forceinline
00295   UnaryPropagator<View,pc>::UnaryPropagator
00296   (Space* home, bool share, UnaryPropagator<View,pc>& p)
00297     : Propagator(home,share,p) {
00298     x0.update(home,share,p.x0);
00299   }
00300 
00301   template <class View, PropCond pc>
00302   forceinline
00303   UnaryPropagator<View,pc>::UnaryPropagator
00304   (Space* home, bool share, Propagator& p, View y0)
00305     : Propagator(home,share,p) {
00306     x0.update(home,share,y0);
00307   }
00308 
00309   template <class View, PropCond pc>
00310   PropCost
00311   UnaryPropagator<View,pc>::cost(void) const {
00312     return PC_UNARY_LO;
00313   }
00314 
00315   template <class View, PropCond pc>
00316   size_t
00317   UnaryPropagator<View,pc>::dispose(Space* home) {
00318     if (!home->failed())
00319       x0.cancel(home,this,pc);
00320     (void) Propagator::dispose(home);
00321     return sizeof(*this);
00322   }
00323 
00324 
00325   /*
00326    * Binary propagators
00327    *
00328    */
00329 
00330   template <class View, PropCond pc>
00331   BinaryPropagator<View,pc>::BinaryPropagator
00332   (Space* home, View y0, View y1, bool fd)
00333     : Propagator(home,fd), x0(y0), x1(y1) {
00334     x0.subscribe(home,this,pc);
00335     x1.subscribe(home,this,pc);
00336   }
00337 
00338   template <class View, PropCond pc>
00339   forceinline
00340   BinaryPropagator<View,pc>::BinaryPropagator
00341   (Space* home, bool share, BinaryPropagator<View,pc>& p)
00342     : Propagator(home,share,p) {
00343     x0.update(home,share,p.x0);
00344     x1.update(home,share,p.x1);
00345   }
00346 
00347   template <class View, PropCond pc>
00348   forceinline
00349   BinaryPropagator<View,pc>::BinaryPropagator
00350   (Space* home, bool share, Propagator& p, View y0, View y1)
00351     : Propagator(home,share,p) {
00352     x0.update(home,share,y0);
00353     x1.update(home,share,y1);
00354   }
00355 
00356   template <class View, PropCond pc>
00357   PropCost
00358   BinaryPropagator<View,pc>::cost(void) const {
00359     return PC_BINARY_LO;
00360   }
00361 
00362   template <class View, PropCond pc>
00363   size_t
00364   BinaryPropagator<View,pc>::dispose(Space* home) {
00365     if (!home->failed()) {
00366       x0.cancel(home,this,pc);
00367       x1.cancel(home,this,pc);
00368     }
00369     (void) Propagator::dispose(home);
00370     return sizeof(*this);
00371   }
00372 
00373 
00374   /*
00375    * Ternary propagators
00376    *
00377    */
00378 
00379   template <class View, PropCond pc>
00380   TernaryPropagator<View,pc>::TernaryPropagator
00381   (Space* home, View y0, View y1, View y2, bool fd)
00382     : Propagator(home,fd), x0(y0), x1(y1), x2(y2) {
00383     x0.subscribe(home,this,pc);
00384     x1.subscribe(home,this,pc);
00385     x2.subscribe(home,this,pc);
00386   }
00387 
00388   template <class View, PropCond pc>
00389   forceinline
00390   TernaryPropagator<View,pc>::TernaryPropagator
00391   (Space* home, bool share, TernaryPropagator<View,pc>& p)
00392     : Propagator(home,share,p) {
00393     x0.update(home,share,p.x0);
00394     x1.update(home,share,p.x1);
00395     x2.update(home,share,p.x2);
00396   }
00397 
00398   template <class View, PropCond pc>
00399   forceinline
00400   TernaryPropagator<View,pc>::TernaryPropagator
00401   (Space* home, bool share, Propagator& p, View y0, View y1, View y2)
00402     : Propagator(home,share,p) {
00403     x0.update(home,share,y0);
00404     x1.update(home,share,y1);
00405     x2.update(home,share,y2);
00406   }
00407 
00408   template <class View, PropCond pc>
00409   PropCost
00410   TernaryPropagator<View,pc>::cost(void) const {
00411     return PC_TERNARY_LO;
00412   }
00413 
00414   template <class View, PropCond pc>
00415   size_t
00416   TernaryPropagator<View,pc>::dispose(Space* home) {
00417     if (!home->failed()) {
00418       x0.cancel(home,this,pc);
00419       x1.cancel(home,this,pc);
00420       x2.cancel(home,this,pc);
00421     }
00422     (void) Propagator::dispose(home);
00423     return sizeof(*this);
00424   }
00425 
00426 
00427   /*
00428    * Nary propagators
00429    *
00430    */
00431 
00432   template <class View, PropCond pc>
00433   NaryPropagator<View,pc>::NaryPropagator
00434   (Space* home, ViewArray<View>& y, bool fd)
00435     : Propagator(home,fd), x(y) {
00436     x.subscribe(home,this,pc);
00437   }
00438 
00439   template <class View, PropCond pc>
00440   forceinline
00441   NaryPropagator<View,pc>::NaryPropagator
00442   (Space* home, bool share, NaryPropagator<View,pc>& p)
00443     : Propagator(home,share,p) {
00444     x.update(home,share,p.x);
00445   }
00446 
00447   template <class View, PropCond pc>
00448   forceinline
00449   NaryPropagator<View,pc>::NaryPropagator
00450   (Space* home, bool share, Propagator& p, ViewArray<View>& x0)
00451     : Propagator(home,share,p) {
00452     x.update(home,share,x0);
00453   }
00454 
00455   template <class View, PropCond pc>
00456   PropCost
00457   NaryPropagator<View,pc>::cost(void) const {
00458     return cost_lo(x.size(), PC_LINEAR_LO);
00459   }
00460 
00461   template <class View, PropCond pc>
00462   size_t
00463   NaryPropagator<View,pc>::dispose(Space* home) {
00464     if (!home->failed())
00465       x.cancel(home,this,pc);
00466     (void) Propagator::dispose(home);
00467     return sizeof(*this);
00468   }
00469 
00470 
00471   /*
00472    * NaryOne (one additional variable) propagators
00473    *
00474    */
00475 
00476   template <class View, PropCond pc>
00477   NaryOnePropagator<View,pc>::NaryOnePropagator
00478   (Space* home, ViewArray<View>& x0, View y0, bool fd)
00479     : Propagator(home,fd), x(x0), y(y0) {
00480     x.subscribe(home,this,pc);
00481     y.subscribe(home,this,pc);
00482   }
00483 
00484   template <class View, PropCond pc>
00485   forceinline
00486   NaryOnePropagator<View,pc>::NaryOnePropagator
00487   (Space* home, bool share, NaryOnePropagator<View,pc>& p)
00488     : Propagator(home,share,p) {
00489     x.update(home,share,p.x);
00490     y.update(home,share,p.y);
00491   }
00492 
00493   template <class View, PropCond pc>
00494   forceinline
00495   NaryOnePropagator<View,pc>::NaryOnePropagator
00496   (Space* home, bool share, Propagator& p, ViewArray<View>& x0, View y0)
00497     : Propagator(home,share,p) {
00498     x.update(home,share,x0);
00499     y.update(home,share,y0);
00500   }
00501 
00502   template <class View, PropCond pc>
00503   PropCost
00504   NaryOnePropagator<View,pc>::cost(void) const {
00505     return cost_lo(x.size()+1, PC_LINEAR_LO);
00506   }
00507 
00508   template <class View, PropCond pc>
00509   size_t
00510   NaryOnePropagator<View,pc>::dispose(Space* home) {
00511     if (!home->failed()) {
00512       x.cancel(home,this,pc);
00513       y.cancel(home,this,pc);
00514     }
00515     (void) Propagator::dispose(home);
00516     return sizeof(*this);
00517   }
00518 
00519 
00520   /*
00521    * Inhomogeneous binary propagators
00522    *
00523    */
00524 
00525   template <class View0, PropCond pc0, class View1, PropCond pc1>
00526   InhomBinaryPropagator<View0,pc0,View1,pc1>::InhomBinaryPropagator
00527   (Space* home, View0 y0, View1 y1, bool fd)
00528     : Propagator(home,fd), x0(y0), x1(y1) {
00529     x0.subscribe(home,this,pc0);
00530     x1.subscribe(home,this,pc1);
00531   }
00532 
00533   template <class View0, PropCond pc0, class View1, PropCond pc1>
00534   forceinline
00535   InhomBinaryPropagator<View0,pc0,View1,pc1>::InhomBinaryPropagator
00536   (Space* home, bool share, InhomBinaryPropagator<View0,pc0,View1,pc1>& p)
00537     : Propagator(home,share,p) {
00538     x0.update(home,share,p.x0);
00539     x1.update(home,share,p.x1);
00540   }
00541 
00542   template <class View0, PropCond pc0, class View1, PropCond pc1>
00543   forceinline
00544   InhomBinaryPropagator<View0,pc0,View1,pc1>::InhomBinaryPropagator
00545   (Space* home, bool share, Propagator& p, View0 y0, View1 y1)
00546     : Propagator(home,share,p) {
00547     x0.update(home,share,y0);
00548     x1.update(home,share,y1);
00549   }
00550 
00551   template <class View0, PropCond pc0, class View1, PropCond pc1>
00552   PropCost
00553   InhomBinaryPropagator<View0,pc0,View1,pc1>::cost(void) const {
00554     return PC_BINARY_LO;
00555   }
00556 
00557   template <class View0, PropCond pc0, class View1, PropCond pc1>
00558   size_t
00559   InhomBinaryPropagator<View0,pc0,View1,pc1>::dispose(Space* home) {
00560     if (!home->failed()) {
00561       x0.cancel(home,this,pc0);
00562       x1.cancel(home,this,pc1);
00563     }
00564     (void) Propagator::dispose(home);
00565     return sizeof(*this);
00566   }
00567 
00568 
00569   /*
00570    * Inhomogeneous ternary propagators
00571    *
00572    */
00573 
00574   template <class View0, PropCond pc0, class View1, PropCond pc1,
00575             class View2, PropCond pc2>
00576   InhomTernaryPropagator<View0,pc0,View1,pc1,View2,pc2>::
00577   InhomTernaryPropagator(Space* home, View0 y0, View1 y1, View2 y2, bool fd)
00578     : Propagator(home,fd), x0(y0), x1(y1), x2(y2) {
00579     x0.subscribe(home,this,pc0);
00580     x1.subscribe(home,this,pc1);
00581     x2.subscribe(home,this,pc2);
00582   }
00583 
00584   template <class View0, PropCond pc0, class View1, PropCond pc1,
00585             class View2, PropCond pc2>
00586   forceinline
00587   InhomTernaryPropagator<View0,pc0,View1,pc1,View2,pc2>::
00588   InhomTernaryPropagator(Space* home, bool share,
00589                          InhomTernaryPropagator<View0,pc0,View1,pc1,
00590                          View2,pc2>& p)
00591     : Propagator(home,share,p) {
00592     x0.update(home,share,p.x0);
00593     x1.update(home,share,p.x1);
00594     x2.update(home,share,p.x2);
00595   }
00596 
00597   template <class View0, PropCond pc0, class View1, PropCond pc1,
00598             class View2, PropCond pc2>
00599   forceinline
00600   InhomTernaryPropagator<View0,pc0,View1,pc1,View2,pc2>::InhomTernaryPropagator
00601   (Space* home, bool share, Propagator& p, View0 y0, View1 y1, View2 y2)
00602     : Propagator(home,share,p) {
00603     x0.update(home,share,y0);
00604     x1.update(home,share,y1);
00605     x2.update(home,share,y2);
00606   }
00607 
00608   template <class View0, PropCond pc0, class View1, PropCond pc1,
00609             class View2, PropCond pc2>
00610   PropCost
00611   InhomTernaryPropagator<View0,pc0,View1,pc1,View2,pc2>::cost(void) const {
00612     return PC_BINARY_LO;
00613   }
00614 
00615   template <class View0, PropCond pc0, class View1, PropCond pc1,
00616             class View2, PropCond pc2>
00617   size_t
00618   InhomTernaryPropagator<View0,pc0,View1,pc1,View2,pc2>::
00619   dispose(Space* home) {
00620     if (!home->failed()) {
00621       x0.cancel(home,this,pc0);
00622       x1.cancel(home,this,pc1);
00623       x2.cancel(home,this,pc2);
00624     }
00625     (void) Propagator::dispose(home);
00626     return sizeof(*this);
00627   }
00628 
00629 
00630   /*
00631    * InhomNaryOne (one additional variable) propagators
00632    *
00633    */
00634 
00635   template <class View0, PropCond pc0, class View1, PropCond pc1>
00636   InhomNaryOnePropagator<View0,pc0,View1,pc1>::InhomNaryOnePropagator
00637   (Space* home, ViewArray<View0>& x0, View1 y0, bool fd)
00638     : Propagator(home,fd), x(x0), y(y0) {
00639     x.subscribe(home,this,pc0);
00640     y.subscribe(home,this,pc1);
00641   }
00642 
00643   template <class View0, PropCond pc0, class View1, PropCond pc1>
00644   forceinline
00645   InhomNaryOnePropagator<View0,pc0,View1,pc1>::InhomNaryOnePropagator
00646   (Space* home, bool share, InhomNaryOnePropagator<View0,pc0,View1,pc1>& p)
00647     : Propagator(home,share,p) {
00648     x.update(home,share,p.x);
00649     y.update(home,share,p.y);
00650   }
00651 
00652   template <class View0, PropCond pc0, class View1, PropCond pc1>
00653   forceinline
00654   InhomNaryOnePropagator<View0,pc0,View1,pc1>::InhomNaryOnePropagator
00655   (Space* home, bool share, Propagator& p, ViewArray<View0>& x0, View1 y0)
00656     : Propagator(home,share,p) {
00657     x.update(home,share,x0);
00658     y.update(home,share,y0);
00659   }
00660 
00661   template <class View0, PropCond pc0, class View1, PropCond pc1>
00662   PropCost
00663   InhomNaryOnePropagator<View0,pc0,View1,pc1>::cost(void) const {
00664     return cost_lo(x.size()+1, PC_LINEAR_LO);
00665   }
00666 
00667   template <class View0, PropCond pc0, class View1, PropCond pc1>
00668   size_t
00669   InhomNaryOnePropagator<View0,pc0,View1,pc1>::dispose(Space* home) {
00670     if (!home->failed()) {
00671       x.cancel(home,this,pc0);
00672       y.cancel(home,this,pc1);
00673     }
00674     (void) Propagator::dispose(home);
00675     return sizeof(*this);
00676   }
00677 
00678 }
00679 
00680 // STATISTICS: kernel-other