Generated on Sat Feb 7 2015 02:01:14 for Gecode by doxygen 1.8.9.1
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: 2013-02-14 16:29:11 +0100 (Thu, 14 Feb 2013) $ by $Author: schulte $
11  * $Revision: 13292 $
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>
142  : BinaryPropagator<View,pc>(home,share,p) {}
143 
144  template<class View, PropCond pc>
145  Actor*
146  MultZeroOne<View,pc>::copy(Space& home, bool share) {
147  return new (home) MultZeroOne<View,pc>(home,share,*this);
148  }
149 
150  template<class View, PropCond pc>
151  ExecStatus
153  switch (equal(x0,0)) {
154  case RT_FALSE:
155  GECODE_ME_CHECK(x1.eq(home,1));
156  break;
157  case RT_TRUE:
158  break;
159  case RT_MAYBE:
160  switch (equal(x1,1)) {
161  case RT_FALSE:
162  GECODE_ME_CHECK(x0.eq(home,0));
163  break;
164  case RT_TRUE:
165  break;
166  case RT_MAYBE:
167  return ES_FIX;
168  default: GECODE_NEVER;
169  }
170  break;
171  default: GECODE_NEVER;
172  }
173  return home.ES_SUBSUMED(*this);
174  }
175 
176 
177  /*
178  * Positive bounds consistent multiplication
179  *
180  */
181  template<class VA, class VB, class VC>
183  prop_mult_plus_bnd(Space& home, Propagator& p, VA x0, VB x1, VC x2) {
184  assert(pos(x0) && pos(x1) && pos(x2));
185  bool mod;
186  do {
187  mod = false;
188  {
189  ModEvent me = x2.lq(home,mll(x0.max(),x1.max()));
190  if (me_failed(me)) return ES_FAILED;
191  mod |= me_modified(me);
192  }
193  {
194  ModEvent me = x2.gq(home,mll(x0.min(),x1.min()));
195  if (me_failed(me)) return ES_FAILED;
196  mod |= me_modified(me);
197  }
198  {
199  ModEvent me = x0.lq(home,floor_div_pp(x2.max(),x1.min()));
200  if (me_failed(me)) return ES_FAILED;
201  mod |= me_modified(me);
202  }
203  {
204  ModEvent me = x0.gq(home,ceil_div_pp(x2.min(),x1.max()));
205  if (me_failed(me)) return ES_FAILED;
206  mod |= me_modified(me);
207  }
208  {
209  ModEvent me = x1.lq(home,floor_div_pp(x2.max(),x0.min()));
210  if (me_failed(me)) return ES_FAILED;
211  mod |= me_modified(me);
212  }
213  {
214  ModEvent me = x1.gq(home,ceil_div_pp(x2.min(),x0.max()));
215  if (me_failed(me)) return ES_FAILED;
216  mod |= me_modified(me);
217  }
218  } while (mod);
219  return x0.assigned() && x1.assigned() ?
220  home.ES_SUBSUMED(p) : ES_FIX;
221  }
222 
223  template<class VA, class VB, class VC>
225  MultPlusBnd<VA,VB,VC>::MultPlusBnd(Home home, VA x0, VB x1, VC x2)
227  (home,x0,x1,x2) {}
228 
229  template<class VA, class VB, class VC>
234  (home,share,p) {}
235 
236  template<class VA, class VB, class VC>
237  Actor*
238  MultPlusBnd<VA,VB,VC>::copy(Space& home, bool share) {
239  return new (home) MultPlusBnd<VA,VB,VC>(home,share,*this);
240  }
241 
242  template<class VA, class VB, class VC>
243  ExecStatus
245  return prop_mult_plus_bnd<VA,VB,VC>(home,*this,x0,x1,x2);
246  }
247 
248  template<class VA, class VB, class VC>
250  MultPlusBnd<VA,VB,VC>::post(Home home, VA x0, VB x1, VC x2) {
251  GECODE_ME_CHECK(x0.gr(home,0));
252  GECODE_ME_CHECK(x1.gr(home,0));
253  GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.min())));
254  GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
255  (void) new (home) MultPlusBnd<VA,VB,VC>(home,x0,x1,x2);
256  return ES_OK;
257  }
258 
259 
260  /*
261  * Bounds consistent multiplication
262  *
263  */
266  : TernaryPropagator<IntView,PC_INT_BND>(home,x0,x1,x2) {}
267 
269  MultBnd::MultBnd(Space& home, bool share, MultBnd& p)
270  : TernaryPropagator<IntView,PC_INT_BND>(home,share,p) {}
271 
272  /*
273  * Positive domain consistent multiplication
274  *
275  */
276  template<class View>
278  prop_mult_dom(Space& home, Propagator& p, View x0, View x1, View x2) {
279  Region r(home);
280  SupportValues<View,Region> s0(r,x0), s1(r,x1), s2(r,x2);
281  while (s0()) {
282  while (s1()) {
283  if (s2.support(mll(s0.val(),s1.val()))) {
284  s0.support(); s1.support();
285  }
286  ++s1;
287  }
288  s1.reset(); ++s0;
289  }
290  GECODE_ME_CHECK(s0.tell(home));
291  GECODE_ME_CHECK(s1.tell(home));
292  GECODE_ME_CHECK(s2.tell(home));
293  return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(p) : ES_FIX;
294  }
295 
296  template<class VA, class VB, class VC>
298  MultPlusDom<VA,VB,VC>::MultPlusDom(Home home, VA x0, VB x1, VC x2)
300  (home,x0,x1,x2) {}
301 
302  template<class VA, class VB, class VC>
307  (home,share,p) {}
308 
309  template<class VA, class VB, class VC>
310  Actor*
311  MultPlusDom<VA,VB,VC>::copy(Space& home, bool share) {
312  return new (home) MultPlusDom<VA,VB,VC>(home,share,*this);
313  }
314 
315  template<class VA, class VB, class VC>
316  PropCost
318  const ModEventDelta& med) const {
319  if (VA::me(med) == ME_INT_DOM)
321  else
323  }
324 
325  template<class VA, class VB, class VC>
326  ExecStatus
328  if (VA::me(med) != ME_INT_DOM) {
329  GECODE_ES_CHECK((prop_mult_plus_bnd<VA,VB,VC>(home,*this,x0,x1,x2)));
330  return home.ES_FIX_PARTIAL(*this,VA::med(ME_INT_DOM));
331  }
332  IntView y0(x0.varimp()), y1(x1.varimp()), y2(x2.varimp());
333  return prop_mult_dom<IntView>(home,*this,y0,y1,y2);
334  }
335 
336  template<class VA, class VB, class VC>
338  MultPlusDom<VA,VB,VC>::post(Home home, VA x0, VB x1, VC x2) {
339  GECODE_ME_CHECK(x0.gr(home,0));
340  GECODE_ME_CHECK(x1.gr(home,0));
341  GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.min())));
342  GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
343  (void) new (home) MultPlusDom<VA,VB,VC>(home,x0,x1,x2);
344  return ES_OK;
345  }
346 
347 
348  /*
349  * Domain consistent multiplication
350  *
351  */
354  : TernaryPropagator<IntView,PC_INT_DOM>(home,x0,x1,x2) {}
355 
357  MultDom::MultDom(Space& home, bool share, MultDom& p)
358  : TernaryPropagator<IntView,PC_INT_DOM>(home,share,p) {}
359 
360 }}}
361 
362 // STATISTICS: int-prop
363 
IntType ceil_div_pp(IntType x, IntType y)
Compute where x and y are non-negative.
Definition: div.hpp:42
Relation may hold or not.
Definition: view.hpp:1616
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.
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntConLevel icl)
Post propagator for .
Definition: arithmetic.cpp:213
static ExecStatus post(Home home, View x0, View x1)
Post propagator .
Definition: mult.hpp:113
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: mult.hpp:146
MultZeroOne(Space &home, bool share, MultZeroOne< View, pc > &p)
Constructor for cloning p.
Definition: mult.hpp:140
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:338
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
int ModEvent
Type for modification events.
Definition: core.hpp:146
Base-class for propagators.
Definition: core.hpp:755
Expensive.
Definition: core.hpp:564
long long int mll(long long int x, long long int y)
Multiply x and .
Definition: mult.hpp:52
Handle to region.
Definition: region.hpp:61
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
Base-class for both propagators and branchers.
Definition: core.hpp:666
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:84
ExecStatus prop_mult_dom(Space &home, Propagator &p, View x0, View x1, View x2)
Definition: mult.hpp:278
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
MultDom(Space &home, bool share, MultDom &p)
Constructor for cloning p.
Definition: mult.hpp:357
Execution has resulted in failure.
Definition: core.hpp:525
ExecStatus prop_mult_plus_bnd(Space &home, Propagator &p, VA x0, VB x1, VC x2)
Definition: mult.hpp:183
Domain consistent positive multiplication propagator.
Definition: arithmetic.hh:705
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Binary propagator.
Definition: propagator.hpp:87
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: mult.hpp:311
Relation does not hold.
Definition: view.hpp:1615
RelTest
Result of testing relation.
Definition: view.hpp:1614
Mixed ternary propagator.
Definition: propagator.hpp:235
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 ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: mult.hpp:244
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
Ternary propagator.
Definition: propagator.hpp:115
static RelTest equal(View x, int n)
Test whether x is equal to n.
Definition: mult.hpp:103
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: mult.hpp:327
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
RelTest rtest_eq_dom(View x, View y)
Test whether views x and y are equal (use full domain information)
Definition: rel-test.hpp:68
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:2979
void support(void)
Mark current (iterator) value as supported.
Integer view for integer variables.
Definition: view.hpp:129
Bounds consistent multiplication propagator.
Definition: arithmetic.hh:676
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Propagation cost.
Definition: core.hpp:537
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
ExecStatus
Definition: core.hpp:523
#define forceinline
Definition: config.hpp:132
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:225
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
Execution is okay.
Definition: core.hpp:527
RelTest rtest_eq_bnd(View x, View y)
Test whether views x and y are equal (use bounds information)
Definition: rel-test.hpp:47
MultPlusDom(Home home, VA x0, VB x1, VC x2)
Constructor for posting.
Definition: mult.hpp:298
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: mult.hpp:317
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4050
Gecode toplevel namespace
Bounds or domain consistent propagator for .
Definition: arithmetic.hh:622
Domain consistent multiplication propagator.
Definition: arithmetic.hh:738
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: mult.hpp:152
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
#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:1617
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: mult.hpp:238
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:250
Bounds consistent positive multiplication propagator.
Definition: arithmetic.hh:650
MultBnd(Space &home, bool share, MultBnd &p)
Constructor for cloning p.
Definition: mult.hpp:269