Generated on Wed Nov 1 15:04:34 2006 for Gecode by doxygen 1.4.5

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-09-06 15:51:28 +0200 (Wed, 06 Sep 2006) $ by $Author: schulte $
00012  *     $Revision: 3604 $
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 VX>
00756   class LinBoolInt : public Propagator {
00757   protected:
00759     ViewArray<VX> x;
00761     int n_s;
00763     int c;
00765     LinBoolInt(Space* home, bool share, LinBoolInt& p);
00767     LinBoolInt(Space* home, ViewArray<VX>& x, int n_s, int c);
00768   public:
00770     virtual PropCost cost(void) const;
00772     virtual size_t dispose(Space* home);
00773   };
00774 
00781   template <class VX>
00782   class EqBoolInt : public LinBoolInt<VX> {
00783   protected:
00784     using LinBoolInt<VX>::x;
00785     using LinBoolInt<VX>::n_s;
00786     using LinBoolInt<VX>::c;
00788     EqBoolInt(Space* home, bool share, EqBoolInt& p);
00790     EqBoolInt(Space* home, ViewArray<VX>& x, int n_s, int c);
00791   public:
00793     virtual Actor* copy(Space* home, bool share);
00795     virtual ExecStatus propagate(Space* home);
00797     static ExecStatus post(Space* home, ViewArray<VX>& x, int c);
00798   };
00799 
00806   template <class VX>
00807   class GqBoolInt : public LinBoolInt<VX> {
00808   protected:
00809     using LinBoolInt<VX>::x;
00810     using LinBoolInt<VX>::n_s;
00811     using LinBoolInt<VX>::c;
00813     GqBoolInt(Space* home, bool share, GqBoolInt& p);
00815     GqBoolInt(Space* home, ViewArray<VX>& x, int n_s, int c);
00816   public:
00818     virtual Actor* copy(Space* home, bool share);
00820     virtual ExecStatus propagate(Space* home);
00822     static ExecStatus post(Space* home, ViewArray<VX>& x, int c);
00823   };
00824 
00831   template<class VX>
00832   class NqBoolInt : public BinaryPropagator<VX,PC_INT_VAL> {
00833   protected:
00834     using BinaryPropagator<VX,PC_INT_VAL>::x0;
00835     using BinaryPropagator<VX,PC_INT_VAL>::x1;
00837     ViewArray<VX> x;
00839     int c;
00841     bool resubscribe(Space* home, VX& y);
00843     NqBoolInt(Space* home,  ViewArray<VX>& b, int c);
00845     NqBoolInt(Space* home, bool share, NqBoolInt<VX>& p);
00846   public:
00848     virtual Actor* copy(Space* home, bool share);
00850     virtual PropCost cost(void) const;
00852     virtual ExecStatus propagate(Space* home);
00854     static  ExecStatus post(Space* home, ViewArray<VX>& b, int c);
00855   };
00856 
00857 }}}
00858 
00859 #include "gecode/int/linear/bool-int.icc"
00860 
00861 namespace Gecode { namespace Int { namespace Linear {
00862 
00867   template <class XV, class YV>
00868   class LinBoolView : public Propagator {
00869   protected:
00871     ViewArray<XV> x;
00873     YV y;
00875     int c;
00877     LinBoolView(Space* home, bool share, LinBoolView& p);
00879     LinBoolView(Space* home, ViewArray<XV>& x, YV y, int c);
00880   public:
00882     virtual PropCost cost(void) const;
00884     virtual size_t dispose(Space* home);
00885   };
00886 
00887 
00894   template <class XV, class YV>
00895   class EqBoolView : public LinBoolView<XV,YV> {
00896   protected:
00897     using LinBoolView<XV,YV>::x;
00898     using LinBoolView<XV,YV>::y;
00899     using LinBoolView<XV,YV>::c;
00900 
00902     EqBoolView(Space* home, bool share, EqBoolView& p);
00904     EqBoolView(Space* home, ViewArray<XV>& x, YV y, int c);
00905   public:
00907     virtual Actor* copy(Space* home, bool share);
00909     virtual ExecStatus propagate(Space* home);
00911     static ExecStatus post(Space* home, ViewArray<XV>& x, YV y, int c);
00912   };
00913 
00920   template <class XV, class YV>
00921   class NqBoolView : public LinBoolView<XV,YV> {
00922   protected:
00923     using LinBoolView<XV,YV>::x;
00924     using LinBoolView<XV,YV>::y;
00925     using LinBoolView<XV,YV>::c;
00926 
00928     NqBoolView(Space* home, bool share, NqBoolView& p);
00930     NqBoolView(Space* home, ViewArray<XV>& x, YV y, int c);
00931   public:
00933     virtual Actor* copy(Space* home, bool share);
00935     virtual ExecStatus propagate(Space* home);
00937     static ExecStatus post(Space* home, ViewArray<XV>& x, YV y, int c);
00938   };
00939 
00946   template <class XV, class YV>
00947   class GqBoolView : public LinBoolView<XV,YV> {
00948   protected:
00949     using LinBoolView<XV,YV>::x;
00950     using LinBoolView<XV,YV>::y;
00951     using LinBoolView<XV,YV>::c;
00952 
00954     GqBoolView(Space* home, bool share, GqBoolView& p);
00956     GqBoolView(Space* home, ViewArray<XV>& x, YV y, int c);
00957   public:
00959     virtual Actor* copy(Space* home, bool share);
00961     virtual ExecStatus propagate(Space* home);
00963     static ExecStatus post(Space* home, ViewArray<XV>& x, YV y, int c);
00964   };
00965 
00966 }}}
00967 
00968 #include "gecode/int/linear/bool-view.icc"
00969 
00970 namespace Gecode { namespace Int { namespace Linear {
00971 
00972 
00973   /*
00974    * Support for preprocessing and posting
00975    *
00976    */
00977 
00982   class Term {
00983   public:
00985     int a;
00987     IntView x;
00988   };
00989 
01017   GECODE_INT_EXPORT void
01018   post(Space* home, Term t[], int n, IntRelType r, int c, IntConLevel=ICL_DEF);
01019 
01048   GECODE_INT_EXPORT void
01049   post(Space* home, Term t[], int n, IntRelType r, int c, BoolView b);
01050 
01051 }}}
01052 
01053 #endif
01054 
01055 // STATISTICS: int-prop
01056