Generated on Thu Feb 21 2013 23:11:40 for Gecode by doxygen 1.8.3.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  * Last modified:
12  * $Date: 2011-08-09 02:04:53 +1000 (Tue, 09 Aug 2011) $ by $Author: schulte $
13  * $Revision: 12253 $
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>
111  AbsBnd<View>::AbsBnd(Space& home, bool share, AbsBnd<View>& p)
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  template<class View>
137  AbsDom<View>::AbsDom(Home home, View x0, View x1)
138  : BinaryPropagator<View,PC_INT_DOM>(home,x0,x1) {}
139 
140  template<class View>
141  ExecStatus
142  AbsDom<View>::post(Home home, View x0, View x1) {
143  if (x0.min() >= 0) {
144  return Rel::EqDom<View,View>::post(home,x0,x1);
145  } else if (x0.max() <= 0) {
146  return Rel::EqDom<MinusView,View>::post(home,MinusView(x0),x1);
147  } else {
148  assert(!x0.assigned());
149  GECODE_ME_CHECK(x1.gq(home,0));
150  if (x1.assigned()) {
151  int mp[2] = {-x1.val(),x1.val()};
152  Iter::Values::Array i(mp,2);
153  GECODE_ME_CHECK(x0.inter_v(home,i,false));
154  } else if (!same(x0,x1)) {
155  GECODE_ME_CHECK(x1.lq(home,std::max(-x0.min(),x0.max())));
156  (void) new (home) AbsDom<View>(home,x0,x1);
157  }
158  }
159  return ES_OK;
160  }
161 
162  template<class View>
164  AbsDom<View>::AbsDom(Space& home, bool share, AbsDom<View>& p)
165  : BinaryPropagator<View,PC_INT_DOM>(home,share,p) {}
166 
167  template<class View>
168  Actor*
169  AbsDom<View>::copy(Space& home,bool share) {
170  return new (home) AbsDom<View>(home,share,*this);
171  }
172 
173  template<class View>
174  PropCost
175  AbsDom<View>::cost(const Space&, const ModEventDelta& med) const {
176  if (View::me(med) == ME_INT_VAL)
178  else
179  return PropCost::binary((View::me(med) == ME_INT_DOM) ?
181  }
182 
183  template<class View>
184  ExecStatus
186  if (View::me(med) != ME_INT_DOM) {
187  GECODE_ES_CHECK((prop_abs_bnd<View,Rel::EqDom>(home, *this, x0, x1)));
188  return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
189  }
190 
191  Region r(home);
192 
193  {
194  ViewRanges<View> i(x0), j(x0);
195 
196  using namespace Iter::Ranges;
197  Positive<ViewRanges<View> > p(i);
198  Negative<ViewRanges<View> > n(j);
199 
200  Minus m(r,n);
201 
202  Union<Positive<ViewRanges<View> >,Minus> u(p,m);
203 
204  GECODE_ME_CHECK(x1.inter_r(home,u,false));
205 
206  }
207 
208  {
209  ViewRanges<View> i(x1), j(x1);
210 
211  using namespace Iter::Ranges;
212  Minus m(r,j);
213 
214  Union<ViewRanges<View>,Minus> u(i,m);
215 
216  GECODE_ME_CHECK(x0.inter_r(home,u,false));
217  }
218 
219  if (x1.assigned())
220  return home.ES_SUBSUMED(*this);
221 
222  if (x0.min() >= 0)
223  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x1)));
224 
225  if (x0.max() <= 0) {
226  MinusView mx0(x0);
227  GECODE_REWRITE(*this,(Rel::EqDom<MinusView,View>::post(home(*this),mx0,x1)));
228  }
229 
230  return ES_FIX;
231  }
232 
233 }}}
234 
235 // STATISTICS: int-prop
236