Generated on Sat Feb 7 2015 02:01:19 for Gecode by doxygen 1.8.9.1
mult.cpp
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 <gecode/int/arithmetic.hh>
39 
40 namespace Gecode { namespace Int { namespace Arithmetic {
41 
42  /*
43  * Bounds consistent multiplication
44  *
45  */
46  Actor*
47  MultBnd::copy(Space& home, bool share) {
48  return new (home) MultBnd(home,share,*this);
49  }
50 
53  if (pos(x0)) {
54  if (pos(x1) || pos(x2)) goto rewrite_ppp;
55  if (neg(x1) || neg(x2)) goto rewrite_pnn;
56  goto prop_pxx;
57  }
58  if (neg(x0)) {
59  if (neg(x1) || pos(x2)) goto rewrite_nnp;
60  if (pos(x1) || neg(x2)) goto rewrite_npn;
61  goto prop_nxx;
62  }
63  if (pos(x1)) {
64  if (pos(x2)) goto rewrite_ppp;
65  if (neg(x2)) goto rewrite_npn;
66  goto prop_xpx;
67  }
68  if (neg(x1)) {
69  if (pos(x2)) goto rewrite_nnp;
70  if (neg(x2)) goto rewrite_pnn;
71  goto prop_xnx;
72  }
73 
74  assert(any(x0) && any(x1));
76  mll(x0.min(),x1.min()))));
78  mll(x0.max(),x1.min()))));
79 
80  if (x0.assigned()) {
81  assert((x0.val() == 0) && (x2.val() == 0));
82  return home.ES_SUBSUMED(*this);
83  }
84 
85  if (x1.assigned()) {
86  assert((x1.val() == 0) && (x2.val() == 0));
87  return home.ES_SUBSUMED(*this);
88  }
89 
90  return ES_NOFIX;
91 
92  prop_xpx:
93  std::swap(x0,x1);
94  prop_pxx:
95  assert(pos(x0) && any(x1) && any(x2));
96 
97  GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
98  GECODE_ME_CHECK(x2.gq(home,mll(x0.max(),x1.min())));
99 
100  if (pos(x2)) goto rewrite_ppp;
101  if (neg(x2)) goto rewrite_pnn;
102 
104  GECODE_ME_CHECK(x1.gq(home,ceil_div_xp(x2.min(),x0.min())));
105 
106  if (x0.assigned() && x1.assigned()) {
107  GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
108  return home.ES_SUBSUMED(*this);
109  }
110 
111  return ES_NOFIX;
112 
113  prop_xnx:
114  std::swap(x0,x1);
115  prop_nxx:
116  assert(neg(x0) && any(x1) && any(x2));
117 
118  GECODE_ME_CHECK(x2.lq(home,mll(x0.min(),x1.min())));
119  GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.max())));
120 
121  if (pos(x2)) goto rewrite_nnp;
122  if (neg(x2)) goto rewrite_npn;
123 
125  GECODE_ME_CHECK(x1.gq(home,ceil_div_xx(x2.max(),x0.max())));
126 
127  if (x0.assigned() && x1.assigned()) {
128  GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
129  return home.ES_SUBSUMED(*this);
130  }
131 
132  return ES_NOFIX;
133 
134  rewrite_ppp:
136  ::post(home(*this),x0,x1,x2)));
137  rewrite_nnp:
139  ::post(home(*this),MinusView(x0),MinusView(x1),x2)));
140  rewrite_pnn:
141  std::swap(x0,x1);
142  rewrite_npn:
144  ::post(home(*this),MinusView(x0),x1,MinusView(x2))));
145  }
146 
147  ExecStatus
149  if (same(x0,x1)) {
150  SqrOps ops;
151  return PowBnd<SqrOps>::post(home,x0,x2,ops);
152  }
153  if (same(x0,x2))
154  return MultZeroOne<IntView,PC_INT_BND>::post(home,x0,x1);
155  if (same(x1,x2))
156  return MultZeroOne<IntView,PC_INT_BND>::post(home,x1,x0);
157  if (pos(x0)) {
158  if (pos(x1) || pos(x2)) goto post_ppp;
159  if (neg(x1) || neg(x2)) goto post_pnn;
160  } else if (neg(x0)) {
161  if (neg(x1) || pos(x2)) goto post_nnp;
162  if (pos(x1) || neg(x2)) goto post_npn;
163  } else if (pos(x1)) {
164  if (pos(x2)) goto post_ppp;
165  if (neg(x2)) goto post_npn;
166  } else if (neg(x1)) {
167  if (pos(x2)) goto post_nnp;
168  if (neg(x2)) goto post_pnn;
169  }
170  {
171  long long int a = mll(x0.min(),x1.min());
172  long long int b = mll(x0.min(),x1.max());
173  long long int c = mll(x0.max(),x1.min());
174  long long int d = mll(x0.max(),x1.max());
175  GECODE_ME_CHECK(x2.gq(home,std::min(std::min(a,b),std::min(c,d))));
176  GECODE_ME_CHECK(x2.lq(home,std::max(std::max(a,b),std::max(c,d))));
177  (void) new (home) MultBnd(home,x0,x1,x2);
178  }
179  return ES_OK;
180 
181  post_ppp:
183  ::post(home,x0,x1,x2);
184  post_nnp:
186  ::post(home,MinusView(x0),MinusView(x1),x2);
187  post_pnn:
188  std::swap(x0,x1);
189  post_npn:
191  ::post(home,MinusView(x0),x1,MinusView(x2));
192  }
193 
194 
195 
196  /*
197  * Domain consistent multiplication
198  *
199  */
200  Actor*
201  MultDom::copy(Space& home, bool share) {
202  return new (home) MultDom(home,share,*this);
203  }
204 
205  PropCost
206  MultDom::cost(const Space&, const ModEventDelta& med) const {
207  if (IntView::me(med) == ME_INT_DOM)
209  else
211  }
212 
213  ExecStatus
215  if (IntView::me(med) != ME_INT_DOM) {
216  if (pos(x0)) {
217  if (pos(x1) || pos(x2)) goto rewrite_ppp;
218  if (neg(x1) || neg(x2)) goto rewrite_pnn;
219  goto prop_pxx;
220  }
221  if (neg(x0)) {
222  if (neg(x1) || pos(x2)) goto rewrite_nnp;
223  if (pos(x1) || neg(x2)) goto rewrite_npn;
224  goto prop_nxx;
225  }
226  if (pos(x1)) {
227  if (pos(x2)) goto rewrite_ppp;
228  if (neg(x2)) goto rewrite_npn;
229  goto prop_xpx;
230  }
231  if (neg(x1)) {
232  if (pos(x2)) goto rewrite_nnp;
233  if (neg(x2)) goto rewrite_pnn;
234  goto prop_xnx;
235  }
236 
237  assert(any(x0) && any(x1));
239  mll(x0.min(),x1.min()))));
241  mll(x0.max(),x1.min()))));
242 
243  if (x0.assigned()) {
244  assert((x0.val() == 0) && (x2.val() == 0));
245  return home.ES_SUBSUMED(*this);
246  }
247 
248  if (x1.assigned()) {
249  assert((x1.val() == 0) && (x2.val() == 0));
250  return home.ES_SUBSUMED(*this);
251  }
252 
253  return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
254 
255  prop_xpx:
256  std::swap(x0,x1);
257  prop_pxx:
258  assert(pos(x0) && any(x1) && any(x2));
259 
260  GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
261  GECODE_ME_CHECK(x2.gq(home,mll(x0.max(),x1.min())));
262 
263  if (pos(x2)) goto rewrite_ppp;
264  if (neg(x2)) goto rewrite_pnn;
265 
267  GECODE_ME_CHECK(x1.gq(home,ceil_div_xp(x2.min(),x0.min())));
268 
269  if (x0.assigned() && x1.assigned()) {
270  GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
271  return home.ES_SUBSUMED(*this);
272  }
273 
274  return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
275 
276  prop_xnx:
277  std::swap(x0,x1);
278  prop_nxx:
279  assert(neg(x0) && any(x1) && any(x2));
280 
281  GECODE_ME_CHECK(x2.lq(home,mll(x0.min(),x1.min())));
282  GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.max())));
283 
284  if (pos(x2)) goto rewrite_nnp;
285  if (neg(x2)) goto rewrite_npn;
286 
288  GECODE_ME_CHECK(x1.gq(home,ceil_div_xx(x2.max(),x0.max())));
289 
290  if (x0.assigned() && x1.assigned()) {
291  GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
292  return home.ES_SUBSUMED(*this);
293  }
294 
295  return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
296 
297  rewrite_ppp:
299  ::post(home(*this),x0,x1,x2)));
300  rewrite_nnp:
302  ::post(home(*this),
303  MinusView(x0),MinusView(x1),x2)));
304  rewrite_pnn:
305  std::swap(x0,x1);
306  rewrite_npn:
308  ::post(home(*this),
309  MinusView(x0),x1,MinusView(x2))));
310  }
311  return prop_mult_dom<IntView>(home,*this,x0,x1,x2);
312  }
313 
314  ExecStatus
316  if (same(x0,x1)) {
317  SqrOps ops;
318  return PowDom<SqrOps>::post(home,x0,x2,ops);
319  }
320  if (same(x0,x2))
321  return MultZeroOne<IntView,PC_INT_DOM>::post(home,x0,x1);
322  if (same(x1,x2))
323  return MultZeroOne<IntView,PC_INT_DOM>::post(home,x1,x0);
324  if (pos(x0)) {
325  if (pos(x1) || pos(x2)) goto post_ppp;
326  if (neg(x1) || neg(x2)) goto post_pnn;
327  } else if (neg(x0)) {
328  if (neg(x1) || pos(x2)) goto post_nnp;
329  if (pos(x1) || neg(x2)) goto post_npn;
330  } else if (pos(x1)) {
331  if (pos(x2)) goto post_ppp;
332  if (neg(x2)) goto post_npn;
333  } else if (neg(x1)) {
334  if (pos(x2)) goto post_nnp;
335  if (neg(x2)) goto post_pnn;
336  }
337  {
338  long long int a = mll(x0.min(),x1.min());
339  long long int b = mll(x0.min(),x1.max());
340  long long int c = mll(x0.max(),x1.min());
341  long long int d = mll(x0.max(),x1.max());
342  GECODE_ME_CHECK(x2.gq(home,std::min(std::min(a,b),std::min(c,d))));
343  GECODE_ME_CHECK(x2.lq(home,std::max(std::max(a,b),std::max(c,d))));
344  (void) new (home) MultDom(home,x0,x1,x2);
345  }
346  return ES_OK;
347 
348  post_ppp:
350  ::post(home,x0,x1,x2);
351  post_nnp:
353  ::post(home,MinusView(x0),MinusView(x1),x2);
354  post_pnn:
355  std::swap(x0,x1);
356  post_npn:
358  ::post(home,MinusView(x0),x1,MinusView(x2));
359  }
360 
361 }}}
362 
363 // STATISTICS: int-prop
364 
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:70
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:109
bool any(const View &x)
Test whether x is neither positive nor negative.
Definition: mult.hpp:86
static ExecStatus post(Home home, View x0, View x1)
Post propagator .
Definition: mult.hpp:113
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:160
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:2986
static ExecStatus post(Home home, VA x0, VB x1, VC x2)
Post propagator .
Definition: mult.hpp:338
Expensive.
Definition: core.hpp:564
long long int mll(long long int x, long long int y)
Multiply x and .
Definition: mult.hpp:52
IntType floor_div_xx(IntType x, IntType y)
Compute .
Definition: div.hpp:91
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator .
Definition: mult.cpp:148
Computation spaces.
Definition: core.hpp:1362
Base-class for both propagators and branchers.
Definition: core.hpp:666
Gecode::IntSet d(v, 7)
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
bool same(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:389
Gecode::FloatVal c(-8, 8)
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
MultDom(Space &home, bool share, MultDom &p)
Constructor for cloning p.
Definition: mult.hpp:357
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: mult.cpp:214
Domain consistent positive multiplication propagator.
Definition: arithmetic.hh:705
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:115
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition: pow.hpp:154
Operations for square and square-root propagators.
Definition: arithmetic.hh:304
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
IntType floor_div_xp(IntType x, IntType y)
Compute where y is non-negative.
Definition: div.hpp:79
IntType ceil_div_xp(IntType x, IntType y)
Compute where y is non-negative.
Definition: div.hpp:73
IntType ceil_div_xx(IntType x, IntType y)
Compute .
Definition: div.hpp:86
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: mult.cpp:201
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: mult.cpp:47
Integer view for integer variables.
Definition: view.hpp:129
Propagation cost.
Definition: core.hpp:537
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator .
Definition: mult.cpp:315
ExecStatus
Definition: core.hpp:523
Minus integer view.
Definition: view.hpp:276
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:74
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: mult.cpp:206
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:448
static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops)
Post propagator.
Definition: pow.hpp:392
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:133
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.hpp:66
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4050
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: mult.cpp:52
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
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