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: 2017-03-10 16:45:34 +0100 (Fri, 10 Mar 2017) $ by $Author: schulte $
00013  *     $Revision: 15568 $
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 void reschedule(Space& home);
00282     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00284     virtual size_t dispose(Space& home);
00291     static  ExecStatus post(Home home, IdxViewArray<VA>& x, VB y);
00292   };
00293 
00294 }}}
00295 
00296 #include <gecode/int/arithmetic/argmax.hpp>
00297 
00298 namespace Gecode { namespace Int { namespace Arithmetic {
00299 
00306   class SqrOps {
00307   public:
00309     bool even(void) const;
00311     int exp(void) const;
00313     void exp(int m);
00315     template<class IntType>
00316     IntType pow(IntType x) const;
00318     int tpow(int x) const;
00320     int fnroot(int x) const;
00322     int cnroot(int x) const;
00323   };
00324 
00331   class PowOps {
00332   protected:
00334     int n;
00336     static bool even(int m);
00338     bool powgr(long long int r, int x) const;
00340     bool powle(long long int r, int x) const;
00341   public:
00343     PowOps(int n);
00345     bool even(void) const;
00347     int exp(void) const;
00349     void exp(int m);
00351     template<class IntType>
00352     IntType pow(IntType x) const;
00354     int tpow(int x) const;
00356     int fnroot(int x) const;
00358     int cnroot(int x) const;
00359   };
00360 
00361 }}}
00362 
00363 #include <gecode/int/arithmetic/pow-ops.hpp>
00364 
00365 namespace Gecode { namespace Int { namespace Arithmetic {
00366 
00372   template<class VA, class VB, class Ops>
00373   class PowPlusBnd : public MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND> {
00374   protected:
00375     using MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>::x0;
00376     using MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>::x1;
00378     Ops ops;
00380     PowPlusBnd(Home home, VA x0, VB x1, const Ops& ops);
00382     PowPlusBnd(Space& home, bool share, PowPlusBnd<VA,VB,Ops>& p);
00383   public:
00385     virtual Actor* copy(Space& home, bool share);
00387     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00389     static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
00390   };
00391 
00398   template<class Ops>
00399   class PowBnd : public BinaryPropagator<IntView,PC_INT_BND> {
00400   protected:
00401     using BinaryPropagator<IntView,PC_INT_BND>::x0;
00402     using BinaryPropagator<IntView,PC_INT_BND>::x1;
00404     Ops ops;
00406     PowBnd(Space& home, bool share, PowBnd& p);
00408     PowBnd(Home home, IntView x0, IntView x1, const Ops& ops);
00409   public:
00411     virtual Actor* copy(Space& home, bool share);
00413     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00415     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00416   };
00417 
00423   template<class VA, class VB, class Ops>
00424   class PowPlusDom : public MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM> {
00425   protected:
00426     using MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>::x0;
00427     using MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>::x1;
00429     Ops ops;
00431     PowPlusDom(Home home, VA x0, VB x1, const Ops& ops);
00433     PowPlusDom(Space& home, bool share, PowPlusDom<VA,VB,Ops>& p);
00434   public:
00436     virtual Actor* copy(Space& home, bool share);
00444     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00446     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00448     static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
00449   };
00450 
00457   template<class Ops>
00458   class PowDom : public BinaryPropagator<IntView,PC_INT_DOM> {
00459   protected:
00460     using BinaryPropagator<IntView,PC_INT_DOM>::x0;
00461     using BinaryPropagator<IntView,PC_INT_DOM>::x1;
00463     Ops ops;
00465     PowDom(Space& home, bool share, PowDom<Ops>& p);
00467     PowDom(Home home, IntView x0, IntView x1, const Ops& ops);
00468   public:
00470     virtual Actor* copy(Space& home, bool share);
00472     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00480     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00482     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00483   };
00484 
00485 }}}
00486 
00487 #include <gecode/int/arithmetic/pow.hpp>
00488 
00489 namespace Gecode { namespace Int { namespace Arithmetic {
00490 
00497   template<class Ops, bool minus>
00498   class NrootPlusBnd : public BinaryPropagator<IntView,PC_INT_BND> {
00499   protected:
00500     using BinaryPropagator<IntView,PC_INT_BND>::x0;
00501     using BinaryPropagator<IntView,PC_INT_BND>::x1;
00503     Ops ops;
00505     NrootPlusBnd(Space& home, bool share, NrootPlusBnd<Ops,minus>& p);
00507     NrootPlusBnd(Home home, IntView x0, IntView x1, const Ops& ops);
00508   public:
00510     virtual Actor* copy(Space& home, bool share);
00512     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00514     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00515   };
00516 
00523   template<class Ops>
00524   class NrootBnd : public BinaryPropagator<IntView,PC_INT_BND> {
00525   protected:
00526     using BinaryPropagator<IntView,PC_INT_BND>::x0;
00527     using BinaryPropagator<IntView,PC_INT_BND>::x1;
00529     Ops ops;
00531     NrootBnd(Space& home, bool share, NrootBnd<Ops>& p);
00533     NrootBnd(Home home, IntView x0, IntView x1, const Ops& ops);
00534   public:
00536     virtual Actor* copy(Space& home, bool share);
00538     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00540     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00541   };
00542 
00549   template<class Ops, bool minus>
00550   class NrootPlusDom : public BinaryPropagator<IntView,PC_INT_DOM> {
00551   protected:
00552     using BinaryPropagator<IntView,PC_INT_DOM>::x0;
00553     using BinaryPropagator<IntView,PC_INT_DOM>::x1;
00555     Ops ops;
00557     NrootPlusDom(Space& home, bool share, NrootPlusDom<Ops,minus>& p);
00559     NrootPlusDom(Home home, IntView x0, IntView x1, const Ops& ops);
00560   public:
00562     virtual Actor* copy(Space& home, bool share);
00564     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00572     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00574     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00575   };
00576 
00583   template<class Ops>
00584   class NrootDom : public BinaryPropagator<IntView,PC_INT_DOM> {
00585   protected:
00586     using BinaryPropagator<IntView,PC_INT_DOM>::x0;
00587     using BinaryPropagator<IntView,PC_INT_DOM>::x1;
00589     Ops ops;
00591     NrootDom(Space& home, bool share, NrootDom<Ops>& p);
00593     NrootDom(Home home, IntView x0, IntView x1, const Ops& ops);
00594   public:
00596     virtual Actor* copy(Space& home, bool share);
00598     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00606     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00608     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00609   };
00610 
00611 }}}
00612 
00613 #include <gecode/int/arithmetic/nroot.hpp>
00614 
00615 namespace Gecode { namespace Int { namespace Arithmetic {
00616 
00623   template<class View, PropCond pc>
00624   class MultZeroOne : public BinaryPropagator<View,pc> {
00625   protected:
00626     using BinaryPropagator<View,pc>::x0;
00627     using BinaryPropagator<View,pc>::x1;
00628 
00630     MultZeroOne(Space& home, bool share, MultZeroOne<View,pc>& p);
00632     MultZeroOne(Home home, View x0, View x1);
00634     static RelTest equal(View x, int n);
00635   public:
00637     virtual Actor* copy(Space& home, bool share);
00639     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00641     static ExecStatus post(Home home, View x0, View x1);
00642   };
00643 
00644 
00645 
00651   template<class VA, class VB, class VC>
00652   class MultPlusBnd :
00653     public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
00654   protected:
00655     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x0;
00656     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x1;
00657     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x2;
00658   public:
00660     MultPlusBnd(Home home, VA x0, VB x1, VC x2);
00662     MultPlusBnd(Space& home, bool share, MultPlusBnd<VA,VB,VC>& p);
00664     static ExecStatus post(Home home, VA x0, VB x1, VC x2);
00666     virtual Actor* copy(Space& home, bool share);
00668     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00669   };
00670 
00678   class MultBnd : public TernaryPropagator<IntView,PC_INT_BND> {
00679   protected:
00680     using TernaryPropagator<IntView,PC_INT_BND>::x0;
00681     using TernaryPropagator<IntView,PC_INT_BND>::x1;
00682     using TernaryPropagator<IntView,PC_INT_BND>::x2;
00684     MultBnd(Space& home, bool share, MultBnd& p);
00685   public:
00687     MultBnd(Home home, IntView x0, IntView x1, IntView x2);
00689     GECODE_INT_EXPORT
00690     static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
00692     GECODE_INT_EXPORT
00693     virtual Actor* copy(Space& home, bool share);
00695     GECODE_INT_EXPORT
00696     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00697   };
00698 
00699 
00700 
00706   template<class VA, class VB, class VC>
00707   class MultPlusDom :
00708     public MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM> {
00709   protected:
00710     using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x0;
00711     using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x1;
00712     using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x2;
00713   public:
00715     MultPlusDom(Home home, VA x0, VB x1, VC x2);
00717     MultPlusDom(Space& home, bool share, MultPlusDom<VA,VB,VC>& p);
00719     static ExecStatus post(Home home, VA x0, VB x1, VC x2);
00721     virtual Actor* copy(Space& home, bool share);
00728     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00730     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00731   };
00732 
00740   class MultDom : public TernaryPropagator<IntView,PC_INT_DOM> {
00741   protected:
00742     using TernaryPropagator<IntView,PC_INT_DOM>::x0;
00743     using TernaryPropagator<IntView,PC_INT_DOM>::x1;
00744     using TernaryPropagator<IntView,PC_INT_DOM>::x2;
00746     MultDom(Space& home, bool share, MultDom& p);
00747   public:
00749     MultDom(Home home, IntView x0, IntView x1, IntView x2);
00751     GECODE_INT_EXPORT
00752     static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
00754     GECODE_INT_EXPORT
00755     virtual Actor* copy(Space& home, bool share);
00762     GECODE_INT_EXPORT
00763     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00765     GECODE_INT_EXPORT
00766     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00767   };
00768 
00769 }}}
00770 
00771 #include <gecode/int/arithmetic/mult.hpp>
00772 
00773 namespace Gecode { namespace Int { namespace Arithmetic {
00774 
00780   template<class VA, class VB, class VC>
00781   class DivPlusBnd :
00782     public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
00783   protected:
00784     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x0;
00785     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x1;
00786     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x2;
00787   public:
00789     DivPlusBnd(Home home, VA x0, VB x1, VC x2);
00791     DivPlusBnd(Space& home, bool share, DivPlusBnd<VA,VB,VC>& p);
00793     static ExecStatus post(Home home, VA x0, VB x1, VC x2);
00795     virtual Actor* copy(Space& home, bool share);
00797     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00798   };
00799 
00807   template<class View>
00808   class DivBnd : public TernaryPropagator<View,PC_INT_BND> {
00809   protected:
00810     using TernaryPropagator<View,PC_INT_BND>::x0;
00811     using TernaryPropagator<View,PC_INT_BND>::x1;
00812     using TernaryPropagator<View,PC_INT_BND>::x2;
00813 
00815     DivBnd(Space& home, bool share, DivBnd<View>& p);
00816   public:
00818     DivBnd(Home home, View x0, View x1, View x2);
00820     static  ExecStatus post(Home home, View x0, View x1, View x2);
00822     virtual Actor* copy(Space& home, bool share);
00824     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00825   };
00826 
00837   template<class View>
00838   class DivMod : public TernaryPropagator<View,PC_INT_BND> {
00839   protected:
00840     using TernaryPropagator<View,PC_INT_BND>::x0;
00841     using TernaryPropagator<View,PC_INT_BND>::x1;
00842     using TernaryPropagator<View,PC_INT_BND>::x2;
00843 
00845     DivMod(Space& home, bool share, DivMod<View>& p);
00846   public:
00848     DivMod(Home home, View x0, View x1, View x2);
00850     static  ExecStatus post(Home home, View x0, View x1, View x2);
00852     virtual Actor* copy(Space& home, bool share);
00854     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00855   };
00856 
00857 }}}
00858 
00859 #include <gecode/int/arithmetic/divmod.hpp>
00860 
00861 #endif
00862 
00863 // STATISTICS: int-prop
00864