arithmetic.hh

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2002
00009  *     Guido Tack, 2004
00010  *
00011  *  Last modified:
00012  *     $Date: 2015-01-16 14:10:48 +0100 (Fri, 16 Jan 2015) $ by $Author: schulte $
00013  *     $Revision: 14362 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #ifndef __GECODE_INT_ARITHMETIC_HH__
00041 #define __GECODE_INT_ARITHMETIC_HH__
00042 
00043 #include <gecode/int.hh>
00044 
00045 #include <gecode/int/idx-view.hh>
00046 #include <gecode/int/rel.hh>
00047 #include <gecode/int/linear.hh>
00048 
00054 namespace Gecode { namespace Int { namespace Arithmetic {
00055 
00062   template<class View>
00063   class AbsBnd : public BinaryPropagator<View,PC_INT_BND> {
00064   protected:
00065     using BinaryPropagator<View,PC_INT_BND>::x0;
00066     using BinaryPropagator<View,PC_INT_BND>::x1;
00067 
00069     AbsBnd(Space& home, bool share, AbsBnd& p);
00071     AbsBnd(Home home, View x0, View x1);
00072   public:
00073 
00075     virtual Actor* copy(Space& home, bool share);
00082     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00084     virtual ExecStatus  propagate(Space& home, const ModEventDelta& med);
00086     static  ExecStatus  post(Home home, View x0, View x1);
00087   };
00088 
00095   template<class View>
00096   class AbsDom : public BinaryPropagator<View,PC_INT_DOM> {
00097   protected:
00098     using BinaryPropagator<View,PC_INT_DOM>::x0;
00099     using BinaryPropagator<View,PC_INT_DOM>::x1;
00100 
00102     AbsDom(Space& home, bool share, AbsDom& p);
00104     AbsDom(Home home, View x0, View x1);
00105   public:
00107     virtual Actor* copy(Space& home, bool share);
00115     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00117     virtual ExecStatus  propagate(Space& home, const ModEventDelta& med);
00119     static  ExecStatus  post(Home home, View x0, View x1);
00120   };
00121 
00122 }}}
00123 
00124 #include <gecode/int/arithmetic/abs.hpp>
00125 
00126 namespace Gecode { namespace Int { namespace Arithmetic {
00127 
00134   template<class View>
00135   class MaxBnd : public TernaryPropagator<View,PC_INT_BND> {
00136   protected:
00137     using TernaryPropagator<View,PC_INT_BND>::x0;
00138     using TernaryPropagator<View,PC_INT_BND>::x1;
00139     using TernaryPropagator<View,PC_INT_BND>::x2;
00140 
00142     MaxBnd(Space& home, bool share, MaxBnd& p);
00144     MaxBnd(Home home, View x0, View x1, View x2);
00145   public:
00147     MaxBnd(Space& home, bool share, Propagator& p, View x0, View x1, View x2);
00149     virtual Actor* copy(Space& home, bool share);
00151     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00153     static  ExecStatus post(Home home, View x0, View x1, View x2);
00154   };
00155 
00162   template<class View>
00163   class NaryMaxBnd : public NaryOnePropagator<View,PC_INT_BND> {
00164   protected:
00165     using NaryOnePropagator<View,PC_INT_BND>::x;
00166     using NaryOnePropagator<View,PC_INT_BND>::y;
00167 
00169     NaryMaxBnd(Space& home, bool share, NaryMaxBnd& p);
00171     NaryMaxBnd(Home home, ViewArray<View>& x, View y);
00172   public:
00174     virtual Actor* copy(Space& home, bool share);
00176     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00178     static  ExecStatus post(Home home, ViewArray<View>& x, View y);
00179   };
00180 
00187   template<class View>
00188   class MaxDom : public TernaryPropagator<View,PC_INT_DOM> {
00189   protected:
00190     using TernaryPropagator<View,PC_INT_DOM>::x0;
00191     using TernaryPropagator<View,PC_INT_DOM>::x1;
00192     using TernaryPropagator<View,PC_INT_DOM>::x2;
00193 
00195     MaxDom(Space& home, bool share, MaxDom& p);
00197     MaxDom(Home home, View x0, View x1, View x2);
00198   public:
00200     MaxDom(Space& home, bool share, Propagator& p, View x0, View x1, View x2);
00202     virtual Actor* copy(Space& home, bool share);
00209     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00211     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00213     static  ExecStatus post(Home home, View x0, View x1, View x2);
00214   };
00215 
00222   template<class View>
00223   class NaryMaxDom : public NaryOnePropagator<View,PC_INT_DOM> {
00224   protected:
00225     using NaryOnePropagator<View,PC_INT_DOM>::x;
00226     using NaryOnePropagator<View,PC_INT_DOM>::y;
00227 
00229     NaryMaxDom(Space& home, bool share, NaryMaxDom& p);
00231     NaryMaxDom(Home home, ViewArray<View>& x, View y);
00232   public:
00234     virtual Actor* copy(Space& home, bool share);
00241     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00243     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00245     static  ExecStatus post(Home home, ViewArray<View>& x, View y);
00246   };
00247 
00248 }}}
00249 
00250 #include <gecode/int/arithmetic/max.hpp>
00251 
00252 namespace Gecode { namespace Int { namespace Arithmetic {
00253 
00263   template<class VA, class VB, bool tiebreak>
00264   class ArgMax : public Propagator { 
00265   protected:
00267     IdxViewArray<VA> x;
00269     VB y;
00271     ArgMax(Space& home, bool share, ArgMax& p);
00273     ArgMax(Home home, IdxViewArray<VA>& x, VB y);
00274   public:
00276     virtual Actor* copy(Space& home, bool share);
00277     // Cost function (defined as low linear)
00278     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00280     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00282     virtual size_t dispose(Space& home);
00289     static  ExecStatus post(Home home, IdxViewArray<VA>& x, VB y);
00290   };
00291 
00292 }}}
00293 
00294 #include <gecode/int/arithmetic/argmax.hpp>
00295 
00296 namespace Gecode { namespace Int { namespace Arithmetic {
00297 
00304   class SqrOps {
00305   public:
00307     bool even(void) const;
00309     int exp(void) const;
00311     void exp(int m);
00313     template<class IntType>
00314     IntType pow(IntType x) const;
00316     int tpow(int x) const;
00318     int fnroot(int x) const;
00320     int cnroot(int x) const;
00321   };
00322 
00329   class PowOps {
00330   protected:
00332     int n;
00334     static bool even(int m);
00336     bool powgr(long long int r, int x) const;
00338     bool powle(long long int r, int x) const;
00339   public:
00341     PowOps(int n);
00343     bool even(void) const;
00345     int exp(void) const;
00347     void exp(int m);
00349     template<class IntType>
00350     IntType pow(IntType x) const;
00352     int tpow(int x) const;
00354     int fnroot(int x) const;
00356     int cnroot(int x) const;
00357   };
00358 
00359 }}}
00360 
00361 #include <gecode/int/arithmetic/pow-ops.hpp>
00362 
00363 namespace Gecode { namespace Int { namespace Arithmetic {
00364 
00370   template<class VA, class VB, class Ops>
00371   class PowPlusBnd : public MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND> {
00372   protected:
00373     using MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>::x0;
00374     using MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>::x1;
00376     Ops ops;
00378     PowPlusBnd(Home home, VA x0, VB x1, const Ops& ops);
00380     PowPlusBnd(Space& home, bool share, PowPlusBnd<VA,VB,Ops>& p);
00381   public:
00383     virtual Actor* copy(Space& home, bool share);
00385     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00387     static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
00388   };
00389 
00396   template<class Ops>
00397   class PowBnd : public BinaryPropagator<IntView,PC_INT_BND> {
00398   protected:
00399     using BinaryPropagator<IntView,PC_INT_BND>::x0;
00400     using BinaryPropagator<IntView,PC_INT_BND>::x1;
00402     Ops ops;
00404     PowBnd(Space& home, bool share, PowBnd& p);
00406     PowBnd(Home home, IntView x0, IntView x1, const Ops& ops);
00407   public:
00409     virtual Actor* copy(Space& home, bool share);
00411     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00413     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00414   };
00415 
00421   template<class VA, class VB, class Ops>
00422   class PowPlusDom : public MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM> {
00423   protected:
00424     using MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>::x0;
00425     using MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>::x1;
00427     Ops ops;
00429     PowPlusDom(Home home, VA x0, VB x1, const Ops& ops);
00431     PowPlusDom(Space& home, bool share, PowPlusDom<VA,VB,Ops>& p);
00432   public:
00434     virtual Actor* copy(Space& home, bool share);
00442     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00444     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00446     static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
00447   };
00448 
00455   template<class Ops>
00456   class PowDom : public BinaryPropagator<IntView,PC_INT_DOM> {
00457   protected:
00458     using BinaryPropagator<IntView,PC_INT_DOM>::x0;
00459     using BinaryPropagator<IntView,PC_INT_DOM>::x1;
00461     Ops ops;
00463     PowDom(Space& home, bool share, PowDom<Ops>& p);
00465     PowDom(Home home, IntView x0, IntView x1, const Ops& ops);
00466   public:
00468     virtual Actor* copy(Space& home, bool share);
00470     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00478     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00480     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00481   };
00482 
00483 }}}
00484 
00485 #include <gecode/int/arithmetic/pow.hpp>
00486 
00487 namespace Gecode { namespace Int { namespace Arithmetic {
00488 
00495   template<class Ops, bool minus>
00496   class NrootPlusBnd : public BinaryPropagator<IntView,PC_INT_BND> {
00497   protected:
00498     using BinaryPropagator<IntView,PC_INT_BND>::x0;
00499     using BinaryPropagator<IntView,PC_INT_BND>::x1;
00501     Ops ops;
00503     NrootPlusBnd(Space& home, bool share, NrootPlusBnd<Ops,minus>& p);
00505     NrootPlusBnd(Home home, IntView x0, IntView x1, const Ops& ops);
00506   public:
00508     virtual Actor* copy(Space& home, bool share);
00510     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00512     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00513   };
00514 
00521   template<class Ops>
00522   class NrootBnd : public BinaryPropagator<IntView,PC_INT_BND> {
00523   protected:
00524     using BinaryPropagator<IntView,PC_INT_BND>::x0;
00525     using BinaryPropagator<IntView,PC_INT_BND>::x1;
00527     Ops ops;
00529     NrootBnd(Space& home, bool share, NrootBnd<Ops>& p);
00531     NrootBnd(Home home, IntView x0, IntView x1, const Ops& ops);
00532   public:
00534     virtual Actor* copy(Space& home, bool share);
00536     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00538     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00539   };
00540 
00547   template<class Ops, bool minus>
00548   class NrootPlusDom : public BinaryPropagator<IntView,PC_INT_DOM> {
00549   protected:
00550     using BinaryPropagator<IntView,PC_INT_DOM>::x0;
00551     using BinaryPropagator<IntView,PC_INT_DOM>::x1;
00553     Ops ops;
00555     NrootPlusDom(Space& home, bool share, NrootPlusDom<Ops,minus>& p);
00557     NrootPlusDom(Home home, IntView x0, IntView x1, const Ops& ops);
00558   public:
00560     virtual Actor* copy(Space& home, bool share);
00562     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00570     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00572     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00573   };
00574 
00581   template<class Ops>
00582   class NrootDom : public BinaryPropagator<IntView,PC_INT_DOM> {
00583   protected:
00584     using BinaryPropagator<IntView,PC_INT_DOM>::x0;
00585     using BinaryPropagator<IntView,PC_INT_DOM>::x1;
00587     Ops ops;
00589     NrootDom(Space& home, bool share, NrootDom<Ops>& p);
00591     NrootDom(Home home, IntView x0, IntView x1, const Ops& ops);
00592   public:
00594     virtual Actor* copy(Space& home, bool share);
00596     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00604     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00606     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00607   };
00608 
00609 }}}
00610 
00611 #include <gecode/int/arithmetic/nroot.hpp>
00612 
00613 namespace Gecode { namespace Int { namespace Arithmetic {
00614 
00621   template<class View, PropCond pc>
00622   class MultZeroOne : public BinaryPropagator<View,pc> {
00623   protected:
00624     using BinaryPropagator<View,pc>::x0;
00625     using BinaryPropagator<View,pc>::x1;
00626 
00628     MultZeroOne(Space& home, bool share, MultZeroOne<View,pc>& p);
00630     MultZeroOne(Home home, View x0, View x1);
00632     static RelTest equal(View x, int n);
00633   public:
00635     virtual Actor* copy(Space& home, bool share);
00637     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00639     static ExecStatus post(Home home, View x0, View x1);
00640   };
00641 
00642 
00643 
00649   template<class VA, class VB, class VC>
00650   class MultPlusBnd :
00651     public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
00652   protected:
00653     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x0;
00654     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x1;
00655     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x2;
00656   public:
00658     MultPlusBnd(Home home, VA x0, VB x1, VC x2);
00660     MultPlusBnd(Space& home, bool share, MultPlusBnd<VA,VB,VC>& p);
00662     static ExecStatus post(Home home, VA x0, VB x1, VC x2);
00664     virtual Actor* copy(Space& home, bool share);
00666     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00667   };
00668 
00676   class MultBnd : public TernaryPropagator<IntView,PC_INT_BND> {
00677   protected:
00678     using TernaryPropagator<IntView,PC_INT_BND>::x0;
00679     using TernaryPropagator<IntView,PC_INT_BND>::x1;
00680     using TernaryPropagator<IntView,PC_INT_BND>::x2;
00682     MultBnd(Space& home, bool share, MultBnd& p);
00683   public:
00685     MultBnd(Home home, IntView x0, IntView x1, IntView x2);
00687     GECODE_INT_EXPORT
00688     static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
00690     GECODE_INT_EXPORT
00691     virtual Actor* copy(Space& home, bool share);
00693     GECODE_INT_EXPORT 
00694     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00695   };
00696 
00697 
00698 
00704   template<class VA, class VB, class VC>
00705   class MultPlusDom :
00706     public MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM> {
00707   protected:
00708     using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x0;
00709     using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x1;
00710     using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x2;
00711   public:
00713     MultPlusDom(Home home, VA x0, VB x1, VC x2);
00715     MultPlusDom(Space& home, bool share, MultPlusDom<VA,VB,VC>& p);
00717     static ExecStatus post(Home home, VA x0, VB x1, VC x2);
00719     virtual Actor* copy(Space& home, bool share);
00726     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00728     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00729   };
00730 
00738   class MultDom : public TernaryPropagator<IntView,PC_INT_DOM> {
00739   protected:
00740     using TernaryPropagator<IntView,PC_INT_DOM>::x0;
00741     using TernaryPropagator<IntView,PC_INT_DOM>::x1;
00742     using TernaryPropagator<IntView,PC_INT_DOM>::x2;
00744     MultDom(Space& home, bool share, MultDom& p);
00745   public:
00747     MultDom(Home home, IntView x0, IntView x1, IntView x2);
00749     GECODE_INT_EXPORT 
00750     static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
00752     GECODE_INT_EXPORT 
00753     virtual Actor* copy(Space& home, bool share);
00760     GECODE_INT_EXPORT 
00761     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00763     GECODE_INT_EXPORT 
00764     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00765   };
00766 
00767 }}}
00768 
00769 #include <gecode/int/arithmetic/mult.hpp>
00770 
00771 namespace Gecode { namespace Int { namespace Arithmetic {
00772 
00778   template<class VA, class VB, class VC>
00779   class DivPlusBnd :
00780     public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
00781   protected:
00782     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x0;
00783     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x1;
00784     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x2;
00785   public:
00787     DivPlusBnd(Home home, VA x0, VB x1, VC x2);
00789     DivPlusBnd(Space& home, bool share, DivPlusBnd<VA,VB,VC>& p);
00791     static ExecStatus post(Home home, VA x0, VB x1, VC x2);
00793     virtual Actor* copy(Space& home, bool share);
00795     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00796   };
00797 
00805   template<class View>
00806   class DivBnd : public TernaryPropagator<View,PC_INT_BND> {
00807   protected:
00808     using TernaryPropagator<View,PC_INT_BND>::x0;
00809     using TernaryPropagator<View,PC_INT_BND>::x1;
00810     using TernaryPropagator<View,PC_INT_BND>::x2;
00811 
00813     DivBnd(Space& home, bool share, DivBnd<View>& p);
00814   public:
00816     DivBnd(Home home, View x0, View x1, View x2);
00818     static  ExecStatus post(Home home, View x0, View x1, View x2);
00820     virtual Actor* copy(Space& home, bool share);
00822     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00823   };
00824 
00835   template<class View>
00836   class DivMod : public TernaryPropagator<View,PC_INT_BND> {
00837   protected:
00838     using TernaryPropagator<View,PC_INT_BND>::x0;
00839     using TernaryPropagator<View,PC_INT_BND>::x1;
00840     using TernaryPropagator<View,PC_INT_BND>::x2;
00841 
00843     DivMod(Space& home, bool share, DivMod<View>& p);
00844   public:
00846     DivMod(Home home, View x0, View x1, View x2);
00848     static  ExecStatus post(Home home, View x0, View x1, View x2);
00850     virtual Actor* copy(Space& home, bool share);
00852     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00853   };
00854 
00855 }}}
00856 
00857 #include <gecode/int/arithmetic/divmod.hpp>
00858 
00859 #endif
00860 
00861 // STATISTICS: int-prop
00862