Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
eq.hpp
Go to the documentation of this file.
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>
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>
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>
69
70 template<class View0, class View1>
73 View0 x0, View1 x1)
75 x0,x1) {}
76
77 template<class View0, class View1>
78 Actor*
80 return new (home) Eq<View0,View1>(home,*this);
81 }
82
83 template<class View0, class View1>
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>
116
117 template<class View>
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>
143
144 template<class View>
145 Actor*
147 return new (home) NaryEq<View>(home,*this);
148 }
149
150 template<class View>
152 NaryEq<View>::cost(const Space&, const ModEventDelta& med) const {
153 if (View::me(med) == ME_FLOAT_VAL)
155 else
156 return PropCost::linear(PropCost::LO, x.size());
157 }
158
159 template<class View>
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 }
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>
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>
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>
234 : Int::ReBinaryPropagator<View,PC_FLOAT_BND,CtrlView>(home,p) {}
235
236 template<class View, class CtrlView, ReifyMode rm>
237 Actor*
239 return new (home) ReEq<View,CtrlView,rm>(home,*this);
240 }
241
242 template<class View, class CtrlView, ReifyMode rm>
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>
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>
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>
307 : Int::ReUnaryPropagator<View,PC_FLOAT_BND,CtrlView>(home,p), c(p.c) {}
308
309 template<class View, class CtrlView, ReifyMode rm>
310 Actor*
312 return new (home) ReEqFloat<View,CtrlView,rm>(home,*this);
313 }
314
315 template<class View, class CtrlView, ReifyMode rm>
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
NNF * l
Left subtree.
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
Float value type.
Definition float.hh:334
Binary bounds consistent equality propagator.
Definition rel.hh:67
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition eq.hpp:85
Eq(Space &home, Eq< View0, View1 > &p)
Constructor for cloning p.
Definition eq.hpp:67
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition eq.hpp:79
static ExecStatus post(Home home, View0 x0, View1 x1)
Post bounds consistent propagator .
Definition eq.hpp:50
n-ary bounds consistent equality propagator
Definition rel.hh:94
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition eq.hpp:161
NaryEq(Space &home, NaryEq< View > &p)
Constructor for cloning p.
Definition eq.hpp:141
static ExecStatus post(Home home, ViewArray< View > &x)
Post bounds consistent propagator .
Definition eq.hpp:119
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition eq.hpp:146
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition eq.hpp:152
Binary bounds consistent disequality propagator.
Definition rel.hh:180
static ExecStatus post(Home home, View0 x0, View1 x1)
Post bounds consistent propagator .
Definition nq.hpp:49
Reified bounds consistent equality with float propagator.
Definition rel.hh:151
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition eq.hpp:317
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition eq.hpp:311
static ExecStatus post(Home home, View x, FloatVal c, CtrlView b)
Post bounds consistent propagator .
Definition eq.hpp:285
ReEqFloat(Space &home, ReEqFloat &p)
Constructor for cloning p.
Definition eq.hpp:306
Reified binary bounds consistent equality propagator.
Definition rel.hh:125
ReEq(Space &home, ReEq &p)
Constructor for cloning p.
Definition eq.hpp:233
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition eq.hpp:238
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition eq.hpp:244
static ExecStatus post(Home home, View x0, View x1, CtrlView b)
Post bounds consistent propagator .
Definition eq.hpp:211
Home class for posting propagators
Definition core.hpp:856
Reified binary propagator.
Reified unary propagator.
Mixed binary propagator.
Definition pattern.hpp:204
n-ary propagator
Definition pattern.hpp:142
Propagation cost.
Definition core.hpp:486
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition core.hpp:4813
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
Base-class for propagators.
Definition core.hpp:1064
Computation spaces.
Definition core.hpp:1742
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
View arrays.
Definition array.hpp:253
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
double FloatNum
Floating point number base type.
Definition float.hh:106
@ RM_IMP
Implication for reification.
Definition int.hh:862
@ RM_PMI
Inverse implication for reification.
Definition int.hh:869
@ RT_TRUE
Relation does hold.
Definition view.hpp:536
@ RT_FALSE
Relation does not hold.
Definition view.hpp:534
@ RT_MAYBE
Relation may hold or not.
Definition view.hpp:535
const Gecode::ModEvent ME_FLOAT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:264
RelTest rtest_eq(View x, View y)
Test whether views x and y are equal.
Definition rel-test.hpp:40
bool overlap(const FloatVal &x, const FloatVal &y)
Definition val.hpp:498
const Gecode::PropCond PC_FLOAT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:292
Gecode toplevel namespace
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56