Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
38namespace 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) {
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>
117
118 template<class View>
119 Actor*
121 return new (home) AbsBnd<View>(home,*this);
122 }
123
124 template<class View>
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>
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>
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) {
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>
172
173 template<class View>
174 Actor*
176 return new (home) AbsDom<View>(home,*this);
177 }
178
179 template<class View>
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>
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
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
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
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
@ 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 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
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 toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
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
#define forceinline
Definition config.hpp:187