Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
int-arith.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, 2006
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/minimodel.hh>
35 
36 namespace Gecode { namespace MiniModel {
37 
40  public:
54  ANLE_ITE
55  } t;
59  int n;
61  int aInt;
66  : t(t0), a(heap.alloc<LinIntExpr>(n0)), n(n0) {}
69  : t(t0), a(heap.alloc<LinIntExpr>(n0)), n(n0), aInt(a0) {}
72  : t(t0), a(heap.alloc<LinIntExpr>(n0)), n(n0), b(b0) {}
76  }
78  virtual IntVar post(Home home, IntVar* ret, IntPropLevel ipl) const {
79  IntVar y;
80  switch (t) {
81  case ANLE_ABS:
82  {
83  IntVar x = a[0].post(home, ipl);
84  if (x.min() >= 0)
85  y = result(home,ret,x);
86  else {
87  y = result(home,ret);
88  abs(home, x, y, ipl);
89  }
90  }
91  break;
92  case ANLE_MIN:
93  if (n==1) {
94  y = result(home,ret, a[0].post(home, ipl));
95  } else if (n==2) {
96  IntVar x0 = a[0].post(home, ipl);
97  IntVar x1 = a[1].post(home, ipl);
98  if (x0.max() <= x1.min())
99  y = result(home,ret,x0);
100  else if (x1.max() <= x0.min())
101  y = result(home,ret,x1);
102  else {
103  y = result(home,ret);
104  min(home, x0, x1, y, ipl);
105  }
106  } else {
107  IntVarArgs x(n);
108  for (int i=n; i--;)
109  x[i] = a[i].post(home, ipl);
110  y = result(home,ret);
111  min(home, x, y, ipl);
112  }
113  break;
114  case ANLE_MAX:
115  if (n==1) {
116  y = result(home,ret,a[0].post(home, ipl));
117  } else if (n==2) {
118  IntVar x0 = a[0].post(home, ipl);
119  IntVar x1 = a[1].post(home, ipl);
120  if (x0.max() <= x1.min())
121  y = result(home,ret,x1);
122  else if (x1.max() <= x0.min())
123  y = result(home,ret,x0);
124  else {
125  y = result(home,ret);
126  max(home, x0, x1, y, ipl);
127  }
128  } else {
129  IntVarArgs x(n);
130  for (int i=n; i--;)
131  x[i] = a[i].post(home, ipl);
132  y = result(home,ret);
133  max(home, x, y, ipl);
134  }
135  break;
136  case ANLE_MULT:
137  {
138  assert(n == 2);
139  IntVar x0 = a[0].post(home, ipl);
140  IntVar x1 = a[1].post(home, ipl);
141  if (x0.assigned() && (x0.val() == 0))
142  y = result(home,ret,x0);
143  else if (x0.assigned() && (x0.val() == 1))
144  y = result(home,ret,x1);
145  else if (x1.assigned() && (x1.val() == 0))
146  y = result(home,ret,x1);
147  else if (x1.assigned() && (x1.val() == 1))
148  y = result(home,ret,x0);
149  else {
150  y = result(home,ret);
151  mult(home, x0, x1, y, ipl);
152  }
153  }
154  break;
155  case ANLE_DIV:
156  {
157  assert(n == 2);
158  IntVar x0 = a[0].post(home, ipl);
159  IntVar x1 = a[1].post(home, ipl);
160  rel(home, x1, IRT_NQ, 0);
161  if (x1.assigned() && (x1.val() == 1))
162  y = result(home,ret,x0);
163  else if (x0.assigned() && (x0.val() == 0))
164  y = result(home,ret,x0);
165  else {
166  y = result(home,ret);
167  div(home, x0, x1, y, ipl);
168  }
169  }
170  break;
171  case ANLE_MOD:
172  {
173  assert(n == 2);
174  IntVar x0 = a[0].post(home, ipl);
175  IntVar x1 = a[1].post(home, ipl);
176  y = result(home,ret);
177  mod(home, x0, x1, y, ipl);
178  }
179  break;
180  case ANLE_SQR:
181  {
182  assert(n == 1);
183  IntVar x = a[0].post(home, ipl);
184  if (x.assigned() && ((x.val() == 0) || (x.val() == 1)))
185  y = result(home,ret,x);
186  else {
187  y = result(home,ret);
188  sqr(home, x, y, ipl);
189  }
190  }
191  break;
192  case ANLE_SQRT:
193  {
194  assert(n == 1);
195  IntVar x = a[0].post(home, ipl);
196  if (x.assigned() && ((x.val() == 0) || (x.val() == 1)))
197  y = result(home,ret,x);
198  else {
199  y = result(home,ret);
200  sqrt(home, x, y, ipl);
201  }
202  }
203  break;
204  case ANLE_POW:
205  {
206  assert(n == 1);
207  IntVar x = a[0].post(home, ipl);
208  if (x.assigned() && (aInt > 0) &&
209  ((x.val() == 0) || (x.val() == 1)))
210  y = result(home,ret,x);
211  else {
212  y = result(home,ret);
213  pow(home, x, aInt, y, ipl);
214  }
215  }
216  break;
217  case ANLE_NROOT:
218  {
219  assert(n == 1);
220  IntVar x = a[0].post(home, ipl);
221  if (x.assigned() && (aInt > 0) &&
222  ((x.val() == 0) || (x.val() == 1)))
223  y = result(home,ret,x);
224  else {
225  y = result(home,ret);
226  nroot(home, x, aInt, y, ipl);
227  }
228  }
229  break;
230  case ANLE_ELMNT:
231  {
232  IntVar z = a[n-1].post(home, ipl);
233  if (z.assigned() && z.val() >= 0 && z.val() < n-1) {
234  y = result(home,ret,a[z.val()].post(home, ipl));
235  } else {
236  IntVarArgs x(n-1);
237  bool assigned = true;
238  for (int i=n-1; i--;) {
239  x[i] = a[i].post(home, ipl);
240  if (!x[i].assigned())
241  assigned = false;
242  }
243  y = result(home,ret);
244  if (assigned) {
245  IntArgs xa(n-1);
246  for (int i=n-1; i--;)
247  xa[i] = x[i].val();
248  element(home, xa, z, y, ipl);
249  } else {
250  element(home, x, z, y, ipl);
251  }
252  }
253  }
254  break;
255  case ANLE_ITE:
256  {
257  assert(n == 2);
258  BoolVar c = b.expr(home, ipl);
259  IntVar x0 = a[0].post(home, ipl);
260  IntVar x1 = a[1].post(home, ipl);
261  y = result(home,ret);
262  ite(home, c, x0, x1, y, ipl);
263  }
264  break;
265  default:
266  GECODE_NEVER;
267  }
268  return y;
269  }
270  virtual void post(Home home, IntRelType irt, int c,
271  IntPropLevel ipl) const {
272  if ( (t == ANLE_MIN && (irt == IRT_GQ || irt == IRT_GR)) ||
273  (t == ANLE_MAX && (irt == IRT_LQ || irt == IRT_LE)) ) {
274  IntVarArgs x(n);
275  for (int i=n; i--;)
276  x[i] = a[i].post(home, ipl);
277  rel(home, x, irt, c);
278  } else {
279  rel(home, post(home,NULL,ipl), irt, c);
280  }
281  }
282  virtual void post(Home home, IntRelType irt, int c,
283  BoolVar b, IntPropLevel ipl) const {
284  rel(home, post(home,NULL,ipl), irt, c, b);
285  }
286  };
289  return e.nle() &&
290  dynamic_cast<ArithNonLinIntExpr*>(e.nle()) != NULL &&
291  dynamic_cast<ArithNonLinIntExpr*>(e.nle())->t == t;
292  }
293 
294 }}
295 
296 namespace Gecode {
297 
298  LinIntExpr
299  abs(const LinIntExpr& e) {
300  using namespace MiniModel;
302  return e;
303  ArithNonLinIntExpr* ae =
304  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ABS,1);
305  ae->a[0] = e;
306  return LinIntExpr(ae);
307  }
308 
309  LinIntExpr
310  min(const LinIntExpr& e0, const LinIntExpr& e1) {
311  using namespace MiniModel;
312  int n = 0;
314  n += static_cast<ArithNonLinIntExpr*>(e0.nle())->n;
315  else
316  n += 1;
318  n += static_cast<ArithNonLinIntExpr*>(e1.nle())->n;
319  else
320  n += 1;
321  ArithNonLinIntExpr* ae =
322  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MIN,n);
323  int i=0;
325  ArithNonLinIntExpr* e0e = static_cast<ArithNonLinIntExpr*>(e0.nle());
326  for (; i<e0e->n; i++)
327  ae->a[i] = e0e->a[i];
328  } else {
329  ae->a[i++] = e0;
330  }
332  ArithNonLinIntExpr* e1e = static_cast<ArithNonLinIntExpr*>(e1.nle());
333  int curN = i;
334  for (; i<curN+e1e->n; i++)
335  ae->a[i] = e1e->a[i-curN];
336  } else {
337  ae->a[i++] = e1;
338  }
339  return LinIntExpr(ae);
340  }
341 
342  LinIntExpr
343  max(const LinIntExpr& e0, const LinIntExpr& e1) {
344  using namespace MiniModel;
345  int n = 0;
347  n += static_cast<ArithNonLinIntExpr*>(e0.nle())->n;
348  else
349  n += 1;
351  n += static_cast<ArithNonLinIntExpr*>(e1.nle())->n;
352  else
353  n += 1;
354  ArithNonLinIntExpr* ae =
355  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MAX,n);
356  int i=0;
358  ArithNonLinIntExpr* e0e = static_cast<ArithNonLinIntExpr*>(e0.nle());
359  for (; i<e0e->n; i++)
360  ae->a[i] = e0e->a[i];
361  } else {
362  ae->a[i++] = e0;
363  }
365  ArithNonLinIntExpr* e1e = static_cast<ArithNonLinIntExpr*>(e1.nle());
366  int curN = i;
367  for (; i<curN+e1e->n; i++)
368  ae->a[i] = e1e->a[i-curN];
369  } else {
370  ae->a[i++] = e1;
371  }
372  return LinIntExpr(ae);
373  }
374 
375  LinIntExpr
376  min(const IntVarArgs& x) {
377  using namespace MiniModel;
378  ArithNonLinIntExpr* ae =
379  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MIN,x.size());
380  for (int i=x.size(); i--;)
381  ae->a[i] = x[i];
382  return LinIntExpr(ae);
383  }
384 
385  LinIntExpr
386  max(const IntVarArgs& x) {
387  using namespace MiniModel;
388  ArithNonLinIntExpr* ae =
389  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MAX,x.size());
390  for (int i=x.size(); i--;)
391  ae->a[i] = x[i];
392  return LinIntExpr(ae);
393  }
394 
395  LinIntExpr
396  operator *(const LinIntExpr& e0, const LinIntExpr& e1) {
397  using namespace MiniModel;
398  ArithNonLinIntExpr* ae =
399  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MULT,2);
400  ae->a[0] = e0;
401  ae->a[1] = e1;
402  return LinIntExpr(ae);
403  }
404 
405  LinIntExpr
406  sqr(const LinIntExpr& e) {
407  using namespace MiniModel;
408  ArithNonLinIntExpr* ae =
409  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_SQR,1);
410  ae->a[0] = e;
411  return LinIntExpr(ae);
412  }
413 
414  LinIntExpr
415  sqrt(const LinIntExpr& e) {
416  using namespace MiniModel;
417  ArithNonLinIntExpr* ae =
418  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_SQRT,1);
419  ae->a[0] = e;
420  return LinIntExpr(ae);
421  }
422 
423  LinIntExpr
424  pow(const LinIntExpr& e, int n) {
425  using namespace MiniModel;
426  ArithNonLinIntExpr* ae =
427  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_POW,1,n);
428  ae->a[0] = e;
429  return LinIntExpr(ae);
430  }
431 
432  LinIntExpr
433  nroot(const LinIntExpr& e, int n) {
434  using namespace MiniModel;
435  ArithNonLinIntExpr* ae =
436  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_NROOT,1,n);
437  ae->a[0] = e;
438  return LinIntExpr(ae);
439  }
440 
441  LinIntExpr
442  operator /(const LinIntExpr& e0, const LinIntExpr& e1) {
443  using namespace MiniModel;
444  ArithNonLinIntExpr* ae =
445  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_DIV,2);
446  ae->a[0] = e0;
447  ae->a[1] = e1;
448  return LinIntExpr(ae);
449  }
450 
451  LinIntExpr
452  operator %(const LinIntExpr& e0, const LinIntExpr& e1) {
453  using namespace MiniModel;
454  ArithNonLinIntExpr* ae =
455  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MOD,2);
456  ae->a[0] = e0;
457  ae->a[1] = e1;
458  return LinIntExpr(ae);
459  }
460 
461  LinIntExpr
462  element(const IntVarArgs& x, const LinIntExpr& e) {
463  using namespace MiniModel;
464  ArithNonLinIntExpr* ae =
465  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ELMNT,x.size()+1);
466  for (int i=x.size(); i--;)
467  ae->a[i] = x[i];
468  ae->a[x.size()] = e;
469  return LinIntExpr(ae);
470  }
471 
472  LinIntExpr
473  element(const IntArgs& x, const LinIntExpr& e) {
474  using namespace MiniModel;
475  ArithNonLinIntExpr* ae =
476  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ELMNT,x.size()+1);
477  for (int i=x.size(); i--;)
478  ae->a[i] = x[i];
479  ae->a[x.size()] = e;
480  return LinIntExpr(ae);
481  }
482 
483  LinIntExpr
484  ite(const BoolExpr& b, const LinIntExpr& e0, const LinIntExpr& e1) {
485  using namespace MiniModel;
486  ArithNonLinIntExpr* ae =
487  new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ITE,2,b);
488  ae->a[0] = e0;
489  ae->a[1] = e1;
490  return LinIntExpr(ae);
491  }
492 
493 }
494 
495 // STATISTICS: minimodel-any
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntPropLevel ipl)
Post propagator for .
Definition: arithmetic.cpp:263
ArithNonLinIntExprType
The expression type.
Definition: int-arith.cpp:42
int n
Size of variable array.
Definition: int-arith.cpp:59
NodeType t
Type of node.
Definition: bool-expr.cpp:230
void mult(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:88
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1569
virtual void post(Home home, IntRelType irt, int c, BoolVar b, IntPropLevel ipl) const
Post reified expression to be in relation irt with c.
Definition: int-arith.cpp:282
FloatVal operator/(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:213
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:41
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:111
Less or equal ( )
Definition: int.hh:928
void nroot(Home home, FloatVar x0, int n, FloatVar x1)
Post propagator for for $n 0$.
Definition: arithmetic.cpp:118
ArithNonLinIntExpr(ArithNonLinIntExprType t0, int n0, const BoolExpr &b0)
Constructor.
Definition: int-arith.cpp:71
void pow(Home home, FloatVar x0, int n, FloatVar x1)
Post propagator for for $n 0$.
Definition: arithmetic.cpp:109
Base class for non-linear expressions over integer variables.
Definition: minimodel.hh:109
virtual IntVar post(Home home, IntVar *ret, IntPropLevel ipl) const
Post expression.
Definition: int-arith.cpp:78
Greater ( )
Definition: int.hh:931
Greater or equal ( )
Definition: int.hh:930
int aInt
Integer argument (used in nroot for example)
Definition: int-arith.cpp:61
Non-linear arithmetic expressions over integer variables.
Definition: int-arith.cpp:39
virtual void post(Home home, IntRelType irt, int c, IntPropLevel ipl) const
Post expression to be in relation irt with c.
Definition: int-arith.cpp:270
bool hasType(const LinFloatExpr &e, ArithNonLinFloatExpr::ArithNonLinFloatExprType t)
Check if e is of type t.
Gecode::FloatVal c(-8, 8)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
BoolExpr b
Boolean expression argument (used in ite for example)
Definition: int-arith.cpp:63
Gecode::IntArgs i({1, 2, 3, 4})
IntRelType
Relation types for integers.
Definition: int.hh:925
LinIntExpr * a
Expressions.
Definition: int-arith.cpp:57
ArithNonLinIntExpr(ArithNonLinIntExprType t0, int n0)
Constructor.
Definition: int-arith.cpp:65
void sqr(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:95
int val(void) const
Return assigned value.
Definition: int.hpp:56
void sqrt(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:102
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
void post(Home home, IntRelType irt, IntPropLevel ipl) const
Post propagator.
Definition: int-expr.cpp:156
Less ( )
Definition: int.hh:929
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:767
Boolean expressions.
Definition: minimodel.hh:1225
Passing integer variables.
Definition: int.hh:656
Passing integer arguments.
Definition: int.hh:628
Boolean integer variables.
Definition: int.hh:512
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
int max(void) const
Return maximum of domain.
Definition: int.hpp:70
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:974
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
void div(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:127
FloatVal operator*(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:200
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:457
Linear expressions over integer variables.
Definition: minimodel.hh:140
int min(void) const
Return minimum of domain.
Definition: int.hpp:62
Integer variables.
Definition: int.hh:371
Heap heap
The single global heap.
Definition: heap.cpp:44
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
NonLinIntExpr * nle(void) const
Return non-linear expression inside, or NULL if not non-linear.
Definition: int-expr.cpp:345
Post propagator for SetVar x
Definition: set.hh:767
LinIntExpr operator%(const LinIntExpr &e0, const LinIntExpr &e1)
Return expression for .
Definition: int-arith.cpp:452
#define GECODE_MINIMODEL_EXPORT
Definition: minimodel.hh:78
ArithNonLinIntExpr(ArithNonLinIntExprType t0, int n0, int a0)
Constructor.
Definition: int-arith.cpp:68
Gecode toplevel namespace
Disequality ( )
Definition: int.hh:927
BoolVar expr(Home home, IntPropLevel ipl) const
Post propagators for expression.
Definition: bool-expr.cpp:574
Home class for posting propagators
Definition: core.hpp:853
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
void ite(Home home, BoolVar b, FloatVar x, FloatVar y, FloatVar z)
Post propagator for if-then-else constraint.
Definition: bool.cpp:39
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
Definition: element.cpp:39
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:138
T * a
Element array.
Definition: array.hpp:526