Generated on Tue Mar 24 2020 14:04:04 for Gecode by doxygen 1.8.17
arithmetic.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, 2002
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 <gecode/int/arithmetic.hh>
35 
36 namespace Gecode {
37 
38  void
39  abs(Home home, IntVar x0, IntVar x1, IntPropLevel ipl) {
40  using namespace Int;
42  if (vbd(ipl) == IPL_DOM) {
44  } else {
46  }
47  }
48 
49 
50  void
51  max(Home home, IntVar x0, IntVar x1, IntVar x2,
52  IntPropLevel ipl) {
53  using namespace Int;
55  if (vbd(ipl) == IPL_DOM) {
57  } else {
59  }
60  }
61 
62  void
63  max(Home home, const IntVarArgs& x, IntVar y,
64  IntPropLevel ipl) {
65  using namespace Int;
66  if (x.size() == 0)
67  throw TooFewArguments("Int::max");
69  ViewArray<IntView> xv(home,x);
70  if (vbd(ipl) == IPL_DOM) {
72  } else {
74  }
75  }
76 
77  void
78  min(Home home, IntVar x0, IntVar x1, IntVar x2,
79  IntPropLevel ipl) {
80  using namespace Int;
82  MinusView m0(x0); MinusView m1(x1); MinusView m2(x2);
83  if (vbd(ipl) == IPL_DOM) {
85  } else {
87  }
88  }
89 
90  void
91  min(Home home, const IntVarArgs& x, IntVar y,
92  IntPropLevel ipl) {
93  using namespace Int;
94  if (x.size() == 0)
95  throw TooFewArguments("Int::min");
97  ViewArray<MinusView> m(home,x.size());
98  for (int i=0; i<x.size(); i++)
99  m[i] = MinusView(x[i]);
100  MinusView my(y);
101  if (vbd(ipl) == IPL_DOM) {
103  } else {
105  }
106  }
107 
108 
109  void
110  argmax(Home home, const IntVarArgs& x, IntVar y, bool tiebreak,
111  IntPropLevel) {
112  using namespace Int;
113  if (x.size() == 0)
114  throw TooFewArguments("Int::argmax");
115  if (same(x,y))
116  throw ArgumentSame("Int::argmax");
117  GECODE_POST;
118  // Constrain y properly
119  IntView yv(y);
120  GECODE_ME_FAIL(yv.gq(home,0));
121  GECODE_ME_FAIL(yv.le(home,x.size()));
122  // Construct index view array
123  IdxViewArray<IntView> ix(home,x.size());
124  for (int i=0; i<x.size(); i++) {
125  ix[i].idx=i; ix[i].view=x[i];
126  }
127  if (tiebreak)
129  ::post(home,ix,yv)));
130  else
132  ::post(home,ix,yv)));
133  }
134 
135  void
136  argmax(Home home, const IntVarArgs& x, int o, IntVar y, bool tiebreak,
137  IntPropLevel) {
138  using namespace Int;
139  Limits::nonnegative(o,"Int::argmax");
140  if (x.size() == 0)
141  throw TooFewArguments("Int::argmax");
142  if (same(x,y))
143  throw ArgumentSame("Int::argmax");
144  GECODE_POST;
145  // Constrain y properly
146  OffsetView yv(y,-o);
147  GECODE_ME_FAIL(yv.gq(home,0));
148  GECODE_ME_FAIL(yv.le(home,x.size()));
149  // Construct index view array
150  IdxViewArray<IntView> ix(home,x.size());
151  for (int i=0; i<x.size(); i++) {
152  ix[i].idx=i; ix[i].view=x[i];
153  }
154  if (tiebreak)
156  ::post(home,ix,yv)));
157  else
159  ::post(home,ix,yv)));
160  }
161 
162  void
163  argmin(Home home, const IntVarArgs& x, IntVar y, bool tiebreak,
164  IntPropLevel) {
165  using namespace Int;
166  if (x.size() == 0)
167  throw TooFewArguments("Int::argmin");
168  if (same(x,y))
169  throw ArgumentSame("Int::argmin");
170  GECODE_POST;
171  // Constrain y properly
172  IntView yv(y);
173  GECODE_ME_FAIL(yv.gq(home,0));
174  GECODE_ME_FAIL(yv.le(home,x.size()));
175  // Construct index view array
176  IdxViewArray<MinusView> ix(home,x.size());
177  for (int i=0; i<x.size(); i++) {
178  ix[i].idx=i; ix[i].view=MinusView(x[i]);
179  }
180  if (tiebreak)
182  ::post(home,ix,yv)));
183  else
185  ::post(home,ix,yv)));
186  }
187 
188  void
189  argmin(Home home, const IntVarArgs& x, int o, IntVar y, bool tiebreak,
190  IntPropLevel) {
191  using namespace Int;
192  Limits::nonnegative(o,"Int::argmin");
193  if (x.size() == 0)
194  throw TooFewArguments("Int::argmin");
195  if (same(x,y))
196  throw ArgumentSame("Int::argmin");
197  GECODE_POST;
198  // Constrain y properly
199  OffsetView yv(y,-o);
200  GECODE_ME_FAIL(yv.gq(home,0));
201  GECODE_ME_FAIL(yv.le(home,x.size()));
202  // Construct index view array
203  IdxViewArray<MinusView> ix(home,x.size());
204  for (int i=0; i<x.size(); i++) {
205  ix[i].idx=i; ix[i].view=MinusView(x[i]);
206  }
207  if (tiebreak)
209  ::post(home,ix,yv)));
210  else
212  ::post(home,ix,yv)));
213  }
214 
215  void
216  argmax(Home home, const BoolVarArgs& x, IntVar y, bool tiebreak,
217  IntPropLevel) {
218  using namespace Int;
219  if (x.size() == 0)
220  throw TooFewArguments("Int::argmax");
221  GECODE_POST;
222  // Constrain y properly
223  IntView yv(y);
224  GECODE_ME_FAIL(yv.gq(home,0));
225  GECODE_ME_FAIL(yv.le(home,x.size()));
226  // Construct index view array
227  IdxViewArray<BoolView> ix(home,x.size());
228  for (int i=x.size(); i--; ) {
229  ix[i].idx=i; ix[i].view=x[i];
230  }
231  if (tiebreak)
233  ::post(home,ix,yv)));
234  else
236  ::post(home,ix,yv)));
237  }
238 
239  void
240  argmax(Home home, const BoolVarArgs& x, int o, IntVar y, bool tiebreak,
241  IntPropLevel) {
242  using namespace Int;
243  Limits::nonnegative(o,"Int::argmax");
244  if (x.size() == 0)
245  throw TooFewArguments("Int::argmax");
246  GECODE_POST;
247  // Constrain y properly
248  OffsetView yv(y,-o);
249  GECODE_ME_FAIL(yv.gq(home,0));
250  GECODE_ME_FAIL(yv.le(home,x.size()));
251  // Construct index view array
252  IdxViewArray<BoolView> ix(home,x.size());
253  for (int i=x.size(); i--; ) {
254  ix[i].idx=i; ix[i].view=x[i];
255  }
256  if (tiebreak)
258  ::post(home,ix,yv)));
259  else
261  ::post(home,ix,yv)));
262  }
263 
264  void
265  argmin(Home home, const BoolVarArgs& x, IntVar y, bool tiebreak,
266  IntPropLevel) {
267  using namespace Int;
268  if (x.size() == 0)
269  throw TooFewArguments("Int::argmin");
270  GECODE_POST;
271  // Constrain y properly
272  IntView yv(y);
273  GECODE_ME_FAIL(yv.gq(home,0));
274  GECODE_ME_FAIL(yv.le(home,x.size()));
275  // Construct index view array
276  IdxViewArray<NegBoolView> ix(home,x.size());
277  for (int i=x.size(); i--; ) {
278  ix[i].idx=i; ix[i].view=NegBoolView(x[i]);
279  }
280  if (tiebreak)
282  ::post(home,ix,yv)));
283  else
285  ::post(home,ix,yv)));
286  }
287 
288  void
289  argmin(Home home, const BoolVarArgs& x, int o, IntVar y, bool tiebreak,
290  IntPropLevel) {
291  using namespace Int;
292  Limits::nonnegative(o,"Int::argmin");
293  if (x.size() == 0)
294  throw TooFewArguments("Int::argmin");
295  GECODE_POST;
296  // Constrain y properly
297  OffsetView yv(y,-o);
298  GECODE_ME_FAIL(yv.gq(home,0));
299  GECODE_ME_FAIL(yv.le(home,x.size()));
300  // Construct index view array
301  IdxViewArray<NegBoolView> ix(home,x.size());
302  for (int i=x.size(); i--; ) {
303  ix[i].idx=i; ix[i].view=NegBoolView(x[i]);
304  }
305  if (tiebreak)
307  ::post(home,ix,yv)));
308  else
310  ::post(home,ix,yv)));
311  }
312 
313  void
314  mult(Home home, IntVar x0, IntVar x1, IntVar x2,
315  IntPropLevel ipl) {
316  using namespace Int;
317  GECODE_POST;
318  if (vbd(ipl) == IPL_DOM) {
320  } else {
322  }
323  }
324 
325 
326  void
327  divmod(Home home, IntVar x0, IntVar x1, IntVar x2, IntVar x3,
328  IntPropLevel) {
329  using namespace Int;
330  GECODE_POST;
331 
333  GECODE_ES_FAIL(Arithmetic::MultBnd::post(home,x1,x2,prod));
335  t[0].a = 1; t[0].x = prod;
336  t[1].a = 1; t[1].x = x3;
337  int min, max;
338  Linear::estimate(t,2,0,min,max);
339  IntView x0v(x0);
340  GECODE_ME_FAIL(x0v.gq(home,min));
341  GECODE_ME_FAIL(x0v.lq(home,max));
342  t[2].a=-1; t[2].x=x0;
343  Linear::post(home,t,3,IRT_EQ,0,IPL_BND);
344  if (home.failed()) return;
345  IntView x1v(x1);
347  Arithmetic::DivMod<IntView>::post(home,x0,x1,x3));
348  }
349 
350  void
351  div(Home home, IntVar x0, IntVar x1, IntVar x2,
352  IntPropLevel) {
353  using namespace Int;
354  GECODE_POST;
356  (Arithmetic::DivBnd<IntView>::post(home,x0,x1,x2)));
357  }
358 
359  void
360  mod(Home home, IntVar x0, IntVar x1, IntVar x2,
361  IntPropLevel ipl) {
362  using namespace Int;
363  GECODE_POST;
365  divmod(home, x0, x1, _div, x2, ipl);
366  }
367 
368  void
369  sqr(Home home, IntVar x0, IntVar x1, IntPropLevel ipl) {
370  using namespace Int;
371  GECODE_POST;
372  Arithmetic::SqrOps ops;
373  if (vbd(ipl) == IPL_DOM) {
375  ::post(home,x0,x1,ops));
376  } else {
378  ::post(home,x0,x1,ops));
379  }
380  }
381 
382  void
383  sqrt(Home home, IntVar x0, IntVar x1, IntPropLevel ipl) {
384  using namespace Int;
385  GECODE_POST;
386  Arithmetic::SqrOps ops;
387  if (vbd(ipl) == IPL_DOM) {
389  ::post(home,x0,x1,ops));
390  } else {
392  ::post(home,x0,x1,ops));
393  }
394  }
395 
396  void
397  pow(Home home, IntVar x0, int n, IntVar x1, IntPropLevel ipl) {
398  using namespace Int;
399  Limits::nonnegative(n,"Int::pow");
400  GECODE_POST;
401  if (n == 2) {
402  sqr(home, x0, x1, ipl);
403  return;
404  }
405  Arithmetic::PowOps ops(n);
406  if (vbd(ipl) == IPL_DOM) {
408  ::post(home,x0,x1,ops));
409  } else {
411  ::post(home,x0,x1,ops));
412  }
413  }
414 
415  void
416  nroot(Home home, IntVar x0, int n, IntVar x1, IntPropLevel ipl) {
417  using namespace Int;
418  Limits::positive(n,"Int::nroot");
419  GECODE_POST;
420  if (n == 2) {
421  sqrt(home, x0, x1, ipl);
422  return;
423  }
424  Arithmetic::PowOps ops(n);
425  if (vbd(ipl) == IPL_DOM) {
427  ::post(home,x0,x1,ops));
428  } else {
430  ::post(home,x0,x1,ops));
431  }
432  }
433 
434 }
435 
436 // STATISTICS: int-post
Negated Boolean view.
Definition: view.hpp:1574
void pow(Home home, FloatVar x0, int n, FloatVar x1)
Post propagator for for $n\geq 0$.
Definition: arithmetic.cpp:109
Post propagator for SetVar x
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103
Class for describing linear term .
Definition: linear.hh:1336
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
An array of IdxView pairs.
Definition: idx-view.hh:67
Passing integer variables.
Definition: int.hh:656
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition: tiebreak.hpp:80
Minus integer view.
Definition: view.hpp:282
void sqr(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:95
Operations for square and square-root propagators.
Definition: arithmetic.hh:302
Bounds consistent absolute value propagator.
Definition: arithmetic.hh:59
NodeType t
Type of node.
Definition: bool-expr.cpp:230
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator .
Definition: mult.cpp:144
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:974
void argmin(Home home, const IntVarArgs &x, IntVar y, bool tiebreak, IntPropLevel)
Post propagator for .
Definition: arithmetic.cpp:163
Bounds consistent division propagator.
Definition: arithmetic.hh:804
void div(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:127
Gecode toplevel namespace
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition: ipl.hpp:37
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator .
Definition: mult.cpp:311
Operations for power and nroot propagators.
Definition: arithmetic.hh:327
Exception: Arguments contain same variable multiply
Definition: exception.hpp:80
Passing Boolean variables.
Definition: int.hh:712
Argument maximum propagator.
Definition: arithmetic.hh:260
void nroot(Home home, FloatVar x0, int n, FloatVar x1)
Post propagator for for $n\geq 0$.
Definition: arithmetic.cpp:118
Home class for posting propagators
Definition: core.hpp:856
Domain consistent n-ary maximum propagator.
Definition: arithmetic.hh:219
Bounds consistent ternary maximum propagator.
Definition: arithmetic.hh:131
void argmax(Home home, const IntVarArgs &x, IntVar y, bool tiebreak, IntPropLevel)
Post propagator for .
Definition: arithmetic.cpp:110
void sqrt(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:102
Domain consistent power propagator.
Definition: arithmetic.hh:454
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: offset.hpp:136
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: offset.hpp:145
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:138
void nonnegative(int n, const char *l)
Check whether n is in range and nonnegative, otherwise throw out of limits with information l.
Definition: limits.hpp:68
Domain consistent ternary maximum propagator.
Definition: arithmetic.hh:184
Bounds consistent power propagator.
Definition: arithmetic.hh:395
const int max
Largest allowed integer value.
Definition: int.hh:116
void mult(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:88
Integer variables.
Definition: int.hh:371
Offset integer view.
Definition: view.hpp:443
@ IPL_BND
Bounds propagation.
Definition: int.hh:978
void positive(int n, const char *l)
Check whether n is in range and strictly positive, otherwise throw out of limits with information l.
Definition: limits.hpp:57
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:41
void divmod(Home home, IntVar x0, IntVar x1, IntVar x2, IntVar x3, IntPropLevel)
Post propagator for .
Definition: arithmetic.cpp:327
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:4048
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntPropLevel ipl)
Post propagator for .
Definition: arithmetic.cpp:360
Domain consistent absolute value propagator.
Definition: arithmetic.hh:92
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:40
Domain consistent n-th root propagator.
Definition: arithmetic.hh:580
Integer view for integer variables.
Definition: view.hpp:129
Integer division/modulo propagator.
Definition: arithmetic.hh:834
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:77
void estimate(Term< View > *t, int n, int c, int &l, int &u)
Estimate lower and upper bounds.
Definition: post.hpp:41
const int min
Smallest allowed integer value.
Definition: int.hh:118
@ IRT_EQ
Equality ( )
Definition: int.hh:926
Bounds consistent n-ary maximum propagator.
Definition: arithmetic.hh:159
void post(Home home, Term< BoolView > *t, int n, IntRelType irt, IntView x, int c, IntPropLevel)
Post propagator for linear constraint over Booleans.
Definition: bool-post.cpp:589
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:121
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition: array.hpp:1937
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:139
Bounds consistent n-th root propagator.
Definition: arithmetic.hh:520
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
Exception: Too few arguments available in argument array
Definition: exception.hpp:66
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: int.hpp:130