this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Contributing authors:
7 * Mikael Lagerkvist <lagerkvist@gecode.org>
8 *
9 * Copyright:
10 * Christian Schulte, 2006
11 * Mikael Lagerkvist, 2006
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38namespace Gecode { namespace Int { namespace Channel {
39
40 /**
41 * \brief Combine view with information for domain propagation
42 *
43 */
44 template<class View, class Offset>
45 class DomInfo {
46 public:
47 /// The view
48 View view;
49 /// Last propagated size
50 unsigned int size;
51 /// Last propagated minimum
52 int min;
53 /// Last propagated maximum
54 int max;
55 /// Initialize
56 void init(View x, int n);
57 /// Update during cloning
58 void update(Space& home, DomInfo<View,Offset>& vcb);
59 /// Check whether propagation for assignment is to be done
60 bool doval(void) const;
61 /// Check whether propagation for domain is to be done
62 bool dodom(void) const;
63 /// Record that view got assigned
64 void assigned(void);
65 /// Record that one value got removed
66 void removed(int i);
67 /// Update the size and bounds information after pruning
68 void done(Offset& o);
69 };
70
71 template<class View, class Offset>
72 forceinline void
73 DomInfo<View,Offset>::init(View x, int n) {
74 view = x;
75 size = static_cast<unsigned int>(n);
76 min = 0;
77 max = n-1;
78 }
79
80 template<class View, class Offset>
81 forceinline void
82 DomInfo<View,Offset>::update(Space& home, DomInfo<View,Offset>& di) {
83 view.update(home,di.view);
84 size = di.size;
85 min = di.min;
86 max = di.max;
87 }
88
89 template<class View, class Offset>
90 forceinline bool
91 DomInfo<View,Offset>::doval(void) const {
92 return (size != 1) && view.assigned();
93 }
94
95 template<class View, class Offset>
96 forceinline bool
97 DomInfo<View,Offset>::dodom(void) const {
98 return size != view.size();
99 }
100
101 template<class View, class Offset>
102 forceinline void
103 DomInfo<View,Offset>::assigned(void) {
104 size = 1;
105 }
106
107 template<class View, class Offset>
108 forceinline void
109 DomInfo<View,Offset>::removed(int i) {
110 size--;
111 if (i == min)
112 min++;
113 else if (i == max)
114 max--;
115 }
116
117 template<class View, class Offset>
118 forceinline void
119 DomInfo<View,Offset>::done(Offset& o) {
120 size = view.size();
121 min = o(view).min();
122 max = o(view).max();
123 }
124
125 // Propagate domain information from x to y
126 template<class View, class Offset>
127 ExecStatus
128 prop_dom(Space& home, int n, DomInfo<View,Offset>* x, Offset& ox,
129 DomInfo<View,Offset>* y, Offset& oy, ProcessStack& ya) {
130 for (int i=0; i<n; i++)
131 // Only views with not yet propagated missing values
132 if (x[i].dodom()) {
133 // Iterate the values in the complement of x[i]
134 ViewRanges<typename Offset::ViewType>
135 xir(ox(x[i].view));
136 Iter::Ranges::ComplVal<ViewRanges<typename Offset::ViewType> >
137 xirc(x[i].min,x[i].max,xir);
138 Iter::Ranges::ToValues<Iter::Ranges::ComplVal<
139 ViewRanges<typename Offset::ViewType> > > jv(xirc);
140 while (jv()) {
141 // j is not in the domain of x[i], so prune i from y[j]
142 int j = jv.val();
143 ModEvent me = oy(y[j].view).nq(home,i);
144 if (me_failed(me))
145 return ES_FAILED;
146 if (me_modified(me)) {
147 if (me == ME_INT_VAL) {
148 // Record that y[j] has been assigned and must be propagated
149 ya.push(j);
150 } else {
151 // Obvious as x[i] is different from j
152 y[j].removed(i);
153 }
154 }
155 ++jv;
156 }
157 // Update which values have been propagated and what are the new bounds
158 x[i].done(ox);
159 }
160 return ES_OK;
161 }
162
163 /*
164 * The actual propagator
165 *
166 */
167 template<class View, class Offset, bool shared>
168 forceinline
169 Dom<View,Offset,shared>::Dom(Home home, int n, DomInfo<View,Offset>* xy,
170 Offset& ox, Offset& oy)
171 : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,n,xy,ox,oy) {}
172
173 template<class View, class Offset, bool shared>
174 forceinline
175 Dom<View,Offset,shared>::Dom(Space& home, Dom<View,Offset,shared>& p)
176 : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,p) {}
177
178 template<class View, class Offset, bool shared>
179 Actor*
180 Dom<View,Offset,shared>::copy(Space& home) {
181 return new (home) Dom<View,Offset,shared>(home,*this);
182 }
183
184 template<class View, class Offset, bool shared>
185 PropCost
186 Dom<View,Offset,shared>::cost(const Space&,
187 const ModEventDelta& med) const {
188 if (View::me(med) == ME_INT_VAL)
189 return PropCost::quadratic(PropCost::LO, 2*n);
190 else
191 return PropCost::quadratic(PropCost::HI, 2*n);
192 }
193
194 template<class View, class Offset, bool shared>
195 ExecStatus
196 Dom<View,Offset,shared>::propagate(Space& home, const ModEventDelta& med) {
197 // MSVC in non-permissive mode needs this, no idea why...
198 const int n = this->n;
199 Region r;
200 ProcessStack xa(r,n);
201 ProcessStack ya(r,n);
202
203 DomInfo<View,Offset>* x = xy;
204 DomInfo<View,Offset>* y = xy+n;
205
206 if (View::me(med) == ME_INT_VAL) {
207 // Scan x and y for assigned but not yet propagated views
208 for (int i=0; i<n; i++) {
209 if (x[i].doval()) xa.push(i);
210 if (y[i].doval()) ya.push(i);
211 }
212
213 if (shared) {
214 do {
215 // Propagate assigned views for x
216 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
217 (home,n,x,ox,y,oy,n_na,xa,ya)));
218 // Propagate assigned views for y
219 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
220 (home,n,y,oy,x,ox,n_na,ya,xa)));
221 assert(ya.empty());
222 } while (!xa.empty() || !ya.empty());
223 return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
224 } else {
225 do {
226 // Propagate assigned views for x
227 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
228 (home,n,x,ox,y,oy,n_na,xa,ya)));
229 // Propagate assigned views for y
230 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
231 (home,n,y,oy,x,ox,n_na,ya,xa)));
232 assert(ya.empty());
233 } while (!xa.empty());
234 return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
235 }
236 }
237
238 // Process changed views for y
239 // This propagates from y to x and possibly records xs that
240 // got assigned
241 GECODE_ES_CHECK(prop_dom(home,n,y,oy,x,ox,xa));
242
243 // Process assigned views for x
244 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
245 (home,n,x,ox,y,oy,n_na,xa,ya)));
246
247 // Perform domain consistent propagation for distinct on the x views
248 if (dc.available()) {
249 GECODE_ES_CHECK(dc.sync());
250 } else {
251 ViewArray<View> xv(r,n);
252 for (int i=0; i<n; i++)
253 xv[i] = x[i].view;
254 GECODE_ES_CHECK(dc.init(home,xv));
255 }
256 bool assigned;
257 GECODE_ES_CHECK(dc.propagate(home,assigned));
258 if (assigned) {
259 // This has assigned some more views in x which goes unnoticed
260 // (that is, not recorded in xa). This must be checked and propagated
261 // to the y views, however the distinctness on x is already
262 // propagated.
263 for (int i=0; i<n; i++)
264 if (x[i].doval()) {
265 int j = ox(x[i].view).val();
266 // Assign the y variable to i (or test if already assigned!)
267 ModEvent me = oy(y[j].view).eq(home,i);
268 if (me_failed(me))
269 return ES_FAILED;
270 if (me_modified(me)) {
271 // Record that y[j] has been assigned and must be propagated
272 assert(me == ME_INT_VAL);
273 // Otherwise the modification event would not be ME_INT_VAL
274 ya.push(j);
275 }
276 x[i].assigned(); n_na--;
277 }
278 }
279
280 // Process changed views for x
281 // This propagates from x to y and possibly records ys that
282 // got assigned
283 GECODE_ES_CHECK(prop_dom(home,n,x,ox,y,oy,ya));
284
285 // Process assigned view again (some might have been found above)
286 while (!xa.empty() || !ya.empty()) {
287 // Process assigned views for x
288 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
289 (home,n,x,ox,y,oy,n_na,xa,ya)));
290 // Process assigned views for y
291 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
292 (home,n,y,oy,x,ox,n_na,ya,xa)));
293 };
294
295 if (shared) {
296 for (int i=0; i<2*n; i++)
297 if (!xy[i].view.assigned())
298 return ES_NOFIX;
299 return home.ES_SUBSUMED(*this);
300 } else {
301 return (n_na == 0) ? home.ES_SUBSUMED(*this) : ES_FIX;
302 }
303 }
304
305 template<class View, class Offset, bool shared>
306 ExecStatus
307 Dom<View,Offset,shared>::post(Home home, int n, DomInfo<View,Offset>* xy,
308 Offset& ox, Offset& oy) {
309 assert(n > 0);
310 if (n == 1) {
311 GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
312 GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
313 return ES_OK;
314 }
315 for (int i=0; i<n; i++) {
316 GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
317 GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
318 GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
319 GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
320 }
321 (void) new (home) Dom<View,Offset,shared>(home,n,xy,ox,oy);
322 return ES_OK;
323 }
324
325}}}
326
327// STATISTICS: int-prop
328