Generated on Thu Mar 7 2013 10:21:18 for Gecode by doxygen 1.8.3.1
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, 2006
8  *
9  * Last modified:
10  * $Date: 2010-07-16 06:33:36 +1000 (Fri, 16 Jul 2010) $ by $Author: tack $
11  * $Revision: 11206 $
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 {
41 
42  namespace MiniModel {
45  public:
56  ANLE_ELMNT
57  } t;
61  int n;
64  : t(t0), a(heap.alloc<LinExpr>(n0)), n(n0) {}
68  virtual IntVar post(Home home, IntVar* ret, IntConLevel icl) const {
69  IntVar y;
70  switch (t) {
71  case ANLE_ABS:
72  {
73  IntVar x = a[0].post(home, icl);
74  if (x.min() >= 0)
75  y = result(home,ret,x);
76  else {
77  y = result(home,ret);
78  abs(home, x, y, icl);
79  }
80  }
81  break;
82  case ANLE_MIN:
83  if (n==1) {
84  y = result(home,ret, a[0].post(home, icl));
85  } else if (n==2) {
86  IntVar x0 = a[0].post(home, icl);
87  IntVar x1 = a[1].post(home, icl);
88  if (x0.max() <= x1.min())
89  y = result(home,ret,x0);
90  else if (x1.max() <= x0.min())
91  y = result(home,ret,x1);
92  else {
93  y = result(home,ret);
94  min(home, x0, x1, y, icl);
95  }
96  } else {
97  IntVarArgs x(n);
98  for (int i=n; i--;)
99  x[i] = a[i].post(home, icl);
100  y = result(home,ret);
101  min(home, x, y, icl);
102  }
103  break;
104  case ANLE_MAX:
105  if (n==1) {
106  y = result(home,ret,a[0].post(home, icl));
107  } else if (n==2) {
108  IntVar x0 = a[0].post(home, icl);
109  IntVar x1 = a[1].post(home, icl);
110  if (x0.max() <= x1.min())
111  y = result(home,ret,x1);
112  else if (x1.max() <= x0.min())
113  y = result(home,ret,x0);
114  else {
115  y = result(home,ret);
116  max(home, x0, x1, y, icl);
117  }
118  } else {
119  IntVarArgs x(n);
120  for (int i=n; i--;)
121  x[i] = a[i].post(home, icl);
122  y = result(home,ret);
123  max(home, x, y, icl);
124  }
125  break;
126  case ANLE_MULT:
127  {
128  assert(n == 2);
129  IntVar x0 = a[0].post(home, icl);
130  IntVar x1 = a[1].post(home, icl);
131  if (x0.assigned() && (x0.val() == 0))
132  y = result(home,ret,x0);
133  else if (x0.assigned() && (x0.val() == 1))
134  y = result(home,ret,x1);
135  else if (x1.assigned() && (x1.val() == 0))
136  y = result(home,ret,x1);
137  else if (x1.assigned() && (x1.val() == 1))
138  y = result(home,ret,x0);
139  else {
140  y = result(home,ret);
141  mult(home, x0, x1, y, icl);
142  }
143  }
144  break;
145  case ANLE_DIV:
146  {
147  assert(n == 2);
148  IntVar x0 = a[0].post(home, icl);
149  IntVar x1 = a[1].post(home, icl);
150  rel(home, x1, IRT_NQ, 0);
151  if (x1.assigned() && (x1.val() == 1))
152  y = result(home,ret,x0);
153  else if (x0.assigned() && (x0.val() == 0))
154  y = result(home,ret,x0);
155  else {
156  y = result(home,ret);
157  div(home, x0, x1, y, icl);
158  }
159  }
160  break;
161  case ANLE_MOD:
162  {
163  assert(n == 2);
164  IntVar x0 = a[0].post(home, icl);
165  IntVar x1 = a[1].post(home, icl);
166  y = result(home,ret);
167  mod(home, x0, x1, y, icl);
168  }
169  break;
170  case ANLE_SQR:
171  {
172  assert(n == 1);
173  IntVar x = a[0].post(home, icl);
174  if (x.assigned() && ((x.val() == 0) || (x.val() == 1)))
175  y = x;
176  else {
177  y = result(home,ret);
178  sqr(home, x, y, icl);
179  }
180  }
181  break;
182  case ANLE_SQRT:
183  {
184  assert(n == 1);
185  IntVar x = a[0].post(home, icl);
186  if (x.assigned() && ((x.val() == 0) || (x.val() == 1)))
187  y = result(home,ret,x);
188  else {
189  y = result(home,ret);
190  sqrt(home, x, y, icl);
191  }
192  }
193  break;
194  case ANLE_ELMNT:
195  {
196  IntVar z = a[n-1].post(home, icl);
197  if (z.assigned() && z.val() >= 0 && z.val() < n-1) {
198  y = result(home,ret,a[z.val()].post(home, icl));
199  } else {
200  IntVarArgs x(n-1);
201  bool assigned = true;
202  for (int i=n-1; i--;) {
203  x[i] = a[i].post(home, icl);
204  if (!x[i].assigned())
205  assigned = false;
206  }
207  y = result(home,ret);
208  if (assigned) {
209  IntArgs xa(n-1);
210  for (int i=n-1; i--;)
211  xa[i] = x[i].val();
212  element(home, xa, z, y, icl);
213  } else {
214  element(home, x, z, y, icl);
215  }
216  }
217  }
218  break;
219  default:
220  GECODE_NEVER;
221  }
222  return y;
223  }
224  virtual void post(Home home, IntRelType irt, int c,
225  IntConLevel icl) const {
226  if ( (t == ANLE_MIN && (irt == IRT_GQ || irt == IRT_GR)) ||
227  (t == ANLE_MAX && (irt == IRT_LQ || irt == IRT_LE)) ) {
228  IntVarArgs x(n);
229  for (int i=n; i--;)
230  x[i] = a[i].post(home, icl);
231  rel(home, x, irt, c);
232  } else {
233  rel(home, post(home,NULL,icl), irt, c);
234  }
235  }
236  virtual void post(Home home, IntRelType irt, int c,
237  BoolVar b, IntConLevel icl) const {
238  rel(home, post(home,NULL,icl), irt, c, b);
239  }
240  };
243  return e.nle() &&
244  dynamic_cast<ArithNonLinExpr*>(e.nle()) != NULL &&
245  dynamic_cast<ArithNonLinExpr*>(e.nle())->t == t;
246  }
247  }
248 
249  using namespace MiniModel;
250 
251  LinExpr
252  abs(const LinExpr& e) {
254  return e;
255  ArithNonLinExpr* ae =
257  ae->a[0] = e;
258  return LinExpr(ae);
259  }
260 
261  LinExpr
262  min(const LinExpr& e0, const LinExpr& e1) {
263  int n = 0;
265  n += static_cast<ArithNonLinExpr*>(e0.nle())->n;
266  else
267  n += 1;
269  n += static_cast<ArithNonLinExpr*>(e1.nle())->n;
270  else
271  n += 1;
272  ArithNonLinExpr* ae =
274  int i=0;
276  ArithNonLinExpr* e0e = static_cast<ArithNonLinExpr*>(e0.nle());
277  for (; i<e0e->n; i++)
278  ae->a[i] = e0e->a[i];
279  } else {
280  ae->a[i++] = e0;
281  }
283  ArithNonLinExpr* e1e = static_cast<ArithNonLinExpr*>(e1.nle());
284  int curN = i;
285  for (; i<curN+e1e->n; i++)
286  ae->a[i] = e1e->a[i-curN];
287  } else {
288  ae->a[i++] = e1;
289  }
290  return LinExpr(ae);
291  }
292 
293  LinExpr
294  max(const LinExpr& e0, const LinExpr& e1) {
295  int n = 0;
297  n += static_cast<ArithNonLinExpr*>(e0.nle())->n;
298  else
299  n += 1;
301  n += static_cast<ArithNonLinExpr*>(e1.nle())->n;
302  else
303  n += 1;
304  ArithNonLinExpr* ae =
306  int i=0;
308  ArithNonLinExpr* e0e = static_cast<ArithNonLinExpr*>(e0.nle());
309  for (; i<e0e->n; i++)
310  ae->a[i] = e0e->a[i];
311  } else {
312  ae->a[i++] = e0;
313  }
315  ArithNonLinExpr* e1e = static_cast<ArithNonLinExpr*>(e1.nle());
316  int curN = i;
317  for (; i<curN+e1e->n; i++)
318  ae->a[i] = e1e->a[i-curN];
319  } else {
320  ae->a[i++] = e1;
321  }
322  return LinExpr(ae);
323  }
324 
325  LinExpr
326  min(const IntVarArgs& x) {
327  ArithNonLinExpr* ae =
329  for (int i=x.size(); i--;)
330  ae->a[i] = x[i];
331  return LinExpr(ae);
332  }
333 
334  LinExpr
335  max(const IntVarArgs& x) {
336  ArithNonLinExpr* ae =
338  for (int i=x.size(); i--;)
339  ae->a[i] = x[i];
340  return LinExpr(ae);
341  }
342 
343  LinExpr
344  operator *(const LinExpr& e0, const LinExpr& e1) {
345  ArithNonLinExpr* ae =
347  ae->a[0] = e0;
348  ae->a[1] = e1;
349  return LinExpr(ae);
350  }
351 
352  LinExpr
353  sqr(const LinExpr& e) {
354  ArithNonLinExpr* ae =
356  ae->a[0] = e;
357  return LinExpr(ae);
358  }
359 
360  LinExpr
361  sqrt(const LinExpr& e) {
362  ArithNonLinExpr* ae =
364  ae->a[0] = e;
365  return LinExpr(ae);
366  }
367 
368  LinExpr
369  operator /(const LinExpr& e0, const LinExpr& e1) {
370  ArithNonLinExpr* ae =
372  ae->a[0] = e0;
373  ae->a[1] = e1;
374  return LinExpr(ae);
375  }
376 
377  LinExpr
378  operator %(const LinExpr& e0, const LinExpr& e1) {
379  ArithNonLinExpr* ae =
381  ae->a[0] = e0;
382  ae->a[1] = e1;
383  return LinExpr(ae);
384  }
385 
386  LinExpr
387  element(const IntVarArgs& x, const LinExpr& e) {
388  ArithNonLinExpr* ae =
390  for (int i=x.size(); i--;)
391  ae->a[i] = x[i];
392  ae->a[x.size()] = e;
393  return LinExpr(ae);
394  }
395 
396  LinExpr
397  element(const IntArgs& x, const LinExpr& e) {
398  ArithNonLinExpr* ae =
400  for (int i=x.size(); i--;)
401  ae->a[i] = x[i];
402  ae->a[x.size()] = e;
403  return LinExpr(ae);
404  }
405 
406 }
407 
408 // STATISTICS: minimodel-any