Generated on Sat Feb 7 2015 02:01:20 for Gecode by doxygen 1.8.9.1
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: 2013-04-29 20:52:35 +0200 (Mon, 29 Apr 2013) $ by $Author: schulte $
11  * $Revision: 13590 $
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 View, PropCond pc>
46  IteBase<View,pc>::IteBase(Home home, BoolView b0, View y0, View y1, View 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 View, PropCond pc>
57  : Propagator(home,share,p) {
58  b.update(home,share,p.b);
59  x0.update(home,share,p.x0);
60  x1.update(home,share,p.x1);
61  x2.update(home,share,p.x2);
62  }
63 
64  template<class View, PropCond pc>
65  PropCost
66  IteBase<View,pc>::cost(const Space&, const ModEventDelta&) const {
68  }
69 
70  template<class View, PropCond pc>
71  forceinline size_t
73  b.cancel(home,*this,PC_BOOL_VAL);
74  x0.cancel(home,*this,pc);
75  x1.cancel(home,*this,pc);
76  x2.cancel(home,*this,pc);
77  (void) Propagator::dispose(home);
78  return sizeof(*this);
79  }
80 
81 
82 
83  template<class View>
85  IteBnd<View>::IteBnd(Home home, BoolView b, View x0, View x1, View x2)
86  : IteBase<View,PC_INT_BND>(home,b,x0,x1,x2) {}
87 
88  template<class View>
91  : IteBase<View,PC_INT_BND>(home,share,p) {}
92 
93  template<class View>
94  Actor*
95  IteBnd<View>::copy(Space& home, bool share) {
96  return new (home) IteBnd<View>(home,share,*this);
97  }
98 
99  template<class View>
100  inline ExecStatus
101  IteBnd<View>::post(Home home, BoolView b, View x0, View x1, View x2) {
102  if (same(x0,x1) || b.one())
103  return Rel::EqBnd<View,View>::post(home,x2,x0);
104  if (b.zero())
105  return Rel::EqBnd<View,View>::post(home,x2,x1);
106  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
107  GECODE_ME_CHECK(x2.gq(home,std::min(x0.min(),x1.min())));
108  (void) new (home) IteBnd<View>(home,b,x0,x1,x2);
109  return ES_OK;
110  }
111 
112  template<class View>
113  ExecStatus
115  if (b.one())
116  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x2,x0)));
117  if (b.zero())
118  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x2,x1)));
119 
120  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
121  GECODE_ME_CHECK(x2.gq(home,std::min(x0.min(),x1.min())));
122 
123  RelTest eq20 = rtest_eq_bnd(x2,x0);
124  RelTest eq21 = rtest_eq_bnd(x2,x1);
125 
126  if ((eq20 == RT_FALSE) && (eq21 == RT_FALSE))
127  return ES_FAILED;
128 
129  if (eq20 == RT_FALSE) {
130  GECODE_ME_CHECK(b.zero_none(home));
131  if (eq21 == RT_TRUE)
132  return home.ES_SUBSUMED(*this);
133  else
134  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x2,x1)));
135  }
136 
137  if (eq21 == RT_FALSE) {
138  GECODE_ME_CHECK(b.one_none(home));
139  if (eq20 == RT_TRUE)
140  return home.ES_SUBSUMED(*this);
141  else
142  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x2,x0)));
143  }
144 
145  if ((eq20 == RT_TRUE) && (eq21 == RT_TRUE))
146  return home.ES_SUBSUMED(*this);
147 
148  return ES_FIX;
149  }
150 
151 
152 
153  template<class View>
155  IteDom<View>::IteDom(Home home, BoolView b, View x0, View x1, View x2)
156  : IteBase<View,PC_INT_DOM>(home,b,x0,x1,x2) {}
157 
158  template<class View>
161  : IteBase<View,PC_INT_DOM>(home,share,p) {}
162 
163  template<class View>
164  Actor*
165  IteDom<View>::copy(Space& home, bool share) {
166  return new (home) IteDom<View>(home,share,*this);
167  }
168 
169  template<class View>
170  inline ExecStatus
171  IteDom<View>::post(Home home, BoolView b, View x0, View x1, View x2) {
172  if (same(x0,x1) || b.one())
173  return Rel::EqDom<View,View>::post(home,x2,x0);
174  if (b.zero())
175  return Rel::EqDom<View,View>::post(home,x2,x1);
176  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
177  GECODE_ME_CHECK(x2.gq(home,std::min(x0.min(),x1.min())));
178  (void) new (home) IteDom<View>(home,b,x0,x1,x2);
179  return ES_OK;
180  }
181 
182  template<class View>
183  PropCost
184  IteDom<View>::cost(const Space&, const ModEventDelta& med) const {
185  if (View::me(med) == ME_INT_DOM)
187  else
189  }
190 
191  template<class View>
192  ExecStatus
194  if (b.one())
195  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x2,x0)));
196  if (b.zero())
197  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x2,x1)));
198 
199  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
200  GECODE_ME_CHECK(x2.gq(home,std::min(x0.min(),x1.min())));
201 
202  if (View::me(med) != ME_INT_DOM) {
203  RelTest eq20 = rtest_eq_bnd(x2,x0);
204  RelTest eq21 = rtest_eq_bnd(x2,x1);
205 
206  if ((eq20 == RT_FALSE) && (eq21 == RT_FALSE))
207  return ES_FAILED;
208 
209  if (eq20 == RT_FALSE) {
210  GECODE_ME_CHECK(b.zero_none(home));
211  if (eq21 == RT_TRUE)
212  return home.ES_SUBSUMED(*this);
213  else
214  GECODE_REWRITE(*this,
215  (Rel::EqDom<View,View>::post(home(*this),x2,x1)));
216  }
217 
218  if (eq21 == RT_FALSE) {
219  GECODE_ME_CHECK(b.one_none(home));
220  if (eq20 == RT_TRUE)
221  return home.ES_SUBSUMED(*this);
222  else
223  GECODE_REWRITE(*this,
224  (Rel::EqDom<View,View>::post(home(*this),x2,x0)));
225  }
226 
227  if ((eq20 == RT_TRUE) && (eq21 == RT_TRUE))
228  return home.ES_SUBSUMED(*this);
229 
230  return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
231  }
232 
233  RelTest eq20 = rtest_eq_dom(x2,x0);
234  RelTest eq21 = rtest_eq_dom(x2,x1);
235 
236  if ((eq20 == RT_FALSE) && (eq21 == RT_FALSE))
237  return ES_FAILED;
238 
239  if (eq20 == RT_FALSE) {
240  GECODE_ME_CHECK(b.zero_none(home));
241  if (eq21 == RT_TRUE)
242  return home.ES_SUBSUMED(*this);
243  else
244  GECODE_REWRITE(*this,
245  (Rel::EqDom<View,View>::post(home(*this),x2,x1)));
246  }
247 
248  if (eq21 == RT_FALSE) {
249  GECODE_ME_CHECK(b.one_none(home));
250  if (eq20 == RT_TRUE)
251  return home.ES_SUBSUMED(*this);
252  else
253  GECODE_REWRITE(*this,
254  (Rel::EqDom<View,View>::post(home(*this),x2,x0)));
255  }
256 
257  assert((eq20 != RT_TRUE) || (eq21 != RT_TRUE));
258 
259  ViewRanges<View> r0(x0), r1(x1);
261 
262  if (!same(x0,x2) && !same(x1,x2))
263  GECODE_ME_CHECK(x2.inter_r(home,u,false));
264  else
265  GECODE_ME_CHECK(x2.inter_r(home,u,true));
266 
267  return ES_FIX;
268  }
269 
270 }}}
271 
272 // STATISTICS: int-prop
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:109
If-then-else bounds-consistent propagator.
Definition: bool.hh:600
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: ite.hpp:72
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high ternary)
Definition: ite.hpp:184
Binary domain consistent equality propagator.
Definition: rel.hh:71
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
IteDom(Space &home, bool share, IteDom &p)
Constructor for cloning p.
Definition: ite.hpp:160
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: ite.hpp:165
Base-class for propagators.
Definition: core.hpp:755
Expensive.
Definition: core.hpp:564
IteBase(Space &home, bool share, IteBase &p)
Constructor for cloning p.
Definition: ite.hpp:56
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
Base-class for both propagators and branchers.
Definition: core.hpp:666
Range iterator for integer views.
Definition: view.hpp:54
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: ite.hpp:95
bool same(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:389
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: view.hpp:453
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
If-then-else propagator base-class.
Definition: bool.hh:576
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Execution has resulted in failure.
Definition: core.hpp:525
Relation does not hold.
Definition: view.hpp:1615
RelTest
Result of testing relation.
Definition: view.hpp:1614
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
Binary bounds consistent equality propagator.
Definition: rel.hh:107
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
void update(Space &home, bool share, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition: view.hpp:494
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: ite.hpp:114
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
RelTest rtest_eq_dom(View x, View y)
Test whether views x and y are equal (use full domain information)
Definition: rel-test.hpp:68
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:2979
Range iterator for computing union (binary)
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
If-then-else domain-consistent propagator.
Definition: bool.hh:626
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low ternary)
Definition: ite.hpp:66
IteBnd(Space &home, bool share, IteBnd &p)
Constructor for cloning p.
Definition: ite.hpp:90
bool one(void) const
Test whether view is assigned to be one.
Definition: bool.hpp:218
static ExecStatus post(Home home, BoolView b, View x0, View x1, View x2)
Post if-then-else propagator.
Definition: ite.hpp:171
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
ExecStatus
Definition: core.hpp:523
#define forceinline
Definition: config.hpp:132
static ExecStatus post(Home home, BoolView b, View x0, View x1, View x2)
Post if-then-else propagator.
Definition: ite.hpp:101
Execution is okay.
Definition: core.hpp:527
RelTest rtest_eq_bnd(View x, View y)
Test whether views x and y are equal (use bounds information)
Definition: rel-test.hpp:47
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4050
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: ite.hpp:193
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
BoolView b
View for condition.
Definition: bool.hh:579
Gecode toplevel namespace
bool zero(void) const
Test whether view is assigned to be zero.
Definition: bool.hpp:214
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
Relation does hold.
Definition: view.hpp:1617
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:1315