Generated on Mon Jul 27 2020 00:00:00 for Gecode by doxygen 1.8.18
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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/int/rel.hh>
35 
36 namespace Gecode { namespace Int { namespace Arithmetic {
37 
38  /*
39  * Ternary bounds consistent maximum
40  *
41  */
42 
43  template<class View>
45  prop_max_bnd(Space& home, View x0, View x1, View x2) {
46  bool mod = false;
47  do {
48  mod = false;
49  {
50  ModEvent me = x2.lq(home,std::max(x0.max(),x1.max()));
51  if (me_failed(me)) return ES_FAILED;
52  mod |= me_modified(me);
53  }
54  {
55  ModEvent me = x2.gq(home,std::max(x0.min(),x1.min()));
56  if (me_failed(me)) return ES_FAILED;
57  mod |= me_modified(me);
58  }
59  {
60  ModEvent me = x0.lq(home,x2.max());
61  if (me_failed(me)) return ES_FAILED;
62  mod |= me_modified(me);
63  }
64  {
65  ModEvent me = x1.lq(home,x2.max());
66  if (me_failed(me)) return ES_FAILED;
67  mod |= me_modified(me);
68  }
69  } while (mod);
70  return ES_OK;
71  }
72 
73  template<class View>
75  MaxBnd<View>::MaxBnd(Home home, View x0, View x1, View x2)
76  : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
77 
78  template<class View>
80  MaxBnd<View>::post(Home home, View x0, View x1, View x2) {
81  GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
82  GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
83  if (x0 == x1)
84  return Rel::EqBnd<View,View>::post(home,x0,x2);
85  if (x0 == x2)
86  return Rel::Lq<View,View>::post(home,x1,x2);
87  if (x1 == x2)
88  return Rel::Lq<View,View>::post(home,x0,x2);
89  (void) new (home) MaxBnd<View>(home,x0,x1,x2);
90  return ES_OK;
91  }
92 
93  template<class View>
96  : TernaryPropagator<View,PC_INT_BND>(home,p) {}
97 
98  template<class View>
101  View x0, View x1, View x2)
102  : TernaryPropagator<View,PC_INT_BND>(home,p,x0,x1,x2) {}
103 
104  template<class View>
105  Actor*
107  return new (home) MaxBnd<View>(home,*this);
108  }
109 
110  template<class View>
111  ExecStatus
113  GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2));
114  if ((x0.max() <= x1.min()) || (x0.max() < x2.min()))
115  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x1,x2)));
116  if ((x1.max() <= x0.min()) || (x1.max() < x2.min()))
117  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x0,x2)));
118  return x0.assigned() && x1.assigned() && x2.assigned() ?
119  home.ES_SUBSUMED(*this) : ES_FIX;
120  }
121 
122  /*
123  * Nary bounds consistent maximum
124  *
125  */
126 
127  template<class View>
130  : NaryOnePropagator<View,PC_INT_BND>(home,x,y) {}
131 
132  template<class View>
133  ExecStatus
135  assert(x.size() > 0);
136  x.unique();
137  if (x.size() == 1)
138  return Rel::EqBnd<View,View>::post(home,x[0],y);
139  if (x.size() == 2)
140  return MaxBnd<View>::post(home,x[0],x[1],y);
141  int l = x[0].min();
142  int u = x[0].max();
143  for (int i=1; i<x.size(); i++) {
144  l = std::max(l,x[i].min());
145  u = std::max(u,x[i].max());
146  }
147  GECODE_ME_CHECK(y.gq(home,l));
148  GECODE_ME_CHECK(y.lq(home,u));
149  if (x.same(y)) {
150  // Check whether y occurs in x
151  for (int i=0; i<x.size(); i++)
153  } else {
154  (void) new (home) NaryMaxBnd<View>(home,x,y);
155  }
156  return ES_OK;
157  }
158 
159  template<class View>
162  : NaryOnePropagator<View,PC_INT_BND>(home,p) {}
163 
164  template<class View>
165  Actor*
167  if (x.size() == 1)
168  return new (home) Rel::EqBnd<View,View>(home,*this,x[0],y);
169  if (x.size() == 2)
170  return new (home) MaxBnd<View>(home,*this,x[0],x[1],y);
171  return new (home) NaryMaxBnd<View>(home,*this);
172  }
173 
176  MPS_ASSIGNED = 1<<0,
177  MPS_REMOVED = 1<<1,
178  MPS_NEW_BOUND = 1<<2
179  };
180 
181  template<class View>
184  ViewArray<View>& x, View y, PropCond pc) {
185  rerun:
186  assert(x.size() > 0);
187  int maxmax = x[0].max();
188  int maxmin = x[0].min();
189  for (int i=1; i<x.size(); i++) {
190  maxmax = std::max(x[i].max(),maxmax);
191  maxmin = std::max(x[i].min(),maxmin);
192  }
193  GECODE_ME_CHECK(y.lq(home,maxmax));
194  GECODE_ME_CHECK(y.gq(home,maxmin));
195  maxmin = y.min();
196  maxmax = y.max();
197  int status = MPS_ASSIGNED;
198  for (int i=x.size(); i--; ) {
199  ModEvent me = x[i].lq(home,maxmax);
200  if (me == ME_INT_FAILED)
201  return ES_FAILED;
202  if (me_modified(me) && (x[i].max() != maxmax))
203  status |= MPS_NEW_BOUND;
204  if (x[i].max() < maxmin) {
205  x.move_lst(i,home,p,pc);
206  status |= MPS_REMOVED;
207  } else if (!x[i].assigned())
208  status &= ~MPS_ASSIGNED;
209  }
210  if (x.size() == 0)
211  return ES_FAILED;
212  if ((status & MPS_REMOVED) != 0)
213  goto rerun;
214  if (((status & MPS_ASSIGNED) != 0) && y.assigned())
215  return home.ES_SUBSUMED(p);
216  return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
217  }
218 
219  template<class View>
220  ExecStatus
222  ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_BND);
223  GECODE_ES_CHECK(es);
224  if (x.size() == 1)
225  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x[0],y)));
226  return es;
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 (x0 == x1)
246  return Rel::EqDom<View,View>::post(home,x0,x2);
247  if (x0 == x2)
248  return Rel::Lq<View,View>::post(home,x1,x2);
249  if (x1 == x2)
250  return Rel::Lq<View,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>
258  : TernaryPropagator<View,PC_INT_DOM>(home,p) {}
259 
260  template<class View>
263  View x0, View x1, View x2)
264  : TernaryPropagator<View,PC_INT_DOM>(home,p,x0,x1,x2) {}
265 
266  template<class View>
267  Actor*
269  return new (home) MaxDom<View>(home,*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();
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 = x[0].min();
326  int u = x[0].max();
327  for (int i=0; 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(y)) {
334  // Check whether y occurs in x
335  for (int i=0; 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,p) {}
347 
348  template<class View>
349  Actor*
351  if (x.size() == 1)
352  return new (home) Rel::EqDom<View,View>(home,*this,x[0],y);
353  if (x.size() == 2)
354  return new (home) MaxDom<View>(home,*this,x[0],x[1],y);
355  return new (home) NaryMaxDom<View>(home,*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;
378  ViewRanges<View>* i_x = r.alloc<ViewRanges<View> >(x.size());
379  for (int i=0; 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) {
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 
Post propagator for SetVar x
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Less or equal propagator.
Definition: rel.hh:493
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: max.hpp:106
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: max.hpp:281
MaxPropStatus
Status of propagation for nary max.
Definition: max.hpp:175
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
@ LO
Cheap.
Definition: core.hpp:513
ExecStatus prop_nary_max_bnd(Space &home, Propagator &p, ViewArray< View > &x, View y, PropCond pc)
Definition: max.hpp:183
static ExecStatus post(Home home, View0 x0, View1 x1)
Post domain consistent propagator .
Definition: eq.hpp:176
Computation spaces.
Definition: core.hpp:1742
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4796
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:3576
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: max.hpp:166
Base-class for both propagators and branchers.
Definition: core.hpp:628
@ RT_TRUE
Relation does hold.
Definition: view.hpp:1737
static ExecStatus post(Home home, V0 x0, V1 x1)
Post propagator .
Definition: lq-le.hpp:50
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:111
static ExecStatus post(Home home, ViewArray< View > &x, View y)
Post propagator .
Definition: max.hpp:134
@ MPS_ASSIGNED
All views are assigned.
Definition: max.hpp:176
static ExecStatus post(Home home, View x0, View x1, View x2)
Post propagator .
Definition: max.hpp:80
RelTest rtest_nq_dom(VX x, VY y)
Test whether views x and y are different (use full domain information)
Definition: rel-test.hpp:126
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
static ExecStatus post(Home home, View x0, View x1, View x2)
Post propagator .
Definition: max.hpp:242
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
Range iterator for integer views.
Definition: view.hpp:54
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
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
Home class for posting propagators
Definition: core.hpp:856
@ MPS_NEW_BOUND
Telling has found a new upper bound.
Definition: max.hpp:178
Ternary propagator.
Definition: pattern.hpp:113
Domain consistent n-ary maximum propagator.
Definition: arithmetic.hh:219
Bounds consistent ternary maximum propagator.
Definition: arithmetic.hh:131
(n+1)-ary propagator
Definition: pattern.hpp:172
Handle to region.
Definition: region.hpp:55
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: max.hpp:369
@ MPS_REMOVED
A view is removed.
Definition: max.hpp:177
MaxDom(Space &home, MaxDom &p)
Constructor for cloning p.
Definition: max.hpp:257
Domain consistent ternary maximum propagator.
Definition: arithmetic.hh:184
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: max.hpp:268
Range iterator for union of iterators.
MaxBnd(Space &home, MaxBnd &p)
Constructor for cloning p.
Definition: max.hpp:95
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
NaryMaxBnd(Space &home, NaryMaxBnd &p)
Constructor for cloning p.
Definition: max.hpp:161
int ModEvent
Type for modification events.
Definition: core.hpp:62
Range iterator for computing union (binary)
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
static ExecStatus post(Home home, ViewArray< View > &x, View y)
Post propagator .
Definition: max.hpp:318
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4805
Propagation cost.
Definition: core.hpp:486
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntPropLevel ipl)
Post propagator for .
Definition: arithmetic.cpp:360
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
Binary bounds consistent equality propagator.
Definition: rel.hh:134
#define forceinline
Definition: config.hpp:185
ExecStatus prop_max_bnd(Space &home, View x0, View x1, View x2)
Definition: max.hpp:45
Bounds consistent n-ary maximum propagator.
Definition: arithmetic.hh:159
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: max.hpp:221
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
@ HI
Expensive.
Definition: core.hpp:514
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: max.hpp:350
View arrays.
Definition: array.hpp:253
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: max.hpp:360
NaryMaxDom(Space &home, NaryMaxDom &p)
Constructor for cloning p.
Definition: max.hpp:345
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:3569
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475
Gecode::IntArgs i({1, 2, 3, 4})
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:116
@ ES_OK
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: max.hpp:274
ExecStatus
Definition: core.hpp:472
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: max.hpp:112