Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
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 
36 namespace 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 (!same(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>
68  : MixBinaryPropagator<View0,PC_FLOAT_BND,View1,PC_FLOAT_BND>(home,p) {}
69 
70  template<class View0, class View1>
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*
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>
115  : NaryPropagator<View,PC_FLOAT_BND>(home,x) {}
116 
117  template<class View>
118  ExecStatus
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>
142  : NaryPropagator<View,PC_FLOAT_BND>(home,p) {}
143 
144  template<class View>
145  Actor*
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)
155  else
156  return PropCost::linear(PropCost::LO, x.size());
157  }
158 
159  template<class View>
160  ExecStatus
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>
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 (!same(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>
243  ExecStatus
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)
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>
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>
316  ExecStatus
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
Reified binary bounds consistent equality propagator.
Definition: rel.hh:125
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:116
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
Inverse implication for reification.
Definition: int.hh:844
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4715
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3482
ReEq(Space &home, ReEq &p)
Constructor for cloning p.
Definition: eq.hpp:233
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
bool overlap(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:498
Reified binary propagator.
Definition: propagator.hpp:87
Binary bounds consistent equality propagator.
Definition: rel.hh:66
Relation does hold.
Definition: view.hpp:494
Eq(Space &home, Eq< View0, View1 > &p)
Constructor for cloning p.
Definition: eq.hpp:67
ViewArray< View > x
Array of views.
Definition: pattern.hpp:145
Base-class for propagators.
Definition: core.hpp:1023
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: eq.hpp:79
Relation does not hold.
Definition: view.hpp:492
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: eq.hpp:317
const Gecode::ModEvent ME_FLOAT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:264
#define forceinline
Definition: config.hpp:185
Propagation has computed fixpoint.
Definition: core.hpp:476
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4732
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: eq.hpp:311
Computation spaces.
Definition: core.hpp:1701
static ExecStatus post(Home home, View x, FloatVal c, CtrlView b)
Post bounds consistent propagator .
Definition: eq.hpp:285
Base-class for both propagators and branchers.
Definition: core.hpp:627
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: eq.hpp:244
Reified bounds consistent equality with float propagator.
Definition: rel.hh:151
static ExecStatus post(Home home, View0 x0, View1 x1)
Post bounds consistent propagator .
Definition: eq.hpp:50
Binary bounds consistent disequality propagator.
Definition: rel.hh:179
NaryEq(Space &home, NaryEq< View > &p)
Constructor for cloning p.
Definition: eq.hpp:141
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
bool same(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether two views are the same.
Definition: view.hpp:676
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: eq.hpp:152
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1034
n-ary propagator
Definition: pattern.hpp:142
static ExecStatus post(Home home, ViewArray< View > &x)
Post bounds consistent propagator .
Definition: eq.hpp:119
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
View arrays.
Definition: array.hpp:224
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
ReEqFloat(Space &home, ReEqFloat &p)
Constructor for cloning p.
Definition: eq.hpp:306
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Float value type.
Definition: float.hh:334
RelTest rtest_eq(View x, View y)
Test whether views x and y are equal.
Definition: rel-test.hpp:40
Mixed binary propagator.
Definition: pattern.hpp:204
Propagation cost.
Definition: core.hpp:485
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: eq.hpp:161
ExecStatus
Definition: core.hpp:471
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
static ExecStatus post(Home home, View x0, View x1, CtrlView b)
Post bounds consistent propagator .
Definition: eq.hpp:211
static ExecStatus post(Home home, View0 x0, View1 x1)
Post bounds consistent propagator .
Definition: nq.hpp:49
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:85
Post propagator for SetVar x
Definition: set.hh:765
Execution is okay.
Definition: core.hpp:475
void unique(void)
Remove all duplicate views from array (changes element order)
Definition: array.hpp:1489
const Gecode::PropCond PC_FLOAT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:292
FloatVal c
Float constant to check.
Definition: rel.hh:157
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: eq.hpp:146
Gecode toplevel namespace
Implication for reification.
Definition: int.hh:837
n-ary bounds consistent equality propagator
Definition: rel.hh:94
Relation may hold or not.
Definition: view.hpp:493
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1199
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Home class for posting propagators
Definition: core.hpp:853
double FloatNum
Floating point number base type.
Definition: float.hh:106
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56