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

linear.hh

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-06-20 07:40:00 +0200 (Tue, 20 Jun 2006) $ by $Author: schulte $
00012  *     $Revision: 3309 $
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 #ifndef __GECODE_INT_LINEAR_HH__
00025 #define __GECODE_INT_LINEAR_HH__
00026 
00027 #include "gecode/int.hh"
00028 
00034 namespace Gecode { namespace Int { namespace Linear {
00035 
00036   /*
00037    * Binary propagators
00038    *
00039    */
00040 
00050   template <class Val, class A, class B, PropCond pc>
00051   class LinBin : public Propagator {
00052   protected:
00054     A x0;
00056     B x1; 
00058     Val c;
00060     LinBin(Space* home, bool share, LinBin& p);
00062     LinBin(Space* home, bool share, Propagator& p, A x0, B x1, Val c);
00064     LinBin(Space* home, A x0, B x1, Val c);
00065   public:
00067     virtual PropCost cost(void) const;
00069     virtual size_t dispose(Space* home);
00070   };
00071 
00081   template <class Val, class A, class B, PropCond pc, class Ctrl>
00082   class ReLinBin : public Propagator {
00083   protected:
00085     A x0;
00087     B x1; 
00089     Val c;
00091     Ctrl b;
00093     ReLinBin(Space* home, bool share, ReLinBin& p);
00095     ReLinBin(Space* home, A x0, B x1, Val c, Ctrl b);
00096   public:
00098     virtual PropCost cost(void) const;
00100     virtual size_t dispose(Space* home);
00101   };
00102 
00115   template <class Val, class A, class B>
00116   class EqBin : public LinBin<Val,A,B,PC_INT_BND> {
00117   protected:
00118     using LinBin<Val,A,B,PC_INT_BND>::x0;
00119     using LinBin<Val,A,B,PC_INT_BND>::x1;
00120     using LinBin<Val,A,B,PC_INT_BND>::c;
00121 
00123     EqBin(Space* home, bool share, EqBin& p);
00125     EqBin(Space* home, A x0, B x1, Val c);
00126   public:
00128     EqBin(Space* home, bool share, Propagator& p, A x0, B x1, Val c);
00130     virtual Actor* copy(Space* home, bool share);
00132     virtual ExecStatus propagate(Space* home);
00134     static ExecStatus post(Space* home, A x0, B x1, Val c);
00135   };
00136 
00149   template <class Val, class A, class B, class Ctrl>
00150   class ReEqBin : public ReLinBin<Val,A,B,PC_INT_BND,Ctrl> {
00151   protected:
00152     using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::x0;
00153     using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::x1;
00154     using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::c;
00155     using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::b;
00156 
00158     ReEqBin(Space* home, bool share, ReEqBin& p);
00160     ReEqBin(Space* home,A,B,Val,Ctrl);
00161   public:
00163     virtual Actor* copy(Space* home, bool share);
00165     virtual ExecStatus propagate(Space* home);
00167     static ExecStatus post(Space* home, A x0, B x1, Val c, Ctrl b);
00168   };
00169 
00182   template <class Val, class A, class B>
00183   class NqBin : public LinBin<Val,A,B,PC_INT_VAL> {
00184   protected:
00185     using LinBin<Val,A,B,PC_INT_VAL>::x0;
00186     using LinBin<Val,A,B,PC_INT_VAL>::x1;
00187     using LinBin<Val,A,B,PC_INT_VAL>::c;
00188 
00190     NqBin(Space* home, bool share, NqBin& p);
00192     NqBin(Space* home, A x0, B x1, Val c);
00193   public:
00195     NqBin(Space* home, bool share, Propagator& p, A x0, B x1, Val c);
00197     virtual Actor* copy(Space* home, bool share);
00199     virtual ExecStatus propagate(Space* home);
00201     virtual PropCost cost(void) const;
00203     static ExecStatus post(Space* home, A x0, B x1, Val c);
00204   };
00205 
00218   template <class Val, class A, class B>
00219   class LqBin : public LinBin<Val,A,B,PC_INT_BND> {
00220   protected:
00221     using LinBin<Val,A,B,PC_INT_BND>::x0;
00222     using LinBin<Val,A,B,PC_INT_BND>::x1;
00223     using LinBin<Val,A,B,PC_INT_BND>::c;
00224 
00226     LqBin(Space* home, bool share, LqBin& p);
00228     LqBin(Space* home, A x0, B x1, Val c);
00229   public:
00231     LqBin(Space* home, bool share, Propagator& p, A x0, B x1, Val c);
00233     virtual Actor* copy(Space* home, bool share);
00235     virtual ExecStatus propagate(Space* home);
00237     static ExecStatus post(Space* home, A x0, B x1, Val c);
00238   };
00239 
00252   template <class Val, class A, class B>
00253   class GqBin : public LinBin<Val,A,B,PC_INT_BND> {
00254   protected:
00255     using LinBin<Val,A,B,PC_INT_BND>::x0;
00256     using LinBin<Val,A,B,PC_INT_BND>::x1;
00257     using LinBin<Val,A,B,PC_INT_BND>::c;
00258 
00260     GqBin(Space* home, bool share, GqBin& p);
00262     GqBin(Space* home, A x0, B x1, Val c);
00263   public:
00265     GqBin(Space* home, bool share, Propagator& p, A x0, B x1, Val c);
00267     virtual Actor* copy(Space* home, bool share);
00269     virtual ExecStatus propagate(Space* home);
00271     static ExecStatus post(Space* home, A x0, B x1, Val c);
00272   };
00273 
00286   template <class Val, class A, class B>
00287   class ReLqBin : public ReLinBin<Val,A,B,PC_INT_BND,BoolView> {
00288   protected:
00289     using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::x0;
00290     using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::x1;
00291     using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::c;
00292     using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::b;
00293 
00295     ReLqBin(Space* home, bool share, ReLqBin& p);
00297     ReLqBin(Space* home, A x0, B x1, Val c, BoolView b);
00298   public:
00300     virtual Actor* copy(Space* home, bool share);
00302     virtual ExecStatus propagate(Space* home);
00304     static ExecStatus post(Space* home, A x0, B x1, Val c, BoolView b);
00305   };
00306 
00307 }}}
00308 
00309 #include "gecode/int/linear/binary.icc"
00310 
00311 namespace Gecode { namespace Int { namespace Linear {
00312 
00313   /*
00314    * Ternary propagators
00315    *
00316    */
00317 
00327   template <class Val, class A, class B, class C, PropCond pc>
00328   class LinTer : public Propagator {
00329   protected:
00331     A x0;
00333     B x1; 
00335     C x2; 
00337     Val c;
00339     LinTer(Space* home, bool share, LinTer& p);
00341     LinTer(Space* home, A x0, B x1, C x2, Val c);
00343     LinTer(Space* home, bool share, Propagator& p, A x0, B x1, C x2, Val c);
00344   public:
00346     virtual PropCost cost(void) const;
00348     virtual size_t dispose(Space* home);
00349   };
00350 
00363   template <class Val, class A, class B, class C>
00364   class EqTer : public LinTer<Val,A,B,C,PC_INT_BND> {
00365   protected:
00366     using LinTer<Val,A,B,C,PC_INT_BND>::x0;
00367     using LinTer<Val,A,B,C,PC_INT_BND>::x1;
00368     using LinTer<Val,A,B,C,PC_INT_BND>::x2;
00369     using LinTer<Val,A,B,C,PC_INT_BND>::c;
00370 
00372     EqTer(Space* home, bool share, EqTer& p);
00374     EqTer(Space* home, A x0, B x1, C x2, Val c);
00375   public:
00377     EqTer(Space* home, bool share, Propagator& p, A x0, B x1, C x2, Val c);
00379     virtual Actor* copy(Space* home, bool share);
00381     virtual ExecStatus propagate(Space* home);
00383     static ExecStatus post(Space* home, A x0, B x1, C x2, Val c);
00384   };
00385 
00398   template <class Val, class A, class B, class C>
00399   class NqTer : public LinTer<Val,A,B,C,PC_INT_VAL> {
00400   protected:
00401     using LinTer<Val,A,B,C,PC_INT_VAL>::x0;
00402     using LinTer<Val,A,B,C,PC_INT_VAL>::x1;
00403     using LinTer<Val,A,B,C,PC_INT_VAL>::x2;
00404     using LinTer<Val,A,B,C,PC_INT_VAL>::c;
00405 
00407     NqTer(Space* home, bool share, NqTer& p);
00409     NqTer(Space* home, A x0, B x1, C x2, Val c);
00410   public:
00412     NqTer(Space* home, bool share, Propagator& p, A x0, B x1, C x2, Val c);
00414     virtual Actor* copy(Space* home, bool share);
00416     virtual ExecStatus propagate(Space* home);
00418     static ExecStatus post(Space* home, A x0, B x1, C x2, Val c);
00419   };
00420 
00433   template <class Val, class A, class B, class C>
00434   class LqTer : public LinTer<Val,A,B,C,PC_INT_BND> {
00435   protected:
00436     using LinTer<Val,A,B,C,PC_INT_BND>::x0;
00437     using LinTer<Val,A,B,C,PC_INT_BND>::x1;
00438     using LinTer<Val,A,B,C,PC_INT_BND>::x2;
00439     using LinTer<Val,A,B,C,PC_INT_BND>::c;
00440 
00442     LqTer(Space* home, bool share, LqTer& p);
00444     LqTer(Space* home, A x0, B x1, C x2, Val c);
00445   public:
00447     LqTer(Space* home, bool share, Propagator& p, A x0, B x1, C x2, Val c);
00449     virtual Actor* copy(Space* home, bool share);
00451     virtual ExecStatus propagate(Space* home);
00453     static ExecStatus post(Space* home, A x0, B x1, C x2, Val c);
00454   };
00455 
00456 }}}
00457 
00458 #include "gecode/int/linear/ternary.icc"
00459 
00460 namespace Gecode { namespace Int { namespace Linear {
00461 
00462   /*
00463    * n-ary propagators
00464    *
00465    */
00466 
00476   template <class Val, class P, class N, PropCond pc>
00477   class Lin : public Propagator {
00478   protected:
00480     ViewArray<P> x; 
00482     ViewArray<N> y; 
00484     Val c;
00485 
00487     Lin(Space* home, bool share, Lin& p);
00489     Lin(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00490   public:
00492     virtual PropCost cost(void) const;
00494     virtual size_t dispose(Space* home);
00495   };
00496 
00506   template <class Val, class P, class N, PropCond pc, class Ctrl>
00507   class ReLin : public Lin<Val,P,N,pc> {
00508   protected:
00510     Ctrl b;
00512     ReLin(Space* home, bool share, ReLin& p);
00514     ReLin(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
00515   public:
00517     virtual size_t dispose(Space* home);
00518   };
00519 
00525   template <class Val, class View>
00526   void bounds_p(const Propagator*, ViewArray<View>& x, 
00527                 Val& c, Val& sl, Val& su);
00528 
00534   template <class Val, class View>
00535   void bounds_n(const Propagator*, ViewArray<View>& y, 
00536                 Val& c, Val& sl, Val& su);
00537 
00550   template <class Val, class P, class N>
00551   class Eq : public Lin<Val,P,N,PC_INT_BND> {
00552   protected:
00553     using Lin<Val,P,N,PC_INT_BND>::x;
00554     using Lin<Val,P,N,PC_INT_BND>::y;
00555     using Lin<Val,P,N,PC_INT_BND>::c;
00556 
00558     Eq(Space* home, bool share, Eq& p);
00559   public:
00561     Eq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00563     virtual Actor* copy(Space* home, bool share);
00565     virtual ExecStatus propagate(Space* home);
00567     static ExecStatus
00568     post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00569   };
00570 
00581   template <class Val, class View>
00582   class DomEq 
00583     : public Lin<Val,View,View,PC_INT_DOM> {
00584   protected:
00585     using Lin<Val,View,View,PC_INT_DOM>::x;
00586     using Lin<Val,View,View,PC_INT_DOM>::y;
00587     using Lin<Val,View,View,PC_INT_DOM>::c;
00588 
00590     DomEq(Space* home, bool share, DomEq& p);
00591   public:
00593     DomEq(Space* home, ViewArray<View>& x, ViewArray<View>& y, Val c);
00595     virtual Actor* copy(Space* home, bool share);
00597     virtual PropCost cost(void) const;
00599     virtual ExecStatus propagate(Space* home);
00601     static ExecStatus 
00602     post(Space* home, ViewArray<View>& x, ViewArray<View>& y, Val c);
00603   };
00604 
00617   template <class Val, class P, class N, class Ctrl>
00618   class ReEq : public ReLin<Val,P,N,PC_INT_BND,Ctrl> {
00619   protected:
00620     using ReLin<Val,P,N,PC_INT_BND,Ctrl>::x;
00621     using ReLin<Val,P,N,PC_INT_BND,Ctrl>::y;
00622     using ReLin<Val,P,N,PC_INT_BND,Ctrl>::c;
00623     using ReLin<Val,P,N,PC_INT_BND,Ctrl>::b;
00624 
00626     ReEq(Space* home, bool share, ReEq& p);
00627   public:
00629     ReEq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
00631     virtual Actor* copy(Space* home, bool share);
00633     virtual ExecStatus propagate(Space* home);
00635     static ExecStatus 
00636     post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
00637   };
00638 
00651   template <class Val, class P, class N>
00652   class Nq : public Lin<Val,P,N,PC_INT_VAL> {
00653   protected:
00654     using Lin<Val,P,N,PC_INT_VAL>::x;
00655     using Lin<Val,P,N,PC_INT_VAL>::y;
00656     using Lin<Val,P,N,PC_INT_VAL>::c;
00657 
00659     Nq(Space* home, bool share, Nq& p);
00660   public:
00662     Nq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00664     virtual Actor* copy(Space* home, bool share);
00666     virtual ExecStatus propagate(Space* home);
00668     static ExecStatus 
00669     post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00670   };
00671 
00684   template <class Val, class P, class N>
00685   class Lq : public Lin<Val,P,N,PC_INT_BND> {
00686   protected:
00687     using Lin<Val,P,N,PC_INT_BND>::x;
00688     using Lin<Val,P,N,PC_INT_BND>::y;
00689     using Lin<Val,P,N,PC_INT_BND>::c;
00690 
00692     Lq(Space* home, bool share, Lq& p);
00693   public:
00695     Lq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00697     virtual Actor* copy(Space* home, bool share);
00699     virtual ExecStatus propagate(Space* home);
00701     static ExecStatus 
00702     post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00703   };
00704 
00717   template <class Val, class P, class N>
00718   class ReLq : public ReLin<Val,P,N,PC_INT_BND,BoolView> {
00719   protected:
00720     using ReLin<Val,P,N,PC_INT_BND,BoolView>::x;
00721     using ReLin<Val,P,N,PC_INT_BND,BoolView>::y;
00722     using ReLin<Val,P,N,PC_INT_BND,BoolView>::c;
00723     using ReLin<Val,P,N,PC_INT_BND,BoolView>::b;
00724 
00726     ReLq(Space* home, bool share, ReLq& p);
00727   public:
00729     ReLq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b);
00731     virtual Actor* copy(Space* home, bool share);
00733     virtual ExecStatus propagate(Space* home);
00735     static ExecStatus
00736     post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b);
00737   };
00738 
00739 }}}
00740 
00741 #include "gecode/int/linear/nary.icc"
00742 #include "gecode/int/linear/dom.icc"
00743 
00744 namespace Gecode { namespace Int { namespace Linear {
00745 
00746   /*
00747    * Boolean linear propagators
00748    *
00749    */
00750 
00755   template <class View>
00756   class LinBool : public Propagator {
00757   protected:
00759     ViewArray<BoolView> x;
00761     int n;
00763     View y;
00764 
00766     void eliminate(void);
00768     void all_one(Space* home);
00770     void all_zero(Space* home);
00771 
00773     LinBool(Space* home, bool share, LinBool& p);
00775     LinBool(Space* home, ViewArray<BoolView>& x, int n, View y);
00776   public:
00778     virtual PropCost cost(void) const;
00780     virtual size_t dispose(Space* home);
00781   };
00782 
00783 
00790   template <class View>
00791   class EqBool : public LinBool<View> {
00792   protected:
00793     using LinBool<View>::x;
00794     using LinBool<View>::n;
00795     using LinBool<View>::y;
00796 
00798     EqBool(Space* home, bool share, EqBool& p);
00800     EqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
00801   public:
00803     virtual Actor* copy(Space* home, bool share);
00805     virtual ExecStatus propagate(Space* home);
00807     static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
00808   };
00809 
00816   template <class View>
00817   class NqBool : public LinBool<View> {
00818   protected:
00819     using LinBool<View>::x;
00820     using LinBool<View>::n;
00821     using LinBool<View>::y;
00822 
00824     NqBool(Space* home, bool share, NqBool& p);
00826     NqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
00827   public:
00829     virtual Actor* copy(Space* home, bool share);
00831     virtual ExecStatus propagate(Space* home);
00833     static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
00834   };
00835 
00842   template <class View>
00843   class LqBool : public LinBool<View> {
00844   protected:
00845     using LinBool<View>::x;
00846     using LinBool<View>::n;
00847     using LinBool<View>::y;
00848 
00850     LqBool(Space* home, bool share, LqBool& p);
00852     LqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
00853   public:
00855     virtual Actor* copy(Space* home, bool share);
00857     virtual ExecStatus propagate(Space* home);
00859     static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
00860   };
00861 
00868   template <class View>
00869   class GqBool : public LinBool<View> {
00870   protected:
00871     using LinBool<View>::x;
00872     using LinBool<View>::n;
00873     using LinBool<View>::y;
00874 
00876     GqBool(Space* home, bool share, GqBool& p);
00878     GqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
00879   public:
00881     virtual Actor* copy(Space* home, bool share);
00883     virtual ExecStatus propagate(Space* home);
00885     static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
00886   };
00887 
00888 }}}
00889 
00890 #include "gecode/int/linear/bool.icc"
00891 
00892 namespace Gecode { namespace Int { namespace Linear {
00893 
00894 
00895   /*
00896    * Support for preprocessing and posting
00897    *
00898    */
00899 
00904   class Term {
00905   public:
00907     int a; 
00909     IntView x;
00910   };
00911 
00939   GECODE_INT_EXPORT void
00940   post(Space* home, Term t[], int n, IntRelType r, int c, IntConLevel=ICL_DEF);
00941 
00970   GECODE_INT_EXPORT void
00971   post(Space* home, Term t[], int n, IntRelType r, int c, BoolView b);
00972 
00973 }}}
00974 
00975 #endif
00976 
00977 // STATISTICS: int-prop
00978