Generated on Thu Mar 16 2017 03:24:14 for Gecode by doxygen 1.8.13
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  * Last modified:
10  * $Date: 2016-05-23 22:18:23 +0200 (Mon, 23 May 2016) $ by $Author: schulte $
11  * $Revision: 15073 $
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 {
41 
42  void
43  abs(Home home, IntVar x0, IntVar x1, IntPropLevel ipl) {
44  using namespace Int;
46  switch (vbd(ipl)) {
47  case IPL_VAL:
49  ::post(home,x0,x1)));
50  break;
51  case IPL_BND:
52  case IPL_DEF:
54  ::post(home,x0,x1)));
55  break;
56  case IPL_DOM:
58  break;
59  default: GECODE_NEVER;
60  }
61  }
62 
63 
64  void
65  max(Home home, IntVar x0, IntVar x1, IntVar x2,
66  IntPropLevel ipl) {
67  using namespace Int;
69  if (vbd(ipl) == IPL_DOM) {
71  } else {
73  }
74  }
75 
76  void
77  max(Home home, const IntVarArgs& x, IntVar y,
78  IntPropLevel ipl) {
79  using namespace Int;
80  if (x.size() == 0)
81  throw TooFewArguments("Int::max");
83  ViewArray<IntView> xv(home,x);
84  if (vbd(ipl) == IPL_DOM) {
86  } else {
88  }
89  }
90 
91  void
92  min(Home home, IntVar x0, IntVar x1, IntVar x2,
93  IntPropLevel ipl) {
94  using namespace Int;
96  MinusView m0(x0); MinusView m1(x1); MinusView m2(x2);
97  if (vbd(ipl) == IPL_DOM) {
99  } else {
101  }
102  }
103 
104  void
105  min(Home home, const IntVarArgs& x, IntVar y,
106  IntPropLevel ipl) {
107  using namespace Int;
108  if (x.size() == 0)
109  throw TooFewArguments("Int::min");
110  GECODE_POST;
111  ViewArray<MinusView> m(home,x.size());
112  for (int i=x.size(); i--; )
113  m[i] = MinusView(x[i]);
114  MinusView my(y);
115  if (vbd(ipl) == IPL_DOM) {
117  } else {
119  }
120  }
121 
122 
123  void
124  argmax(Home home, const IntVarArgs& x, IntVar y, bool tiebreak,
125  IntPropLevel) {
126  using namespace Int;
127  if (x.size() == 0)
128  throw TooFewArguments("Int::argmax");
129  if (x.same(home,y))
130  throw ArgumentSame("Int::argmax");
131  GECODE_POST;
132  // Constrain y properly
133  IntView yv(y);
134  GECODE_ME_FAIL(yv.gq(home,0));
135  GECODE_ME_FAIL(yv.le(home,x.size()));
136  // Construct index view array
137  IdxViewArray<IntView> ix(home,x.size());
138  for (int i=x.size(); i--; ) {
139  ix[i].idx=i; ix[i].view=x[i];
140  }
141  if (tiebreak)
143  ::post(home,ix,yv)));
144  else
146  ::post(home,ix,yv)));
147  }
148 
149  void
150  argmax(Home home, const IntVarArgs& x, int o, IntVar y, bool tiebreak,
151  IntPropLevel) {
152  using namespace Int;
153  Limits::nonnegative(o,"Int::argmax");
154  if (x.size() == 0)
155  throw TooFewArguments("Int::argmax");
156  if (x.same(home,y))
157  throw ArgumentSame("Int::argmax");
158  GECODE_POST;
159  // Constrain y properly
160  OffsetView yv(y,-o);
161  GECODE_ME_FAIL(yv.gq(home,0));
162  GECODE_ME_FAIL(yv.le(home,x.size()));
163  // Construct index view array
164  IdxViewArray<IntView> ix(home,x.size());
165  for (int i=x.size(); i--; ) {
166  ix[i].idx=i; ix[i].view=x[i];
167  }
168  if (tiebreak)
170  ::post(home,ix,yv)));
171  else
173  ::post(home,ix,yv)));
174  }
175 
176  void
177  argmin(Home home, const IntVarArgs& x, IntVar y, bool tiebreak,
178  IntPropLevel) {
179  using namespace Int;
180  if (x.size() == 0)
181  throw TooFewArguments("Int::argmin");
182  if (x.same(home,y))
183  throw ArgumentSame("Int::argmin");
184  GECODE_POST;
185  // Constrain y properly
186  IntView yv(y);
187  GECODE_ME_FAIL(yv.gq(home,0));
188  GECODE_ME_FAIL(yv.le(home,x.size()));
189  // Construct index view array
190  IdxViewArray<MinusView> ix(home,x.size());
191  for (int i=x.size(); i--; ) {
192  ix[i].idx=i; ix[i].view=MinusView(x[i]);
193  }
194  if (tiebreak)
196  ::post(home,ix,yv)));
197  else
199  ::post(home,ix,yv)));
200  }
201 
202  void
203  argmin(Home home, const IntVarArgs& x, int o, IntVar y, bool tiebreak,
204  IntPropLevel) {
205  using namespace Int;
206  Limits::nonnegative(o,"Int::argmin");
207  if (x.size() == 0)
208  throw TooFewArguments("Int::argmin");
209  if (x.same(home,y))
210  throw ArgumentSame("Int::argmin");
211  GECODE_POST;
212  // Constrain y properly
213  OffsetView yv(y,-o);
214  GECODE_ME_FAIL(yv.gq(home,0));
215  GECODE_ME_FAIL(yv.le(home,x.size()));
216  // Construct index view array
217  IdxViewArray<MinusView> ix(home,x.size());
218  for (int i=x.size(); i--; ) {
219  ix[i].idx=i; ix[i].view=MinusView(x[i]);
220  }
221  if (tiebreak)
223  ::post(home,ix,yv)));
224  else
226  ::post(home,ix,yv)));
227  }
228 
229 
230  void
231  mult(Home home, IntVar x0, IntVar x1, IntVar x2,
232  IntPropLevel ipl) {
233  using namespace Int;
234  GECODE_POST;
235  if (vbd(ipl) == IPL_DOM) {
237  } else {
239  }
240  }
241 
242 
243  void
244  divmod(Home home, IntVar x0, IntVar x1, IntVar x2, IntVar x3,
245  IntPropLevel) {
246  using namespace Int;
247  GECODE_POST;
248 
250  GECODE_ES_FAIL(Arithmetic::MultBnd::post(home,x1,x2,prod));
252  t[0].a = 1; t[0].x = prod;
253  t[1].a = 1; t[1].x = x3;
254  int min, max;
255  Linear::estimate(t,2,0,min,max);
256  IntView x0v(x0);
257  GECODE_ME_FAIL(x0v.gq(home,min));
258  GECODE_ME_FAIL(x0v.lq(home,max));
259  t[2].a=-1; t[2].x=x0;
260  Linear::post(home,t,3,IRT_EQ,0);
261  if (home.failed()) return;
262  IntView x1v(x1);
264  Arithmetic::DivMod<IntView>::post(home,x0,x1,x3));
265  }
266 
267  void
268  div(Home home, IntVar x0, IntVar x1, IntVar x2,
269  IntPropLevel) {
270  using namespace Int;
271  GECODE_POST;
273  (Arithmetic::DivBnd<IntView>::post(home,x0,x1,x2)));
274  }
275 
276  void
277  mod(Home home, IntVar x0, IntVar x1, IntVar x2,
278  IntPropLevel ipl) {
279  using namespace Int;
280  GECODE_POST;
282  divmod(home, x0, x1, _div, x2, ipl);
283  }
284 
285  void
286  sqr(Home home, IntVar x0, IntVar x1, IntPropLevel ipl) {
287  using namespace Int;
288  GECODE_POST;
289  Arithmetic::SqrOps ops;
290  if (vbd(ipl) == IPL_DOM) {
292  ::post(home,x0,x1,ops));
293  } else {
295  ::post(home,x0,x1,ops));
296  }
297  }
298 
299  void
300  sqrt(Home home, IntVar x0, IntVar x1, IntPropLevel ipl) {
301  using namespace Int;
302  GECODE_POST;
303  Arithmetic::SqrOps ops;
304  if (vbd(ipl) == IPL_DOM) {
306  ::post(home,x0,x1,ops));
307  } else {
309  ::post(home,x0,x1,ops));
310  }
311  }
312 
313  void
314  pow(Home home, IntVar x0, int n, IntVar x1, IntPropLevel ipl) {
315  using namespace Int;
316  Limits::nonnegative(n,"Int::pow");
317  GECODE_POST;
318  if (n == 2) {
319  sqr(home, x0, x1, ipl);
320  return;
321  }
322  Arithmetic::PowOps ops(n);
323  if (vbd(ipl) == IPL_DOM) {
325  ::post(home,x0,x1,ops));
326  } else {
328  ::post(home,x0,x1,ops));
329  }
330  }
331 
332  void
333  nroot(Home home, IntVar x0, int n, IntVar x1, IntPropLevel ipl) {
334  using namespace Int;
335  Limits::positive(n,"Int::nroot");
336  GECODE_POST;
337  if (n == 2) {
338  sqrt(home, x0, x1, ipl);
339  return;
340  }
341  Arithmetic::PowOps ops(n);
342  if (vbd(ipl) == IPL_DOM) {
344  ::post(home,x0,x1,ops));
345  } else {
347  ::post(home,x0,x1,ops));
348  }
349  }
350 
351 }
352 
353 // STATISTICS: int-post
Bounds propagation.
Definition: int.hh:945
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntPropLevel ipl)
Post propagator for .
Definition: arithmetic.cpp:277
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition: ipl.hpp:41
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Integer division/modulo propagator.
Definition: arithmetic.hh:838
void mult(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:96
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
Domain consistent ternary maximum propagator.
Definition: arithmetic.hh:188
Domain consistent n-th root propagator.
Definition: arithmetic.hh:584
int a
Coefficient.
Definition: linear.hh:1343
Domain consistent n-ary maximum propagator.
Definition: arithmetic.hh:223
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:49
void nroot(Home home, FloatVar x0, int n, FloatVar x1)
Post propagator for for $n 0$.
Definition: arithmetic.cpp:126
void pow(Home home, FloatVar x0, int n, FloatVar x1)
Post propagator for for $n 0$.
Definition: arithmetic.cpp:117
Exception: Too few arguments available in argument array
Definition: exception.hpp:70
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:72
void argmin(Home home, const IntVarArgs &x, IntVar y, bool tiebreak, IntPropLevel)
Post propagator for .
Definition: arithmetic.cpp:177
Bounds consistent power propagator.
Definition: arithmetic.hh:399
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator .
Definition: mult.cpp:148
const int max
Largest allowed integer value.
Definition: int.hh:114
const int min
Smallest allowed integer value.
Definition: int.hh:116
Bounds consistent absolute value propagator.
Definition: arithmetic.hh:63
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: int.hpp:124
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: offset.hpp:130
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:905
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: offset.hpp:139
void divmod(Home home, IntVar x0, IntVar x1, IntVar x2, IntVar x3, IntPropLevel)
Post propagator for .
Definition: arithmetic.cpp:244
Domain consistent absolute value propagator.
Definition: arithmetic.hh:96
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:115
void sqr(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:103
Simple propagation levels.
Definition: int.hh:943
void sqrt(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:110
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3967
Value propagation.
Definition: int.hh:944
Operations for square and square-root propagators.
Definition: arithmetic.hh:306
void argmax(Home home, const IntVarArgs &x, IntVar y, bool tiebreak, IntPropLevel)
Post propagator for .
Definition: arithmetic.cpp:124
Bounds consistent n-ary maximum propagator.
Definition: arithmetic.hh:163
Offset integer view.
Definition: view.hpp:422
Argument maximum propagator.
Definition: arithmetic.hh:264
Passing integer variables.
Definition: int.hh:637
Bounds consistent division propagator.
Definition: arithmetic.hh:808
Domain consistent power propagator.
Definition: arithmetic.hh:458
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:941
Integer view for integer variables.
Definition: view.hpp:129
void div(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:135
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2)
Post propagator .
Definition: mult.cpp:315
Operations for power and nroot propagators.
Definition: arithmetic.hh:331
Bounds consistent ternary maximum propagator.
Definition: arithmetic.hh:135
Minus integer view.
Definition: view.hpp:276
Integer variables.
Definition: int.hh:351
Exception: Arguments contain same variable multiply
Definition: exception.hpp:84
void estimate(Term< View > *t, int n, int c, int &l, int &u)
Estimate lower and upper bounds.
Definition: post.hpp:45
Domain propagation Preferences: prefer speed or memory.
Definition: int.hh:946
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:133
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:81
An array of IdxView pairs.
Definition: idx-view.hh:71
Class for describing linear term .
Definition: linear.hh:1340
Gecode toplevel namespace
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:608
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:44
Home class for posting propagators
Definition: core.hpp:905
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:107
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
Bounds consistent n-th root propagator.
Definition: arithmetic.hh:524
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:61
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
bool same(const Space &home) const
Test whether array contains same variable multiply.
Definition: array.hpp:2081