Generated on Sat Feb 7 2015 02:01:19 for Gecode by doxygen 1.8.9.1
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: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13068 $
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>
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  ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_BND);
227  GECODE_ES_CHECK(es);
228  if (x.size() == 1)
229  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x[0],y)));
230  return es;
231  }
232 
233 
234  /*
235  * Ternary domain consistent maximum
236  *
237  */
238 
239  template<class View>
241  MaxDom<View>::MaxDom(Home home, View x0, View x1, View x2)
242  : TernaryPropagator<View,PC_INT_DOM>(home,x0,x1,x2) {}
243 
244  template<class View>
245  ExecStatus
246  MaxDom<View>::post(Home home, View x0, View x1, View x2) {
247  GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
248  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
249  if (same(x0,x1))
250  return Rel::EqDom<View,View>::post(home,x0,x2);
251  if (same(x0,x2))
252  return Rel::Lq<View>::post(home,x1,x2);
253  if (same(x1,x2))
254  return Rel::Lq<View>::post(home,x0,x2);
255  (void) new (home) MaxDom<View>(home,x0,x1,x2);
256  return ES_OK;
257  }
258 
259  template<class View>
262  : TernaryPropagator<View,PC_INT_DOM>(home,share,p) {}
263 
264  template<class View>
266  MaxDom<View>::MaxDom(Space& home, bool share, Propagator& p,
267  View x0, View x1, View x2)
268  : TernaryPropagator<View,PC_INT_DOM>(home,share,p,x0,x1,x2) {}
269 
270  template<class View>
271  Actor*
272  MaxDom<View>::copy(Space& home, bool share) {
273  return new (home) MaxDom<View>(home,share,*this);
274  }
275 
276  template<class View>
277  PropCost
278  MaxDom<View>::cost(const Space&, const ModEventDelta& med) const {
279  return PropCost::ternary((View::me(med) == ME_INT_DOM) ?
281  }
282 
283  template<class View>
284  ExecStatus
286  if (View::me(med) != ME_INT_DOM) {
287  GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2));
288  if ((x0.max() <= x1.min()) || (x0.max() < x2.min()))
289  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2)));
290  if ((x1.max() <= x0.min()) || (x1.max() < x2.min()))
291  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2)));
292  return x0.assigned() && x1.assigned() && x2.assigned() ?
293  home.ES_SUBSUMED(*this) :
294  home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
295  }
296  ViewRanges<View> r0(x0), r1(x1);
298  GECODE_ME_CHECK(x2.inter_r(home,u,false));
299  if (rtest_nq_dom(x0,x2) == RT_TRUE) {
301  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2)));
302  }
303  if (rtest_nq_dom(x1,x2) == RT_TRUE) {
305  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2)));
306  }
307  return ES_FIX;
308  }
309 
310  /*
311  * Nary domain consistent maximum
312  *
313  */
314 
315  template<class View>
318  : NaryOnePropagator<View,PC_INT_DOM>(home,x,y) {}
319 
320  template<class View>
321  ExecStatus
323  assert(x.size() > 0);
324  x.unique(home);
325  if (x.size() == 1)
326  return Rel::EqDom<View,View>::post(home,x[0],y);
327  if (x.size() == 2)
328  return MaxDom<View>::post(home,x[0],x[1],y);
329  int l = Int::Limits::min;
330  int u = Int::Limits::min;
331  for (int i=x.size(); i--; ) {
332  l = std::max(l,x[i].min());
333  u = std::max(u,x[i].max());
334  }
335  GECODE_ME_CHECK(y.gq(home,l));
336  GECODE_ME_CHECK(y.lq(home,u));
337  if (x.same(home,y)) {
338  // Check whether y occurs in x
339  for (int i=x.size(); i--; )
341  } else {
342  (void) new (home) NaryMaxDom<View>(home,x,y);
343  }
344  return ES_OK;
345  }
346 
347  template<class View>
350  : NaryOnePropagator<View,PC_INT_DOM>(home,share,p) {}
351 
352  template<class View>
353  Actor*
354  NaryMaxDom<View>::copy(Space& home, bool share) {
355  if (x.size() == 1)
356  return new (home) Rel::EqDom<View,View>(home,share,*this,x[0],y);
357  if (x.size() == 2)
358  return new (home) MaxDom<View>(home,share,*this,x[0],x[1],y);
359  return new (home) NaryMaxDom<View>(home,share,*this);
360  }
361 
362  template<class View>
363  PropCost
364  NaryMaxDom<View>::cost(const Space&, const ModEventDelta& med) const {
365  if (View::me(med) == ME_INT_DOM)
366  return PropCost::linear(PropCost::HI, y.size());
367  else
368  return PropCost::linear(PropCost::LO, x.size());
369  }
370 
371  template<class View>
372  ExecStatus
374  if (View::me(med) != ME_INT_DOM) {
375  ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_DOM);
376  GECODE_ES_CHECK(es);
377  return (es == ES_FIX) ?
378  home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM)) :
379  home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
380  }
381  Region r(home);
382  ViewRanges<View>* i_x = r.alloc<ViewRanges<View> >(x.size());
383  for (int i = x.size(); i--; ) {
384  ViewRanges<View> i_xi(x[i]); i_x[i]=i_xi;
385  }
386  Iter::Ranges::NaryUnion u(r, i_x, x.size());
387  GECODE_ME_CHECK(y.inter_r(home,u,false));
388  for (int i = x.size(); i--; )
389  if (rtest_nq_dom(x[i],y) == RT_TRUE) {
391  x.move_lst(i,home,*this,PC_INT_DOM);
392  }
393  assert(x.size() > 0);
394  if (x.size() == 1)
395  GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x[0],y)));
396  return ES_FIX;
397  }
398 
399 }}}
400 
401 // STATISTICS: int-prop
402 
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: max.hpp:354
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:109
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntConLevel icl)
Post propagator for .
Definition: arithmetic.cpp:213
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4041
Binary domain consistent equality propagator.
Definition: rel.hh:71
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
Domain consistent ternary maximum propagator.
Definition: arithmetic.hh:188
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
MaxPropStatus
Status of propagation for nary max.
Definition: max.hpp:179
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:2986
Domain consistent n-ary maximum propagator.
Definition: arithmetic.hh:223
NaryMaxBnd(Space &home, bool share, NaryMaxBnd &p)
Constructor for cloning p.
Definition: max.hpp:165
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: max.hpp:364
int ModEvent
Type for modification events.
Definition: core.hpp:146
Base-class for propagators.
Definition: core.hpp:755
Expensive.
Definition: core.hpp:564
Handle to region.
Definition: region.hpp:61
Propagation has computed fixpoint.
Definition: core.hpp:528
void unique(const Space &home)
Remove all duplicate views from array (changes element order)
Definition: array.hpp:1498
Computation spaces.
Definition: core.hpp:1362
const int min
Smallest allowed integer value.
Definition: int.hh:115
Base-class for both propagators and branchers.
Definition: core.hpp:666
Range iterator for integer views.
Definition: view.hpp:54
static ExecStatus post(Home home, ViewArray< View > &x, View y)
Post propagator .
Definition: max.hpp:138
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
bool same(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:389
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
Execution has resulted in failure.
Definition: core.hpp:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
Range iterator for union of iterators.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: max.hpp:373
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: max.hpp:110
Binary bounds consistent equality propagator.
Definition: rel.hh:107
Less or equal propagator.
Definition: rel.hh:465
RelTest rtest_nq_dom(View x, View y)
Test whether views x and y are different (use full domain information)
Definition: rel-test.hpp:128
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
static ExecStatus post(Home home, View x0, View x1, View x2)
Post propagator .
Definition: max.hpp:246
Ternary propagator.
Definition: propagator.hpp:115
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:766
(n+1)-ary propagator
Definition: propagator.hpp:172
Bounds consistent n-ary maximum propagator.
Definition: arithmetic.hh:163
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: max.hpp:278
View arrays.
Definition: array.hpp:234
ExecStatus prop_max_bnd(Space &home, View x0, View x1, View x2)
Definition: max.hpp:49
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: max.hpp:116
ExecStatus prop_nary_max_bnd(Space &home, Propagator &p, ViewArray< View > &x, View y, PropCond pc)
Definition: max.hpp:187
All views are assigned.
Definition: max.hpp:180
MaxDom(Space &home, bool share, MaxDom &p)
Constructor for cloning p.
Definition: max.hpp:261
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:2979
void move_lst(int i)
Move view from position size()-1 to position i (truncate array by one)
Definition: array.hpp:1295
Range iterator for computing union (binary)
MaxBnd(Space &home, bool share, MaxBnd &p)
Constructor for cloning p.
Definition: max.hpp:99
static ExecStatus post(Home home, ViewArray< View > &x, View y)
Post propagator .
Definition: max.hpp:322
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Propagation cost.
Definition: core.hpp:537
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
ExecStatus
Definition: core.hpp:523
Bounds consistent ternary maximum propagator.
Definition: arithmetic.hh:135
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: max.hpp:285
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
static ExecStatus post(Home home, View x0, View x1, View x2)
Post propagator .
Definition: max.hpp:84
#define forceinline
Definition: config.hpp:132
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
bool same(const Space &home) const
Test whether array has multiple occurence of the same view.
Definition: array.hpp:1468
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: max.hpp:170
Execution is okay.
Definition: core.hpp:527
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: max.hpp:225
Propagation has not computed fixpoint.
Definition: core.hpp:526
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: max.hpp:272
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4050
Gecode toplevel namespace
NaryMaxDom(Space &home, bool share, NaryMaxDom &p)
Constructor for cloning p.
Definition: max.hpp:349
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
Telling has found a new upper bound.
Definition: max.hpp:182
Relation does hold.
Definition: view.hpp:1617
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58