Generated on Sat Jul 29 2017 12:41:24 for Gecode by doxygen 1.8.13
arithmetic.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2002
9  * Guido Tack, 2004
10  *
11  * Last modified:
12  * $Date: 2017-03-10 16:45:34 +0100 (Fri, 10 Mar 2017) $ by $Author: schulte $
13  * $Revision: 15568 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #ifndef __GECODE_INT_ARITHMETIC_HH__
41 #define __GECODE_INT_ARITHMETIC_HH__
42 
43 #include <gecode/int.hh>
44 
45 #include <gecode/int/idx-view.hh>
46 #include <gecode/int/rel.hh>
47 #include <gecode/int/linear.hh>
48 
54 namespace Gecode { namespace Int { namespace Arithmetic {
55 
62  template<class View>
63  class AbsBnd : public BinaryPropagator<View,PC_INT_BND> {
64  protected:
67 
69  AbsBnd(Space& home, bool share, AbsBnd& p);
71  AbsBnd(Home home, View x0, View x1);
72  public:
73 
75  virtual Actor* copy(Space& home, bool share);
82  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
84  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
86  static ExecStatus post(Home home, View x0, View x1);
87  };
88 
95  template<class View>
96  class AbsDom : public BinaryPropagator<View,PC_INT_DOM> {
97  protected:
100 
102  AbsDom(Space& home, bool share, AbsDom& p);
104  AbsDom(Home home, View x0, View x1);
105  public:
107  virtual Actor* copy(Space& home, bool share);
115  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
117  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
119  static ExecStatus post(Home home, View x0, View x1);
120  };
121 
122 }}}
123 
125 
126 namespace Gecode { namespace Int { namespace Arithmetic {
127 
134  template<class View>
135  class MaxBnd : public TernaryPropagator<View,PC_INT_BND> {
136  protected:
140 
142  MaxBnd(Space& home, bool share, MaxBnd& p);
144  MaxBnd(Home home, View x0, View x1, View x2);
145  public:
147  MaxBnd(Space& home, bool share, Propagator& p, View x0, View x1, View x2);
149  virtual Actor* copy(Space& home, bool share);
151  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
153  static ExecStatus post(Home home, View x0, View x1, View x2);
154  };
155 
162  template<class View>
163  class NaryMaxBnd : public NaryOnePropagator<View,PC_INT_BND> {
164  protected:
167 
169  NaryMaxBnd(Space& home, bool share, NaryMaxBnd& p);
171  NaryMaxBnd(Home home, ViewArray<View>& x, View y);
172  public:
174  virtual Actor* copy(Space& home, bool share);
176  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
178  static ExecStatus post(Home home, ViewArray<View>& x, View y);
179  };
180 
187  template<class View>
188  class MaxDom : public TernaryPropagator<View,PC_INT_DOM> {
189  protected:
193 
195  MaxDom(Space& home, bool share, MaxDom& p);
197  MaxDom(Home home, View x0, View x1, View x2);
198  public:
200  MaxDom(Space& home, bool share, Propagator& p, View x0, View x1, View x2);
202  virtual Actor* copy(Space& home, bool share);
209  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
211  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
213  static ExecStatus post(Home home, View x0, View x1, View x2);
214  };
215 
222  template<class View>
223  class NaryMaxDom : public NaryOnePropagator<View,PC_INT_DOM> {
224  protected:
227 
229  NaryMaxDom(Space& home, bool share, NaryMaxDom& p);
231  NaryMaxDom(Home home, ViewArray<View>& x, View y);
232  public:
234  virtual Actor* copy(Space& home, bool share);
241  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
243  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
245  static ExecStatus post(Home home, ViewArray<View>& x, View y);
246  };
247 
248 }}}
249 
251 
252 namespace Gecode { namespace Int { namespace Arithmetic {
253 
263  template<class VA, class VB, bool tiebreak>
264  class ArgMax : public Propagator {
265  protected:
269  VB y;
271  ArgMax(Space& home, bool share, ArgMax& p);
273  ArgMax(Home home, IdxViewArray<VA>& x, VB y);
274  public:
276  virtual Actor* copy(Space& home, bool share);
277  // Cost function (defined as low linear)
278  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
280  virtual void reschedule(Space& home);
282  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
284  virtual size_t dispose(Space& home);
291  static ExecStatus post(Home home, IdxViewArray<VA>& x, VB y);
292  };
293 
294 }}}
295 
297 
298 namespace Gecode { namespace Int { namespace Arithmetic {
299 
306  class SqrOps {
307  public:
309  bool even(void) const;
311  int exp(void) const;
313  void exp(int m);
315  template<class IntType>
316  IntType pow(IntType x) const;
318  int tpow(int x) const;
320  int fnroot(int x) const;
322  int cnroot(int x) const;
323  };
324 
331  class PowOps {
332  protected:
334  int n;
336  static bool even(int m);
338  bool powgr(long long int r, int x) const;
340  bool powle(long long int r, int x) const;
341  public:
343  PowOps(int n);
345  bool even(void) const;
347  int exp(void) const;
349  void exp(int m);
351  template<class IntType>
352  IntType pow(IntType x) const;
354  int tpow(int x) const;
356  int fnroot(int x) const;
358  int cnroot(int x) const;
359  };
360 
361 }}}
362 
364 
365 namespace Gecode { namespace Int { namespace Arithmetic {
366 
372  template<class VA, class VB, class Ops>
373  class PowPlusBnd : public MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND> {
374  protected:
378  Ops ops;
380  PowPlusBnd(Home home, VA x0, VB x1, const Ops& ops);
382  PowPlusBnd(Space& home, bool share, PowPlusBnd<VA,VB,Ops>& p);
383  public:
385  virtual Actor* copy(Space& home, bool share);
387  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
389  static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
390  };
391 
398  template<class Ops>
399  class PowBnd : public BinaryPropagator<IntView,PC_INT_BND> {
400  protected:
404  Ops ops;
406  PowBnd(Space& home, bool share, PowBnd& p);
408  PowBnd(Home home, IntView x0, IntView x1, const Ops& ops);
409  public:
411  virtual Actor* copy(Space& home, bool share);
413  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
415  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
416  };
417 
423  template<class VA, class VB, class Ops>
424  class PowPlusDom : public MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM> {
425  protected:
429  Ops ops;
431  PowPlusDom(Home home, VA x0, VB x1, const Ops& ops);
433  PowPlusDom(Space& home, bool share, PowPlusDom<VA,VB,Ops>& p);
434  public:
436  virtual Actor* copy(Space& home, bool share);
444  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
446  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
448  static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
449  };
450 
457  template<class Ops>
458  class PowDom : public BinaryPropagator<IntView,PC_INT_DOM> {
459  protected:
463  Ops ops;
465  PowDom(Space& home, bool share, PowDom<Ops>& p);
467  PowDom(Home home, IntView x0, IntView x1, const Ops& ops);
468  public:
470  virtual Actor* copy(Space& home, bool share);
472  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
480  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
482  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
483  };
484 
485 }}}
486 
488 
489 namespace Gecode { namespace Int { namespace Arithmetic {
490 
497  template<class Ops, bool minus>
498  class NrootPlusBnd : public BinaryPropagator<IntView,PC_INT_BND> {
499  protected:
503  Ops ops;
505  NrootPlusBnd(Space& home, bool share, NrootPlusBnd<Ops,minus>& p);
507  NrootPlusBnd(Home home, IntView x0, IntView x1, const Ops& ops);
508  public:
510  virtual Actor* copy(Space& home, bool share);
512  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
514  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
515  };
516 
523  template<class Ops>
524  class NrootBnd : public BinaryPropagator<IntView,PC_INT_BND> {
525  protected:
529  Ops ops;
531  NrootBnd(Space& home, bool share, NrootBnd<Ops>& p);
533  NrootBnd(Home home, IntView x0, IntView x1, const Ops& ops);
534  public:
536  virtual Actor* copy(Space& home, bool share);
538  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
540  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
541  };
542 
549  template<class Ops, bool minus>
550  class NrootPlusDom : public BinaryPropagator<IntView,PC_INT_DOM> {
551  protected:
555  Ops ops;
557  NrootPlusDom(Space& home, bool share, NrootPlusDom<Ops,minus>& p);
559  NrootPlusDom(Home home, IntView x0, IntView x1, const Ops& ops);
560  public:
562  virtual Actor* copy(Space& home, bool share);
564  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
572  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
574  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
575  };
576 
583  template<class Ops>
584  class NrootDom : public BinaryPropagator<IntView,PC_INT_DOM> {
585  protected:
589  Ops ops;
591  NrootDom(Space& home, bool share, NrootDom<Ops>& p);
593  NrootDom(Home home, IntView x0, IntView x1, const Ops& ops);
594  public:
596  virtual Actor* copy(Space& home, bool share);
598  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
606  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
608  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
609  };
610 
611 }}}
612 
614 
615 namespace Gecode { namespace Int { namespace Arithmetic {
616 
623  template<class View, PropCond pc>
624  class MultZeroOne : public BinaryPropagator<View,pc> {
625  protected:
628 
630  MultZeroOne(Space& home, bool share, MultZeroOne<View,pc>& p);
632  MultZeroOne(Home home, View x0, View x1);
634  static RelTest equal(View x, int n);
635  public:
637  virtual Actor* copy(Space& home, bool share);
639  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
641  static ExecStatus post(Home home, View x0, View x1);
642  };
643 
644 
645 
651  template<class VA, class VB, class VC>
652  class MultPlusBnd :
653  public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
654  protected:
658  public:
660  MultPlusBnd(Home home, VA x0, VB x1, VC x2);
662  MultPlusBnd(Space& home, bool share, MultPlusBnd<VA,VB,VC>& p);
664  static ExecStatus post(Home home, VA x0, VB x1, VC x2);
666  virtual Actor* copy(Space& home, bool share);
668  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
669  };
670 
678  class MultBnd : public TernaryPropagator<IntView,PC_INT_BND> {
679  protected:
684  MultBnd(Space& home, bool share, MultBnd& p);
685  public:
687  MultBnd(Home home, IntView x0, IntView x1, IntView x2);
690  static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
693  virtual Actor* copy(Space& home, bool share);
696  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
697  };
698 
699 
700 
706  template<class VA, class VB, class VC>
707  class MultPlusDom :
708  public MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM> {
709  protected:
713  public:
715  MultPlusDom(Home home, VA x0, VB x1, VC x2);
717  MultPlusDom(Space& home, bool share, MultPlusDom<VA,VB,VC>& p);
719  static ExecStatus post(Home home, VA x0, VB x1, VC x2);
721  virtual Actor* copy(Space& home, bool share);
728  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
730  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
731  };
732 
740  class MultDom : public TernaryPropagator<IntView,PC_INT_DOM> {
741  protected:
746  MultDom(Space& home, bool share, MultDom& p);
747  public:
749  MultDom(Home home, IntView x0, IntView x1, IntView x2);
752  static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
755  virtual Actor* copy(Space& home, bool share);
763  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
766  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
767  };
768 
769 }}}
770 
772 
773 namespace Gecode { namespace Int { namespace Arithmetic {
774 
780  template<class VA, class VB, class VC>
781  class DivPlusBnd :
782  public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
783  protected:
787  public:
789  DivPlusBnd(Home home, VA x0, VB x1, VC x2);
791  DivPlusBnd(Space& home, bool share, DivPlusBnd<VA,VB,VC>& p);
793  static ExecStatus post(Home home, VA x0, VB x1, VC x2);
795  virtual Actor* copy(Space& home, bool share);
797  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
798  };
799 
807  template<class View>
808  class DivBnd : public TernaryPropagator<View,PC_INT_BND> {
809  protected:
813 
815  DivBnd(Space& home, bool share, DivBnd<View>& p);
816  public:
818  DivBnd(Home home, View x0, View x1, View x2);
820  static ExecStatus post(Home home, View x0, View x1, View x2);
822  virtual Actor* copy(Space& home, bool share);
824  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
825  };
826 
837  template<class View>
838  class DivMod : public TernaryPropagator<View,PC_INT_BND> {
839  protected:
843 
845  DivMod(Space& home, bool share, DivMod<View>& p);
846  public:
848  DivMod(Home home, View x0, View x1, View x2);
850  static ExecStatus post(Home home, View x0, View x1, View x2);
852  virtual Actor* copy(Space& home, bool share);
854  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
855  };
856 
857 }}}
858 
860 
861 #endif
862 
863 // STATISTICS: int-prop
864 
Bounds consistent positive division propagator.
Definition: arithmetic.hh:781
Integer division/modulo propagator.
Definition: arithmetic.hh:838
Domain consistent ternary maximum propagator.
Definition: arithmetic.hh:188
Domain consistent n-th root propagator.
Definition: arithmetic.hh:584
Positive bounds consistent n-th root propagator.
Definition: arithmetic.hh:498
Domain consistent n-ary maximum propagator.
Definition: arithmetic.hh:223
void pow(Home home, FloatVar x0, int n, FloatVar x1)
Post propagator for for $n 0$.
Definition: arithmetic.cpp:113
bool powle(int n, long long int r, int x)
Definition: arithmetic.cpp:316
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: abs.hpp:122
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Base-class for propagators.
Definition: core.hpp:1092
Bounds consistent power propagator.
Definition: arithmetic.hh:399
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: propagator.hpp:406
VB y
Position of maximum view (maximal argument)
Definition: arithmetic.hh:269
Computation spaces.
Definition: core.hpp:1748
Base-class for both propagators and branchers.
Definition: core.hpp:696
Bounds consistent absolute value propagator.
Definition: arithmetic.hh:63
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Domain consistent n-th root propagator.
Definition: arithmetic.hh:550
Domain consistent absolute value propagator.
Definition: arithmetic.hh:96
Domain consistent positive multiplication propagator.
Definition: arithmetic.hh:707
int fnroot(int n, int x)
Definition: arithmetic.cpp:301
Binary propagator.
Definition: propagator.hpp:89
RelTest
Result of testing relation.
Definition: view.hpp:1614
Mixed ternary propagator.
Definition: propagator.hpp:247
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1103
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: abs.hpp:131
Bounds consistent positive power propagator.
Definition: arithmetic.hh:373
Operations for square and square-root propagators.
Definition: arithmetic.hh:306
Ternary propagator.
Definition: propagator.hpp:119
(n+1)-ary propagator
Definition: propagator.hpp:180
Bounds consistent n-ary maximum propagator.
Definition: arithmetic.hh:163
int cnroot(int n, int x)
Definition: arithmetic.cpp:329
View arrays.
Definition: array.hpp:234
int n
The exponent and root index.
Definition: arithmetic.hh:334
Argument maximum propagator.
Definition: arithmetic.hh:264
Bounds consistent division propagator.
Definition: arithmetic.hh:808
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: abs.hpp:116
bool powgr(int n, long long int r, int x)
Definition: arithmetic.cpp:289
Domain consistent power propagator.
Definition: arithmetic.hh:458
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
Domain consistent positive power propagator.
Definition: arithmetic.hh:424
Integer view for integer variables.
Definition: view.hpp:129
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
Bounds consistent multiplication propagator.
Definition: arithmetic.hh:678
Mixed binary propagator.
Definition: propagator.hpp:213
Propagation cost.
Definition: core.hpp:554
virtual void reschedule(Space &home)
Schedule function.
Definition: propagator.hpp:397
Operations for power and nroot propagators.
Definition: arithmetic.hh:331
ExecStatus
Definition: core.hpp:540
Bounds consistent ternary maximum propagator.
Definition: arithmetic.hh:135
IdxViewArray< VA > x
Map of index and views.
Definition: arithmetic.hh:267
Post propagator for SetVar x
Definition: set.hh:784
Gecode toplevel namespace
Bounds or domain consistent propagator for .
Definition: arithmetic.hh:624
Domain consistent multiplication propagator.
Definition: arithmetic.hh:740
IntType
Description of integer types.
Definition: int-type.hpp:43
#define GECODE_INT_EXPORT
Definition: int.hh:81
void exp(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
Bounds consistent n-th root propagator.
Definition: arithmetic.hh:524
AbsBnd(Space &home, bool share, AbsBnd &p)
Constructor for cloning p.
Definition: abs.hpp:111
Bounds consistent positive multiplication propagator.
Definition: arithmetic.hh:652
static ExecStatus post(Home home, View x0, View x1)
Post bounds consistent propagator .
Definition: abs.hpp:89