Generated on Fri Jan 28 2022 04:43:06 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  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 #ifndef __GECODE_INT_ARITHMETIC_HH__
37 #define __GECODE_INT_ARITHMETIC_HH__
38 
39 #include <gecode/int.hh>
40 
41 #include <gecode/int/idx-view.hh>
42 #include <gecode/int/rel.hh>
43 #include <gecode/int/linear.hh>
44 
50 namespace Gecode { namespace Int { namespace Arithmetic {
51 
58  template<class View>
59  class AbsBnd : public BinaryPropagator<View,PC_INT_BND> {
60  protected:
63 
65  AbsBnd(Space& home, AbsBnd& p);
67  AbsBnd(Home home, View x0, View x1);
68  public:
69 
71  virtual Actor* copy(Space& home);
78  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
80  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
82  static ExecStatus post(Home home, View x0, View x1);
83  };
84 
91  template<class View>
92  class AbsDom : public BinaryPropagator<View,PC_INT_DOM> {
93  protected:
96 
98  AbsDom(Space& home, AbsDom& p);
100  AbsDom(Home home, View x0, View x1);
101  public:
103  virtual Actor* copy(Space& home);
111  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
113  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
115  static ExecStatus post(Home home, View x0, View x1);
116  };
117 
118 }}}
119 
121 
122 namespace Gecode { namespace Int { namespace Arithmetic {
123 
130  template<class View>
131  class MaxBnd : public TernaryPropagator<View,PC_INT_BND> {
132  protected:
136 
138  MaxBnd(Space& home, MaxBnd& p);
140  MaxBnd(Home home, View x0, View x1, View x2);
141  public:
143  MaxBnd(Space& home, Propagator& p, View x0, View x1, View x2);
145  virtual Actor* copy(Space& home);
147  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
149  static ExecStatus post(Home home, View x0, View x1, View x2);
150  };
151 
158  template<class View>
159  class NaryMaxBnd : public NaryOnePropagator<View,PC_INT_BND> {
160  protected:
163 
165  NaryMaxBnd(Space& home, NaryMaxBnd& p);
167  NaryMaxBnd(Home home, ViewArray<View>& x, View y);
168  public:
170  virtual Actor* copy(Space& home);
172  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
174  static ExecStatus post(Home home, ViewArray<View>& x, View y);
175  };
176 
183  template<class View>
184  class MaxDom : public TernaryPropagator<View,PC_INT_DOM> {
185  protected:
189 
191  MaxDom(Space& home, MaxDom& p);
193  MaxDom(Home home, View x0, View x1, View x2);
194  public:
196  MaxDom(Space& home, Propagator& p, View x0, View x1, View x2);
198  virtual Actor* copy(Space& home);
205  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
207  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
209  static ExecStatus post(Home home, View x0, View x1, View x2);
210  };
211 
218  template<class View>
219  class NaryMaxDom : public NaryOnePropagator<View,PC_INT_DOM> {
220  protected:
223 
225  NaryMaxDom(Space& home, NaryMaxDom& p);
227  NaryMaxDom(Home home, ViewArray<View>& x, View y);
228  public:
230  virtual Actor* copy(Space& home);
237  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
239  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
241  static ExecStatus post(Home home, ViewArray<View>& x, View y);
242  };
243 
244 }}}
245 
247 
248 namespace Gecode { namespace Int { namespace Arithmetic {
249 
259  template<class VA, class VB, bool tiebreak>
260  class ArgMax : public Propagator {
261  protected:
265  VB y;
267  ArgMax(Space& home, ArgMax& p);
269  ArgMax(Home home, IdxViewArray<VA>& x, VB y);
270  public:
272  virtual Actor* copy(Space& home);
273  // Cost function (defined as low linear)
274  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
276  virtual void reschedule(Space& home);
278  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
280  virtual size_t dispose(Space& home);
287  static ExecStatus post(Home home, IdxViewArray<VA>& x, VB y);
288  };
289 
290 }}}
291 
293 
294 namespace Gecode { namespace Int { namespace Arithmetic {
295 
302  class SqrOps {
303  public:
305  bool even(void) const;
307  int exp(void) const;
309  void exp(int m);
311  template<class IntType>
312  IntType pow(IntType x) const;
314  int tpow(int x) const;
316  int fnroot(int x) const;
318  int cnroot(int x) const;
319  };
320 
327  class PowOps {
328  protected:
330  int n;
332  static bool even(int m);
334  bool powgr(long long int r, int x) const;
336  bool powle(long long int r, int x) const;
337  public:
339  PowOps(int n);
341  bool even(void) const;
343  int exp(void) const;
345  void exp(int m);
347  template<class IntType>
348  IntType pow(IntType x) const;
350  int tpow(int x) const;
352  int fnroot(int x) const;
354  int cnroot(int x) const;
355  };
356 
357 }}}
358 
360 
361 namespace Gecode { namespace Int { namespace Arithmetic {
362 
368  template<class VA, class VB, class Ops>
369  class PowPlusBnd : public MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND> {
370  protected:
374  Ops ops;
376  PowPlusBnd(Home home, VA x0, VB x1, const Ops& ops);
379  public:
381  virtual Actor* copy(Space& home);
383  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
385  static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
386  };
387 
394  template<class Ops>
395  class PowBnd : public BinaryPropagator<IntView,PC_INT_BND> {
396  protected:
400  Ops ops;
402  PowBnd(Space& home, PowBnd& p);
404  PowBnd(Home home, IntView x0, IntView x1, const Ops& ops);
405  public:
407  virtual Actor* copy(Space& home);
409  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
411  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
412  };
413 
419  template<class VA, class VB, class Ops>
420  class PowPlusDom : public MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM> {
421  protected:
425  Ops ops;
427  PowPlusDom(Home home, VA x0, VB x1, const Ops& ops);
430  public:
432  virtual Actor* copy(Space& home);
440  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
442  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
444  static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
445  };
446 
453  template<class Ops>
454  class PowDom : public BinaryPropagator<IntView,PC_INT_DOM> {
455  protected:
459  Ops ops;
461  PowDom(Space& home, PowDom<Ops>& p);
463  PowDom(Home home, IntView x0, IntView x1, const Ops& ops);
464  public:
466  virtual Actor* copy(Space& home);
468  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
476  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
478  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
479  };
480 
481 }}}
482 
484 
485 namespace Gecode { namespace Int { namespace Arithmetic {
486 
493  template<class Ops, bool minus>
494  class NrootPlusBnd : public BinaryPropagator<IntView,PC_INT_BND> {
495  protected:
499  Ops ops;
503  NrootPlusBnd(Home home, IntView x0, IntView x1, const Ops& ops);
504  public:
506  virtual Actor* copy(Space& home);
508  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
510  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
511  };
512 
519  template<class Ops>
520  class NrootBnd : public BinaryPropagator<IntView,PC_INT_BND> {
521  protected:
525  Ops ops;
527  NrootBnd(Space& home, NrootBnd<Ops>& p);
529  NrootBnd(Home home, IntView x0, IntView x1, const Ops& ops);
530  public:
532  virtual Actor* copy(Space& home);
534  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
536  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
537  };
538 
545  template<class Ops, bool minus>
546  class NrootPlusDom : public BinaryPropagator<IntView,PC_INT_DOM> {
547  protected:
551  Ops ops;
555  NrootPlusDom(Home home, IntView x0, IntView x1, const Ops& ops);
556  public:
558  virtual Actor* copy(Space& home);
560  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
568  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
570  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
571  };
572 
579  template<class Ops>
580  class NrootDom : public BinaryPropagator<IntView,PC_INT_DOM> {
581  protected:
585  Ops ops;
587  NrootDom(Space& home, NrootDom<Ops>& p);
589  NrootDom(Home home, IntView x0, IntView x1, const Ops& ops);
590  public:
592  virtual Actor* copy(Space& home);
594  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
602  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
604  static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
605  };
606 
607 }}}
608 
610 
611 namespace Gecode { namespace Int { namespace Arithmetic {
612 
619  template<class View, PropCond pc>
620  class MultZeroOne : public BinaryPropagator<View,pc> {
621  protected:
624 
628  MultZeroOne(Home home, View x0, View x1);
630  static RelTest equal(View x, int n);
631  public:
633  virtual Actor* copy(Space& home);
635  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
637  static ExecStatus post(Home home, View x0, View x1);
638  };
639 
640 
641 
647  template<class VA, class VB, class VC>
648  class MultPlusBnd :
649  public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
650  protected:
654  public:
656  MultPlusBnd(Home home, VA x0, VB x1, VC x2);
660  static ExecStatus post(Home home, VA x0, VB x1, VC x2);
662  virtual Actor* copy(Space& home);
664  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
665  };
666 
674  class MultBnd : public TernaryPropagator<IntView,PC_INT_BND> {
675  protected:
680  MultBnd(Space& home, MultBnd& p);
681  public:
683  MultBnd(Home home, IntView x0, IntView x1, IntView x2);
686  static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
689  virtual Actor* copy(Space& home);
692  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
693  };
694 
695 
696 
702  template<class VA, class VB, class VC>
703  class MultPlusDom :
704  public MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM> {
705  protected:
709  public:
711  MultPlusDom(Home home, VA x0, VB x1, VC x2);
715  static ExecStatus post(Home home, VA x0, VB x1, VC x2);
717  virtual Actor* copy(Space& home);
724  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
726  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
727  };
728 
736  class MultDom : public TernaryPropagator<IntView,PC_INT_DOM> {
737  protected:
742  MultDom(Space& home, MultDom& p);
743  public:
745  MultDom(Home home, IntView x0, IntView x1, IntView x2);
748  static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
751  virtual Actor* copy(Space& home);
759  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
762  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
763  };
764 
765 }}}
766 
768 
769 namespace Gecode { namespace Int { namespace Arithmetic {
770 
776  template<class VA, class VB, class VC>
777  class DivPlusBnd :
778  public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
779  protected:
783  public:
785  DivPlusBnd(Home home, VA x0, VB x1, VC x2);
789  static ExecStatus post(Home home, VA x0, VB x1, VC x2);
791  virtual Actor* copy(Space& home);
793  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
794  };
795 
803  template<class View>
804  class DivBnd : public TernaryPropagator<View,PC_INT_BND> {
805  protected:
809 
811  DivBnd(Space& home, DivBnd<View>& p);
812  public:
814  DivBnd(Home home, View x0, View x1, View x2);
816  static ExecStatus post(Home home, View x0, View x1, View x2);
818  virtual Actor* copy(Space& home);
820  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
821  };
822 
833  template<class View>
834  class DivMod : public TernaryPropagator<View,PC_INT_BND> {
835  protected:
839 
841  DivMod(Space& home, DivMod<View>& p);
842  public:
844  DivMod(Home home, View x0, View x1, View x2);
846  static ExecStatus post(Home home, View x0, View x1, View x2);
848  virtual Actor* copy(Space& home);
850  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
851  };
852 
853 }}}
854 
856 
857 #endif
858 
859 // STATISTICS: int-prop
860 
Bounds consistent positive division propagator.
Definition: arithmetic.hh:777
Integer division/modulo propagator.
Definition: arithmetic.hh:834
Domain consistent ternary maximum propagator.
Definition: arithmetic.hh:184
Domain consistent n-th root propagator.
Definition: arithmetic.hh:580
Positive bounds consistent n-th root propagator.
Definition: arithmetic.hh:494
Domain consistent n-ary maximum propagator.
Definition: arithmetic.hh:219
void pow(Home home, FloatVar x0, int n, FloatVar x1)
Post propagator for for $n 0$.
Definition: arithmetic.cpp:109
bool powle(int n, long long int r, int x)
Definition: arithmetic.cpp:312
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: abs.hpp:126
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Base-class for propagators.
Definition: core.hpp:1023
Bounds consistent power propagator.
Definition: arithmetic.hh:395
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: pattern.hpp:396
VB y
Position of maximum view (maximal argument)
Definition: arithmetic.hh:265
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: abs.hpp:120
AbsBnd(Space &home, AbsBnd &p)
Constructor for cloning p.
Definition: abs.hpp:115
Computation spaces.
Definition: core.hpp:1701
Base-class for both propagators and branchers.
Definition: core.hpp:627
Bounds consistent absolute value propagator.
Definition: arithmetic.hh:59
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Domain consistent n-th root propagator.
Definition: arithmetic.hh:546
Domain consistent absolute value propagator.
Definition: arithmetic.hh:92
Domain consistent positive multiplication propagator.
Definition: arithmetic.hh:703
int fnroot(int n, int x)
Definition: arithmetic.cpp:297
Binary propagator.
Definition: pattern.hpp:84
RelTest
Result of testing relation.
Definition: view.hpp:1701
Mixed ternary propagator.
Definition: pattern.hpp:237
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1034
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: abs.hpp:135
Bounds consistent positive power propagator.
Definition: arithmetic.hh:369
Operations for square and square-root propagators.
Definition: arithmetic.hh:302
Ternary propagator.
Definition: pattern.hpp:113
(n+1)-ary propagator
Definition: pattern.hpp:172
Bounds consistent n-ary maximum propagator.
Definition: arithmetic.hh:159
int cnroot(int n, int x)
Definition: arithmetic.cpp:325
View arrays.
Definition: array.hpp:235
int n
The exponent and root index.
Definition: arithmetic.hh:330
Argument maximum propagator.
Definition: arithmetic.hh:260
Bounds consistent division propagator.
Definition: arithmetic.hh:804
bool powgr(int n, long long int r, int x)
Definition: arithmetic.cpp:285
Domain consistent power propagator.
Definition: arithmetic.hh:454
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Domain consistent positive power propagator.
Definition: arithmetic.hh:420
Integer view for integer variables.
Definition: view.hpp:129
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Bounds consistent multiplication propagator.
Definition: arithmetic.hh:674
Mixed binary propagator.
Definition: pattern.hpp:204
Propagation cost.
Definition: core.hpp:485
virtual void reschedule(Space &home)
Schedule function.
Definition: pattern.hpp:387
Operations for power and nroot propagators.
Definition: arithmetic.hh:327
ExecStatus
Definition: core.hpp:471
Bounds consistent ternary maximum propagator.
Definition: arithmetic.hh:131
IdxViewArray< VA > x
Map of index and views.
Definition: arithmetic.hh:263
Post propagator for SetVar x
Definition: set.hh:767
Gecode toplevel namespace
Bounds or domain consistent propagator for .
Definition: arithmetic.hh:620
Domain consistent multiplication propagator.
Definition: arithmetic.hh:736
IntType
Description of integer types.
Definition: int-type.hpp:39
#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:89
Home class for posting propagators
Definition: core.hpp:853
Bounds consistent n-th root propagator.
Definition: arithmetic.hh:520
Bounds consistent positive multiplication propagator.
Definition: arithmetic.hh:648
static ExecStatus post(Home home, View x0, View x1)
Post bounds consistent propagator .
Definition: abs.hpp:93