Generated on Tue Mar 5 2013 22:37:28 for Gecode by doxygen 1.8.3.1
lin-expr.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, 2010
8  *
9  * Last modified:
10  * $Date: 2011-04-12 20:54:34 +1000 (Tue, 12 Apr 2011) $ by $Author: tack $
11  * $Revision: 11941 $
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  bool
43  LinExpr::Node::decrement(void) {
44  if (--use == 0) {
45  if ((l != NULL) && l->decrement())
46  delete l;
47  if ((r != NULL) && r->decrement())
48  delete r;
49  return true;
50  }
51  return false;
52  }
53 
54  /*
55  * Operations for expressions
56  *
57  */
59  n(new Node) {
60  n->n_int = n->n_bool = 0;
61  n->t = NT_VAR_INT;
62  n->l = n->r = NULL;
63  n->a = 0;
64  }
65 
67  n(new Node) {
68  n->n_int = n->n_bool = 0;
69  n->t = NT_CONST;
70  n->l = n->r = NULL;
71  n->a = 0;
72  Int::Limits::check(c,"MiniModel::LinExpr");
73  n->c = c;
74  }
75 
76  LinExpr::LinExpr(const IntVar& x, int a) :
77  n(new Node) {
78  n->n_int = 1;
79  n->n_bool = 0;
80  n->t = NT_VAR_INT;
81  n->l = n->r = NULL;
82  n->a = a;
83  n->x_int = x;
84  }
85 
86  LinExpr::LinExpr(const BoolVar& x, int a) :
87  n(new Node) {
88  n->n_int = 0;
89  n->n_bool = 1;
90  n->t = NT_VAR_BOOL;
91  n->l = n->r = NULL;
92  n->a = a;
93  n->x_bool = x;
94  }
95 
97  n(new Node) {
98  n->n_int = x.size();
99  n->n_bool = 0;
100  n->t = NT_SUM_INT;
101  n->l = n->r = NULL;
102  if (x.size() > 0) {
103  n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size());
104  for (int i=x.size(); i--; ) {
105  n->sum.ti[i].x = x[i];
106  n->sum.ti[i].a = 1;
107  }
108  }
109  }
110 
111  LinExpr::LinExpr(const IntArgs& a, const IntVarArgs& x) :
112  n(new Node) {
113  if (a.size() != x.size())
114  throw Int::ArgumentSizeMismatch("MiniModel::LinExpr");
115  n->n_int = x.size();
116  n->n_bool = 0;
117  n->t = NT_SUM_INT;
118  n->l = n->r = NULL;
119  if (x.size() > 0) {
120  n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size());
121  for (int i=x.size(); i--; ) {
122  n->sum.ti[i].x = x[i];
123  n->sum.ti[i].a = a[i];
124  }
125  }
126  }
127 
129  n(new Node) {
130  n->n_int = 0;
131  n->n_bool = x.size();
132  n->t = NT_SUM_BOOL;
133  n->l = n->r = NULL;
134  if (x.size() > 0) {
135  n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size());
136  for (int i=x.size(); i--; ) {
137  n->sum.tb[i].x = x[i];
138  n->sum.tb[i].a = 1;
139  }
140  }
141  }
142 
143  LinExpr::LinExpr(const IntArgs& a, const BoolVarArgs& x) :
144  n(new Node) {
145  if (a.size() != x.size())
146  throw Int::ArgumentSizeMismatch("MiniModel::LinExpr");
147  n->n_int = 0;
148  n->n_bool = x.size();
149  n->t = NT_SUM_BOOL;
150  n->l = n->r = NULL;
151  if (x.size() > 0) {
152  n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size());
153  for (int i=x.size(); i--; ) {
154  n->sum.tb[i].x = x[i];
155  n->sum.tb[i].a = a[i];
156  }
157  }
158  }
159 
160  LinExpr::LinExpr(const LinExpr& e0, NodeType t, const LinExpr& e1) :
161  n(new Node) {
162  n->n_int = e0.n->n_int + e1.n->n_int;
163  n->n_bool = e0.n->n_bool + e1.n->n_bool;
164  n->t = t;
165  n->l = e0.n; n->l->use++;
166  n->r = e1.n; n->r->use++;
167  }
168 
169  LinExpr::LinExpr(const LinExpr& e, NodeType t, int c) :
170  n(new Node) {
171  n->n_int = e.n->n_int;
172  n->n_bool = e.n->n_bool;
173  n->t = t;
174  n->l = NULL;
175  n->r = e.n; n->r->use++;
176  n->c = c;
177  }
178 
179  LinExpr::LinExpr(int a, const LinExpr& e) :
180  n(new Node) {
181  n->n_int = e.n->n_int;
182  n->n_bool = e.n->n_bool;
183  n->t = NT_MUL;
184  n->l = e.n; n->l->use++;
185  n->r = NULL;
186  n->a = a;
187  }
188 
190  n(new Node) {
191  n->n_int = 1;
192  n->n_bool = 0;
193  n->t = NT_NONLIN;
194  n->l = n->r = NULL;
195  n->a = 0;
196  n->sum.ne = e;
197  }
198 
199  const LinExpr&
201  if (this != &e) {
202  if (n->decrement())
203  delete n;
204  n = e.n; n->use++;
205  }
206  return *this;
207  }
208 
210  if (n->decrement())
211  delete n;
212  }
213 
214 
215  void
216  LinExpr::Node::fill(Home home, IntConLevel icl,
219  double m, double& d) const {
220  switch (this->t) {
221  case NT_CONST:
222  Int::Limits::check(m*c,"MiniModel::LinExpr");
223  d += m*c;
224  break;
225  case NT_VAR_INT:
226  Int::Limits::check(m*a,"MiniModel::LinExpr");
227  ti->a=static_cast<int>(m*a); ti->x=x_int; ti++;
228  break;
229  case NT_NONLIN:
230  ti->a=static_cast<int>(m); ti->x=sum.ne->post(home, NULL, icl); ti++;
231  break;
232  case NT_VAR_BOOL:
233  Int::Limits::check(m*a,"MiniModel::LinExpr");
234  tb->a=static_cast<int>(m*a); tb->x=x_bool; tb++;
235  break;
236  case NT_SUM_INT:
237  for (int i=n_int; i--; ) {
238  Int::Limits::check(m*sum.ti[i].a,"MiniModel::LinExpr");
239  ti[i].x = sum.ti[i].x; ti[i].a = static_cast<int>(m*sum.ti[i].a);
240  }
241  ti += n_int;
242  break;
243  case NT_SUM_BOOL:
244  for (int i=n_bool; i--; ) {
245  Int::Limits::check(m*sum.tb[i].a,"MiniModel::LinExpr");
246  tb[i].x = sum.tb[i].x; tb[i].a = static_cast<int>(m*sum.tb[i].a);
247  }
248  tb += n_bool;
249  break;
250  case NT_ADD:
251  if (l == NULL) {
252  Int::Limits::check(m*c,"MiniModel::LinExpr");
253  d += m*c;
254  } else {
255  l->fill(home,icl,ti,tb,m,d);
256  }
257  r->fill(home,icl,ti,tb,m,d);
258  break;
259  case NT_SUB:
260  if (l == NULL) {
261  Int::Limits::check(m*c,"MiniModel::LinExpr");
262  d += m*c;
263  } else {
264  l->fill(home,icl,ti,tb,m,d);
265  }
266  r->fill(home,icl,ti,tb,-m,d);
267  break;
268  case NT_MUL:
269  Int::Limits::check(m*a,"MiniModel::LinExpr");
270  l->fill(home,icl,ti,tb,m*a,d);
271  break;
272  default:
273  GECODE_NEVER;
274  }
275  }
276 
277 
278  /*
279  * Operators
280  *
281  */
282  LinExpr
283  operator +(int c, const IntVar& x) {
284  if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val()))
285  return LinExpr(static_cast<double>(c)+x.val());
286  else
287  return LinExpr(x,LinExpr::NT_ADD,c);
288  }
289  LinExpr
290  operator +(int c, const BoolVar& x) {
291  if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val()))
292  return LinExpr(static_cast<double>(c)+x.val());
293  else
294  return LinExpr(x,LinExpr::NT_ADD,c);
295  }
296  LinExpr
297  operator +(int c, const LinExpr& e) {
298  return LinExpr(e,LinExpr::NT_ADD,c);
299  }
300  LinExpr
301  operator +(const IntVar& x, int c) {
302  if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val()))
303  return LinExpr(static_cast<double>(c)+x.val());
304  else
305  return LinExpr(x,LinExpr::NT_ADD,c);
306  }
307  LinExpr
308  operator +(const BoolVar& x, int c) {
309  if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val()))
310  return LinExpr(static_cast<double>(c)+x.val());
311  else
312  return LinExpr(x,LinExpr::NT_ADD,c);
313  }
314  LinExpr
315  operator +(const LinExpr& e, int c) {
316  return LinExpr(e,LinExpr::NT_ADD,c);
317  }
318  LinExpr
319  operator +(const IntVar& x, const IntVar& y) {
320  if (x.assigned())
321  return x.val() + y;
322  else if (y.assigned())
323  return x + y.val();
324  else
325  return LinExpr(x,LinExpr::NT_ADD,y);
326  }
327  LinExpr
328  operator +(const IntVar& x, const BoolVar& y) {
329  if (x.assigned())
330  return x.val() + y;
331  else if (y.assigned())
332  return x + y.val();
333  else
334  return LinExpr(x,LinExpr::NT_ADD,y);
335  }
336  LinExpr
337  operator +(const BoolVar& x, const IntVar& y) {
338  if (x.assigned())
339  return x.val() + y;
340  else if (y.assigned())
341  return x + y.val();
342  else
343  return LinExpr(x,LinExpr::NT_ADD,y);
344  }
345  LinExpr
346  operator +(const BoolVar& x, const BoolVar& y) {
347  if (x.assigned())
348  return x.val() + y;
349  else if (y.assigned())
350  return x + y.val();
351  else
352  return LinExpr(x,LinExpr::NT_ADD,y);
353  }
354  LinExpr
355  operator +(const IntVar& x, const LinExpr& e) {
356  if (x.assigned())
357  return x.val() + e;
358  else
359  return LinExpr(x,LinExpr::NT_ADD,e);
360  }
361  LinExpr
362  operator +(const BoolVar& x, const LinExpr& e) {
363  if (x.assigned())
364  return x.val() + e;
365  else
366  return LinExpr(x,LinExpr::NT_ADD,e);
367  }
368  LinExpr
369  operator +(const LinExpr& e, const IntVar& x) {
370  if (x.assigned())
371  return e + x.val();
372  else
373  return LinExpr(e,LinExpr::NT_ADD,x);
374  }
375  LinExpr
376  operator +(const LinExpr& e, const BoolVar& x) {
377  if (x.assigned())
378  return e + x.val();
379  else
380  return LinExpr(e,LinExpr::NT_ADD,x);
381  }
382  LinExpr
383  operator +(const LinExpr& e1, const LinExpr& e2) {
384  return LinExpr(e1,LinExpr::NT_ADD,e2);
385  }
386 
387  LinExpr
388  operator -(int c, const IntVar& x) {
389  if (x.assigned() && Int::Limits::valid(static_cast<double>(c)-x.val()))
390  return LinExpr(static_cast<double>(c)-x.val());
391  else
392  return LinExpr(x,LinExpr::NT_SUB,c);
393  }
394  LinExpr
395  operator -(int c, const BoolVar& x) {
396  if (x.assigned() && Int::Limits::valid(static_cast<double>(c)-x.val()))
397  return LinExpr(static_cast<double>(c)-x.val());
398  else
399  return LinExpr(x,LinExpr::NT_SUB,c);
400  }
401  LinExpr
402  operator -(int c, const LinExpr& e) {
403  return LinExpr(e,LinExpr::NT_SUB,c);
404  }
405  LinExpr
406  operator -(const IntVar& x, int c) {
407  if (x.assigned() && Int::Limits::valid(x.val()-static_cast<double>(c)))
408  return LinExpr(x.val()-static_cast<double>(c));
409  else
410  return LinExpr(x,LinExpr::NT_ADD,-c);
411  }
412  LinExpr
413  operator -(const BoolVar& x, int c) {
414  if (x.assigned() && Int::Limits::valid(x.val()-static_cast<double>(c)))
415  return LinExpr(x.val()-static_cast<double>(c));
416  else
417  return LinExpr(x,LinExpr::NT_ADD,-c);
418  }
419  LinExpr
420  operator -(const LinExpr& e, int c) {
421  return LinExpr(e,LinExpr::NT_ADD,-c);
422  }
423  LinExpr
424  operator -(const IntVar& x, const IntVar& y) {
425  if (x.assigned())
426  return x.val() - y;
427  else if (y.assigned())
428  return x - y.val();
429  else
430  return LinExpr(x,LinExpr::NT_SUB,y);
431  }
432  LinExpr
433  operator -(const IntVar& x, const BoolVar& y) {
434  if (x.assigned())
435  return x.val() - y;
436  else if (y.assigned())
437  return x - y.val();
438  else
439  return LinExpr(x,LinExpr::NT_SUB,y);
440  }
441  LinExpr
442  operator -(const BoolVar& x, const IntVar& y) {
443  if (x.assigned())
444  return x.val() - y;
445  else if (y.assigned())
446  return x - y.val();
447  else
448  return LinExpr(x,LinExpr::NT_SUB,y);
449  }
450  LinExpr
451  operator -(const BoolVar& x, const BoolVar& y) {
452  if (x.assigned())
453  return x.val() - y;
454  else if (y.assigned())
455  return x - y.val();
456  else
457  return LinExpr(x,LinExpr::NT_SUB,y);
458  }
459  LinExpr
460  operator -(const IntVar& x, const LinExpr& e) {
461  if (x.assigned())
462  return x.val() - e;
463  else
464  return LinExpr(x,LinExpr::NT_SUB,e);
465  }
466  LinExpr
467  operator -(const BoolVar& x, const LinExpr& e) {
468  if (x.assigned())
469  return x.val() - e;
470  else
471  return LinExpr(x,LinExpr::NT_SUB,e);
472  }
473  LinExpr
474  operator -(const LinExpr& e, const IntVar& x) {
475  if (x.assigned())
476  return e - x.val();
477  else
478  return LinExpr(e,LinExpr::NT_SUB,x);
479  }
480  LinExpr
481  operator -(const LinExpr& e, const BoolVar& x) {
482  if (x.assigned())
483  return e - x.val();
484  else
485  return LinExpr(e,LinExpr::NT_SUB,x);
486  }
487  LinExpr
488  operator -(const LinExpr& e1, const LinExpr& e2) {
489  return LinExpr(e1,LinExpr::NT_SUB,e2);
490  }
491 
492  LinExpr
493  operator -(const IntVar& x) {
494  if (x.assigned())
495  return LinExpr(-x.val());
496  else
497  return LinExpr(x,LinExpr::NT_SUB,0);
498  }
499  LinExpr
500  operator -(const BoolVar& x) {
501  if (x.assigned())
502  return LinExpr(-x.val());
503  else
504  return LinExpr(x,LinExpr::NT_SUB,0);
505  }
506  LinExpr
507  operator -(const LinExpr& e) {
508  return LinExpr(e,LinExpr::NT_SUB,0);
509  }
510 
511  LinExpr
512  operator *(int a, const IntVar& x) {
513  if (a == 0)
514  return LinExpr(0.0);
515  else if (x.assigned() &&
516  Int::Limits::valid(static_cast<double>(a)*x.val()))
517  return LinExpr(static_cast<double>(a)*x.val());
518  else
519  return LinExpr(x,a);
520  }
521  LinExpr
522  operator *(int a, const BoolVar& x) {
523  if (a == 0)
524  return LinExpr(0.0);
525  else if (x.assigned() &&
526  Int::Limits::valid(static_cast<double>(a)*x.val()))
527  return LinExpr(static_cast<double>(a)*x.val());
528  else
529  return LinExpr(x,a);
530  }
531  LinExpr
532  operator *(const IntVar& x, int a) {
533  if (a == 0)
534  return LinExpr(0.0);
535  else if (x.assigned() &&
536  Int::Limits::valid(static_cast<double>(a)*x.val()))
537  return LinExpr(static_cast<double>(a)*x.val());
538  else
539  return LinExpr(x,a);
540  }
541  LinExpr
542  operator *(const BoolVar& x, int a) {
543  if (a == 0)
544  return LinExpr(0.0);
545  else if (x.assigned() &&
546  Int::Limits::valid(static_cast<double>(a)*x.val()))
547  return LinExpr(static_cast<double>(a)*x.val());
548  else
549  return LinExpr(x,a);
550  }
551  LinExpr
552  operator *(const LinExpr& e, int a) {
553  if (a == 0)
554  return LinExpr(0.0);
555  else
556  return LinExpr(a,e);
557  }
558  LinExpr
559  operator *(int a, const LinExpr& e) {
560  if (a == 0)
561  return LinExpr(0.0);
562  else
563  return LinExpr(a,e);
564  }
565 
566  LinExpr
567  sum(const IntVarArgs& x) {
568  return LinExpr(x);
569  }
570  LinExpr
571  sum(const IntArgs& a, const IntVarArgs& x) {
572  return LinExpr(a,x);
573  }
574  LinExpr
575  sum(const BoolVarArgs& x) {
576  return LinExpr(x);
577  }
578  LinExpr
579  sum(const IntArgs& a, const BoolVarArgs& x) {
580  return LinExpr(a,x);
581  }
582 
583 
584  IntVar
585  expr(Home home, const LinExpr& e, IntConLevel icl) {
586  if (!home.failed())
587  return e.post(home,icl);
589  return x;
590  }
591 
592 }
593 
594 // STATISTICS: minimodel-any