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