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 SView, class RView>
39 forceinline
40 ElementDisjoint<SView,RView>::ElementDisjoint(Home home,
41 IdxViewArray& iv0,
42 RView y1)
43 : Propagator(home), iv(iv0), x1(y1) {
44
45 x1.subscribe(home,*this, PC_SET_ANY);
46 iv.subscribe(home,*this, PC_SET_ANY);
47 }
48
49 template<class SView, class RView>
50 forceinline
51 ElementDisjoint<SView,RView>::ElementDisjoint(Space& home,
52 ElementDisjoint& p)
53 : Propagator(home,p) {
54 x1.update(home,p.x1);
55 iv.update(home,p.iv);
56 }
57
58 template<class SView, class RView>
59 forceinline ExecStatus
60 ElementDisjoint<SView,RView>::post(Home home, IdxViewArray& xs,
61 RView x1) {
62 int n = xs.size();
63
64 // s2 \subseteq {0,...,n-1}
65 Iter::Ranges::Singleton s(0, n-1);
66 GECODE_ME_CHECK(x1.intersectI(home,s));
67 (void) new (home)
68 ElementDisjoint(home,xs,x1);
69 return ES_OK;
70 }
71
72 template<class SView, class RView>
73 PropCost
74 ElementDisjoint<SView,RView>::cost(const Space&, const ModEventDelta&) const {
75 return PropCost::quadratic(PropCost::LO, iv.size()+2);
76 }
77
78 template<class SView, class RView>
79 void
80 ElementDisjoint<SView,RView>::reschedule(Space& home) {
81 x1.reschedule(home,*this, PC_SET_ANY);
82 iv.reschedule(home,*this, PC_SET_ANY);
83 }
84
85 template<class SView, class RView>
86 forceinline size_t
87 ElementDisjoint<SView,RView>::dispose(Space& home) {
88 x1.cancel(home,*this, PC_SET_ANY);
89 iv.cancel(home,*this,PC_SET_ANY);
90 (void) Propagator::dispose(home);
91 return sizeof(*this);
92 }
93
94 template<class SView, class RView>
95 Actor*
96 ElementDisjoint<SView,RView>::copy(Space& home) {
97 return new (home) ElementDisjoint(home,*this);
98 }
99
100 template<class SView, class RView>
101 ExecStatus
102 ElementDisjoint<SView,RView>::propagate(Space& home, const ModEventDelta&) {
103 int n = iv.size();
104
105 Region r;
106
107 bool fix_flag = false;
108 do {
109 fix_flag = false;
110 // Compute union of all selected elements' lower bounds
111 GlbRanges<RView> x1lb(x1);
112 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb);
113 GLBndSet unionOfSelected(home);
114 for(int i=0; vx1lb(); ++vx1lb) {
115 while (iv[i].idx < vx1lb.val()) i++;
116 GlbRanges<SView> clb(iv[i].view);
117 unionOfSelected.includeI(home,clb);
118 }
119
120 {
121 LubRanges<RView> x1ub(x1);
122 Iter::Ranges::ToValues<LubRanges<RView> > vx1ub(x1ub);
123 int i=0;
124 int j=0;
125 // Cancel all elements that are no longer in the upper bound
126 while (vx1ub()) {
127 if (iv[i].idx < vx1ub.val()) {
128 iv[i].view.cancel(home,*this, PC_SET_ANY);
129 i++;
130 continue;
131 }
132 iv[j] = iv[i];
133 ++vx1ub;
134 ++i; ++j;
135 }
136
137 // cancel the variables with index greater than
138 // max of lub(x1)
139 for (int k=i; k<n; k++) {
140 iv[k].view.cancel(home,*this, PC_SET_ANY);
141 }
142 n = j;
143 iv.size(n);
144 }
145
146 {
147 UnknownRanges<RView> x1u(x1);
148 Iter::Ranges::Cache x1uc(r,x1u);
149 Iter::Ranges::ToValues<Iter::Ranges::Cache>
150 vx1u(x1uc);
151 int i=0;
152 int j=0;
153 while (vx1u()) {
154 while (iv[i].idx < vx1u.val()) {
155 iv[j] = iv[i];
156 i++; j++;
157 }
158 assert(iv[i].idx == vx1u.val());
159
160 SView candidate = iv[i].view;
161 int candidateInd = iv[i].idx;
162
163 GlbRanges<SView> clb(candidate);
164 BndSetRanges uos(unionOfSelected);
165 Iter::Ranges::Inter<GlbRanges<SView>, BndSetRanges>
166 inter(clb, uos);
167 if (inter()) {
168 ModEvent me = x1.exclude(home,candidateInd);
169 fix_flag |= me_modified(me);
170 GECODE_ME_CHECK(me);
171
172 candidate.cancel(home,*this, PC_SET_ANY);
173 ++i;
174 ++vx1u;
175 continue;
176 }
177 iv[j] = iv[i];
178 ++vx1u;
179 ++i; ++j;
180 }
181
182 unionOfSelected.dispose(home);
183
184 // copy remaining variables
185 for (int k=i; k<n; k++) {
186 iv[j] = iv[k];
187 j++;
188 }
189 n = j;
190 iv.size(n);
191 }
192
193 if (x1.cardMax()==0) {
194 // Selector is empty, we're done
195 return home.ES_SUBSUMED(*this);
196 }
197
198 {
199 // remove all elements in a selected variable from
200 // all other selected variables
201 GlbRanges<RView> x1lb(x1);
202 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb);
203 int i=0;
204 for (; vx1lb(); ++vx1lb) {
205 while (iv[i].idx < vx1lb.val()) i++;
206 assert(iv[i].idx==vx1lb.val());
207 GlbRanges<RView> x1lb2(x1);
208 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb2(x1lb2);
209 for (int j=0; vx1lb2(); ++vx1lb2) {
210 while (iv[j].idx < vx1lb2.val()) j++;
211 assert(iv[j].idx==vx1lb2.val());
212 if (iv[i].idx!=iv[j].idx) {
213 GlbRanges<SView> xilb(iv[i].view);
214 ModEvent me = iv[j].view.excludeI(home,xilb);
215 fix_flag |= me_modified(me);
216 GECODE_ME_CHECK(me);
217 }
218 }
219 }
220 }
221
222 // remove all elements from the selector that overlap
223 // with all other possibly selected elements, if
224 // at least two more elements need to be selected
225 if (x1.cardMin()-x1.glbSize() > 1) {
226 UnknownRanges<RView> x1u(x1);
227 Iter::Ranges::Cache x1uc(r,x1u);
228 Iter::Ranges::ToValues<Iter::Ranges::Cache>
229 vx1u(x1uc);
230
231 for (; vx1u() && x1.cardMin()-x1.glbSize() > 1; ++vx1u) {
232 int i = 0;
233 while (iv[i].idx < vx1u.val()) i++;
234 assert(iv[i].idx == vx1u.val());
235 bool flag=true;
236
237 UnknownRanges<RView> x1u2(x1);
238 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2);
239 for (; vx1u2(); ++vx1u2) {
240 int j = 0;
241 while (iv[j].idx < vx1u2.val()) j++;
242 assert(iv[j].idx == vx1u2.val());
243 if (iv[i].idx!=iv[j].idx) {
244 GlbRanges<SView> xjlb(iv[j].view);
245 GlbRanges<SView> xilb(iv[i].view);
246 Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> >
247 inter(xjlb, xilb);
248 if (!inter()) {
249 flag = false;
250 goto here;
251 }
252 }
253 }
254 here:
255 if (flag) {
256 ModEvent me = x1.exclude(home,iv[i].idx);
257 fix_flag |= me_modified(me);
258 GECODE_ME_CHECK(me);
259 }
260 }
261 }
262
263 // if exactly two more elements need to be selected
264 // and there is a possible element i such that all other pairs of
265 // elements overlap, select i
266 UnknownRanges<RView> x1u(x1);
267 Iter::Ranges::Cache x1uc(r,x1u);
268 Iter::Ranges::ToValues<Iter::Ranges::Cache>
269 vx1u(x1uc);
270
271 for (; x1.cardMin()-x1.glbSize() == 2 && vx1u(); ++vx1u) {
272 int i = 0;
273 while (iv[i].idx < vx1u.val()) i++;
274 assert (iv[i].idx == vx1u.val());
275 bool flag=true;
276
277 UnknownRanges<RView> x1u2(x1);
278 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2);
279 for (; vx1u2(); ++vx1u2) {
280 int j = 0;
281 while (iv[j].idx < vx1u2.val()) j++;
282 assert (iv[j].idx == vx1u2.val());
283 if (iv[i].idx!=iv[j].idx) {
284 UnknownRanges<RView> x1u3(x1);
285 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u3(x1u3);
286 for (; vx1u3(); ++vx1u3) {
287 int k = 0;
288 while (iv[k].idx < vx1u3.val()) k++;
289 assert (iv[k].idx == vx1u3.val());
290 if (iv[j].idx!=iv[k].idx && iv[i].idx!=iv[k].idx) {
291 GlbRanges<SView> xjlb(iv[j].view);
292 GlbRanges<SView> xilb(iv[k].view);
293 Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> >
294 inter(xjlb, xilb);
295 if (!inter()) {
296 flag = false;
297 goto here2;
298 }
299 }
300 }
301 }
302 }
303 here2:
304 if (flag) {
305 ModEvent me = x1.include(home,iv[i].idx);
306 fix_flag |= me_modified(me);
307 GECODE_ME_CHECK(me);
308 }
309 }
310 } while (fix_flag);
311
312 for (int i=iv.size(); i--;)
313 if (!iv[i].view.assigned())
314 return ES_FIX;
315 if (!x1.assigned())
316 return ES_FIX;
317 return home.ES_SUBSUMED(*this);
318 }
319
320
321}}}
322
323// STATISTICS: set-prop