this repo has no description
dekker.one
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>
41 ExecStatus
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)
70 GECODE_REWRITE(p,(Eq<MinusView,View>::post(home(p),MinusView(x0),x1)));
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>
87 forceinline
88 AbsBnd<View>::AbsBnd(Home home, View x0, View x1)
89 : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
90
91 template<class View>
92 ExecStatus
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>
114 forceinline
115 AbsBnd<View>::AbsBnd(Space& home, AbsBnd<View>& p)
116 : BinaryPropagator<View,PC_INT_BND>(home,p) {}
117
118 template<class View>
119 Actor*
120 AbsBnd<View>::copy(Space& home) {
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)
128 return PropCost::unary(PropCost::LO);
129 else
130 return PropCost::binary(PropCost::LO);
131 }
132
133 template<class View>
134 ExecStatus
135 AbsBnd<View>::propagate(Space& home, const ModEventDelta&) {
136 return prop_abs_bnd<View,Rel::EqBnd>(home, *this, x0, x1);
137 }
138
139
140
141 template<class View>
142 forceinline
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>
169 forceinline
170 AbsDom<View>::AbsDom(Space& home, AbsDom<View>& p)
171 : BinaryPropagator<View,PC_INT_DOM>(home,p) {}
172
173 template<class View>
174 Actor*
175 AbsDom<View>::copy(Space& home) {
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)
183 return PropCost::unary(PropCost::LO);
184 else
185 return PropCost::binary((View::me(med) == ME_INT_DOM) ?
186 PropCost::HI : PropCost::LO);
187 }
188
189 template<class View>
190 ExecStatus
191 AbsDom<View>::propagate(Space& home, const ModEventDelta& med) {
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