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 * Vincent Barichard <Vincent.Barichard@univ-angers.fr>
6 *
7 * Copyright:
8 * Christian Schulte, 2004
9 * Vincent Barichard, 2012
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 Float { namespace Rel {
37
38 /*
39 * Binary bounds consistent equality
40 *
41 */
42
43 template<class View0, class View1>
44 forceinline
45 Eq<View0,View1>::Eq(Home home, View0 x0, View1 x1)
46 : MixBinaryPropagator<View0,PC_FLOAT_BND,View1,PC_FLOAT_BND>(home,x0,x1) {}
47
48 template<class View0, class View1>
49 ExecStatus
50 Eq<View0,View1>::post(Home home, View0 x0, View1 x1){
51 if (x0.assigned()) {
52 GECODE_ME_CHECK(x1.eq(home,x0.val()));
53 } else if (x1.assigned()) {
54 GECODE_ME_CHECK(x0.eq(home,x1.val()));
55 } else if (x0 != x1) {
56 GECODE_ME_CHECK(x0.lq(home,x1.max()));
57 GECODE_ME_CHECK(x1.lq(home,x0.max()));
58 GECODE_ME_CHECK(x0.gq(home,x1.min()));
59 GECODE_ME_CHECK(x1.gq(home,x0.min()));
60 (void) new (home) Eq<View0,View1>(home,x0,x1);
61 }
62 return ES_OK;
63 }
64
65 template<class View0, class View1>
66 forceinline
67 Eq<View0,View1>::Eq(Space& home, Eq<View0,View1>& p)
68 : MixBinaryPropagator<View0,PC_FLOAT_BND,View1,PC_FLOAT_BND>(home,p) {}
69
70 template<class View0, class View1>
71 forceinline
72 Eq<View0,View1>::Eq(Space& home, Propagator& p,
73 View0 x0, View1 x1)
74 : MixBinaryPropagator<View0,PC_FLOAT_BND,View1,PC_FLOAT_BND>(home,p,
75 x0,x1) {}
76
77 template<class View0, class View1>
78 Actor*
79 Eq<View0,View1>::copy(Space& home) {
80 return new (home) Eq<View0,View1>(home,*this);
81 }
82
83 template<class View0, class View1>
84 ExecStatus
85 Eq<View0,View1>::propagate(Space& home, const ModEventDelta&) {
86 if (x0.assigned()) {
87 GECODE_ME_CHECK(x1.eq(home,x0.val()));
88 } else if (x1.assigned()) {
89 GECODE_ME_CHECK(x0.eq(home,x1.val()));
90 } else {
91 do {
92 GECODE_ME_CHECK(x0.gq(home,x1.min()));
93 GECODE_ME_CHECK(x1.gq(home,x0.min()));
94 } while (x0.min() != x1.min());
95 do {
96 GECODE_ME_CHECK(x0.lq(home,x1.max()));
97 GECODE_ME_CHECK(x1.lq(home,x0.max()));
98 } while (x0.max() != x1.max());
99 if (!x0.assigned())
100 return ES_FIX;
101 }
102 assert(x0.assigned() && x1.assigned());
103 return home.ES_SUBSUMED(*this);
104 }
105
106
107 /*
108 * Nary bound consistent equality
109 *
110 */
111
112 template<class View>
113 forceinline
114 NaryEq<View>::NaryEq(Home home, ViewArray<View>& x)
115 : NaryPropagator<View,PC_FLOAT_BND>(home,x) {}
116
117 template<class View>
118 ExecStatus
119 NaryEq<View>::post(Home home, ViewArray<View>& x) {
120 x.unique(home);
121 if (x.size() == 2) {
122 return Eq<View,View>::post(home,x[0],x[1]);
123 } else if (x.size() > 2) {
124 FloatNum l = x[0].min();
125 FloatNum u = x[0].max();
126 for (int i=x.size(); i-- > 1; ) {
127 l = std::max(l,x[i].min());
128 u = std::min(u,x[i].max());
129 }
130 for (int i=x.size(); i--; ) {
131 GECODE_ME_CHECK(x[i].gq(home,l));
132 GECODE_ME_CHECK(x[i].lq(home,u));
133 }
134 (void) new (home) NaryEq<View>(home,x);
135 }
136 return ES_OK;
137 }
138
139 template<class View>
140 forceinline
141 NaryEq<View>::NaryEq(Space& home, NaryEq<View>& p)
142 : NaryPropagator<View,PC_FLOAT_BND>(home,p) {}
143
144 template<class View>
145 Actor*
146 NaryEq<View>::copy(Space& home) {
147 return new (home) NaryEq<View>(home,*this);
148 }
149
150 template<class View>
151 PropCost
152 NaryEq<View>::cost(const Space&, const ModEventDelta& med) const {
153 if (View::me(med) == ME_FLOAT_VAL)
154 return PropCost::unary(PropCost::LO);
155 else
156 return PropCost::linear(PropCost::LO, x.size());
157 }
158
159 template<class View>
160 ExecStatus
161 NaryEq<View>::propagate(Space& home, const ModEventDelta& med) {
162 assert(x.size() > 2);
163 if (View::me(med) == ME_FLOAT_VAL) {
164 // One of the variables is assigned
165 for (int i = 0; ; i++)
166 if (x[i].assigned()) {
167 FloatVal n = x[i].val();
168 x.move_lst(i);
169 for (int j = x.size(); j--; )
170 GECODE_ME_CHECK(x[j].eq(home,n));
171 return home.ES_SUBSUMED(*this);
172 }
173 GECODE_NEVER;
174 }
175
176 FloatNum mn = x[0].min();
177 restart_min:
178 for (int i = x.size(); i--; ) {
179 GECODE_ME_CHECK(x[i].gq(home,mn));
180 if (mn < x[i].min()) {
181 mn = x[i].min();
182 goto restart_min;
183 }
184 }
185 FloatNum mx = x[0].max();
186 restart_max:
187 for (int i = x.size(); i--; ) {
188 GECODE_ME_CHECK(x[i].lq(home,mx));
189 if (mx > x[i].max()) {
190 mx = x[i].max();
191 goto restart_max;
192 }
193 }
194 return x[0].assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
195 }
196
197
198
199 /*
200 * Reified bounds consistent equality
201 *
202 */
203
204 template<class View, class CtrlView, ReifyMode rm>
205 forceinline
206 ReEq<View,CtrlView,rm>::ReEq(Home home, View x0, View x1, CtrlView b)
207 : Int::ReBinaryPropagator<View,PC_FLOAT_BND,CtrlView>(home,x0,x1,b) {}
208
209 template<class View, class CtrlView, ReifyMode rm>
210 ExecStatus
211 ReEq<View,CtrlView,rm>::post(Home home, View x0, View x1, CtrlView b){
212 if (b.one()) {
213 if (rm == RM_PMI)
214 return ES_OK;
215 return Eq<View,View>::post(home,x0,x1);
216 }
217 if (b.zero()) {
218 if (rm == RM_IMP)
219 return ES_OK;
220 return Nq<View,View>::post(home,x0,x1);
221 }
222 if (x0 != x1) {
223 (void) new (home) ReEq(home,x0,x1,b);
224 } else if (rm != RM_IMP) {
225 GECODE_ME_CHECK(b.one(home));
226 }
227 return ES_OK;
228 }
229
230
231 template<class View, class CtrlView, ReifyMode rm>
232 forceinline
233 ReEq<View,CtrlView,rm>::ReEq(Space& home, ReEq& p)
234 : Int::ReBinaryPropagator<View,PC_FLOAT_BND,CtrlView>(home,p) {}
235
236 template<class View, class CtrlView, ReifyMode rm>
237 Actor*
238 ReEq<View,CtrlView,rm>::copy(Space& home) {
239 return new (home) ReEq<View,CtrlView,rm>(home,*this);
240 }
241
242 template<class View, class CtrlView, ReifyMode rm>
243 ExecStatus
244 ReEq<View,CtrlView,rm>::propagate(Space& home, const ModEventDelta&) {
245 if (b.one()) {
246 if (rm == RM_PMI)
247 return home.ES_SUBSUMED(*this);
248 GECODE_REWRITE(*this,(Eq<View,View>::post(home(*this),x0,x1)));
249 }
250 if (b.zero()) {
251 if (rm == RM_IMP)
252 return home.ES_SUBSUMED(*this);
253 GECODE_REWRITE(*this,(Nq<View,View>::post(home(*this),x0,x1)));
254 }
255 switch (rtest_eq(x0,x1)) {
256 case RT_TRUE:
257 if (rm != RM_IMP)
258 GECODE_ME_CHECK(b.one_none(home));
259 break;
260 case RT_FALSE:
261 if (rm != RM_PMI)
262 GECODE_ME_CHECK(b.zero_none(home));
263 break;
264 case RT_MAYBE:
265 return ES_FIX;
266 default: GECODE_NEVER;
267 }
268 return home.ES_SUBSUMED(*this);
269 }
270
271
272 /*
273 * Reified bounds consistent equality (one variable)
274 *
275 */
276
277 template<class View, class CtrlView, ReifyMode rm>
278 forceinline
279 ReEqFloat<View,CtrlView,rm>::ReEqFloat
280 (Home home, View x, FloatVal c0, CtrlView b)
281 : Int::ReUnaryPropagator<View,PC_FLOAT_BND,CtrlView>(home,x,b), c(c0) {}
282
283 template<class View, class CtrlView, ReifyMode rm>
284 ExecStatus
285 ReEqFloat<View,CtrlView,rm>::post(Home home, View x, FloatVal c, CtrlView b) {
286 if (b.one()) {
287 if (rm != RM_PMI)
288 GECODE_ME_CHECK(x.eq(home,c));
289 } else if (x.assigned()) {
290 if (overlap(x.val(),c)) {
291 if (rm != RM_IMP)
292 GECODE_ME_CHECK(b.one(home));
293 } else {
294 if (rm != RM_PMI)
295 GECODE_ME_CHECK(b.zero(home));
296 }
297 } else {
298 (void) new (home) ReEqFloat(home,x,c,b);
299 }
300 return ES_OK;
301 }
302
303
304 template<class View, class CtrlView, ReifyMode rm>
305 forceinline
306 ReEqFloat<View,CtrlView,rm>::ReEqFloat(Space& home, ReEqFloat& p)
307 : Int::ReUnaryPropagator<View,PC_FLOAT_BND,CtrlView>(home,p), c(p.c) {}
308
309 template<class View, class CtrlView, ReifyMode rm>
310 Actor*
311 ReEqFloat<View,CtrlView,rm>::copy(Space& home) {
312 return new (home) ReEqFloat<View,CtrlView,rm>(home,*this);
313 }
314
315 template<class View, class CtrlView, ReifyMode rm>
316 ExecStatus
317 ReEqFloat<View,CtrlView,rm>::propagate(Space& home, const ModEventDelta&) {
318 if (b.one()) {
319 if (rm != RM_PMI)
320 GECODE_ME_CHECK(x0.eq(home,c));
321 } else {
322 switch (rtest_eq(x0,c)) {
323 case RT_TRUE:
324 if (rm != RM_IMP)
325 GECODE_ME_CHECK(b.one(home));
326 break;
327 case RT_FALSE:
328 if (rm != RM_PMI)
329 GECODE_ME_CHECK(b.zero(home));
330 break;
331 case RT_MAYBE:
332 return ES_FIX;
333 default: GECODE_NEVER;
334 }
335 }
336 return home.ES_SUBSUMED(*this);
337 }
338
339
340}}}
341
342// STATISTICS: float-prop