Generated on Thu Mar 16 2017 03:24:18 for Gecode by doxygen 1.8.13
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: 2016-06-17 15:43:08 +0200 (Fri, 17 Jun 2016) $ by $Author: schulte $
13  * $Revision: 15116 $
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, PropCond pc>
84  AbsBnd<View,pc>::AbsBnd(Home home, View x0, View x1)
85  : BinaryPropagator<View,pc>(home,x0,x1) {}
86 
87  template<class View, PropCond pc>
89  AbsBnd<View,pc>::post(Home home, View x0, View x1) {
90  if (x0.min() >= 0) {
91  if (pc == PC_INT_VAL)
92  return Rel::EqVal<View,View>::post(home,x0,x1);
93  else
94  return Rel::EqBnd<View,View>::post(home,x0,x1);
95  } else if (x0.max() <= 0) {
96  if (pc == PC_INT_VAL)
97  return Rel::EqVal<MinusView,View>::post(home,MinusView(x0),x1);
98  else
99  return Rel::EqBnd<MinusView,View>::post(home,MinusView(x0),x1);
100  } else {
101  assert(!x0.assigned());
102  GECODE_ME_CHECK(x1.gq(home,0));
103  if (x1.assigned()) {
104  int mp[2] = {-x1.val(),x1.val()};
105  Iter::Values::Array i(mp,2);
106  GECODE_ME_CHECK(x0.inter_v(home,i,false));
107  } else if (!same(x0,x1)) {
108  if (pc != PC_INT_VAL)
109  GECODE_ME_CHECK(x1.lq(home,std::max(-x0.min(),x0.max())));
110  (void) new (home) AbsBnd<View,pc>(home,x0,x1);
111  }
112  }
113  return ES_OK;
114  }
115 
116  template<class View, PropCond pc>
119  : BinaryPropagator<View,pc>(home,share,p) {}
120 
121  template<class View, PropCond pc>
122  Actor*
123  AbsBnd<View,pc>::copy(Space& home,bool share) {
124  return new (home) AbsBnd<View,pc>(home,share,*this);
125  }
126 
127  template<class View, PropCond pc>
128  PropCost
130  (void) med;
131  if ((pc == PC_INT_VAL) || (View::me(med) == ME_INT_VAL))
133  else
135  }
136 
137  template<class View, PropCond pc>
138  ExecStatus
140  return prop_abs_bnd<View,Rel::EqBnd>(home, *this, x0, x1);
141  }
142 
143 
144 
145  template<class View>
147  AbsDom<View>::AbsDom(Home home, View x0, View x1)
148  : BinaryPropagator<View,PC_INT_DOM>(home,x0,x1) {}
149 
150  template<class View>
151  ExecStatus
152  AbsDom<View>::post(Home home, View x0, View x1) {
153  if (x0.min() >= 0) {
154  return Rel::EqDom<View,View>::post(home,x0,x1);
155  } else if (x0.max() <= 0) {
156  return Rel::EqDom<MinusView,View>::post(home,MinusView(x0),x1);
157  } else {
158  assert(!x0.assigned());
159  GECODE_ME_CHECK(x1.gq(home,0));
160  if (x1.assigned()) {
161  int mp[2] = {-x1.val(),x1.val()};
162  Iter::Values::Array i(mp,2);
163  GECODE_ME_CHECK(x0.inter_v(home,i,false));
164  } else if (!same(x0,x1)) {
165  GECODE_ME_CHECK(x1.lq(home,std::max(-x0.min(),x0.max())));
166  (void) new (home) AbsDom<View>(home,x0,x1);
167  }
168  }
169  return ES_OK;
170  }
171 
172  template<class View>
175  : BinaryPropagator<View,PC_INT_DOM>(home,share,p) {}
176 
177  template<class View>
178  Actor*
179  AbsDom<View>::copy(Space& home,bool share) {
180  return new (home) AbsDom<View>(home,share,*this);
181  }
182 
183  template<class View>
184  PropCost
185  AbsDom<View>::cost(const Space&, const ModEventDelta& med) const {
186  if (View::me(med) == ME_INT_VAL)
188  else
189  return PropCost::binary((View::me(med) == ME_INT_DOM) ?
191  }
192 
193  template<class View>
194  ExecStatus
196  if (View::me(med) != ME_INT_DOM) {
197  GECODE_ES_CHECK((prop_abs_bnd<View,Rel::EqDom>(home, *this, x0, x1)));
198  return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
199  }
200 
201  Region r(home);
202 
203  {
204  ViewRanges<View> i(x0), j(x0);
205 
206  using namespace Iter::Ranges;
207  Positive<ViewRanges<View> > p(i);
208  Negative<ViewRanges<View> > n(j);
209 
210  Minus m(r,n);
211 
212  Union<Positive<ViewRanges<View> >,Minus> u(p,m);
213 
214  GECODE_ME_CHECK(x1.inter_r(home,u,false));
215 
216  }
217 
218  {
219  ViewRanges<View> i(x1), j(x1);
220 
221  using namespace Iter::Ranges;
222  Minus m(r,j);
223 
224  Union<ViewRanges<View>,Minus> u(i,m);
225 
226  GECODE_ME_CHECK(x0.inter_r(home,u,false));
227  }
228 
229  if (x1.assigned())
230  return home.ES_SUBSUMED(*this);
231 
232  if (x0.min() >= 0)
233  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x1)));
234 
235  if (x0.max() <= 0) {
236  MinusView mx0(x0);
237  GECODE_REWRITE(*this,(Rel::EqDom<MinusView,View>::post(home(*this),mx0,x1)));
238  }
239 
240  return ES_FIX;
241  }
242 
243 }}}
244 
245 // STATISTICS: int-prop
246 
static ExecStatus post(Home home, View x0, View x1)
Post bounds consistent propagator .
Definition: abs.hpp:89
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:120
AbsBnd(Space &home, bool share, AbsBnd &p)
Constructor for cloning p.
Definition: abs.hpp:118
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: abs.hpp:195
Binary domain consistent equality propagator.
Definition: rel.hh:71
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3484
const FloatNum max
Largest allowed float value.
Definition: float.hh:846
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:3497
static ExecStatus post(Home home, View0 x0, View1 x1)
Post domain consistent propagator .
Definition: eq.hpp:180
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: abs.hpp:185
ExecStatus prop_abs_bnd(Space &home, Propagator &p, View x0, View x1)
Definition: abs.hpp:46
Base-class for propagators.
Definition: core.hpp:1012
Handle to region.
Definition: region.hpp:61
View x0
Two views.
Definition: propagator.hpp:92
Propagation has computed fixpoint.
Definition: core.hpp:541
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4594
Computation spaces.
Definition: core.hpp:1672
Base-class for both propagators and branchers.
Definition: core.hpp:682
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:112
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
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:152
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
union Gecode::@554::NNF::@60 u
Union depending on nodetype t.
Domain consistent absolute value propagator.
Definition: arithmetic.hh:96
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Binary propagator.
Definition: propagator.hpp:89
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: abs.hpp:139
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1022
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
Expensive.
Definition: core.hpp:578
static ExecStatus post(Home home, View0 x0, View1 x1)
Post value propagation propagator .
Definition: eq.hpp:52
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
Propagation cost.
Definition: core.hpp:550
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
ExecStatus
Definition: core.hpp:536
Minus integer view.
Definition: view.hpp:276
#define forceinline
Definition: config.hpp:173
Propagator for set equality
Definition: rel.hh:150
Execution is okay.
Definition: core.hpp:540
Propagation has not computed fixpoint.
Definition: core.hpp:539
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: abs.hpp:129
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:905
AbsDom(Space &home, bool share, AbsDom &p)
Constructor for cloning p.
Definition: abs.hpp:174
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4590
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: abs.hpp:123
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: abs.hpp:179
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82