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