Generated on Thu Jul 6 07:06:45 2006 for Gecode by doxygen 1.4.7

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