this repo has no description
dekker.one
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
41namespace Gecode {
42
43 void
44 rel(Home home, SetVar s, IntRelType rt, IntVar x) {
45 GECODE_POST;
46 switch (rt) {
47 case IRT_EQ:
48 {
49 Gecode::Int::IntView xv(x);
50 Set::SingletonView xsingle(xv);
51 GECODE_ES_FAIL(
52 (Set::Rel::Eq<Set::SetView,Set::SingletonView>
53 ::post(home,s,xsingle)));
54
55 }
56 break;
57 case IRT_NQ:
58 {
59 Gecode::Set::SetView sv(s);
60 GECODE_ME_FAIL( sv.cardMin(home, 1));
61 Gecode::Int::IntView xv(x);
62 Set::SingletonView xsingle(xv);
63 GECODE_ES_FAIL(
64 (Set::Rel::NoSubset<Set::SingletonView,Set::SetView>
65 ::post(home,xsingle,sv)));
66
67 }
68 break;
69 case IRT_LQ:
70 {
71 IntVar tmp(home, Int::Limits::min, Int::Limits::max);
72 rel(home, tmp, IRT_LQ, x);
73 GECODE_ES_FAIL(Set::Int::MaxElement<Set::SetView>::post(home,s,tmp));
74 }
75 break;
76 case IRT_LE:
77 {
78 IntVar tmp(home, Int::Limits::min, Int::Limits::max);
79 rel(home, tmp, IRT_LE, x);
80 GECODE_ES_FAIL(Set::Int::MaxElement<Set::SetView>::post(home,s,tmp));
81 }
82 break;
83 case IRT_GQ:
84 {
85 IntVar tmp(home, Int::Limits::min, Int::Limits::max);
86 rel(home, tmp, IRT_GQ, x);
87 GECODE_ES_FAIL(Set::Int::MinElement<Set::SetView>::post(home,s,tmp));
88 }
89 break;
90 case IRT_GR:
91 {
92 IntVar tmp(home, Int::Limits::min, Int::Limits::max);
93 rel(home, tmp, IRT_GR, x);
94 GECODE_ES_FAIL(Set::Int::MinElement<Set::SetView>::post(home,s,tmp));
95 }
96 break;
97 default:
98 throw Int::UnknownRelation("Set::rel");
99 }
100
101 }
102
103}
104
105namespace Gecode { namespace Set { namespace Int {
106
107 /// Reify \a m to be the minimum of \a s
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
119 /// Reify \a m to be the maximum of \a s
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
133namespace 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:
145 GECODE_ES_FAIL((Set::Rel::ReEq<Set::SetView,Set::SingletonView,
146 Gecode::Int::BoolView,RM_EQV>
147 ::post(home,s,xs,r.var())));
148 break;
149 case RM_IMP:
150 GECODE_ES_FAIL((Set::Rel::ReEq<Set::SetView,Set::SingletonView,
151 Gecode::Int::BoolView,RM_IMP>
152 ::post(home,s,xs,r.var())));
153 break;
154 case RM_PMI:
155 GECODE_ES_FAIL((Set::Rel::ReEq<Set::SetView,Set::SingletonView,
156 Gecode::Int::BoolView,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 {
197 IntVar tmp(home, Int::Limits::min, Int::Limits::max);
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 {
204 IntVar tmp(home, Int::Limits::min, Int::Limits::max);
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 {
211 IntVar tmp(home, Int::Limits::min, Int::Limits::max);
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 {
218 IntVar tmp(home, Int::Limits::min, Int::Limits::max);
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;
231 GECODE_ES_FAIL(Set::Int::MinElement<Set::SetView>::post(home,s,x));
232 }
233
234 void
235 notMin(Home home, SetVar s, IntVar x) {
236 GECODE_POST;
237 GECODE_ES_FAIL(Set::Int::NotMinElement<Set::SetView>::post(home,s,x));
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:
245 GECODE_ES_FAIL((Set::Int::ReMinElement<Set::SetView,RM_EQV>
246 ::post(home,s,x,r.var())));
247 break;
248 case RM_IMP:
249 GECODE_ES_FAIL((Set::Int::ReMinElement<Set::SetView,RM_IMP>
250 ::post(home,s,x,r.var())));
251 break;
252 case RM_PMI:
253 GECODE_ES_FAIL((Set::Int::ReMinElement<Set::SetView,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;
263 GECODE_ES_FAIL(Set::Int::MaxElement<Set::SetView>::post(home,s,x));
264 }
265
266 void
267 notMax(Home home, SetVar s, IntVar x) {
268 GECODE_POST;
269 GECODE_ES_FAIL(Set::Int::NotMaxElement<Set::SetView>::post(home,s,x));
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:
277 GECODE_ES_FAIL((Set::Int::ReMaxElement<Set::SetView,RM_EQV>
278 ::post(home,s,x,r.var())));
279 break;
280 case RM_IMP:
281 GECODE_ES_FAIL((Set::Int::ReMaxElement<Set::SetView,RM_IMP>
282 ::post(home,s,x,r.var())));
283 break;
284 case RM_PMI:
285 GECODE_ES_FAIL((Set::Int::ReMaxElement<Set::SetView,RM_PMI>
286 ::post(home,s,x,r.var())));
287 break;
288 default: throw Gecode::Int::UnknownReifyMode("Set::max");
289 }
290 }
291
292 void weights(Home home, IntSharedArray elements, IntSharedArray weights,
293 SetVar x, IntVar y) {
294 GECODE_POST;
295 GECODE_ES_FAIL(Set::Int::Weights<Set::SetView>::post(home,elements,
296 weights,x,y));
297 }
298
299}
300
301// STATISTICS: set-post