Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
ite.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  *
6  * Copyright:
7  * Christian Schulte, 2013
8  *
9  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
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 
38 #include <gecode/int/rel.hh>
39 
40 #include <algorithm>
41 
42 namespace Gecode { namespace Int { namespace Bool {
43 
44  template<class V0, class V1, class V2, PropCond pc>
46  IteBase<V0,V1,V2,pc>::IteBase(Home home, BoolView b0, V0 y0, V1 y1, V2 y2)
47  : Propagator(home), b(b0), x0(y0), x1(y1), x2(y2) {
48  b.subscribe(home,*this,PC_BOOL_VAL);
49  x0.subscribe(home,*this,pc);
50  x1.subscribe(home,*this,pc);
51  x2.subscribe(home,*this,pc);
52  }
53 
54  template<class V0, class V1, class V2, PropCond pc>
57  : Propagator(home,p) {
58  b.update(home,p.b);
59  x0.update(home,p.x0);
60  x1.update(home,p.x1);
61  x2.update(home,p.x2);
62  }
63 
64  template<class V0, class V1, class V2, PropCond pc>
65  PropCost
67  return PropCost::ternary(PropCost::LO);
68  }
69 
70  template<class V0, class V1, class V2, PropCond pc>
71  void
73  b.reschedule(home,*this,PC_BOOL_VAL);
74  x0.reschedule(home,*this,pc);
75  x1.reschedule(home,*this,pc);
76  x2.reschedule(home,*this,pc);
77  }
78 
79  template<class V0, class V1, class V2, PropCond pc>
80  forceinline size_t
82  b.cancel(home,*this,PC_BOOL_VAL);
83  x0.cancel(home,*this,pc);
84  x1.cancel(home,*this,pc);
85  x2.cancel(home,*this,pc);
86  (void) Propagator::dispose(home);
87  return sizeof(*this);
88  }
89 
90 
91 
92  template<class V0, class V1, class V2>
94  IteBnd<V0,V1,V2>::IteBnd(Home home, BoolView b, V0 x0, V1 x1, V2 x2)
95  : IteBase<V0,V1,V2,PC_INT_BND>(home,b,x0,x1,x2) {}
96 
97  template<class V0, class V1, class V2>
100  : IteBase<V0,V1,V2,PC_INT_BND>(home,p) {}
101 
102  template<class V0, class V1, class V2>
103  Actor*
105  return new (home) IteBnd<V0,V1,V2>(home,*this);
106  }
107 
108  template<class V0, class V1, class V2>
109  inline ExecStatus
110  IteBnd<V0,V1,V2>::post(Home home, BoolView b, V0 x0, V1 x1, V2 x2) {
111  if (b.one())
112  return Rel::EqBnd<V2,V0>::post(home,x2,x0);
113  if (b.zero())
114  return Rel::EqBnd<V2,V1>::post(home,x2,x1);
115  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
116  GECODE_ME_CHECK(x2.gq(home,std::min(x0.min(),x1.min())));
117  (void) new (home) IteBnd<V0,V1,V2>(home,b,x0,x1,x2);
118  return ES_OK;
119  }
120 
121  template<class V0, class V1, class V2>
122  ExecStatus
124  if (b.one())
125  GECODE_REWRITE(*this,(Rel::EqBnd<V2,V0>::post(home(*this),x2,x0)));
126  if (b.zero())
127  GECODE_REWRITE(*this,(Rel::EqBnd<V2,V1>::post(home(*this),x2,x1)));
128 
129  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
130  GECODE_ME_CHECK(x2.gq(home,std::min(x0.min(),x1.min())));
131 
132  RelTest eq20 = rtest_eq_bnd(x2,x0);
133  RelTest eq21 = rtest_eq_bnd(x2,x1);
134 
135  if ((eq20 == RT_FALSE) && (eq21 == RT_FALSE))
136  return ES_FAILED;
137 
138  if (eq20 == RT_FALSE) {
139  GECODE_ME_CHECK(b.zero_none(home));
140  if (eq21 == RT_TRUE)
141  return home.ES_SUBSUMED(*this);
142  else
143  GECODE_REWRITE(*this,(Rel::EqBnd<V2,V1>::post(home(*this),x2,x1)));
144  }
145 
146  if (eq21 == RT_FALSE) {
147  GECODE_ME_CHECK(b.one_none(home));
148  if (eq20 == RT_TRUE)
149  return home.ES_SUBSUMED(*this);
150  else
151  GECODE_REWRITE(*this,(Rel::EqBnd<V2,V0>::post(home(*this),x2,x0)));
152  }
153 
154  if ((eq20 == RT_TRUE) && (eq21 == RT_TRUE))
155  return home.ES_SUBSUMED(*this);
156 
157  return ES_FIX;
158  }
159 
160 
161 
162  template<class V0, class V1, class V2>
165  : IteBase<V0,V1,V2,PC_INT_DOM>(home,b,x0,x1,x2) {}
166 
167  template<class V0, class V1, class V2>
170  : IteBase<V0,V1,V2,PC_INT_DOM>(home,p) {}
171 
172  template<class V0, class V1, class V2>
173  Actor*
175  return new (home) IteDom<V0,V1,V2>(home,*this);
176  }
177 
178  template<class V0, class V1, class V2>
179  inline ExecStatus
180  IteDom<V0,V1,V2>::post(Home home, BoolView b, V0 x0, V1 x1, V2 x2) {
181  if (b.one())
182  return Rel::EqDom<V2,V0>::post(home,x2,x0);
183  if (b.zero())
184  return Rel::EqDom<V2,V1>::post(home,x2,x1);
185  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
186  GECODE_ME_CHECK(x2.gq(home,std::min(x0.min(),x1.min())));
187  (void) new (home) IteDom<V0,V1,V2>(home,b,x0,x1,x2);
188  return ES_OK;
189  }
190 
191  template<class V0, class V1, class V2>
192  PropCost
194  if (V0::me(med) == ME_INT_DOM)
196  else
198  }
199 
200  template<class V0, class V1, class V2>
201  ExecStatus
203  if (b.one())
204  GECODE_REWRITE(*this,(Rel::EqDom<V2,V0>::post(home(*this),x2,x0)));
205  if (b.zero())
206  GECODE_REWRITE(*this,(Rel::EqDom<V2,V1>::post(home(*this),x2,x1)));
207 
208  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
209  GECODE_ME_CHECK(x2.gq(home,std::min(x0.min(),x1.min())));
210 
211  if (V0::me(med) != ME_INT_DOM) {
212  RelTest eq20 = rtest_eq_bnd(x2,x0);
213  RelTest eq21 = rtest_eq_bnd(x2,x1);
214 
215  if ((eq20 == RT_FALSE) && (eq21 == RT_FALSE))
216  return ES_FAILED;
217 
218  if (eq20 == RT_FALSE) {
219  GECODE_ME_CHECK(b.zero_none(home));
220  if (eq21 == RT_TRUE)
221  return home.ES_SUBSUMED(*this);
222  else
223  GECODE_REWRITE(*this,
224  (Rel::EqDom<V2,V1>::post(home(*this),x2,x1)));
225  }
226 
227  if (eq21 == RT_FALSE) {
228  GECODE_ME_CHECK(b.one_none(home));
229  if (eq20 == RT_TRUE)
230  return home.ES_SUBSUMED(*this);
231  else
232  GECODE_REWRITE(*this,
233  (Rel::EqDom<V2,V0>::post(home(*this),x2,x0)));
234  }
235 
236  if ((eq20 == RT_TRUE) && (eq21 == RT_TRUE))
237  return home.ES_SUBSUMED(*this);
238 
239  return home.ES_FIX_PARTIAL(*this,V0::med(ME_INT_DOM));
240  }
241 
242  RelTest eq20 = rtest_eq_dom(x2,x0);
243  RelTest eq21 = rtest_eq_dom(x2,x1);
244 
245  if ((eq20 == RT_FALSE) && (eq21 == RT_FALSE))
246  return ES_FAILED;
247 
248  if (eq20 == RT_FALSE) {
249  GECODE_ME_CHECK(b.zero_none(home));
250  if (eq21 == RT_TRUE)
251  return home.ES_SUBSUMED(*this);
252  else
253  GECODE_REWRITE(*this,
254  (Rel::EqDom<V2,V1>::post(home(*this),x2,x1)));
255  }
256 
257  if (eq21 == RT_FALSE) {
258  GECODE_ME_CHECK(b.one_none(home));
259  if (eq20 == RT_TRUE)
260  return home.ES_SUBSUMED(*this);
261  else
262  GECODE_REWRITE(*this,
263  (Rel::EqDom<V2,V0>::post(home(*this),x2,x0)));
264  }
265 
266  assert((eq20 != RT_TRUE) || (eq21 != RT_TRUE));
267 
268  ViewRanges<V0> r0(x0);
269  ViewRanges<V1> r1(x1);
271 
272  if (!shared<V0,V2>(x0,x2) && !shared<V1,V2>(x1,x2))
273  GECODE_ME_CHECK(x2.inter_r(home,u,false));
274  else
275  GECODE_ME_CHECK(x2.inter_r(home,u,true));
276 
277  return ES_FIX;
278  }
279 
280 }}}
281 
282 // STATISTICS: int-prop
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:120
If-then-else bounds-consistent propagator.
Definition: bool.hh:610
bool zero(void) const
Test whether view is assigned to be zero.
Definition: bool.hpp:214
Binary domain consistent equality propagator.
Definition: rel.hh:71
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3433
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
RelTest rtest_eq_dom(VX x, VY y)
Test whether views x and y are equal (use full domain information)
Definition: rel-test.hpp:69
bool one(void) const
Test whether view is assigned to be one.
Definition: bool.hpp:218
Base-class for propagators.
Definition: core.hpp:1016
#define forceinline
Definition: config.hpp:182
Propagation has computed fixpoint.
Definition: core.hpp:469
Computation spaces.
Definition: core.hpp:1668
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: ite.hpp:104
static ExecStatus post(Home home, BoolView b, V0 x0, V1 x1, V2 x2)
Post if-then-else propagator.
Definition: ite.hpp:180
Base-class for both propagators and branchers.
Definition: core.hpp:620
Range iterator for integer views.
Definition: view.hpp:54
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
If-then-else propagator base-class.
Definition: bool.hh:584
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Execution has resulted in failure.
Definition: core.hpp:466
ModEvent zero_none(Space &home)
Assign not yet assigned view to zero.
Definition: bool.hpp:232
Relation does not hold.
Definition: view.hpp:1633
RelTest
Result of testing relation.
Definition: view.hpp:1632
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
IteBnd(Space &home, IteBnd &p)
Constructor for cloning p.
Definition: ite.hpp:99
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1027
Binary bounds consistent equality propagator.
Definition: rel.hh:137
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high ternary)
Definition: ite.hpp:193
static ExecStatus post(Home home, BoolView b, V0 x0, V1 x1, V2 x2)
Post if-then-else propagator.
Definition: ite.hpp:110
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
Expensive.
Definition: core.hpp:506
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: ite.hpp:123
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:3439
RelTest rtest_eq_bnd(VX x, VY y)
Test whether views x and y are equal (use bounds information)
Definition: rel-test.hpp:47
Range iterator for computing union (binary)
BoolView b
View for condition.
Definition: bool.hh:587
If-then-else domain-consistent propagator.
Definition: bool.hh:636
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Propagation cost.
Definition: core.hpp:478
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
ExecStatus
Definition: core.hpp:464
Execution is okay.
Definition: core.hpp:468
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: ite.hpp:174
IteDom(Space &home, IteDom &p)
Constructor for cloning p.
Definition: ite.hpp:169
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4652
Gecode toplevel namespace
ModEvent one_none(Space &home)
Assign not yet assigned view to one.
Definition: bool.hpp:236
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
Home class for posting propagators
Definition: core.hpp:846
Relation does hold.
Definition: view.hpp:1635
IteBase(Space &home, IteBase &p)
Constructor for cloning p.
Definition: ite.hpp:56
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: ite.hpp:202
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:126
Boolean view for Boolean variables.
Definition: view.hpp:1329