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