Generated on Tue May 22 09:39:42 2018 for Gecode by doxygen 1.6.3

arithmetic.hh

Go to the documentation of this file.
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  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #ifndef __GECODE_INT_ARITHMETIC_HH__
00037 #define __GECODE_INT_ARITHMETIC_HH__
00038 
00039 #include <gecode/int.hh>
00040 
00041 #include <gecode/int/idx-view.hh>
00042 #include <gecode/int/rel.hh>
00043 #include <gecode/int/linear.hh>
00044 
00050 namespace Gecode { namespace Int { namespace Arithmetic {
00051 
00058   template<class View>
00059   class AbsBnd : public BinaryPropagator<View,PC_INT_BND> {
00060   protected:
00061     using BinaryPropagator<View,PC_INT_BND>::x0;
00062     using BinaryPropagator<View,PC_INT_BND>::x1;
00063 
00065     AbsBnd(Space& home, AbsBnd& p);
00067     AbsBnd(Home home, View x0, View x1);
00068   public:
00069 
00071     virtual Actor* copy(Space& home);
00078     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00080     virtual ExecStatus  propagate(Space& home, const ModEventDelta& med);
00082     static  ExecStatus  post(Home home, View x0, View x1);
00083   };
00084 
00091   template<class View>
00092   class AbsDom : public BinaryPropagator<View,PC_INT_DOM> {
00093   protected:
00094     using BinaryPropagator<View,PC_INT_DOM>::x0;
00095     using BinaryPropagator<View,PC_INT_DOM>::x1;
00096 
00098     AbsDom(Space& home, AbsDom& p);
00100     AbsDom(Home home, View x0, View x1);
00101   public:
00103     virtual Actor* copy(Space& home);
00111     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00113     virtual ExecStatus  propagate(Space& home, const ModEventDelta& med);
00115     static  ExecStatus  post(Home home, View x0, View x1);
00116   };
00117 
00118 }}}
00119 
00120 #include <gecode/int/arithmetic/abs.hpp>
00121 
00122 namespace Gecode { namespace Int { namespace Arithmetic {
00123 
00130   template<class View>
00131   class MaxBnd : public TernaryPropagator<View,PC_INT_BND> {
00132   protected:
00133     using TernaryPropagator<View,PC_INT_BND>::x0;
00134     using TernaryPropagator<View,PC_INT_BND>::x1;
00135     using TernaryPropagator<View,PC_INT_BND>::x2;
00136 
00138     MaxBnd(Space& home, MaxBnd& p);
00140     MaxBnd(Home home, View x0, View x1, View x2);
00141   public:
00143     MaxBnd(Space& home, Propagator& p, View x0, View x1, View x2);
00145     virtual Actor* copy(Space& home);
00147     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00149     static  ExecStatus post(Home home, View x0, View x1, View x2);
00150   };
00151 
00158   template<class View>
00159   class NaryMaxBnd : public NaryOnePropagator<View,PC_INT_BND> {
00160   protected:
00161     using NaryOnePropagator<View,PC_INT_BND>::x;
00162     using NaryOnePropagator<View,PC_INT_BND>::y;
00163 
00165     NaryMaxBnd(Space& home, NaryMaxBnd& p);
00167     NaryMaxBnd(Home home, ViewArray<View>& x, View y);
00168   public:
00170     virtual Actor* copy(Space& home);
00172     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00174     static  ExecStatus post(Home home, ViewArray<View>& x, View y);
00175   };
00176 
00183   template<class View>
00184   class MaxDom : public TernaryPropagator<View,PC_INT_DOM> {
00185   protected:
00186     using TernaryPropagator<View,PC_INT_DOM>::x0;
00187     using TernaryPropagator<View,PC_INT_DOM>::x1;
00188     using TernaryPropagator<View,PC_INT_DOM>::x2;
00189 
00191     MaxDom(Space& home, MaxDom& p);
00193     MaxDom(Home home, View x0, View x1, View x2);
00194   public:
00196     MaxDom(Space& home, Propagator& p, View x0, View x1, View x2);
00198     virtual Actor* copy(Space& home);
00205     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00207     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00209     static  ExecStatus post(Home home, View x0, View x1, View x2);
00210   };
00211 
00218   template<class View>
00219   class NaryMaxDom : public NaryOnePropagator<View,PC_INT_DOM> {
00220   protected:
00221     using NaryOnePropagator<View,PC_INT_DOM>::x;
00222     using NaryOnePropagator<View,PC_INT_DOM>::y;
00223 
00225     NaryMaxDom(Space& home, NaryMaxDom& p);
00227     NaryMaxDom(Home home, ViewArray<View>& x, View y);
00228   public:
00230     virtual Actor* copy(Space& home);
00237     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00239     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00241     static  ExecStatus post(Home home, ViewArray<View>& x, View y);
00242   };
00243 
00244 }}}
00245 
00246 #include <gecode/int/arithmetic/max.hpp>
00247 
00248 namespace Gecode { namespace Int { namespace Arithmetic {
00249 
00259   template<class VA, class VB, bool tiebreak>
00260   class ArgMax : public Propagator {
00261   protected:
00263     IdxViewArray<VA> x;
00265     VB y;
00267     ArgMax(Space& home, ArgMax& p);
00269     ArgMax(Home home, IdxViewArray<VA>& x, VB y);
00270   public:
00272     virtual Actor* copy(Space& home);
00273     // Cost function (defined as low linear)
00274     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00276     virtual void reschedule(Space& home);
00278     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00280     virtual size_t dispose(Space& home);
00287     static  ExecStatus post(Home home, IdxViewArray<VA>& x, VB y);
00288   };
00289 
00290 }}}
00291 
00292 #include <gecode/int/arithmetic/argmax.hpp>
00293 
00294 namespace Gecode { namespace Int { namespace Arithmetic {
00295 
00302   class SqrOps {
00303   public:
00305     bool even(void) const;
00307     int exp(void) const;
00309     void exp(int m);
00311     template<class IntType>
00312     IntType pow(IntType x) const;
00314     int tpow(int x) const;
00316     int fnroot(int x) const;
00318     int cnroot(int x) const;
00319   };
00320 
00327   class PowOps {
00328   protected:
00330     int n;
00332     static bool even(int m);
00334     bool powgr(long long int r, int x) const;
00336     bool powle(long long int r, int x) const;
00337   public:
00339     PowOps(int n);
00341     bool even(void) const;
00343     int exp(void) const;
00345     void exp(int m);
00347     template<class IntType>
00348     IntType pow(IntType x) const;
00350     int tpow(int x) const;
00352     int fnroot(int x) const;
00354     int cnroot(int x) const;
00355   };
00356 
00357 }}}
00358 
00359 #include <gecode/int/arithmetic/pow-ops.hpp>
00360 
00361 namespace Gecode { namespace Int { namespace Arithmetic {
00362 
00368   template<class VA, class VB, class Ops>
00369   class PowPlusBnd : public MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND> {
00370   protected:
00371     using MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>::x0;
00372     using MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>::x1;
00374     Ops ops;
00376     PowPlusBnd(Home home, VA x0, VB x1, const Ops& ops);
00378     PowPlusBnd(Space& home, PowPlusBnd<VA,VB,Ops>& p);
00379   public:
00381     virtual Actor* copy(Space& home);
00383     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00385     static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
00386   };
00387 
00394   template<class Ops>
00395   class PowBnd : public BinaryPropagator<IntView,PC_INT_BND> {
00396   protected:
00397     using BinaryPropagator<IntView,PC_INT_BND>::x0;
00398     using BinaryPropagator<IntView,PC_INT_BND>::x1;
00400     Ops ops;
00402     PowBnd(Space& home, PowBnd& p);
00404     PowBnd(Home home, IntView x0, IntView x1, const Ops& ops);
00405   public:
00407     virtual Actor* copy(Space& home);
00409     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00411     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00412   };
00413 
00419   template<class VA, class VB, class Ops>
00420   class PowPlusDom : public MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM> {
00421   protected:
00422     using MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>::x0;
00423     using MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>::x1;
00425     Ops ops;
00427     PowPlusDom(Home home, VA x0, VB x1, const Ops& ops);
00429     PowPlusDom(Space& home, PowPlusDom<VA,VB,Ops>& p);
00430   public:
00432     virtual Actor* copy(Space& home);
00440     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00442     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00444     static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
00445   };
00446 
00453   template<class Ops>
00454   class PowDom : public BinaryPropagator<IntView,PC_INT_DOM> {
00455   protected:
00456     using BinaryPropagator<IntView,PC_INT_DOM>::x0;
00457     using BinaryPropagator<IntView,PC_INT_DOM>::x1;
00459     Ops ops;
00461     PowDom(Space& home, PowDom<Ops>& p);
00463     PowDom(Home home, IntView x0, IntView x1, const Ops& ops);
00464   public:
00466     virtual Actor* copy(Space& home);
00468     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00476     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00478     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00479   };
00480 
00481 }}}
00482 
00483 #include <gecode/int/arithmetic/pow.hpp>
00484 
00485 namespace Gecode { namespace Int { namespace Arithmetic {
00486 
00493   template<class Ops, bool minus>
00494   class NrootPlusBnd : public BinaryPropagator<IntView,PC_INT_BND> {
00495   protected:
00496     using BinaryPropagator<IntView,PC_INT_BND>::x0;
00497     using BinaryPropagator<IntView,PC_INT_BND>::x1;
00499     Ops ops;
00501     NrootPlusBnd(Space& home, NrootPlusBnd<Ops,minus>& p);
00503     NrootPlusBnd(Home home, IntView x0, IntView x1, const Ops& ops);
00504   public:
00506     virtual Actor* copy(Space& home);
00508     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00510     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00511   };
00512 
00519   template<class Ops>
00520   class NrootBnd : public BinaryPropagator<IntView,PC_INT_BND> {
00521   protected:
00522     using BinaryPropagator<IntView,PC_INT_BND>::x0;
00523     using BinaryPropagator<IntView,PC_INT_BND>::x1;
00525     Ops ops;
00527     NrootBnd(Space& home, NrootBnd<Ops>& p);
00529     NrootBnd(Home home, IntView x0, IntView x1, const Ops& ops);
00530   public:
00532     virtual Actor* copy(Space& home);
00534     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00536     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00537   };
00538 
00545   template<class Ops, bool minus>
00546   class NrootPlusDom : public BinaryPropagator<IntView,PC_INT_DOM> {
00547   protected:
00548     using BinaryPropagator<IntView,PC_INT_DOM>::x0;
00549     using BinaryPropagator<IntView,PC_INT_DOM>::x1;
00551     Ops ops;
00553     NrootPlusDom(Space& home, NrootPlusDom<Ops,minus>& p);
00555     NrootPlusDom(Home home, IntView x0, IntView x1, const Ops& ops);
00556   public:
00558     virtual Actor* copy(Space& home);
00560     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00568     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00570     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00571   };
00572 
00579   template<class Ops>
00580   class NrootDom : public BinaryPropagator<IntView,PC_INT_DOM> {
00581   protected:
00582     using BinaryPropagator<IntView,PC_INT_DOM>::x0;
00583     using BinaryPropagator<IntView,PC_INT_DOM>::x1;
00585     Ops ops;
00587     NrootDom(Space& home, NrootDom<Ops>& p);
00589     NrootDom(Home home, IntView x0, IntView x1, const Ops& ops);
00590   public:
00592     virtual Actor* copy(Space& home);
00594     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00602     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00604     static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
00605   };
00606 
00607 }}}
00608 
00609 #include <gecode/int/arithmetic/nroot.hpp>
00610 
00611 namespace Gecode { namespace Int { namespace Arithmetic {
00612 
00619   template<class View, PropCond pc>
00620   class MultZeroOne : public BinaryPropagator<View,pc> {
00621   protected:
00622     using BinaryPropagator<View,pc>::x0;
00623     using BinaryPropagator<View,pc>::x1;
00624 
00626     MultZeroOne(Space& home, MultZeroOne<View,pc>& p);
00628     MultZeroOne(Home home, View x0, View x1);
00630     static RelTest equal(View x, int n);
00631   public:
00633     virtual Actor* copy(Space& home);
00635     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00637     static ExecStatus post(Home home, View x0, View x1);
00638   };
00639 
00640 
00641 
00647   template<class VA, class VB, class VC>
00648   class MultPlusBnd :
00649     public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
00650   protected:
00651     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x0;
00652     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x1;
00653     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x2;
00654   public:
00656     MultPlusBnd(Home home, VA x0, VB x1, VC x2);
00658     MultPlusBnd(Space& home, MultPlusBnd<VA,VB,VC>& p);
00660     static ExecStatus post(Home home, VA x0, VB x1, VC x2);
00662     virtual Actor* copy(Space& home);
00664     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00665   };
00666 
00674   class MultBnd : public TernaryPropagator<IntView,PC_INT_BND> {
00675   protected:
00676     using TernaryPropagator<IntView,PC_INT_BND>::x0;
00677     using TernaryPropagator<IntView,PC_INT_BND>::x1;
00678     using TernaryPropagator<IntView,PC_INT_BND>::x2;
00680     MultBnd(Space& home, MultBnd& p);
00681   public:
00683     MultBnd(Home home, IntView x0, IntView x1, IntView x2);
00685     GECODE_INT_EXPORT
00686     static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
00688     GECODE_INT_EXPORT
00689     virtual Actor* copy(Space& home);
00691     GECODE_INT_EXPORT
00692     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00693   };
00694 
00695 
00696 
00702   template<class VA, class VB, class VC>
00703   class MultPlusDom :
00704     public MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM> {
00705   protected:
00706     using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x0;
00707     using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x1;
00708     using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x2;
00709   public:
00711     MultPlusDom(Home home, VA x0, VB x1, VC x2);
00713     MultPlusDom(Space& home, MultPlusDom<VA,VB,VC>& p);
00715     static ExecStatus post(Home home, VA x0, VB x1, VC x2);
00717     virtual Actor* copy(Space& home);
00724     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00726     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00727   };
00728 
00736   class MultDom : public TernaryPropagator<IntView,PC_INT_DOM> {
00737   protected:
00738     using TernaryPropagator<IntView,PC_INT_DOM>::x0;
00739     using TernaryPropagator<IntView,PC_INT_DOM>::x1;
00740     using TernaryPropagator<IntView,PC_INT_DOM>::x2;
00742     MultDom(Space& home, MultDom& p);
00743   public:
00745     MultDom(Home home, IntView x0, IntView x1, IntView x2);
00747     GECODE_INT_EXPORT
00748     static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
00750     GECODE_INT_EXPORT
00751     virtual Actor* copy(Space& home);
00758     GECODE_INT_EXPORT
00759     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00761     GECODE_INT_EXPORT
00762     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00763   };
00764 
00765 }}}
00766 
00767 #include <gecode/int/arithmetic/mult.hpp>
00768 
00769 namespace Gecode { namespace Int { namespace Arithmetic {
00770 
00776   template<class VA, class VB, class VC>
00777   class DivPlusBnd :
00778     public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
00779   protected:
00780     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x0;
00781     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x1;
00782     using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x2;
00783   public:
00785     DivPlusBnd(Home home, VA x0, VB x1, VC x2);
00787     DivPlusBnd(Space& home, DivPlusBnd<VA,VB,VC>& p);
00789     static ExecStatus post(Home home, VA x0, VB x1, VC x2);
00791     virtual Actor* copy(Space& home);
00793     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00794   };
00795 
00803   template<class View>
00804   class DivBnd : public TernaryPropagator<View,PC_INT_BND> {
00805   protected:
00806     using TernaryPropagator<View,PC_INT_BND>::x0;
00807     using TernaryPropagator<View,PC_INT_BND>::x1;
00808     using TernaryPropagator<View,PC_INT_BND>::x2;
00809 
00811     DivBnd(Space& home, DivBnd<View>& p);
00812   public:
00814     DivBnd(Home home, View x0, View x1, View x2);
00816     static  ExecStatus post(Home home, View x0, View x1, View x2);
00818     virtual Actor* copy(Space& home);
00820     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00821   };
00822 
00833   template<class View>
00834   class DivMod : public TernaryPropagator<View,PC_INT_BND> {
00835   protected:
00836     using TernaryPropagator<View,PC_INT_BND>::x0;
00837     using TernaryPropagator<View,PC_INT_BND>::x1;
00838     using TernaryPropagator<View,PC_INT_BND>::x2;
00839 
00841     DivMod(Space& home, DivMod<View>& p);
00842   public:
00844     DivMod(Home home, View x0, View x1, View x2);
00846     static  ExecStatus post(Home home, View x0, View x1, View x2);
00848     virtual Actor* copy(Space& home);
00850     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00851   };
00852 
00853 }}}
00854 
00855 #include <gecode/int/arithmetic/divmod.hpp>
00856 
00857 #endif
00858 
00859 // STATISTICS: int-prop
00860