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