Generated on Tue Jun 16 2015 12:49:07 for Gecode by doxygen 1.8.9.1
set-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  * Guido Tack <tack@gecode.org>
5  * Christian Schulte <schulte@gecode.org>
6  *
7  * Copyright:
8  * Guido Tack, 2010
9  * Christian Schulte, 2004
10  *
11  * Last modified:
12  * $Date: 2015-03-20 15:37:34 +0100 (Fri, 20 Mar 2015) $ by $Author: schulte $
13  * $Revision: 14471 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <gecode/minimodel.hh>
41 
42 #ifdef GECODE_HAS_SET_VARS
43 
44 namespace Gecode {
45 
46  namespace {
48  static bool same(SetExpr::NodeType t0, SetExpr::NodeType t1) {
49  return (t0==t1) || (t1==SetExpr::NT_VAR) ||
50  (t1==SetExpr::NT_CONST) || (t1==SetExpr::NT_LEXP);
51  }
52  }
53 
55  class SetExpr::Node {
56  public:
58  unsigned int use;
60  int same;
64  Node *l, *r;
71 
73  Node(void);
76  bool decrement(void);
78  static void* operator new(size_t size);
80  static void operator delete(void* p, size_t size);
81  };
82 
83  /*
84  * Operations for nodes
85  *
86  */
87  SetExpr::Node::Node(void) : use(1) {}
88 
89  void*
90  SetExpr::Node::operator new(size_t size) {
91  return heap.ralloc(size);
92  }
93  void
94  SetExpr::Node::operator delete(void* p, size_t) {
95  heap.rfree(p);
96  }
97 
98  bool
100  if (--use == 0) {
101  if ((l != NULL) && l->decrement())
102  delete l;
103  if ((r != NULL) && r->decrement())
104  delete r;
105  return true;
106  }
107  return false;
108  }
109 
110  namespace {
112  class NNF {
113  public:
114  typedef SetExpr::NodeType NodeType;
115  typedef SetExpr::Node Node;
117  NodeType t;
119  int p;
121  int n;
123  union {
125  struct {
127  NNF* l;
129  NNF* r;
130  } b;
132  struct {
134  Node* x;
135  } a;
136  } u;
138  bool neg;
140  static NNF* nnf(Region& r, Node* n, bool neg);
142  void post(Home home, NodeType t, SetVarArgs& b, int& i) const;
144  void post(Home home, SetRelType srt, SetVar s) const;
146  void post(Home home, SetRelType srt, SetVar s, BoolVar b) const;
148  void post(Home home, SetRelType srt, const NNF* n) const;
150  void post(Home home, BoolVar b, bool t, SetRelType srt,
151  const NNF* n) const;
153  static void* operator new(size_t s, Region& r);
155  static void operator delete(void*);
157  static void operator delete(void*, Region&);
158  };
159 
160  /*
161  * Operations for negation normalform
162  *
163  */
164  forceinline void
165  NNF::operator delete(void*) {}
166 
167  forceinline void
168  NNF::operator delete(void*, Region&) {}
169 
170  forceinline void*
171  NNF::operator new(size_t s, Region& r) {
172  return r.ralloc(s);
173  }
174 
175  void
176  NNF::post(Home home, SetRelType srt, SetVar s) const {
177  switch (t) {
178  case SetExpr::NT_VAR:
179  if (neg) {
180  switch (srt) {
181  case SRT_EQ:
182  rel(home, u.a.x->x, SRT_CMPL, s);
183  break;
184  case SRT_CMPL:
185  rel(home, u.a.x->x, SRT_EQ, s);
186  break;
187  default:
188  SetVar bc(home,IntSet::empty,
190  rel(home, s, SRT_CMPL, bc);
191  rel(home, u.a.x->x, srt, bc);
192  break;
193  }
194  } else
195  rel(home, u.a.x->x, srt, s);
196  break;
197  case SetExpr::NT_CONST:
198  {
199  IntSet ss;
200  if (neg) {
201  IntSetRanges sr(u.a.x->s);
202  Set::RangesCompl<IntSetRanges> src(sr);
203  ss = IntSet(src);
204  } else {
205  ss = u.a.x->s;
206  }
207  switch (srt) {
208  case SRT_SUB: srt = SRT_SUP; break;
209  case SRT_SUP: srt = SRT_SUB; break;
210  default: break;
211  }
212  dom(home, s, srt, ss);
213  }
214  break;
215  case SetExpr::NT_LEXP:
216  {
217  IntVar iv = u.a.x->e.post(home,ICL_DEF);
218  if (neg) {
219  SetVar ic(home,IntSet::empty,
221  rel(home, iv, SRT_CMPL, ic);
222  rel(home,ic,srt,s);
223  } else {
224  rel(home,iv,srt,s);
225  }
226  }
227  break;
228  case SetExpr::NT_INTER:
229  {
230  SetVarArgs bs(p+n);
231  int i=0;
232  post(home, SetExpr::NT_INTER, bs, i);
233  if (i == 2) {
234  rel(home, bs[0], SOT_INTER, bs[1], srt, s);
235  } else {
236  if (srt == SRT_EQ)
237  rel(home, SOT_INTER, bs, s);
238  else {
239  SetVar bc(home,IntSet::empty,
241  rel(home, SOT_INTER, bs, bc);
242  rel(home, bc, srt, s);
243  }
244  }
245  }
246  break;
247  case SetExpr::NT_UNION:
248  {
249  SetVarArgs bs(p+n);
250  int i=0;
251  post(home, SetExpr::NT_UNION, bs, i);
252  if (i == 2) {
253  rel(home, bs[0], SOT_UNION, bs[1], srt, s);
254  } else {
255  if (srt == SRT_EQ)
256  rel(home, SOT_UNION, bs, s);
257  else {
258  SetVar bc(home,IntSet::empty,
260  rel(home, SOT_UNION, bs, bc);
261  rel(home, bc, srt, s);
262  }
263  }
264  }
265  break;
266  case SetExpr::NT_DUNION:
267  {
268  SetVarArgs bs(p+n);
269  int i=0;
270  post(home, SetExpr::NT_DUNION, bs, i);
271 
272  if (i == 2) {
273  if (neg) {
274  if (srt == SRT_CMPL) {
275  rel(home, bs[0], SOT_DUNION, bs[1], srt, s);
276  } else {
277  SetVar bc(home,IntSet::empty,
279  rel(home,s,SRT_CMPL,bc);
280  rel(home, bs[0], SOT_DUNION, bs[1], srt, bc);
281  }
282  } else {
283  rel(home, bs[0], SOT_DUNION, bs[1], srt, s);
284  }
285  } else {
286  if (neg) {
287  if (srt == SRT_CMPL) {
288  rel(home, SOT_DUNION, bs, s);
289  } else {
290  SetVar br(home,IntSet::empty,
292  rel(home, SOT_DUNION, bs, br);
293  if (srt == SRT_EQ)
294  rel(home, br, SRT_CMPL, s);
295  else {
296  SetVar bc(home,IntSet::empty,
298  rel(home, br, srt, bc);
299  rel(home, bc, SRT_CMPL, s);
300  }
301  }
302  } else {
303  if (srt == SRT_EQ)
304  rel(home, SOT_DUNION, bs, s);
305  else {
306  SetVar br(home,IntSet::empty,
308  rel(home, SOT_DUNION, bs, br);
309  rel(home, br, srt, s);
310  }
311  }
312  }
313  }
314  break;
315  default:
316  GECODE_NEVER;
317  }
318  }
319 
320  void
321  NNF::post(Home home, SetRelType srt, SetVar s, BoolVar b) const {
322  switch (t) {
323  case SetExpr::NT_VAR:
324  if (neg) {
325  switch (srt) {
326  case SRT_EQ:
327  rel(home, u.a.x->x, SRT_CMPL, s, b);
328  break;
329  case SRT_CMPL:
330  rel(home, u.a.x->x, SRT_EQ, s, b);
331  break;
332  default:
333  SetVar bc(home,IntSet::empty,
335  rel(home, s, SRT_CMPL, bc);
336  rel(home, u.a.x->x, srt, bc, b);
337  break;
338  }
339  } else
340  rel(home, u.a.x->x, srt, s, b);
341  break;
342  case SetExpr::NT_CONST:
343  {
344  IntSet ss;
345  if (neg) {
346  IntSetRanges sr(u.a.x->s);
347  Set::RangesCompl<IntSetRanges> src(sr);
348  ss = IntSet(src);
349  } else {
350  ss = u.a.x->s;
351  }
352  SetRelType invsrt;
353  switch (srt) {
354  case SRT_SUB: invsrt = SRT_SUP; break;
355  case SRT_SUP: invsrt = SRT_SUB; break;
356  case SRT_LQ: invsrt = SRT_GQ; break;
357  case SRT_LE: invsrt = SRT_GR; break;
358  case SRT_GQ: invsrt = SRT_LQ; break;
359  case SRT_GR: invsrt = SRT_LE; break;
360  case SRT_EQ:
361  case SRT_NQ:
362  case SRT_DISJ:
363  case SRT_CMPL:
364  invsrt = srt;
365  break;
366  default:
367  invsrt = srt;
368  GECODE_NEVER;
369  }
370  dom(home, s, invsrt, ss, b);
371  }
372  break;
373  case SetExpr::NT_LEXP:
374  {
375  IntVar iv = u.a.x->e.post(home,ICL_DEF);
376  if (neg) {
377  SetVar ic(home,IntSet::empty,
379  rel(home, iv, SRT_CMPL, ic);
380  rel(home,ic,srt,s,b);
381  } else {
382  rel(home,iv,srt,s,b);
383  }
384  }
385  case SetExpr::NT_INTER:
386  {
387  SetVarArgs bs(p+n);
388  int i=0;
389  post(home, SetExpr::NT_INTER, bs, i);
390  SetVar br(home,IntSet::empty,
392  rel(home, SOT_INTER, bs, br);
393  rel(home, br, srt, s, b);
394  }
395  break;
396  case SetExpr::NT_UNION:
397  {
398  SetVarArgs bs(p+n);
399  int i=0;
400  post(home, SetExpr::NT_UNION, bs, i);
401  SetVar br(home,IntSet::empty,
403  rel(home, SOT_UNION, bs, br);
404  rel(home, br, srt, s, b);
405  }
406  break;
407  case SetExpr::NT_DUNION:
408  {
409  SetVarArgs bs(p+n);
410  int i=0;
411  post(home, SetExpr::NT_DUNION, bs, i);
412 
413  if (neg) {
414  SetVar br(home,IntSet::empty,
416  rel(home, SOT_DUNION, bs, br);
417  if (srt == SRT_CMPL)
418  rel(home, br, SRT_EQ, s, b);
419  else if (srt == SRT_EQ)
420  rel(home, br, SRT_CMPL, s, b);
421  else {
422  SetVar bc(home,IntSet::empty,
424  rel(home, br, srt, bc);
425  rel(home, bc, SRT_CMPL, s, b);
426  }
427  } else {
428  SetVar br(home,IntSet::empty,
430  rel(home, SOT_DUNION, bs, br);
431  rel(home, br, srt, s, b);
432  }
433  }
434  break;
435  default:
436  GECODE_NEVER;
437  }
438  }
439 
440  void
441  NNF::post(Home home, NodeType t, SetVarArgs& b, int& i) const {
442  if (this->t != t) {
443  switch (this->t) {
444  case SetExpr::NT_VAR:
445  if (neg) {
446  SetVar xc(home,IntSet::empty,
448  rel(home, xc, SRT_CMPL, u.a.x->x);
449  b[i++]=xc;
450  } else {
451  b[i++]=u.a.x->x;
452  }
453  break;
454  default:
455  {
456  SetVar s(home,IntSet::empty,
458  post(home,SRT_EQ,s);
459  b[i++] = s;
460  }
461  break;
462  }
463  } else {
464  u.b.l->post(home, t, b, i);
465  u.b.r->post(home, t, b, i);
466  }
467  }
468 
469  void
470  NNF::post(Home home, SetRelType srt, const NNF* n) const {
471  if (n->t == SetExpr::NT_VAR && !n->neg) {
472  post(home,srt,n->u.a.x->x);
473  } else if (t == SetExpr::NT_VAR && !neg) {
474  SetRelType n_srt;
475  switch (srt) {
476  case SRT_SUB: n_srt = SRT_SUP; break;
477  case SRT_SUP: n_srt = SRT_SUB; break;
478  default: n_srt = srt;
479  }
480  n->post(home,n_srt,this);
481  } else {
482  SetVar nx(home,IntSet::empty,
484  n->post(home,SRT_EQ,nx);
485  post(home,srt,nx);
486  }
487  }
488 
489  void
490  NNF::post(Home home, BoolVar b, bool pt,
491  SetRelType srt, const NNF* n) const {
492  if (pt) {
493  if (n->t == SetExpr::NT_VAR && !n->neg) {
494  post(home,srt,n->u.a.x->x,b);
495  } else if (t == SetExpr::NT_VAR && !neg) {
496  SetRelType n_srt;
497  switch (srt) {
498  case SRT_SUB: n_srt = SRT_SUP; break;
499  case SRT_SUP: n_srt = SRT_SUB; break;
500  default: n_srt = srt;
501  }
502  n->post(home,b,true,n_srt,this);
503  } else {
504  SetVar nx(home,IntSet::empty,
506  n->post(home,SRT_EQ,nx);
507  post(home,srt,nx,b);
508  }
509  } else if (srt == SRT_EQ) {
510  post(home,b,true,SRT_NQ,n);
511  } else if (srt == SRT_NQ) {
512  post(home,b,true,SRT_EQ,n);
513  } else {
514  BoolVar nb(home,0,1);
515  rel(home,b,IRT_NQ,nb);
516  post(home,nb,true,srt,n);
517  }
518  }
519 
520  NNF*
521  NNF::nnf(Region& r, Node* n, bool neg) {
522  switch (n->t) {
523  case SetExpr::NT_VAR:
524  case SetExpr::NT_CONST:
525  case SetExpr::NT_LEXP:
526  {
527  NNF* x = new (r) NNF;
528  x->t = n->t; x->neg = neg; x->u.a.x = n;
529  if (neg) {
530  x->p = 0; x->n = 1;
531  } else {
532  x->p = 1; x->n = 0;
533  }
534  return x;
535  }
536  case SetExpr::NT_CMPL:
537  return nnf(r,n->l,!neg);
538  case SetExpr::NT_INTER:
539  case SetExpr::NT_UNION:
540  case SetExpr::NT_DUNION:
541  {
542  NodeType t; bool xneg;
543  if (n->t == SetExpr::NT_DUNION) {
544  t = n->t; xneg = neg; neg = false;
545  } else {
546  t = ((n->t == SetExpr::NT_INTER) == neg) ?
548  xneg = false;
549  }
550  NNF* x = new (r) NNF;
551  x->neg = xneg;
552  x->t = t;
553  x->u.b.l = nnf(r,n->l,neg);
554  x->u.b.r = nnf(r,n->r,neg);
555  int p_l, n_l;
556  if ((x->u.b.l->t == t) || (x->u.b.l->t == SetExpr::NT_VAR)) {
557  p_l=x->u.b.l->p; n_l=x->u.b.l->n;
558  } else {
559  p_l=1; n_l=0;
560  }
561  int p_r, n_r;
562  if ((x->u.b.r->t == t) || (x->u.b.r->t == SetExpr::NT_VAR)) {
563  p_r=x->u.b.r->p; n_r=x->u.b.r->n;
564  } else {
565  p_r=1; n_r=0;
566  }
567  x->p = p_l+p_r;
568  x->n = n_l+n_r;
569  return x;
570  }
571  default:
572  GECODE_NEVER;
573  }
574  GECODE_NEVER;
575  return NULL;
576  }
577  }
578 
579  SetExpr::SetExpr(const SetVar& x) : n(new Node) {
580  n->same = 1;
581  n->t = NT_VAR;
582  n->l = NULL;
583  n->r = NULL;
584  n->x = x;
585  }
586 
587  SetExpr::SetExpr(const IntSet& s) : n(new Node) {
588  n->same = 1;
589  n->t = NT_CONST;
590  n->l = NULL;
591  n->r = NULL;
592  n->s = s;
593  }
594 
595  SetExpr::SetExpr(const LinIntExpr& e) : n(new Node) {
596  n->same = 1;
597  n->t = NT_LEXP;
598  n->l = NULL;
599  n->r = NULL;
600  n->e = e;
601  }
602 
604  : n(new Node) {
605  int ls = same(t,l.n->t) ? l.n->same : 1;
606  int rs = same(t,r.n->t) ? r.n->same : 1;
607  n->same = ls+rs;
608  n->t = t;
609  n->l = l.n;
610  n->l->use++;
611  n->r = r.n;
612  n->r->use++;
613  }
614 
616  (void) t;
617  assert(t == NT_CMPL);
618  if (l.n->t == NT_CMPL) {
619  n = l.n->l;
620  n->use++;
621  } else {
622  n = new Node;
623  n->same = 1;
624  n->t = NT_CMPL;
625  n->l = l.n;
626  n->l->use++;
627  n->r = NULL;
628  }
629  }
630 
631  const SetExpr&
633  if (this != &e) {
634  if (n != NULL && n->decrement())
635  delete n;
636  n = e.n;
637  n->use++;
638  }
639  return *this;
640  }
641 
643  if (n != NULL && n->decrement())
644  delete n;
645  }
646 
647  SetExpr::SetExpr(const SetExpr& e) : n(e.n) {
648  n->use++;
649  }
650 
651  SetVar
652  SetExpr::post(Home home) const {
653  Region r(home);
654  SetVar s(home,IntSet::empty,
656  NNF::nnf(r,n,false)->post(home,SRT_EQ,s);
657  return s;
658  }
659 
660  void
661  SetExpr::post(Home home, SetRelType srt, const SetExpr& e) const {
662  Region r(home);
663  return NNF::nnf(r,n,false)->post(home,srt,NNF::nnf(r,e.n,false));
664  }
665  void
666  SetExpr::post(Home home, BoolVar b, bool t,
667  SetRelType srt, const SetExpr& e) const {
668  Region r(home);
669  return NNF::nnf(r,n,false)->post(home,b,t,srt,
670  NNF::nnf(r,e.n,false));
671  }
672 
673  SetExpr
674  operator &(const SetExpr& l, const SetExpr& r) {
675  return SetExpr(l,SetExpr::NT_INTER,r);
676  }
677  SetExpr
678  operator |(const SetExpr& l, const SetExpr& r) {
679  return SetExpr(l,SetExpr::NT_UNION,r);
680  }
681  SetExpr
682  operator +(const SetExpr& l, const SetExpr& r) {
683  return SetExpr(l,SetExpr::NT_DUNION,r);
684  }
685  SetExpr
686  operator -(const SetExpr& e) {
687  return SetExpr(e,SetExpr::NT_CMPL);
688  }
689  SetExpr
690  operator -(const SetExpr& l, const SetExpr& r) {
691  return SetExpr(l,SetExpr::NT_INTER,-r);
692  }
693  SetExpr
694  singleton(const LinIntExpr& e) {
695  return SetExpr(e);
696  }
697 
698  SetExpr
699  inter(const SetVarArgs& x) {
700  if (x.size() == 0)
702  SetExpr r(x[0]);
703  for (int i=1; i<x.size(); i++)
704  r = (r & x[i]);
705  return r;
706  }
707  SetExpr
708  setunion(const SetVarArgs& x) {
709  if (x.size() == 0)
710  return SetExpr(IntSet::empty);
711  SetExpr r(x[0]);
712  for (int i=1; i<x.size(); i++)
713  r = (r | x[i]);
714  return r;
715  }
716  SetExpr
717  setdunion(const SetVarArgs& x) {
718  if (x.size() == 0)
719  return SetExpr(IntSet::empty);
720  SetExpr r(x[0]);
721  for (int i=1; i<x.size(); i++)
722  r = (r + x[i]);
723  return r;
724  }
725 
726  namespace MiniModel {
729  public:
734  SNLE_MAX
735  } t;
740  : t(t0), e(e0) {}
742  virtual IntVar post(Home home, IntVar* ret, IntConLevel) const {
743  IntVar m = result(home,ret);
744  switch (t) {
745  case SNLE_CARD:
746  cardinality(home, e.post(home), m);
747  break;
748  case SNLE_MIN:
749  min(home, e.post(home), m);
750  break;
751  case SNLE_MAX:
752  max(home, e.post(home), m);
753  break;
754  default:
755  GECODE_NEVER;
756  break;
757  }
758  return m;
759  }
760  virtual void post(Home home, IntRelType irt, int c,
761  IntConLevel icl) const {
762  if (t==SNLE_CARD && irt!=IRT_NQ) {
763  switch (irt) {
764  case IRT_LQ:
765  cardinality(home, e.post(home),
766  0U,
767  static_cast<unsigned int>(c));
768  break;
769  case IRT_LE:
770  cardinality(home, e.post(home),
771  0U,
772  static_cast<unsigned int>(c-1));
773  break;
774  case IRT_GQ:
775  cardinality(home, e.post(home),
776  static_cast<unsigned int>(c),
778  break;
779  case IRT_GR:
780  cardinality(home, e.post(home),
781  static_cast<unsigned int>(c+1),
783  break;
784  case IRT_EQ:
785  cardinality(home, e.post(home),
786  static_cast<unsigned int>(c),
787  static_cast<unsigned int>(c));
788  break;
789  default:
790  GECODE_NEVER;
791  }
792  } else if (t==SNLE_MIN && (irt==IRT_GR || irt==IRT_GQ)) {
793  c = (irt==IRT_GQ ? c : c+1);
794  dom(home, e.post(home), SRT_SUB, c, Set::Limits::max);
795  } else if (t==SNLE_MAX && (irt==IRT_LE || irt==IRT_LQ)) {
796  c = (irt==IRT_LQ ? c : c-1);
797  dom(home, e.post(home), SRT_SUB, Set::Limits::min, c);
798  } else {
799  rel(home, post(home,NULL,icl), irt, c);
800  }
801  }
802  virtual void post(Home home, IntRelType irt, int c,
803  BoolVar b, IntConLevel icl) const {
804  if (t==SNLE_MIN && (irt==IRT_GR || irt==IRT_GQ)) {
805  c = (irt==IRT_GQ ? c : c+1);
806  dom(home, e.post(home), SRT_SUB, c, Set::Limits::max, b);
807  } else if (t==SNLE_MAX && (irt==IRT_LE || irt==IRT_LQ)) {
808  c = (irt==IRT_LQ ? c : c-1);
809  dom(home, e.post(home), SRT_SUB, Set::Limits::min, c, b);
810  } else {
811  rel(home, post(home,NULL,icl), irt, c, b);
812  }
813  }
814  };
815  }
816 
817  LinIntExpr
818  cardinality(const SetExpr& e) {
821  }
822  LinIntExpr
823  min(const SetExpr& e) {
826  }
827  LinIntExpr
828  max(const SetExpr& e) {
831  }
832 
833  /*
834  * Posting set expressions
835  *
836  */
837  SetVar
838  expr(Home home, const SetExpr& e) {
839  if (!home.failed())
840  return e.post(home);
842  return x;
843  }
844 
845 
846 }
847 
848 #endif
849 
850 // STATISTICS: minimodel-any
union Gecode::@536::NNF::@66 u
Union depending on nodetype t.
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3446
FloatVal operator-(const FloatVal &x)
Definition: val.hpp:172
int same
Number of variables in subtree with same type (for INTER and UNION)
Definition: set-expr.cpp:60
SetExpr singleton(const LinIntExpr &e)
Singleton expression.
Definition: set-expr.cpp:694
SetRelType
Common relation types for sets.
Definition: set.hh:644
IntConLevel
Consistency levels for integer propagators.
Definition: int.hh:937
const SetExpr & operator=(const SetExpr &e)
Assignment operator.
Definition: set-expr.cpp:632
SetExpr operator&(const SetExpr &l, const SetExpr &r)
Intersection of set expressions.
Definition: set-expr.cpp:674
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
const int min
Smallest allowed integer in integer set.
Definition: set.hh:101
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
LinIntExpr e
Possibly a linear expression.
Definition: set-expr.cpp:70
bool neg
Is formula negative.
Definition: set-expr.cpp:138
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
Less or equal ( )
Definition: int.hh:906
virtual IntVar post(Home home, IntVar *ret, IntConLevel) const
Post expression.
Definition: set-expr.cpp:742
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
Base class for non-linear expressions over integer variables.
Definition: minimodel.hh:107
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:341
SetVar x
Possibly a variable.
Definition: set-expr.cpp:66
NNF * l
Left subtree.
Definition: set-expr.cpp:127
struct Gecode::@536::NNF::@66::@67 b
For binary nodes (and, or, eqv)
Handle to region.
Definition: region.hpp:61
Greater ( )
Definition: int.hh:909
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: set-expr.cpp:802
Superset ( )
Definition: set.hh:648
Complement.
Definition: set.hh:650
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
const int max
Largest allowed integer in integer set.
Definition: set.hh:99
Linear expression.
Definition: minimodel.hh:1075
Greater or equal ( )
Definition: int.hh:908
Set expressions
Definition: minimodel.hh:1069
Node * l
Subexpressions.
Definition: set-expr.cpp:64
Heap heap
The single global heap.
Definition: heap.cpp:49
SetExpr setdunion(const SetVarArgs &x)
Disjoint union of set variables.
Definition: set-expr.cpp:717
Gecode::FloatVal c(-8, 8)
bool same(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether two views are the same.
Definition: view.hpp:603
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:904
IntSet s
Possibly a constant.
Definition: set-expr.cpp:68
IntRelType
Relation types for integers.
Definition: int.hh:903
FloatVal operator+(const FloatVal &x)
Definition: val.hpp:168
NodeType t
Type of expression.
Definition: set-expr.cpp:62
Less or equal ( )
Definition: set.hh:651
SetExpr(void)
Default constructor.
Definition: set-expr.hpp:48
unsigned int size(I &i)
Size of all ranges of range iterator i.
Node(void)
Default constructor.
Definition: set-expr.cpp:87
Subset ( )
Definition: set.hh:647
virtual void post(Home home, IntRelType irt, int c, IntConLevel icl) const
Post expression to be in relation irt with c.
Definition: set-expr.cpp:760
Intersection
Definition: set.hh:664
Less ( )
Definition: int.hh:907
NodeType
Type of set expression.
Definition: minimodel.hh:1072
Integer sets.
Definition: int.hh:171
Less ( )
Definition: set.hh:652
SetExpr setunion(const SetVarArgs &x)
Union of set variables.
Definition: set-expr.cpp:708
Integer valued set expressions.
Definition: set-expr.cpp:728
NodeType t
Type of node.
Definition: set-expr.cpp:117
static const IntSet empty
Empty set.
Definition: int.hh:262
Boolean integer variables.
Definition: int.hh:491
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.
Definition: set-expr.cpp:818
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:699
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Union.
Definition: set.hh:662
Passing set variables.
Definition: set.hh:490
Greater or equal ( )
Definition: set.hh:653
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
Set variables
Definition: set.hh:129
Node for set expression
Definition: set-expr.cpp:55
Linear expressions over integer variables.
Definition: minimodel.hh:138
Disjoint union.
Definition: set.hh:663
Integer variables.
Definition: int.hh:350
#define forceinline
Definition: config.hpp:132
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
The default consistency for a constraint.
Definition: int.hh:941
unsigned int use
Nodes are reference counted.
Definition: set-expr.cpp:58
Greater ( )
Definition: set.hh:654
Equality ( )
Definition: set.hh:645
Disjoint ( )
Definition: set.hh:649
struct Gecode::@536::NNF::@66::@68 a
For atomic nodes.
SetExpr e
The expression.
Definition: set-expr.cpp:737
#define GECODE_MINIMODEL_EXPORT
Definition: minimodel.hh:82
SetExpr operator|(const SetExpr &l, const SetExpr &r)
Union of set expressions.
Definition: set-expr.cpp:678
NNF * r
Right subtree.
Definition: set-expr.cpp:129
Disequality ( )
Definition: set.hh:646
SetNonLinIntExprType
The expression type.
Definition: set-expr.cpp:731
Gecode toplevel namespace
Disequality ( )
Definition: int.hh:905
Node * x
Pointer to corresponding Boolean expression node.
Definition: set-expr.cpp:134
Home class for posting propagators
Definition: core.hpp:717
~SetExpr(void)
Destructor.
Definition: set-expr.cpp:642
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
SetNonLinIntExpr(const SetExpr &e0, SetNonLinIntExprType t0)
Constructor.
Definition: set-expr.cpp:739
bool decrement(void)
Decrement reference count and possibly free memory.
Definition: set-expr.cpp:99
SetVar post(Home home) const
Post propagators for expression.
Definition: set-expr.cpp:652
int p
Number of positive literals for node type.
Definition: set-expr.cpp:119