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

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: 2005-11-01 16:35:02 +0100 (Tue, 01 Nov 2005) $ by $Author: schulte $
00012  *     $Revision: 2467 $
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 "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, A x0, B x1, Val c);
00063   public:
00065     virtual PropCost cost(void) const;
00067     virtual ~LinBin(void);
00068   };
00069 
00079   template <class Val, class A, class B, PropCond pc, class Ctrl>
00080   class ReLinBin : public Propagator {
00081   protected:
00083     A x0;
00085     B x1; 
00087     Val c;
00089     Ctrl b;
00091     ReLinBin(Space* home, bool share, ReLinBin& p);
00093     ReLinBin(Space* home, A x0, B x1, Val c, Ctrl b);
00094   public:
00096     virtual PropCost cost(void) const;
00098     virtual ~ReLinBin(void);
00099   };
00100 
00113   template <class Val, class A, class B>
00114   class EqBin : public LinBin<Val,A,B,PC_INT_BND> {
00115   protected:
00116     using LinBin<Val,A,B,PC_INT_BND>::x0;
00117     using LinBin<Val,A,B,PC_INT_BND>::x1;
00118     using LinBin<Val,A,B,PC_INT_BND>::c;
00119 
00121     EqBin(Space* home, bool share, EqBin& p);
00123     EqBin(Space* home, A x0, B x1, Val c);
00124   public:
00126     virtual Actor* copy(Space* home, bool share);
00128     virtual ExecStatus propagate(Space* home);
00130     static ExecStatus post(Space* home, A x0, B x1, Val c);
00131   };
00132 
00145   template <class Val, class A, class B, class Ctrl>
00146   class ReEqBin : public ReLinBin<Val,A,B,PC_INT_BND,Ctrl> {
00147   protected:
00148     using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::x0;
00149     using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::x1;
00150     using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::c;
00151     using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::b;
00152 
00154     ReEqBin(Space* home, bool share, ReEqBin& p);
00156     ReEqBin(Space* home,A,B,Val,Ctrl);
00157   public:
00159     virtual Actor* copy(Space* home, bool share);
00161     virtual ExecStatus propagate(Space* home);
00163     static ExecStatus post(Space* home, A x0, B x1, Val c, Ctrl b);
00164   };
00165 
00178   template <class Val, class A, class B>
00179   class NqBin : public LinBin<Val,A,B,PC_INT_VAL> {
00180   protected:
00181     using LinBin<Val,A,B,PC_INT_VAL>::x0;
00182     using LinBin<Val,A,B,PC_INT_VAL>::x1;
00183     using LinBin<Val,A,B,PC_INT_VAL>::c;
00184 
00186     NqBin(Space* home, bool share, NqBin& p);
00188     NqBin(Space* home,A,B,Val);
00189   public:
00191     virtual Actor* copy(Space* home, bool share);
00193     virtual ExecStatus propagate(Space* home);
00195     virtual PropCost cost(void) const;
00197     static ExecStatus post(Space* home, A x0, B x1, Val c);
00198   };
00199 
00212   template <class Val, class A, class B>
00213   class LqBin : public LinBin<Val,A,B,PC_INT_BND> {
00214   protected:
00215     using LinBin<Val,A,B,PC_INT_BND>::x0;
00216     using LinBin<Val,A,B,PC_INT_BND>::x1;
00217     using LinBin<Val,A,B,PC_INT_BND>::c;
00218 
00220     LqBin(Space* home, bool share, LqBin& p);
00222     LqBin(Space* home, A x0, B x1, Val c);
00223   public:
00225     virtual Actor* copy(Space* home, bool share);
00227     virtual ExecStatus propagate(Space* home);
00229     static ExecStatus post(Space* home, A x0, B x1, Val c);
00230   };
00231 
00244   template <class Val, class A, class B>
00245   class GqBin : public LinBin<Val,A,B,PC_INT_BND> {
00246   protected:
00247     using LinBin<Val,A,B,PC_INT_BND>::x0;
00248     using LinBin<Val,A,B,PC_INT_BND>::x1;
00249     using LinBin<Val,A,B,PC_INT_BND>::c;
00250 
00252     GqBin(Space* home, bool share, GqBin& p);
00254     GqBin(Space* home, A x0, B x1, Val c);
00255   public:
00257     virtual Actor* copy(Space* home, bool share);
00259     virtual ExecStatus propagate(Space* home);
00261     static ExecStatus post(Space* home, A x0, B x1, Val c);
00262   };
00263 
00276   template <class Val, class A, class B>
00277   class ReLqBin : public ReLinBin<Val,A,B,PC_INT_BND,BoolView> {
00278   protected:
00279     using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::x0;
00280     using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::x1;
00281     using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::c;
00282     using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::b;
00283 
00285     ReLqBin(Space* home, bool share, ReLqBin& p);
00287     ReLqBin(Space* home, A x0, B x1, Val c, BoolView b);
00288   public:
00290     virtual Actor* copy(Space* home, bool share);
00292     virtual ExecStatus propagate(Space* home);
00294     static ExecStatus post(Space* home, A x0, B x1, Val c, BoolView b);
00295   };
00296 
00297 }}}
00298 
00299 #include "int/linear/binary.icc"
00300 
00301 namespace Gecode { namespace Int { namespace Linear {
00302 
00303   /*
00304    * Ternary propagators
00305    *
00306    */
00307 
00317   template <class Val, class A, class B, class C, PropCond pc>
00318   class LinTer : public Propagator {
00319   protected:
00321     A x0;
00323     B x1; 
00325     C x2; 
00327     Val c;
00329     LinTer(Space* home, bool share, LinTer& p);
00331     LinTer(Space* home, A x0, B x1, C x2, Val c);
00332   public:
00334     virtual PropCost cost(void) const;
00336     virtual ~LinTer(void);
00337   };
00338 
00351   template <class Val, class A, class B, class C>
00352   class EqTer : public LinTer<Val,A,B,C,PC_INT_BND> {
00353   protected:
00354     using LinTer<Val,A,B,C,PC_INT_BND>::x0;
00355     using LinTer<Val,A,B,C,PC_INT_BND>::x1;
00356     using LinTer<Val,A,B,C,PC_INT_BND>::x2;
00357     using LinTer<Val,A,B,C,PC_INT_BND>::c;
00358 
00360     EqTer(Space* home, bool share, EqTer& p);
00362     EqTer(Space* home, A x0, B x1, C x2, Val c);
00363   public:
00365     virtual Actor* copy(Space* home, bool share);
00367     virtual ExecStatus propagate(Space* home);
00369     static ExecStatus post(Space* home, A x0, B x1, C x2, Val c);
00370   };
00371 
00384   template <class Val, class A, class B, class C>
00385   class NqTer : public LinTer<Val,A,B,C,PC_INT_VAL> {
00386   protected:
00387     using LinTer<Val,A,B,C,PC_INT_VAL>::x0;
00388     using LinTer<Val,A,B,C,PC_INT_VAL>::x1;
00389     using LinTer<Val,A,B,C,PC_INT_VAL>::x2;
00390     using LinTer<Val,A,B,C,PC_INT_VAL>::c;
00391 
00393     NqTer(Space* home, bool share, NqTer& p);
00395     NqTer(Space* home, A x0, B x1, C x2, Val c);
00396   public:
00398     virtual Actor* copy(Space* home, bool share);
00400     virtual ExecStatus propagate(Space* home);
00402     static ExecStatus post(Space* home, A x0, B x1, C x2, Val c);
00403   };
00404 
00417   template <class Val, class A, class B, class C>
00418   class LqTer : public LinTer<Val,A,B,C,PC_INT_BND> {
00419   protected:
00420     using LinTer<Val,A,B,C,PC_INT_BND>::x0;
00421     using LinTer<Val,A,B,C,PC_INT_BND>::x1;
00422     using LinTer<Val,A,B,C,PC_INT_BND>::x2;
00423     using LinTer<Val,A,B,C,PC_INT_BND>::c;
00424 
00426     LqTer(Space* home, bool share, LqTer& p);
00428     LqTer(Space* home, A x0, B x1, C x2, Val c);
00429   public:
00431     virtual Actor* copy(Space* home, bool share);
00433     virtual ExecStatus propagate(Space* home);
00435     static ExecStatus post(Space* home, A x0, B x1, C x2, Val c);
00436   };
00437 
00438 }}}
00439 
00440 #include "int/linear/ternary.icc"
00441 
00442 namespace Gecode { namespace Int { namespace Linear {
00443 
00444   /*
00445    * n-ary propagators
00446    *
00447    */
00448 
00458   template <class Val, class P, class N, PropCond pc>
00459   class Lin : public Propagator {
00460   protected:
00462     ViewArray<P> x; 
00464     ViewArray<N> y; 
00466     Val c;
00467 
00469     Lin(Space* home, bool share, Lin& p);
00471     Lin(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00472   public:
00474     virtual PropCost cost(void) const;
00476     virtual ~Lin(void);
00477   };
00478 
00488   template <class Val, class P, class N, PropCond pc, class Ctrl>
00489   class ReLin : public Lin<Val,P,N,pc> {
00490   protected:
00492     Ctrl b;
00494     ReLin(Space* home, bool share, ReLin& p);
00496     ReLin(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
00497   public:
00499     virtual ~ReLin(void);
00500   };
00501 
00507   template <class Val, class View>
00508   void bounds_p(const Propagator*, ViewArray<View>& x, 
00509                 Val& c, Val& sl, Val& su);
00510 
00516   template <class Val, class View>
00517   void bounds_n(const Propagator*, ViewArray<View>& y, 
00518                 Val& c, Val& sl, Val& su);
00519 
00532   template <class Val, class P, class N>
00533   class Eq : public Lin<Val,P,N,PC_INT_BND> {
00534   protected:
00535     using Lin<Val,P,N,PC_INT_BND>::x;
00536     using Lin<Val,P,N,PC_INT_BND>::y;
00537     using Lin<Val,P,N,PC_INT_BND>::c;
00538 
00540     Eq(Space* home, bool share, Eq& p);
00541   public:
00543     Eq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00545     virtual Actor* copy(Space* home, bool share);
00547     virtual ExecStatus propagate(Space* home);
00549     static ExecStatus
00550     post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00551   };
00552 
00565   template <class Val, class P, class N, class Ctrl>
00566   class ReEq : public ReLin<Val,P,N,PC_INT_BND,Ctrl> {
00567   protected:
00568     using ReLin<Val,P,N,PC_INT_BND,Ctrl>::x;
00569     using ReLin<Val,P,N,PC_INT_BND,Ctrl>::y;
00570     using ReLin<Val,P,N,PC_INT_BND,Ctrl>::c;
00571     using ReLin<Val,P,N,PC_INT_BND,Ctrl>::b;
00572 
00574     ReEq(Space* home, bool share, ReEq& p);
00575   public:
00577     ReEq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
00579     virtual Actor* copy(Space* home, bool share);
00581     virtual ExecStatus propagate(Space* home);
00583     static ExecStatus 
00584     post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
00585   };
00586 
00599   template <class Val, class P, class N>
00600   class Nq : public Lin<Val,P,N,PC_INT_VAL> {
00601   protected:
00602     using Lin<Val,P,N,PC_INT_VAL>::x;
00603     using Lin<Val,P,N,PC_INT_VAL>::y;
00604     using Lin<Val,P,N,PC_INT_VAL>::c;
00605 
00607     Nq(Space* home, bool share, Nq& p);
00608   public:
00610     Nq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00612     virtual Actor* copy(Space* home, bool share);
00614     virtual ExecStatus propagate(Space* home);
00616     static ExecStatus 
00617     post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00618   };
00619 
00632   template <class Val, class P, class N>
00633   class Lq : public Lin<Val,P,N,PC_INT_BND> {
00634   protected:
00635     using Lin<Val,P,N,PC_INT_BND>::x;
00636     using Lin<Val,P,N,PC_INT_BND>::y;
00637     using Lin<Val,P,N,PC_INT_BND>::c;
00638 
00640     Lq(Space* home, bool share, Lq& p);
00641   public:
00643     Lq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00645     virtual Actor* copy(Space* home, bool share);
00647     virtual ExecStatus propagate(Space* home);
00649     static ExecStatus 
00650     post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
00651   };
00652 
00665   template <class Val, class P, class N>
00666   class ReLq : public ReLin<Val,P,N,PC_INT_BND,BoolView> {
00667   protected:
00668     using ReLin<Val,P,N,PC_INT_BND,BoolView>::x;
00669     using ReLin<Val,P,N,PC_INT_BND,BoolView>::y;
00670     using ReLin<Val,P,N,PC_INT_BND,BoolView>::c;
00671     using ReLin<Val,P,N,PC_INT_BND,BoolView>::b;
00672 
00674     ReLq(Space* home, bool share, ReLq& p);
00675   public:
00677     ReLq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b);
00679     virtual Actor* copy(Space* home, bool share);
00681     virtual ExecStatus propagate(Space* home);
00683     static ExecStatus
00684     post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b);
00685   };
00686 
00687 }}}
00688 
00689 #include "int/linear/nary.icc"
00690 
00691 namespace Gecode { namespace Int { namespace Linear {
00692 
00693   /*
00694    * Boolean linear propagators
00695    *
00696    */
00697 
00702   template <class View>
00703   class LinBool : public Propagator {
00704   protected:
00706     ViewArray<BoolView> x;
00708     int n;
00710     View y;
00711 
00713     void eliminate(void);
00715     void all_one(Space* home);
00717     void all_zero(Space* home);
00718 
00720     LinBool(Space* home, bool share, LinBool& p);
00722     LinBool(Space* home, ViewArray<BoolView>& x, int n, View y);
00723   public:
00725     virtual PropCost cost(void) const;
00727     virtual ~LinBool(void);
00728   };
00729 
00730 
00737   template <class View>
00738   class EqBool : public LinBool<View> {
00739   protected:
00740     using LinBool<View>::x;
00741     using LinBool<View>::n;
00742     using LinBool<View>::y;
00743 
00745     EqBool(Space* home, bool share, EqBool& p);
00747     EqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
00748   public:
00750     virtual Actor* copy(Space* home, bool share);
00752     virtual ExecStatus propagate(Space* home);
00754     static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
00755   };
00756 
00763   template <class View>
00764   class NqBool : public LinBool<View> {
00765   protected:
00766     using LinBool<View>::x;
00767     using LinBool<View>::n;
00768     using LinBool<View>::y;
00769 
00771     NqBool(Space* home, bool share, NqBool& p);
00773     NqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
00774   public:
00776     virtual Actor* copy(Space* home, bool share);
00778     virtual ExecStatus propagate(Space* home);
00780     static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
00781   };
00782 
00789   template <class View>
00790   class LqBool : public LinBool<View> {
00791   protected:
00792     using LinBool<View>::x;
00793     using LinBool<View>::n;
00794     using LinBool<View>::y;
00795 
00797     LqBool(Space* home, bool share, LqBool& p);
00799     LqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
00800   public:
00802     virtual Actor* copy(Space* home, bool share);
00804     virtual ExecStatus propagate(Space* home);
00806     static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
00807   };
00808 
00815   template <class View>
00816   class GqBool : public LinBool<View> {
00817   protected:
00818     using LinBool<View>::x;
00819     using LinBool<View>::n;
00820     using LinBool<View>::y;
00821 
00823     GqBool(Space* home, bool share, GqBool& p);
00825     GqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
00826   public:
00828     virtual Actor* copy(Space* home, bool share);
00830     virtual ExecStatus propagate(Space* home);
00832     static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
00833   };
00834 
00835 }}}
00836 
00837 #include "int/linear/bool.icc"
00838 
00839 namespace Gecode { namespace Int { namespace Linear {
00840 
00841 
00842   /*
00843    * Support for preprocessing and posting
00844    *
00845    */
00846 
00851   class Term {
00852   public:
00854     int a; 
00856     IntView x;
00857   };
00858 
00886   GECODE_INT_EXPORT void
00887   post(Space* home, Term t[], int n, IntRelType r, int c);
00888 
00917   GECODE_INT_EXPORT void
00918   post(Space* home, Term t[], int n, IntRelType r, int c, BoolView b);
00919 
00920 }}}
00921 
00922 #endif
00923 
00924 // STATISTICS: int-prop
00925