Generated on Sat Oct 20 2018 12:43:45 for Gecode by doxygen 1.8.13
int.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, 2004
9  * Christian Schulte, 2004
10  *
11  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 #include <gecode/set.hh>
37 
38 #include <gecode/set/int.hh>
39 #include <gecode/set/rel.hh>
40 
41 namespace Gecode {
42 
43  void
44  rel(Home home, SetVar s, IntRelType rt, IntVar x) {
46  switch (rt) {
47  case IRT_EQ:
48  {
50  Set::SingletonView xsingle(xv);
53  ::post(home,s,xsingle)));
54 
55  }
56  break;
57  case IRT_NQ:
58  {
60  GECODE_ME_FAIL( sv.cardMin(home, 1));
62  Set::SingletonView xsingle(xv);
65  ::post(home,xsingle,sv)));
66 
67  }
68  break;
69  case IRT_LQ:
70  {
72  rel(home, tmp, IRT_LQ, x);
74  }
75  break;
76  case IRT_LE:
77  {
79  rel(home, tmp, IRT_LE, x);
81  }
82  break;
83  case IRT_GQ:
84  {
86  rel(home, tmp, IRT_GQ, x);
88  }
89  break;
90  case IRT_GR:
91  {
93  rel(home, tmp, IRT_GR, x);
95  }
96  break;
97  default:
98  throw Int::UnknownRelation("Set::rel");
99  }
100 
101  }
102 
103 }
104 
105 namespace Gecode { namespace Set { namespace Int {
106 
108  void remin(Home home, SetVar s, IntVar m, Reify r) {
109  IntVar c(home, 0, static_cast<int>(Set::Limits::card));
110  cardinality(home, s, c);
111  // Whether set is not empty
112  BoolVar ne(home, 0, 1);
113  rel(home, c, IRT_GR, 0, ne);
114  if (r.mode() != RM_PMI)
115  rel(home, r.var(), BOT_IMP, ne, 1);
116  min(home, s, m, ne);
117  }
118 
120  void remax(Home home, SetVar s, IntVar m, Reify r) {
121  IntVar c(home, 0, static_cast<int>(Set::Limits::card));
122  cardinality(home, s, c);
123  // Whether set is not empty
124  BoolVar ne(home, 0, 1);
125  rel(home, c, IRT_GR, 0, ne);
126  if (r.mode() != RM_PMI)
127  rel(home, r.var(), BOT_IMP, ne, 1);
128  max(home, s, m, ne);
129  }
130 
131 }}}
132 
133 namespace Gecode {
134 
135  void
136  rel(Home home, SetVar s, IntRelType rt, IntVar x, Reify r) {
137  GECODE_POST;
138  switch (rt) {
139  case IRT_EQ:
140  {
141  Gecode::Int::IntView xv(x);
142  Set::SingletonView xs(xv);
143  switch (r.mode()) {
144  case RM_EQV:
147  ::post(home,s,xs,r.var())));
148  break;
149  case RM_IMP:
152  ::post(home,s,xs,r.var())));
153  break;
154  case RM_PMI:
157  ::post(home,s,xs,r.var())));
158  break;
159  default:
160  throw Gecode::Int::UnknownReifyMode("Set::rel");
161  }
162  }
163  break;
164  case IRT_NQ:
165  {
166  IntVar c(home, 0, static_cast<int>(Set::Limits::card));
167  cardinality(home, s, c);
168  // Whether set is not empty
169  BoolVar ne(home, 0 , 1);
170  rel(home, c, IRT_GR, 0, ne);
171  // Whether {x} is a subset of s
172  BoolVar ss(home, 0 , 1);
173  rel(home, x, SRT_SUB, s, ss);
174  BoolVar b;
175  switch (r.mode()) {
176  case RM_EQV:
177  b=r.var();
178  break;
179  case RM_IMP:
180  b=BoolVar(home, 0, 1);
181  rel(home, r.var(), BOT_IMP, b, 1);
182  break;
183  case RM_PMI:
184  b=BoolVar(home, 0, 1);
185  rel(home, b, BOT_IMP, r.var(), 1);
186  break;
187  default:
188  throw Gecode::Int::UnknownReifyMode("Set::rel");
189  }
190  BoolVarArgs p(1); p[0]=ne;
191  BoolVarArgs n(1); n[0]=ss;
192  clause(home, BOT_AND, p, n, b);
193  }
194  break;
195  case IRT_LQ:
196  {
198  rel(home, tmp, IRT_LQ, x, r);
199  Gecode::Set::Int::remax(home, s, tmp, r);
200  }
201  break;
202  case IRT_LE:
203  {
205  rel(home, tmp, IRT_LE, x, r);
206  Gecode::Set::Int::remax(home, s, tmp, r);
207  }
208  break;
209  case IRT_GQ:
210  {
212  rel(home, tmp, IRT_GQ, x, r);
213  Gecode::Set::Int::remin(home, s, tmp, r);
214  }
215  break;
216  case IRT_GR:
217  {
219  rel(home, tmp, IRT_GR, x, r);
220  Gecode::Set::Int::remin(home, s, tmp, r);
221  }
222  break;
223  default:
224  throw Int::UnknownRelation("Set::rel");
225  }
226  }
227 
228  void
229  min(Home home, SetVar s, IntVar x) {
230  GECODE_POST;
232  }
233 
234  void
235  notMin(Home home, SetVar s, IntVar x) {
236  GECODE_POST;
238  }
239 
240  void
241  min(Home home, SetVar s, IntVar x, Reify r) {
242  GECODE_POST;
243  switch (r.mode()) {
244  case RM_EQV:
246  ::post(home,s,x,r.var())));
247  break;
248  case RM_IMP:
250  ::post(home,s,x,r.var())));
251  break;
252  case RM_PMI:
254  ::post(home,s,x,r.var())));
255  break;
256  default: throw Gecode::Int::UnknownReifyMode("Set::min");
257  }
258  }
259 
260  void
261  max(Home home, SetVar s, IntVar x) {
262  GECODE_POST;
264  }
265 
266  void
267  notMax(Home home, SetVar s, IntVar x) {
268  GECODE_POST;
270  }
271 
272  void
273  max(Home home, SetVar s, IntVar x, Reify r) {
274  GECODE_POST;
275  switch (r.mode()) {
276  case RM_EQV:
278  ::post(home,s,x,r.var())));
279  break;
280  case RM_IMP:
282  ::post(home,s,x,r.var())));
283  break;
284  case RM_PMI:
286  ::post(home,s,x,r.var())));
287  break;
288  default: throw Gecode::Int::UnknownReifyMode("Set::max");
289  }
290  }
291 
293  SetVar x, IntVar y) {
294  GECODE_POST;
296  weights,x,y));
297  }
298 
299 }
300 
301 // STATISTICS: set-post
void notMin(Home home, SetVar s, IntVar x)
Definition: int.cpp:235
Inverse implication for reification.
Definition: int.hh:869
ReifyMode mode(void) const
Return reification mode.
Definition: reify.hpp:56
Propagator for not maximum element
Definition: int.hh:170
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
Less or equal ( )
Definition: int.hh:928
Conjunction.
Definition: int.hh:951
void remin(Home home, SetVar s, IntVar m, Reify r)
Reify m to be the minimum of s.
Definition: int.cpp:108
Implication.
Definition: int.hh:953
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: set.hpp:82
void remax(Home home, SetVar s, IntVar m, Reify r)
Reify m to be the maximum of s.
Definition: int.cpp:120
Greater ( )
Definition: int.hh:931
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
const int max
Largest allowed integer value.
Definition: int.hh:116
Greater or equal ( )
Definition: int.hh:930
const int min
Smallest allowed integer value.
Definition: int.hh:118
Propagator for reified minimum element
Definition: int.hh:111
Gecode::FloatVal c(-8, 8)
Exception: Unknown relation passed as argument
Definition: exception.hpp:87
Reified equality propagator
Definition: rel.hh:174
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Equality ( )
Definition: int.hh:926
Propagator for not minimum element
Definition: int.hh:83
IntRelType
Relation types for integers.
Definition: int.hh:925
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Reification specification.
Definition: int.hh:876
Subset ( )
Definition: set.hh:646
Less ( )
Definition: int.hh:929
Passing Boolean variables.
Definition: int.hh:712
Singleton set view.
Definition: view.hpp:594
Boolean integer variables.
Definition: int.hh:512
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.
Definition: set-expr.cpp:815
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Set view for set variables
Definition: view.hpp:56
Propagator for maximum element
Definition: int.hh:143
Integer view for integer variables.
Definition: view.hpp:129
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Set variables
Definition: set.hh:127
Integer variables.
Definition: int.hh:371
Reified propagator for maximum element
Definition: int.hh:198
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
BoolVar var(void) const
Return Boolean control variable.
Definition: reify.hpp:48
Propagator for set equality
Definition: rel.hh:150
void notMax(Home home, SetVar s, IntVar x)
Definition: int.cpp:267
Post propagator for SetVar x
Definition: set.hh:767
Propagator for the negated subset constraint
Definition: rel.hh:90
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:77
Propagator for weight of a set
Definition: int.hh:257
Exception: Unknown reification mode passed as argument
Definition: exception.hpp:115
Gecode toplevel namespace
void weights(Home home, IntSharedArray elements, IntSharedArray weights, SetVar x, IntVar y)
Definition: int.cpp:292
Implication for reification.
Definition: int.hh:862
Disequality ( )
Definition: int.hh:927
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:40
Home class for posting propagators
Definition: core.hpp:853
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103
Shared array with arbitrary number of elements.
Propagator for minimum element
Definition: int.hh:55
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:138
void clause(Home home, BoolOpType o, const BoolVarArgs &x, const BoolVarArgs &y, int n, IntPropLevel)
Post domain consistent propagator for Boolean clause with positive variables x and negative variables...
Definition: bool.cpp:904
Equivalence for reification (default)
Definition: int.hh:855
Boolean view for Boolean variables.
Definition: view.hpp:1380