Generated on Sat Jul 29 2017 12:41:24 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: 2017-03-10 16:45:34 +0100 (Fri, 10 Mar 2017) $ by $Author: schulte $
13  * $Revision: 15568 $
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 
136 
137  template<class View>
139  AbsDom<View>::AbsDom(Home home, View x0, View x1)
140  : BinaryPropagator<View,PC_INT_DOM>(home,x0,x1) {}
141 
142  template<class View>
143  ExecStatus
144  AbsDom<View>::post(Home home, View x0, View x1) {
145  if (x0.min() >= 0) {
146  return Rel::EqDom<View,View>::post(home,x0,x1);
147  } else if (x0.max() <= 0) {
148  return Rel::EqDom<MinusView,View>::post(home,MinusView(x0),x1);
149  } else {
150  assert(!x0.assigned());
151  GECODE_ME_CHECK(x1.gq(home,0));
152  if (x1.assigned()) {
153  int mp[2] = {-x1.val(),x1.val()};
154  Iter::Values::Array i(mp,2);
155  GECODE_ME_CHECK(x0.inter_v(home,i,false));
156  } else if (!same(x0,x1)) {
157  GECODE_ME_CHECK(x1.lq(home,std::max(-x0.min(),x0.max())));
158  (void) new (home) AbsDom<View>(home,x0,x1);
159  }
160  }
161  return ES_OK;
162  }
163 
164  template<class View>
167  : BinaryPropagator<View,PC_INT_DOM>(home,share,p) {}
168 
169  template<class View>
170  Actor*
171  AbsDom<View>::copy(Space& home,bool share) {
172  return new (home) AbsDom<View>(home,share,*this);
173  }
174 
175  template<class View>
176  PropCost
177  AbsDom<View>::cost(const Space&, const ModEventDelta& med) const {
178  if (View::me(med) == ME_INT_VAL)
180  else
181  return PropCost::binary((View::me(med) == ME_INT_DOM) ?
183  }
184 
185  template<class View>
186  ExecStatus
188  if (View::me(med) != ME_INT_DOM) {
189  GECODE_ES_CHECK((prop_abs_bnd<View,Rel::EqDom>(home, *this, x0, x1)));
190  return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
191  }
192 
193  Region r(home);
194 
195  {
196  ViewRanges<View> i(x0), j(x0);
197 
198  using namespace Iter::Ranges;
199  Positive<ViewRanges<View> > p(i);
200  Negative<ViewRanges<View> > n(j);
201 
202  Minus m(r,n);
203 
204  Union<Positive<ViewRanges<View> >,Minus> u(p,m);
205 
206  GECODE_ME_CHECK(x1.inter_r(home,u,false));
207 
208  }
209 
210  {
211  ViewRanges<View> i(x1), j(x1);
212 
213  using namespace Iter::Ranges;
214  Minus m(r,j);
215 
216  Union<ViewRanges<View>,Minus> u(i,m);
217 
218  GECODE_ME_CHECK(x0.inter_r(home,u,false));
219  }
220 
221  if (x1.assigned())
222  return home.ES_SUBSUMED(*this);
223 
224  if (x0.min() >= 0)
225  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x1)));
226 
227  if (x0.max() <= 0) {
228  MinusView mx0(x0);
229  GECODE_REWRITE(*this,(Rel::EqDom<MinusView,View>::post(home(*this),mx0,x1)));
230  }
231 
232  return ES_FIX;
233  }
234 
235 }}}
236 
237 // STATISTICS: int-prop
238 
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:120
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: abs.hpp:187
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
Binary domain consistent equality propagator.
Definition: rel.hh:71
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
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:3627
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:122
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: abs.hpp:177
ExecStatus prop_abs_bnd(Space &home, Propagator &p, View x0, View x1)
Definition: abs.hpp:46
Base-class for propagators.
Definition: core.hpp:1092
Handle to region.
Definition: region.hpp:61
Propagation has computed fixpoint.
Definition: core.hpp:545
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4858
Computation spaces.
Definition: core.hpp:1748
Base-class for both propagators and branchers.
Definition: core.hpp:696
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:144
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
Binary propagator.
Definition: propagator.hpp:89
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
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1103
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
Expensive.
Definition: core.hpp:582
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: abs.hpp:116
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
Propagation cost.
Definition: core.hpp:554
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
ExecStatus
Definition: core.hpp:540
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:544
Propagation has not computed fixpoint.
Definition: core.hpp:543
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
AbsDom(Space &home, bool share, AbsDom &p)
Constructor for cloning p.
Definition: abs.hpp:166
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4854
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:171