Generated on Fri Aug 31 2012 16:20:48 for Gecode by doxygen 1.8.1.2
max.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  *
6  * Copyright:
7  * Christian Schulte, 2004
8  *
9  * Last modified:
10  * $Date: 2011-08-09 02:04:53 +1000 (Tue, 09 Aug 2011) $ by $Author: schulte $
11  * $Revision: 12253 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/int/rel.hh>
39 
40 namespace Gecode { namespace Int { namespace Arithmetic {
41 
42  /*
43  * Ternary bounds consistent maximum
44  *
45  */
46 
47  template<class View>
49  prop_max_bnd(Space& home, View x0, View x1, View x2) {
50  bool mod = false;
51  do {
52  mod = false;
53  {
54  ModEvent me = x2.lq(home,std::max(x0.max(),x1.max()));
55  if (me_failed(me)) return ES_FAILED;
56  mod |= me_modified(me);
57  }
58  {
59  ModEvent me = x2.gq(home,std::max(x0.min(),x1.min()));
60  if (me_failed(me)) return ES_FAILED;
61  mod |= me_modified(me);
62  }
63  {
64  ModEvent me = x0.lq(home,x2.max());
65  if (me_failed(me)) return ES_FAILED;
66  mod |= me_modified(me);
67  }
68  {
69  ModEvent me = x1.lq(home,x2.max());
70  if (me_failed(me)) return ES_FAILED;
71  mod |= me_modified(me);
72  }
73  } while (mod);
74  return ES_OK;
75  }
76 
77  template<class View>
79  MaxBnd<View>::MaxBnd(Home home, View x0, View x1, View x2)
80  : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
81 
82  template<class View>
84  MaxBnd<View>::post(Home home, View x0, View x1, View x2) {
85  GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
86  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
87  if (same(x0,x1))
88  return Rel::EqBnd<View,View>::post(home,x0,x2);
89  if (same(x0,x2))
90  return Rel::Lq<View>::post(home,x1,x2);
91  if (same(x1,x2))
92  return Rel::Lq<View>::post(home,x0,x2);
93  (void) new (home) MaxBnd<View>(home,x0,x1,x2);
94  return ES_OK;
95  }
96 
97  template<class View>
99  MaxBnd<View>::MaxBnd(Space& home, bool share, MaxBnd<View>& p)
100  : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
101 
102  template<class View>
104  MaxBnd<View>::MaxBnd(Space& home, bool share, Propagator& p,
105  View x0, View x1, View x2)
106  : TernaryPropagator<View,PC_INT_BND>(home,share,p,x0,x1,x2) {}
107 
108  template<class View>
109  Actor*
110  MaxBnd<View>::copy(Space& home, bool share) {
111  return new (home) MaxBnd<View>(home,share,*this);
112  }
113 
114  template<class View>
115  ExecStatus
117  GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2));
118  if ((x0.max() <= x1.min()) || (x0.max() < x2.min()))
119  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x1,x2)));
120  if ((x1.max() <= x0.min()) || (x1.max() < x2.min()))
121  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x0,x2)));
122  return x0.assigned() && x1.assigned() && x2.assigned() ?
123  home.ES_SUBSUMED(*this) : ES_FIX;
124  }
125 
126  /*
127  * Nary bounds consistent maximum
128  *
129  */
130 
131  template<class View>
134  : NaryOnePropagator<View,PC_INT_BND>(home,x,y) {}
135 
136  template<class View>
137  ExecStatus
139  assert(x.size() > 0);
140  x.unique(home);
141  if (x.size() == 1)
142  return Rel::EqBnd<View,View>::post(home,x[0],y);
143  if (x.size() == 2)
144  return MaxBnd<View>::post(home,x[0],x[1],y);
145  int l = Int::Limits::min;
146  int u = Int::Limits::min;
147  for (int i=x.size(); i--; ) {
148  l = std::max(l,x[i].min());
149  u = std::max(u,x[i].max());
150  }
151  GECODE_ME_CHECK(y.gq(home,l));
152  GECODE_ME_CHECK(y.lq(home,u));
153  if (x.same(home,y)) {
154  // Check whether y occurs in x
155  for (int i=x.size(); i--; )
157  } else {
158  (void) new (home) NaryMaxBnd<View>(home,x,y);
159  }
160  return ES_OK;
161  }
162 
163  template<class View>
166  : NaryOnePropagator<View,PC_INT_BND>(home,share,p) {}
167 
168  template<class View>
169  Actor*
170  NaryMaxBnd<View>::copy(Space& home, bool share) {
171  if (x.size() == 1)
172  return new (home) Rel::EqBnd<View,View>(home,share,*this,x[0],y);
173  if (x.size() == 2)
174  return new (home) MaxBnd<View>(home,share,*this,x[0],x[1],y);
175  return new (home) NaryMaxBnd<View>(home,share,*this);
176  }
177 
180  MPS_ASSIGNED = 1<<0,
181  MPS_REMOVED = 1<<1,
183  };
184 
185  template<class View>
188  ViewArray<View>& x, View y, PropCond pc) {
189  rerun:
190  assert(x.size() > 0);
191  int maxmax = x[x.size()-1].max();
192  int maxmin = x[x.size()-1].min();
193  for (int i = x.size()-1; i--; ) {
194  maxmax = std::max(x[i].max(),maxmax);
195  maxmin = std::max(x[i].min(),maxmin);
196  }
197  GECODE_ME_CHECK(y.lq(home,maxmax));
198  GECODE_ME_CHECK(y.gq(home,maxmin));
199  maxmin = y.min();
200  maxmax = y.max();
201  int status = MPS_ASSIGNED;
202  for (int i = x.size(); i--; ) {
203  ModEvent me = x[i].lq(home,maxmax);
204  if (me == ME_INT_FAILED)
205  return ES_FAILED;
206  if (me_modified(me) && (x[i].max() != maxmax))
207  status |= MPS_NEW_BOUND;
208  if (x[i].max() < maxmin) {
209  x.move_lst(i,home,p,pc);
210  status |= MPS_REMOVED;
211  } else if (!x[i].assigned())
212  status &= ~MPS_ASSIGNED;
213  }
214  if (x.size() == 0)
215  return ES_FAILED;
216  if ((status & MPS_REMOVED) != 0)
217  goto rerun;
218  if (((status & MPS_ASSIGNED) != 0) && y.assigned())
219  return home.ES_SUBSUMED(p);
220  return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
221  }
222 
223  template<class View>
224  ExecStatus
226  return prop_nary_max_bnd(home,*this,x,y,PC_INT_BND);
227  }
228 
229 
230  /*
231  * Ternary domain consistent maximum
232  *
233  */
234 
235  template<class View>
237  MaxDom<View>::MaxDom(Home home, View x0, View x1, View x2)
238  : TernaryPropagator<View,PC_INT_DOM>(home,x0,x1,x2) {}
239 
240  template<class View>
241  ExecStatus
242  MaxDom<View>::post(Home home, View x0, View x1, View x2) {
243  GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
244  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
245  if (same(x0,x1))
246  return Rel::EqDom<View,View>::post(home,x0,x2);
247  if (same(x0,x2))
248  return Rel::Lq<View>::post(home,x1,x2);
249  if (same(x1,x2))
250  return Rel::Lq<View>::post(home,x0,x2);
251  (void) new (home) MaxDom<View>(home,x0,x1,x2);
252  return ES_OK;
253  }
254 
255  template<class View>
257  MaxDom<View>::MaxDom(Space& home, bool share, MaxDom<View>& p)
258  : TernaryPropagator<View,PC_INT_DOM>(home,share,p) {}
259 
260  template<class View>
262  MaxDom<View>::MaxDom(Space& home, bool share, Propagator& p,
263  View x0, View x1, View x2)
264  : TernaryPropagator<View,PC_INT_DOM>(home,share,p,x0,x1,x2) {}
265 
266  template<class View>
267  Actor*
268  MaxDom<View>::copy(Space& home, bool share) {
269  return new (home) MaxDom<View>(home,share,*this);
270  }
271 
272  template<class View>
273  PropCost
274  MaxDom<View>::cost(const Space&, const ModEventDelta& med) const {
275  return PropCost::ternary((View::me(med) == ME_INT_DOM) ?
277  }
278 
279  template<class View>
280  ExecStatus
282  if (View::me(med) != ME_INT_DOM) {
283  GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2));
284  if ((x0.max() <= x1.min()) || (x0.max() < x2.min()))
285  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2)));
286  if ((x1.max() <= x0.min()) || (x1.max() < x2.min()))
287  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2)));
288  return x0.assigned() && x1.assigned() && x2.assigned() ?
289  home.ES_SUBSUMED(*this) :
290  home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
291  }
292  ViewRanges<View> r0(x0), r1(x1);
294  GECODE_ME_CHECK(x2.inter_r(home,u,false));
295  if (rtest_nq_dom(x0,x2) == RT_TRUE) {
297  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2)));
298  }
299  if (rtest_nq_dom(x1,x2) == RT_TRUE) {
301  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2)));
302  }
303  return ES_FIX;
304  }
305 
306  /*
307  * Nary domain consistent maximum
308  *
309  */
310 
311  template<class View>
314  : NaryOnePropagator<View,PC_INT_DOM>(home,x,y) {}
315 
316  template<class View>
317  ExecStatus
319  assert(x.size() > 0);
320  x.unique(home);
321  if (x.size() == 1)
322  return Rel::EqDom<View,View>::post(home,x[0],y);
323  if (x.size() == 2)
324  return MaxDom<View>::post(home,x[0],x[1],y);
325  int l = Int::Limits::min;
326  int u = Int::Limits::min;
327  for (int i=x.size(); i--; ) {
328  l = std::max(l,x[i].min());
329  u = std::max(u,x[i].max());
330  }
331  GECODE_ME_CHECK(y.gq(home,l));
332  GECODE_ME_CHECK(y.lq(home,u));
333  if (x.same(home,y)) {
334  // Check whether y occurs in x
335  for (int i=x.size(); i--; )
337  } else {
338  (void) new (home) NaryMaxDom<View>(home,x,y);
339  }
340  return ES_OK;
341  }
342 
343  template<class View>
346  : NaryOnePropagator<View,PC_INT_DOM>(home,share,p) {}
347 
348  template<class View>
349  Actor*
350  NaryMaxDom<View>::copy(Space& home, bool share) {
351  if (x.size() == 1)
352  return new (home) Rel::EqDom<View,View>(home,share,*this,x[0],y);
353  if (x.size() == 2)
354  return new (home) MaxDom<View>(home,share,*this,x[0],x[1],y);
355  return new (home) NaryMaxDom<View>(home,share,*this);
356  }
357 
358  template<class View>
359  PropCost
360  NaryMaxDom<View>::cost(const Space&, const ModEventDelta& med) const {
361  if (View::me(med) == ME_INT_DOM)
362  return PropCost::linear(PropCost::HI, y.size());
363  else
364  return PropCost::linear(PropCost::LO, x.size());
365  }
366 
367  template<class View>
368  ExecStatus
370  if (View::me(med) != ME_INT_DOM) {
371  ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_DOM);
372  GECODE_ES_CHECK(es);
373  return (es == ES_FIX) ?
374  home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM)) :
375  home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
376  }
377  Region r(home);
378  ViewRanges<View>* i_x = r.alloc<ViewRanges<View> >(x.size());
379  for (int i = x.size(); i--; ) {
380  ViewRanges<View> i_xi(x[i]); i_x[i]=i_xi;
381  }
382  Iter::Ranges::NaryUnion u(r, i_x, x.size());
383  GECODE_ME_CHECK(y.inter_r(home,u,false));
384  for (int i = x.size(); i--; )
385  if (rtest_nq_dom(x[i],y) == RT_TRUE) {
386  GECODE_ES_CHECK(Rel::Lq<View>::post(home,x[i],y));
387  x.move_lst(i,home,*this,PC_INT_DOM);
388  }
389  assert(x.size() > 0);
390  if (x.size() == 1)
391  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x[0],y)));
392  return ES_FIX;
393  }
394 
395 }}}
396 
397 // STATISTICS: int-prop
398