Generated on Sat Feb 7 2015 02:01:19 for Gecode by doxygen 1.8.9.1
abs.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  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2004
9  * Guido Tack, 2006
10  *
11  * Last modified:
12  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
13  * $Revision: 13068 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <algorithm>
41 
42 namespace Gecode { namespace Int { namespace Arithmetic {
43 
44  template<class View, template<class View0,class View1> class Eq>
46  prop_abs_bnd(Space& home, Propagator& p, View x0, View x1) {
47  if (x0.assigned()) {
48  GECODE_ME_CHECK(x1.eq(home,(x0.val() < 0) ? -x0.val() : x0.val()));
49  return home.ES_SUBSUMED(p);
50  }
51 
52  if (x1.assigned()) {
53  if (x0.min() >= 0) {
54  GECODE_ME_CHECK(x0.eq(home,x1.val()));
55  return home.ES_SUBSUMED(p);
56  } else if (x0.max() <= 0) {
57  GECODE_ME_CHECK(x0.eq(home,-x1.val()));
58  return home.ES_SUBSUMED(p);
59  } else if (x1.val() == 0) {
60  GECODE_ME_CHECK(x0.eq(home,0));
61  return home.ES_SUBSUMED(p);
62  } else {
63  int mp[2] = {-x1.val(),x1.val()};
64  Iter::Values::Array i(mp,2);
65  GECODE_ME_CHECK(x0.inter_v(home,i,false));
66  return home.ES_SUBSUMED(p);
67  }
68  }
69 
70  if (x0.min() >= 0)
71  GECODE_REWRITE(p,(Eq<View,View>::post(home(p),x0,x1)));
72 
73  if (x0.max() <= 0)
75 
76  GECODE_ME_CHECK(x1.lq(home,std::max(x0.max(),-x0.min())));
77  GECODE_ME_CHECK(x0.lq(home,x1.max()));
78  GECODE_ME_CHECK(x0.gq(home,-x1.max()));
79  return ES_NOFIX;
80  }
81 
82  template<class View>
84  AbsBnd<View>::AbsBnd(Home home, View x0, View x1)
85  : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
86 
87  template<class View>
89  AbsBnd<View>::post(Home home, View x0, View x1) {
90  if (x0.min() >= 0) {
91  return Rel::EqBnd<View,View>::post(home,x0,x1);
92  } else if (x0.max() <= 0) {
93  return Rel::EqBnd<MinusView,View>::post(home,MinusView(x0),x1);
94  } else {
95  assert(!x0.assigned());
96  GECODE_ME_CHECK(x1.gq(home,0));
97  if (x1.assigned()) {
98  int mp[2] = {-x1.val(),x1.val()};
99  Iter::Values::Array i(mp,2);
100  GECODE_ME_CHECK(x0.inter_v(home,i,false));
101  } else if (!same(x0,x1)) {
102  GECODE_ME_CHECK(x1.lq(home,std::max(-x0.min(),x0.max())));
103  (void) new (home) AbsBnd<View>(home,x0,x1);
104  }
105  }
106  return ES_OK;
107  }
108 
109  template<class View>
112  : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
113 
114  template<class View>
115  Actor*
116  AbsBnd<View>::copy(Space& home,bool share) {
117  return new (home) AbsBnd<View>(home,share,*this);
118  }
119 
120  template<class View>
121  PropCost
122  AbsBnd<View>::cost(const Space&, const ModEventDelta& med) const {
123  if (View::me(med) == ME_INT_VAL)
125  else
127  }
128 
129  template<class View>
130  ExecStatus
132  return prop_abs_bnd<View,Rel::EqBnd>(home, *this, x0, x1);
133  }
134 
135  template<class View>
137  AbsDom<View>::AbsDom(Home home, View x0, View x1)
138  : BinaryPropagator<View,PC_INT_DOM>(home,x0,x1) {}
139 
140  template<class View>
141  ExecStatus
142  AbsDom<View>::post(Home home, View x0, View x1) {
143  if (x0.min() >= 0) {
144  return Rel::EqDom<View,View>::post(home,x0,x1);
145  } else if (x0.max() <= 0) {
146  return Rel::EqDom<MinusView,View>::post(home,MinusView(x0),x1);
147  } else {
148  assert(!x0.assigned());
149  GECODE_ME_CHECK(x1.gq(home,0));
150  if (x1.assigned()) {
151  int mp[2] = {-x1.val(),x1.val()};
152  Iter::Values::Array i(mp,2);
153  GECODE_ME_CHECK(x0.inter_v(home,i,false));
154  } else if (!same(x0,x1)) {
155  GECODE_ME_CHECK(x1.lq(home,std::max(-x0.min(),x0.max())));
156  (void) new (home) AbsDom<View>(home,x0,x1);
157  }
158  }
159  return ES_OK;
160  }
161 
162  template<class View>
165  : BinaryPropagator<View,PC_INT_DOM>(home,share,p) {}
166 
167  template<class View>
168  Actor*
169  AbsDom<View>::copy(Space& home,bool share) {
170  return new (home) AbsDom<View>(home,share,*this);
171  }
172 
173  template<class View>
174  PropCost
175  AbsDom<View>::cost(const Space&, const ModEventDelta& med) const {
176  if (View::me(med) == ME_INT_VAL)
178  else
179  return PropCost::binary((View::me(med) == ME_INT_DOM) ?
181  }
182 
183  template<class View>
184  ExecStatus
186  if (View::me(med) != ME_INT_DOM) {
187  GECODE_ES_CHECK((prop_abs_bnd<View,Rel::EqDom>(home, *this, x0, x1)));
188  return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
189  }
190 
191  Region r(home);
192 
193  {
194  ViewRanges<View> i(x0), j(x0);
195 
196  using namespace Iter::Ranges;
197  Positive<ViewRanges<View> > p(i);
198  Negative<ViewRanges<View> > n(j);
199 
200  Minus m(r,n);
201 
202  Union<Positive<ViewRanges<View> >,Minus> u(p,m);
203 
204  GECODE_ME_CHECK(x1.inter_r(home,u,false));
205 
206  }
207 
208  {
209  ViewRanges<View> i(x1), j(x1);
210 
211  using namespace Iter::Ranges;
212  Minus m(r,j);
213 
214  Union<ViewRanges<View>,Minus> u(i,m);
215 
216  GECODE_ME_CHECK(x0.inter_r(home,u,false));
217  }
218 
219  if (x1.assigned())
220  return home.ES_SUBSUMED(*this);
221 
222  if (x0.min() >= 0)
223  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x1)));
224 
225  if (x0.max() <= 0) {
226  MinusView mx0(x0);
227  GECODE_REWRITE(*this,(Rel::EqDom<MinusView,View>::post(home(*this),mx0,x1)));
228  }
229 
230  return ES_FIX;
231  }
232 
233 }}}
234 
235 // STATISTICS: int-prop
236 
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:109
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: abs.hpp:185
Binary domain consistent equality propagator.
Definition: rel.hh:71
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
Propagator for ternary union
Definition: rel-op.hh:156
Value iterator for array of integers
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:2986
static ExecStatus post(Home home, View0 x0, View1 x1)
Post domain consistent propagator .
Definition: eq.hpp:120
ExecStatus prop_abs_bnd(Space &home, Propagator &p, View x0, View x1)
Definition: abs.hpp:46
Base-class for propagators.
Definition: core.hpp:755
Expensive.
Definition: core.hpp:564
Handle to region.
Definition: region.hpp:61
Propagation has computed fixpoint.
Definition: core.hpp:528
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4058
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
Bounds consistent absolute value propagator.
Definition: arithmetic.hh:63
static ExecStatus post(Home home, View0 x0, View1 x1)
Post bounds consistent propagator .
Definition: eq.hpp:52
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
bool same(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:389
static ExecStatus post(Home home, View x0, View x1)
Post domain consistent propagator .
Definition: abs.hpp:142
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Domain consistent absolute value propagator.
Definition: arithmetic.hh:96
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Binary propagator.
Definition: propagator.hpp:87
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: abs.hpp:131
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: abs.hpp:116
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
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
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: abs.hpp:122
Minus integer view.
Definition: view.hpp:276
#define forceinline
Definition: config.hpp:132
Propagator for set equality
Definition: rel.hh:146
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
Gecode toplevel namespace
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: abs.hpp:175
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
AbsDom(Space &home, bool share, AbsDom &p)
Constructor for cloning p.
Definition: abs.hpp:164
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4054
AbsBnd(Space &home, bool share, AbsBnd &p)
Constructor for cloning p.
Definition: abs.hpp:111
static ExecStatus post(Home home, View x0, View x1)
Post bounds consistent propagator .
Definition: abs.hpp:89
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: abs.hpp:169