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,2006
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
36namespace Gecode { namespace Set { namespace Element {
37
38 template<class View, class View0, class View1>
39 forceinline
40 ElementUnion<View,View0,View1>::
41 ElementUnion(Home home, IdxViewArray& iv0, View0 y0, View1 y1)
42 : Propagator(home), iv(iv0), x0(y0), x1(y1) {
43 home.notice(*this,AP_DISPOSE);
44 x0.subscribe(home,*this, PC_SET_ANY);
45 x1.subscribe(home,*this, PC_SET_ANY);
46 iv.subscribe(home,*this, PC_SET_ANY);
47 }
48
49 template<class View, class View0, class View1>
50 forceinline
51 ElementUnion<View,View0,View1>::
52 ElementUnion(Space& home, ElementUnion<View,View0,View1>& p)
53 : Propagator(home,p) {
54 x0.update(home,p.x0);
55 x1.update(home,p.x1);
56 iv.update(home,p.iv);
57 }
58
59 template<class View, class View0, class View1>
60 PropCost
61 ElementUnion<View,View0,View1>::cost(const Space&,
62 const ModEventDelta&) const {
63 return PropCost::linear(PropCost::HI, iv.size()+2);
64 }
65
66 template<class View, class View0, class View1>
67 void
68 ElementUnion<View,View0,View1>::reschedule(Space& home) {
69 x0.reschedule(home,*this, PC_SET_ANY);
70 x1.reschedule(home,*this, PC_SET_ANY);
71 iv.reschedule(home,*this, PC_SET_ANY);
72 }
73
74 template<class View, class View0, class View1>
75 forceinline size_t
76 ElementUnion<View,View0,View1>::dispose(Space& home) {
77 home.ignore(*this,AP_DISPOSE);
78 if (!home.failed()) {
79 x0.cancel(home,*this,PC_SET_ANY);
80 x1.cancel(home,*this,PC_SET_ANY);
81 iv.cancel(home,*this,PC_SET_ANY);
82 }
83 (void) Propagator::dispose(home);
84 return sizeof(*this);
85 }
86
87 template<class View, class View0, class View1>
88 ExecStatus
89 ElementUnion<View,View0,View1>::
90 post(Home home, IdxViewArray& xs, View0 x0, View1 x1) {
91 int n = xs.size();
92
93 // x0 \subseteq {1,...,n}
94 Iter::Ranges::Singleton s(0, n-1);
95 GECODE_ME_CHECK(x0.intersectI(home,s));
96 (void) new (home)
97 ElementUnion<View,View0,View1>(home,xs,x0,x1);
98 return ES_OK;
99 }
100
101 template<class View, class View0, class View1>
102 Actor*
103 ElementUnion<View,View0,View1>::copy(Space& home) {
104 return new (home) ElementUnion<View,View0,View1>(home,*this);
105 }
106
107 template<class View, class View0, class View1>
108 ExecStatus
109 ElementUnion<View,View0,View1>::propagate(Space& home, const ModEventDelta&) {
110 Region r;
111 int n = iv.size();
112
113 bool loopVar;
114 do {
115 loopVar = false;
116
117 // Cache the upper bound iterator, as we have to
118 // modify the upper bound while iterating
119 LubRanges<View0> x0ub(x0);
120 Iter::Ranges::Cache x0ubc(r,x0ub);
121 Iter::Ranges::ToValues<Iter::Ranges::Cache> vx0ub(x0ubc);
122
123 GlbRanges<View0> x0lb(x0);
124 Iter::Ranges::Cache x0lbc(r,x0lb);
125 Iter::Ranges::ToValues<Iter::Ranges::Cache> vx0(x0lbc);
126
127 // In the first iteration, compute in before[i] the union
128 // of all the upper bounds of the x_i. At the same time,
129 // exclude inconsistent x_i from x0 and remove them from
130 // the list, cancel their dependencies.
131
132 GLBndSet sofarBefore(home);
133 LUBndSet selectedInter(home, IntSet (Limits::min,
134 Limits::max));
135 GLBndSet* before =
136 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n));
137
138 int j = 0;
139 int i = 0;
140
141 unsigned int maxCard = 0;
142 unsigned int minCard = Limits::card;
143
144 while ( vx0ub() ) {
145
146 // Remove vars at indices not in the upper bound
147 if (iv[i].idx < vx0ub.val()) {
148 iv[i].view.cancel(home,*this, PC_SET_ANY);
149 ++i;
150 continue;
151 }
152 assert(iv[i].idx == vx0ub.val());
153 iv[j] = iv[i];
154
155 View candidate = iv[j].view;
156 int candidateInd = iv[j].idx;
157
158 // inter = glb(candidate) & complement(lub(x1))
159 GlbRanges<View> candlb(candidate);
160 LubRanges<View1> x1ub(x1);
161 Iter::Ranges::Diff<GlbRanges<View>, LubRanges<View1> >
162 diff(candlb, x1ub);
163
164 bool selectSingleInconsistent = false;
165 if (x0.cardMax() <= 1) {
166 GlbRanges<View1> x1lb(x1);
167 LubRanges<View> candub(candidate);
168 Iter::Ranges::Diff<GlbRanges<View1>,
169 LubRanges<View> > diff2(x1lb, candub);
170 selectSingleInconsistent =
171 diff2() || candidate.cardMax() < x1.cardMin();
172 }
173
174 // exclude inconsistent x_i
175 // an x_i is inconsistent if
176 // * at most one x_i can be selected and there are
177 // elements in x_0 that can't be in x_i
178 // (selectSingleInconsistent)
179 // * its min cardinality is greater than maxCard of x1
180 // * inter is not empty (there are elements in x_i
181 // that can't be in x_0)
182 if (selectSingleInconsistent ||
183 candidate.cardMin() > x1.cardMax() ||
184 diff()) {
185 ModEvent me = (x0.exclude(home,candidateInd));
186 loopVar |= me_modified(me);
187 GECODE_ME_CHECK(me);
188
189 iv[j].view.cancel(home,*this, PC_SET_ANY);
190 ++i;
191 ++vx0ub;
192 continue;
193 } else {
194 // if x_i is consistent, check whether we know
195 // that its index is in x0
196 if (vx0() && vx0.val()==candidateInd) {
197 // x1 >= candidate, candidate <= x1
198 GlbRanges<View> candlb(candidate);
199 ModEvent me = x1.includeI(home,candlb);
200 loopVar |= me_modified(me);
201 GECODE_ME_CHECK(me);
202
203 LubRanges<View1> x1ub(x1);
204 me = candidate.intersectI(home,x1ub);
205 loopVar |= me_modified(me);
206 GECODE_ME_CHECK(me);
207 ++vx0;
208 }
209 new (&before[j]) GLBndSet(home);
210 before[j].update(home,sofarBefore);
211 LubRanges<View> cub(candidate);
212 sofarBefore.includeI(home,cub);
213 GlbRanges<View> clb(candidate);
214 selectedInter.intersectI(home,clb);
215 maxCard = std::max(maxCard, candidate.cardMax());
216 minCard = std::min(minCard, candidate.cardMin());
217 }
218
219 ++vx0ub;
220 ++i; ++j;
221 }
222
223 // cancel the variables with index greater than
224 // max of lub(x0)
225 for (int k=i; k<n; k++) {
226 iv[k].view.cancel(home,*this, PC_SET_ANY);
227 }
228 n = j;
229 iv.size(n);
230
231 if (x0.cardMax()==0) {
232 // Selector is empty, hence the result must be empty
233 {
234 GECODE_ME_CHECK(x1.cardMax(home,0));
235 }
236 for (int i=n; i--;)
237 before[i].dispose(home);
238 return home.ES_SUBSUMED(*this);
239 }
240
241 if (x0.cardMin() > 0) {
242 // Selector is not empty, hence the intersection of the
243 // possibly selected lower bounds is contained in x1
244 BndSetRanges si(selectedInter);
245 ModEvent me = x1.includeI(home, si);
246 loopVar |= me_modified(me);
247 GECODE_ME_CHECK(me);
248 me = x1.cardMin(home, minCard);
249 loopVar |= me_modified(me);
250 GECODE_ME_CHECK(me);
251 }
252 selectedInter.dispose(home);
253
254 if (x0.cardMax() <= 1) {
255 ModEvent me = x1.cardMax(home, maxCard);
256 loopVar |= me_modified(me);
257 GECODE_ME_CHECK(me);
258 }
259
260 {
261 // x1 <= sofarBefore
262 BndSetRanges sfB(sofarBefore);
263 ModEvent me = x1.intersectI(home,sfB);
264 loopVar |= me_modified(me);
265 GECODE_ME_CHECK(me);
266 }
267
268 sofarBefore.dispose(home);
269
270 GLBndSet sofarAfter(home);
271
272 // In the second iteration, this time backwards, compute
273 // sofarAfter as the union of all lub(x_j) with j>i
274 for (int i=n; i--;) {
275 // TODO: check for size of universe here?
276 // if (sofarAfter.size() == 0) break;
277
278 // extra = inter(before[i], sofarAfter) - lub(x1)
279 BndSetRanges b(before[i]);
280 BndSetRanges s(sofarAfter);
281 GlbRanges<View1> x1lb(x1);
282 Iter::Ranges::Union<BndSetRanges, BndSetRanges> inter(b,s);
283 Iter::Ranges::Diff<GlbRanges<View1>,
284 Iter::Ranges::Union<BndSetRanges,BndSetRanges> > diff(x1lb, inter);
285 if (diff()) {
286 ModEvent me = (x0.include(home,iv[i].idx));
287 loopVar |= me_modified(me);
288 GECODE_ME_CHECK(me);
289
290 // candidate != extra
291 me = iv[i].view.includeI(home,diff);
292 loopVar |= me_modified(me);
293 GECODE_ME_CHECK(me);
294 }
295
296 LubRanges<View> iviub(iv[i].view);
297 sofarAfter.includeI(home,iviub);
298 before[i].dispose(home);
299 }
300 sofarAfter.dispose(home);
301
302 } while (loopVar);
303
304 // Test whether we determined x0 without determining x1
305 if (x0.assigned() && !x1.assigned()) {
306 int ubsize = static_cast<int>(x0.lubSize());
307 if (ubsize > 2) {
308 assert(ubsize==n);
309 ViewArray<View> is(home,ubsize);
310 for (int i=n; i--;)
311 is[i]=iv[i].view;
312 GECODE_REWRITE(*this,(RelOp::UnionN<View, View1>
313 ::post(home(*this),is,x1)));
314 } else if (ubsize == 2) {
315 assert(n==2);
316 View a = iv[0].view;
317 View b = iv[1].view;
318 GECODE_REWRITE(*this,(RelOp::Union<View,View,View1>
319 ::post(home(*this),a,b,x1)));
320 } else if (ubsize == 1) {
321 assert(n==1);
322 GECODE_REWRITE(*this,
323 (Rel::Eq<View1,View>::post(home(*this),x1,iv[0].view)));
324 } else {
325 GECODE_ME_CHECK(x1.cardMax(home, 0));
326 return home.ES_SUBSUMED(*this);
327 }
328 }
329
330 for (int i=iv.size(); i--;)
331 if (!iv[i].view.assigned())
332 return ES_FIX;
333 if (!x1.assigned() || !x0.assigned())
334 return ES_FIX;
335 return home.ES_SUBSUMED(*this);
336 }
337
338}}}
339
340// STATISTICS: set-prop