Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.8.18
mult.hpp
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  *
6  * Copyright:
7  * Christian Schulte, 2004
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <cmath>
35 #include <climits>
36 
37 #include <gecode/int/div.hh>
39 
40 namespace Gecode { namespace Int { namespace Arithmetic {
41 
42  /*
43  * Arithmetic help functions
44  *
45  */
47  forceinline long long int
48  mll(long long int x, long long int y) {
49  return x*y;
50  }
52  forceinline long long int
53  ll(int x) {
54  return static_cast<long long int>(x);
55  }
57  forceinline long long int
58  ill(int x) {
59  return static_cast<long long int>(x) + 1;
60  }
62  forceinline long long int
63  dll(int x) {
64  return static_cast<long long int>(x) - 1;
65  }
66 
68  template<class View>
69  forceinline bool
70  pos(const View& x) {
71  return x.min() > 0;
72  }
74  template<class View>
75  forceinline bool
76  neg(const View& x) {
77  return x.max() < 0;
78  }
80  template<class View>
81  forceinline bool
82  any(const View& x) {
83  return (x.min() <= 0) && (x.max() >= 0);
84  }
85 
86 
87  /*
88  * Propagator for x * y = x
89  *
90  */
91 
92  template<class View, PropCond pc>
94  MultZeroOne<View,pc>::MultZeroOne(Home home, View x0, View x1)
95  : BinaryPropagator<View,pc>(home,x0,x1) {}
96 
97  template<class View, PropCond pc>
100  if (pc == PC_INT_DOM) {
101  return rtest_eq_dom(x,n);
102  } else {
103  return rtest_eq_bnd(x,n);
104  }
105  }
106 
107  template<class View, PropCond pc>
109  MultZeroOne<View,pc>::post(Home home, View x0, View x1) {
110  switch (equal(x0,0)) {
111  case RT_FALSE:
112  GECODE_ME_CHECK(x1.eq(home,1));
113  break;
114  case RT_TRUE:
115  break;
116  case RT_MAYBE:
117  switch (equal(x1,1)) {
118  case RT_FALSE:
119  GECODE_ME_CHECK(x0.eq(home,0));
120  break;
121  case RT_TRUE:
122  break;
123  case RT_MAYBE:
124  (void) new (home) MultZeroOne<View,pc>(home,x0,x1);
125  break;
126  default: GECODE_NEVER;
127  }
128  break;
129  default: GECODE_NEVER;
130  }
131  return ES_OK;
132  }
133 
134  template<class View, PropCond pc>
137  : BinaryPropagator<View,pc>(home,p) {}
138 
139  template<class View, PropCond pc>
140  Actor*
142  return new (home) MultZeroOne<View,pc>(home,*this);
143  }
144 
145  template<class View, PropCond pc>
146  ExecStatus
148  switch (equal(x0,0)) {
149  case RT_FALSE:
150  GECODE_ME_CHECK(x1.eq(home,1));
151  break;
152  case RT_TRUE:
153  break;
154  case RT_MAYBE:
155  switch (equal(x1,1)) {
156  case RT_FALSE:
157  GECODE_ME_CHECK(x0.eq(home,0));
158  break;
159  case RT_TRUE:
160  break;
161  case RT_MAYBE:
162  return ES_FIX;
163  default: GECODE_NEVER;
164  }
165  break;
166  default: GECODE_NEVER;
167  }
168  return home.ES_SUBSUMED(*this);
169  }
170 
171 
172  /*
173  * Positive bounds consistent multiplication
174  *
175  */
176  template<class VA, class VB, class VC>
178  prop_mult_plus_bnd(Space& home, Propagator& p, VA x0, VB x1, VC x2) {
179  assert(pos(x0) && pos(x1) && pos(x2));
180  bool mod;
181  do {
182  mod = false;
183  {
184  ModEvent me = x2.lq(home,mll(x0.max(),x1.max()));
185  if (me_failed(me)) return ES_FAILED;
186  mod |= me_modified(me);
187  }
188  {
189  ModEvent me = x2.gq(home,mll(x0.min(),x1.min()));
190  if (me_failed(me)) return ES_FAILED;
191  mod |= me_modified(me);
192  }
193  {
194  ModEvent me = x0.lq(home,floor_div_pp(x2.max(),x1.min()));
195  if (me_failed(me)) return ES_FAILED;
196  mod |= me_modified(me);
197  }
198  {
199  ModEvent me = x0.gq(home,ceil_div_pp(x2.min(),x1.max()));
200  if (me_failed(me)) return ES_FAILED;
201  mod |= me_modified(me);
202  }
203  {
204  ModEvent me = x1.lq(home,floor_div_pp(x2.max(),x0.min()));
205  if (me_failed(me)) return ES_FAILED;
206  mod |= me_modified(me);
207  }
208  {
209  ModEvent me = x1.gq(home,ceil_div_pp(x2.min(),x0.max()));
210  if (me_failed(me)) return ES_FAILED;
211  mod |= me_modified(me);
212  }
213  } while (mod);
214  return x0.assigned() && x1.assigned() ?
215  home.ES_SUBSUMED(p) : ES_FIX;
216  }
217 
218  template<class VA, class VB, class VC>
220  MultPlusBnd<VA,VB,VC>::MultPlusBnd(Home home, VA x0, VB x1, VC x2)
222  (home,x0,x1,x2) {}
223 
224  template<class VA, class VB, class VC>
228  (home,p) {}
229 
230  template<class VA, class VB, class VC>
231  Actor*
233  return new (home) MultPlusBnd<VA,VB,VC>(home,*this);
234  }
235 
236  template<class VA, class VB, class VC>
237  ExecStatus
239  return prop_mult_plus_bnd<VA,VB,VC>(home,*this,x0,x1,x2);
240  }
241 
242  template<class VA, class VB, class VC>
244  MultPlusBnd<VA,VB,VC>::post(Home home, VA x0, VB x1, VC x2) {
245  GECODE_ME_CHECK(x0.gr(home,0));
246  GECODE_ME_CHECK(x1.gr(home,0));
247  GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.min())));
248  GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
249  (void) new (home) MultPlusBnd<VA,VB,VC>(home,x0,x1,x2);
250  return ES_OK;
251  }
252 
253 
254  /*
255  * Bounds consistent multiplication
256  *
257  */
260  : TernaryPropagator<IntView,PC_INT_BND>(home,x0,x1,x2) {}
261 
265 
266  /*
267  * Positive domain consistent multiplication
268  *
269  */
270  template<class View>
272  prop_mult_dom(Space& home, Propagator& p, View x0, View x1, View x2) {
273  Region r;
274  SupportValues<View,Region> s0(r,x0), s1(r,x1), s2(r,x2);
275  while (s0()) {
276  while (s1()) {
277  if (s2.support(mll(s0.val(),s1.val()))) {
278  s0.support(); s1.support();
279  }
280  ++s1;
281  }
282  s1.reset(); ++s0;
283  }
284  GECODE_ME_CHECK(s0.tell(home));
285  GECODE_ME_CHECK(s1.tell(home));
286  GECODE_ME_CHECK(s2.tell(home));
287  return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(p) : ES_FIX;
288  }
289 
290  template<class VA, class VB, class VC>
292  MultPlusDom<VA,VB,VC>::MultPlusDom(Home home, VA x0, VB x1, VC x2)
294  (home,x0,x1,x2) {}
295 
296  template<class VA, class VB, class VC>
300  (home,p) {}
301 
302  template<class VA, class VB, class VC>
303  Actor*
305  return new (home) MultPlusDom<VA,VB,VC>(home,*this);
306  }
307 
308  template<class VA, class VB, class VC>
309  PropCost
311  const ModEventDelta& med) const {
312  if (VA::me(med) == ME_INT_DOM)
314  else
316  }
317 
318  template<class VA, class VB, class VC>
319  ExecStatus
321  if (VA::me(med) != ME_INT_DOM) {
322  GECODE_ES_CHECK((prop_mult_plus_bnd<VA,VB,VC>(home,*this,x0,x1,x2)));
323  return home.ES_FIX_PARTIAL(*this,VA::med(ME_INT_DOM));
324  }
325  IntView y0(x0.varimp()), y1(x1.varimp()), y2(x2.varimp());
326  return prop_mult_dom<IntView>(home,*this,y0,y1,y2);
327  }
328 
329  template<class VA, class VB, class VC>
331  MultPlusDom<VA,VB,VC>::post(Home home, VA x0, VB x1, VC x2) {
332  GECODE_ME_CHECK(x0.gr(home,0));
333  GECODE_ME_CHECK(x1.gr(home,0));
334  GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.min())));
335  GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
336  (void) new (home) MultPlusDom<VA,VB,VC>(home,x0,x1,x2);
337  return ES_OK;
338  }
339 
340 
341  /*
342  * Domain consistent multiplication
343  *
344  */
347  : TernaryPropagator<IntView,PC_INT_DOM>(home,x0,x1,x2) {}
348 
352 
353 }}}
354 
355 // STATISTICS: int-prop
356 
static ExecStatus post(Home home, VA x0, VB x1, VC x2)
Post propagator .
Definition: mult.hpp:331
Post propagator for SetVar x
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
long long int mll(long long int x, long long int y)
Multiply x and \y.
Definition: mult.hpp:48
Bounds consistent positive multiplication propagator.
Definition: arithmetic.hh:649
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:70
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: mult.hpp:232
long long int ll(int x)
Cast x into a long long int.
Definition: mult.hpp:53
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
RelTest rtest_eq_bnd(VX x, VY y)
Test whether views x and y are equal (use bounds information)
Definition: rel-test.hpp:43
Bounds consistent multiplication propagator.
Definition: arithmetic.hh:674
Support value iterator and recorder
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: mult.hpp:310
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: mult.hpp:304
Domain consistent multiplication propagator.
Definition: arithmetic.hh:736
@ LO
Cheap.
Definition: core.hpp:513
static ExecStatus post(Home home, VA x0, VB x1, VC x2)
Post propagator .
Definition: mult.hpp:244
Computation spaces.
Definition: core.hpp:1742
Base-class for both propagators and branchers.
Definition: core.hpp:628
@ RT_TRUE
Relation does hold.
Definition: view.hpp:1737
MultDom(Space &home, MultDom &p)
Constructor for cloning p.
Definition: mult.hpp:350
IntType floor_div_pp(IntType x, IntType y)
Compute where x and y are non-negative.
Definition: div.hpp:49
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: mult.hpp:147
ExecStatus prop_mult_plus_bnd(Space &home, Propagator &p, VA x0, VB x1, VC x2)
Definition: mult.hpp:178
Mixed ternary propagator.
Definition: pattern.hpp:237
MultPlusDom(Home home, VA x0, VB x1, VC x2)
Constructor for posting.
Definition: mult.hpp:292
long long int ill(int x)
Increment x by one.
Definition: mult.hpp:58
ExecStatus prop_mult_dom(Space &home, Propagator &p, View x0, View x1, View x2)
Definition: mult.hpp:272
Gecode toplevel namespace
Domain consistent positive multiplication propagator.
Definition: arithmetic.hh:704
Base-class for propagators.
Definition: core.hpp:1064
@ RT_MAYBE
Relation may hold or not.
Definition: view.hpp:1736
RelTest rtest_eq_dom(VX x, VY y)
Test whether views x and y are equal (use full domain information)
Definition: rel-test.hpp:65
@ RT_FALSE
Relation does not hold.
Definition: view.hpp:1735
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
void support(void)
Mark current (iterator) value as supported.
Home class for posting propagators
Definition: core.hpp:856
Ternary propagator.
Definition: pattern.hpp:113
Handle to region.
Definition: region.hpp:55
MultZeroOne(Space &home, MultZeroOne< View, pc > &p)
Constructor for cloning p.
Definition: mult.hpp:136
bool any(const View &x)
Test whether x is neither positive nor negative.
Definition: mult.hpp:82
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
static ExecStatus post(Home home, View x0, View x1)
Post propagator .
Definition: mult.hpp:109
MultBnd(Space &home, MultBnd &p)
Constructor for cloning p.
Definition: mult.hpp:263
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: mult.hpp:238
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
Bounds or domain consistent propagator for .
Definition: arithmetic.hh:620
int ModEvent
Type for modification events.
Definition: core.hpp:62
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4805
Propagation cost.
Definition: core.hpp:486
bool neg(const View &x)
Test whether x is negative.
Definition: mult.hpp:76
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntPropLevel ipl)
Post propagator for .
Definition: arithmetic.cpp:360
IntType ceil_div_pp(IntType x, IntType y)
Compute where x and y are non-negative.
Definition: div.hpp:38
long long int dll(int x)
Decrement x by one.
Definition: mult.hpp:63
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
static RelTest equal(View x, int n)
Test whether x is equal to n.
Definition: mult.hpp:99
Integer view for integer variables.
Definition: view.hpp:129
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: mult.hpp:141
ModEvent tell(Space &home)
Remove all unsupported values.
#define forceinline
Definition: config.hpp:185
RelTest
Result of testing relation.
Definition: view.hpp:1734
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
MultPlusBnd(Home home, VA x0, VB x1, VC x2)
Constructor for posting.
Definition: mult.hpp:220
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
@ HI
Expensive.
Definition: core.hpp:514
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
Binary propagator.
Definition: pattern.hpp:84
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:3569
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
@ ES_OK
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: mult.hpp:320
ExecStatus
Definition: core.hpp:472