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 * Copyright:
7 * Christian Schulte, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/int/rel.hh>
35
36namespace Gecode { namespace Int { namespace Arithmetic {
37
38 /*
39 * Ternary bounds consistent maximum
40 *
41 */
42
43 template<class View>
44 forceinline ExecStatus
45 prop_max_bnd(Space& home, View x0, View x1, View x2) {
46 bool mod = false;
47 do {
48 mod = false;
49 {
50 ModEvent me = x2.lq(home,std::max(x0.max(),x1.max()));
51 if (me_failed(me)) return ES_FAILED;
52 mod |= me_modified(me);
53 }
54 {
55 ModEvent me = x2.gq(home,std::max(x0.min(),x1.min()));
56 if (me_failed(me)) return ES_FAILED;
57 mod |= me_modified(me);
58 }
59 {
60 ModEvent me = x0.lq(home,x2.max());
61 if (me_failed(me)) return ES_FAILED;
62 mod |= me_modified(me);
63 }
64 {
65 ModEvent me = x1.lq(home,x2.max());
66 if (me_failed(me)) return ES_FAILED;
67 mod |= me_modified(me);
68 }
69 } while (mod);
70 return ES_OK;
71 }
72
73 template<class View>
74 forceinline
75 MaxBnd<View>::MaxBnd(Home home, View x0, View x1, View x2)
76 : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
77
78 template<class View>
79 ExecStatus
80 MaxBnd<View>::post(Home home, View x0, View x1, View x2) {
81 GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
82 GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
83 if (x0 == x1)
84 return Rel::EqBnd<View,View>::post(home,x0,x2);
85 if (x0 == x2)
86 return Rel::Lq<View,View>::post(home,x1,x2);
87 if (x1 == x2)
88 return Rel::Lq<View,View>::post(home,x0,x2);
89 (void) new (home) MaxBnd<View>(home,x0,x1,x2);
90 return ES_OK;
91 }
92
93 template<class View>
94 forceinline
95 MaxBnd<View>::MaxBnd(Space& home, MaxBnd<View>& p)
96 : TernaryPropagator<View,PC_INT_BND>(home,p) {}
97
98 template<class View>
99 forceinline
100 MaxBnd<View>::MaxBnd(Space& home, Propagator& p,
101 View x0, View x1, View x2)
102 : TernaryPropagator<View,PC_INT_BND>(home,p,x0,x1,x2) {}
103
104 template<class View>
105 Actor*
106 MaxBnd<View>::copy(Space& home) {
107 return new (home) MaxBnd<View>(home,*this);
108 }
109
110 template<class View>
111 ExecStatus
112 MaxBnd<View>::propagate(Space& home, const ModEventDelta&) {
113 GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2));
114 if ((x0.max() <= x1.min()) || (x0.max() < x2.min()))
115 GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x1,x2)));
116 if ((x1.max() <= x0.min()) || (x1.max() < x2.min()))
117 GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x0,x2)));
118 return x0.assigned() && x1.assigned() && x2.assigned() ?
119 home.ES_SUBSUMED(*this) : ES_FIX;
120 }
121
122 /*
123 * Nary bounds consistent maximum
124 *
125 */
126
127 template<class View>
128 forceinline
129 NaryMaxBnd<View>::NaryMaxBnd(Home home, ViewArray<View>& x, View y)
130 : NaryOnePropagator<View,PC_INT_BND>(home,x,y) {}
131
132 template<class View>
133 ExecStatus
134 NaryMaxBnd<View>::post(Home home, ViewArray<View>& x, View y) {
135 assert(x.size() > 0);
136 x.unique();
137 if (x.size() == 1)
138 return Rel::EqBnd<View,View>::post(home,x[0],y);
139 if (x.size() == 2)
140 return MaxBnd<View>::post(home,x[0],x[1],y);
141 int l = x[0].min();
142 int u = x[0].max();
143 for (int i=1; i<x.size(); i++) {
144 l = std::max(l,x[i].min());
145 u = std::max(u,x[i].max());
146 }
147 GECODE_ME_CHECK(y.gq(home,l));
148 GECODE_ME_CHECK(y.lq(home,u));
149 if (x.same(y)) {
150 // Check whether y occurs in x
151 for (int i=0; i<x.size(); i++)
152 GECODE_ES_CHECK((Rel::Lq<View,View>::post(home,x[i],y)));
153 } else {
154 (void) new (home) NaryMaxBnd<View>(home,x,y);
155 }
156 return ES_OK;
157 }
158
159 template<class View>
160 forceinline
161 NaryMaxBnd<View>::NaryMaxBnd(Space& home, NaryMaxBnd<View>& p)
162 : NaryOnePropagator<View,PC_INT_BND>(home,p) {}
163
164 template<class View>
165 Actor*
166 NaryMaxBnd<View>::copy(Space& home) {
167 if (x.size() == 1)
168 return new (home) Rel::EqBnd<View,View>(home,*this,x[0],y);
169 if (x.size() == 2)
170 return new (home) MaxBnd<View>(home,*this,x[0],x[1],y);
171 return new (home) NaryMaxBnd<View>(home,*this);
172 }
173
174 /// Status of propagation for nary max
175 enum MaxPropStatus {
176 MPS_ASSIGNED = 1<<0, ///< All views are assigned
177 MPS_REMOVED = 1<<1, ///< A view is removed
178 MPS_NEW_BOUND = 1<<2 ///< Telling has found a new upper bound
179 };
180
181 template<class View>
182 forceinline ExecStatus
183 prop_nary_max_bnd(Space& home, Propagator& p,
184 ViewArray<View>& x, View y, PropCond pc) {
185 rerun:
186 assert(x.size() > 0);
187 int maxmax = x[0].max();
188 int maxmin = x[0].min();
189 for (int i=1; i<x.size(); i++) {
190 maxmax = std::max(x[i].max(),maxmax);
191 maxmin = std::max(x[i].min(),maxmin);
192 }
193 GECODE_ME_CHECK(y.lq(home,maxmax));
194 GECODE_ME_CHECK(y.gq(home,maxmin));
195 maxmin = y.min();
196 maxmax = y.max();
197 int status = MPS_ASSIGNED;
198 for (int i=x.size(); i--; ) {
199 ModEvent me = x[i].lq(home,maxmax);
200 if (me == ME_INT_FAILED)
201 return ES_FAILED;
202 if (me_modified(me) && (x[i].max() != maxmax))
203 status |= MPS_NEW_BOUND;
204 if (x[i].max() < maxmin) {
205 x.move_lst(i,home,p,pc);
206 status |= MPS_REMOVED;
207 } else if (!x[i].assigned())
208 status &= ~MPS_ASSIGNED;
209 }
210 if (x.size() == 0)
211 return ES_FAILED;
212 if ((status & MPS_REMOVED) != 0)
213 goto rerun;
214 if (((status & MPS_ASSIGNED) != 0) && y.assigned())
215 return home.ES_SUBSUMED(p);
216 return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
217 }
218
219 template<class View>
220 ExecStatus
221 NaryMaxBnd<View>::propagate(Space& home, const ModEventDelta&) {
222 ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_BND);
223 GECODE_ES_CHECK(es);
224 if (x.size() == 1)
225 GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x[0],y)));
226 return es;
227 }
228
229
230 /*
231 * Ternary domain consistent maximum
232 *
233 */
234
235 template<class View>
236 forceinline
237 MaxDom<View>::MaxDom(Home home, View x0, View x1, View x2)
238 : TernaryPropagator<View,PC_INT_DOM>(home,x0,x1,x2) {}
239
240 template<class View>
241 ExecStatus
242 MaxDom<View>::post(Home home, View x0, View x1, View x2) {
243 GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
244 GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
245 if (x0 == x1)
246 return Rel::EqDom<View,View>::post(home,x0,x2);
247 if (x0 == x2)
248 return Rel::Lq<View,View>::post(home,x1,x2);
249 if (x1 == x2)
250 return Rel::Lq<View,View>::post(home,x0,x2);
251 (void) new (home) MaxDom<View>(home,x0,x1,x2);
252 return ES_OK;
253 }
254
255 template<class View>
256 forceinline
257 MaxDom<View>::MaxDom(Space& home, MaxDom<View>& p)
258 : TernaryPropagator<View,PC_INT_DOM>(home,p) {}
259
260 template<class View>
261 forceinline
262 MaxDom<View>::MaxDom(Space& home, Propagator& p,
263 View x0, View x1, View x2)
264 : TernaryPropagator<View,PC_INT_DOM>(home,p,x0,x1,x2) {}
265
266 template<class View>
267 Actor*
268 MaxDom<View>::copy(Space& home) {
269 return new (home) MaxDom<View>(home,*this);
270 }
271
272 template<class View>
273 PropCost
274 MaxDom<View>::cost(const Space&, const ModEventDelta& med) const {
275 return PropCost::ternary((View::me(med) == ME_INT_DOM) ?
276 PropCost::HI : PropCost::LO);
277 }
278
279 template<class View>
280 ExecStatus
281 MaxDom<View>::propagate(Space& home, const ModEventDelta& med) {
282 if (View::me(med) != ME_INT_DOM) {
283 GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2));
284 if ((x0.max() <= x1.min()) || (x0.max() < x2.min()))
285 GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2)));
286 if ((x1.max() <= x0.min()) || (x1.max() < x2.min()))
287 GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2)));
288 return x0.assigned() && x1.assigned() && x2.assigned() ?
289 home.ES_SUBSUMED(*this) :
290 home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
291 }
292 ViewRanges<View> r0(x0), r1(x1);
293 Iter::Ranges::Union<ViewRanges<View>,ViewRanges<View> > u(r0,r1);
294 GECODE_ME_CHECK(x2.inter_r(home,u,false));
295 if (rtest_nq_dom(x0,x2) == RT_TRUE) {
296 GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x0,x2)));
297 GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2)));
298 }
299 if (rtest_nq_dom(x1,x2) == RT_TRUE) {
300 GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x1,x2)));
301 GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2)));
302 }
303 return ES_FIX;
304 }
305
306 /*
307 * Nary domain consistent maximum
308 *
309 */
310
311 template<class View>
312 forceinline
313 NaryMaxDom<View>::NaryMaxDom(Home home, ViewArray<View>& x, View y)
314 : NaryOnePropagator<View,PC_INT_DOM>(home,x,y) {}
315
316 template<class View>
317 ExecStatus
318 NaryMaxDom<View>::post(Home home, ViewArray<View>& x, View y) {
319 assert(x.size() > 0);
320 x.unique();
321 if (x.size() == 1)
322 return Rel::EqDom<View,View>::post(home,x[0],y);
323 if (x.size() == 2)
324 return MaxDom<View>::post(home,x[0],x[1],y);
325 int l = x[0].min();
326 int u = x[0].max();
327 for (int i=0; i<x.size(); i++) {
328 l = std::max(l,x[i].min());
329 u = std::max(u,x[i].max());
330 }
331 GECODE_ME_CHECK(y.gq(home,l));
332 GECODE_ME_CHECK(y.lq(home,u));
333 if (x.same(y)) {
334 // Check whether y occurs in x
335 for (int i=0; i<x.size(); i++)
336 GECODE_ES_CHECK((Rel::Lq<View,View>::post(home,x[i],y)));
337 } else {
338 (void) new (home) NaryMaxDom<View>(home,x,y);
339 }
340 return ES_OK;
341 }
342
343 template<class View>
344 forceinline
345 NaryMaxDom<View>::NaryMaxDom(Space& home, NaryMaxDom<View>& p)
346 : NaryOnePropagator<View,PC_INT_DOM>(home,p) {}
347
348 template<class View>
349 Actor*
350 NaryMaxDom<View>::copy(Space& home) {
351 if (x.size() == 1)
352 return new (home) Rel::EqDom<View,View>(home,*this,x[0],y);
353 if (x.size() == 2)
354 return new (home) MaxDom<View>(home,*this,x[0],x[1],y);
355 return new (home) NaryMaxDom<View>(home,*this);
356 }
357
358 template<class View>
359 PropCost
360 NaryMaxDom<View>::cost(const Space&, const ModEventDelta& med) const {
361 if (View::me(med) == ME_INT_DOM)
362 return PropCost::linear(PropCost::HI, y.size());
363 else
364 return PropCost::linear(PropCost::LO, x.size());
365 }
366
367 template<class View>
368 ExecStatus
369 NaryMaxDom<View>::propagate(Space& home, const ModEventDelta& med) {
370 if (View::me(med) != ME_INT_DOM) {
371 ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_DOM);
372 GECODE_ES_CHECK(es);
373 return (es == ES_FIX) ?
374 home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM)) :
375 home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
376 }
377 Region r;
378 ViewRanges<View>* i_x = r.alloc<ViewRanges<View> >(x.size());
379 for (int i=0; i<x.size(); i++) {
380 ViewRanges<View> i_xi(x[i]); i_x[i]=i_xi;
381 }
382 Iter::Ranges::NaryUnion u(r, i_x, x.size());
383 GECODE_ME_CHECK(y.inter_r(home,u,false));
384 for (int i = x.size(); i--; )
385 if (rtest_nq_dom(x[i],y) == RT_TRUE) {
386 GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x[i],y)));
387 x.move_lst(i,home,*this,PC_INT_DOM);
388 }
389 assert(x.size() > 0);
390 if (x.size() == 1)
391 GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x[0],y)));
392 return ES_FIX;
393 }
394
395}}}
396
397// STATISTICS: int-prop
398