Generated on Fri Jul 13 2018 06:08:22 for Gecode by doxygen 1.8.14
min-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  * Vincent Barichard <Vincent.Barichard@univ-angers.fr>
6  *
7  * Copyright:
8  * Christian Schulte, 2004
9  * Vincent Barichard, 2012
10  *
11  * Last modified:
12  * $Date: 2017-04-10 13:21:37 +0200 (Mon, 10 Apr 2017) $ by $Author: schulte $
13  * $Revision: 15631 $
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 <cmath>
41 
42 namespace Gecode { namespace Float { namespace Arithmetic {
43 
44  /*
45  * Bounds consistent min propagator
46  *
47  */
48  template<class A, class B, class C>
50  Min<A,B,C>::Min(Home home, A x0, B x1, C x2)
52 
53  template<class A, class B, class C>
55  Min<A,B,C>::Min(Space& home, bool share, Min<A,B,C>& p)
57 
58  template<class A, class B, class C>
60  Min<A,B,C>::Min(Space& home, bool share, Propagator& p,
61  A x0, B x1, C x2)
62  : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,share,p,x0,x1,x2) {}
63 
64  template<class A, class B, class C>
65  Actor*
66  Min<A,B,C>::copy(Space& home, bool share) {
67  return new (home) Min<A,B,C>(home,share,*this);
68  }
69 
70  template<class A, class B, class C>
72  Min<A,B,C>::post(Home home, A x0, B x1, C x2) {
73  (void) new (home) Min<A,B,C>(home,x0,x1,x2);
74  return ES_OK;
75  }
76 
77  template<class A, class B, class C>
80  GECODE_ME_CHECK(x2.eq(home,min(x0.domain(),x1.domain())));
81  GECODE_ME_CHECK(x0.gq(home,x2.min()));
82  GECODE_ME_CHECK(x1.gq(home,x2.min()));
83  if (same(x0,x1)) {
84  GECODE_ME_CHECK(x0.lq(home,x2.max()));
85  } else {
86  if (!overlap(x1.val(),x2.val())) GECODE_ME_CHECK(x0.lq(home,x2.max()));
87  if (!overlap(x0.val(),x2.val())) GECODE_ME_CHECK(x1.lq(home,x2.max()));
88  }
89  return (x0.assigned() && x1.assigned()) ? home.ES_SUBSUMED(*this) : ES_FIX;
90  }
91 
92  /*
93  * Bounds consistent max propagator
94  *
95  */
96 
97  template<class A, class B, class C>
99  Max<A,B,C>::Max(Home home, A x0, B x1, C x2)
101 
102  template<class A, class B, class C>
104  Max<A,B,C>::Max(Space& home, bool share, Max<A,B,C>& p)
106 
107  template<class A, class B, class C>
109  Max<A,B,C>::Max(Space& home, bool share, Propagator& p,
110  A x0, B x1, C x2)
111  : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,share,p,x0,x1,x2) {}
112 
113  template<class A, class B, class C>
114  Actor*
115  Max<A,B,C>::copy(Space& home, bool share) {
116  return new (home) Max<A,B,C>(home,share,*this);
117  }
118 
119  template<class A, class B, class C>
120  ExecStatus
121  Max<A,B,C>::post(Home home, A x0, B x1, C x2) {
122  (void) new (home) Max<A,B,C>(home,x0,x1,x2);
123  return ES_OK;
124  }
125 
126  template<class A, class B, class C>
127  ExecStatus
129  GECODE_ME_CHECK(x2.eq(home,max(x0.domain(),x1.domain())));
130  GECODE_ME_CHECK(x0.lq(home,x2.max()));
131  GECODE_ME_CHECK(x1.lq(home,x2.max()));
132  if (same(x0,x1)) {
133  GECODE_ME_CHECK(x0.gq(home,x2.min()));
134  } else {
135  if (!overlap(x1.val(),x2.val())) GECODE_ME_CHECK(x0.gq(home,x2.min()));
136  if (!overlap(x0.val(),x2.val())) GECODE_ME_CHECK(x1.gq(home,x2.min()));
137  }
138  return (x0.assigned() && x1.assigned()) ? home.ES_SUBSUMED(*this) : ES_FIX;
139  }
140 
141  /*
142  * Nary bounds consistent maximum
143  *
144  */
145 
146  template<class View>
149  : NaryOnePropagator<View,PC_FLOAT_BND>(home,x,y) {}
150 
151  template<class View>
152  ExecStatus
154  assert(x.size() > 0);
155  x.unique(home);
156  if (x.size() == 1)
157  return Rel::Eq<View,View>::post(home,x[0],y);
158  if (x.size() == 2)
159  return Max<View,View,View>::post(home,x[0],x[1],y);
162  for (int i=x.size(); i--; ) {
163  l = std::max(l,x[i].min());
164  u = std::max(u,x[i].max());
165  }
166  GECODE_ME_CHECK(y.gq(home,l));
167  GECODE_ME_CHECK(y.lq(home,u));
168  if (x.same(home,y)) {
169  // Check whether y occurs in x
170  for (int i=x.size(); i--; )
172  } else {
173  (void) new (home) NaryMax<View>(home,x,y);
174  }
175  return ES_OK;
176  }
177 
178  template<class View>
181  : NaryOnePropagator<View,PC_FLOAT_BND>(home,share,p) {}
182 
183  template<class View>
184  Actor*
185  NaryMax<View>::copy(Space& home, bool share) {
186  if (x.size() == 1)
187  return new (home) Rel::Eq<View,View>(home,share,*this,x[0],y);
188  if (x.size() == 2)
189  return new (home) Max<View,View,View>(home,share,*this,x[0],x[1],y);
190  return new (home) NaryMax<View>(home,share,*this);
191  }
192 
195  MPS_ASSIGNED = 1<<0,
196  MPS_REMOVED = 1<<1,
198  };
199 
200  template<class View>
203  ViewArray<View>& x, View y, PropCond pc) {
204  rerun:
205  assert(x.size() > 0);
206  FloatNum maxmax = x[x.size()-1].max();
207  FloatNum maxmin = x[x.size()-1].min();
208  for (int i = x.size()-1; i--; ) {
209  maxmax = std::max(x[i].max(),maxmax);
210  maxmin = std::max(x[i].min(),maxmin);
211  }
212  GECODE_ME_CHECK(y.lq(home,maxmax));
213  GECODE_ME_CHECK(y.gq(home,maxmin));
214  maxmin = y.min();
215  maxmax = y.max();
216  int status = MPS_ASSIGNED;
217  for (int i = x.size(); i--; ) {
218  ModEvent me = x[i].lq(home,maxmax);
219  if (me == ME_FLOAT_FAILED)
220  return ES_FAILED;
221  if (me_modified(me) && (x[i].max() != maxmax))
222  status |= MPS_NEW_BOUND;
223  if (x[i].max() < maxmin) {
224  x.move_lst(i,home,p,pc);
225  status |= MPS_REMOVED;
226  } else if (!x[i].assigned())
227  status &= ~MPS_ASSIGNED;
228  }
229  if (x.size() == 0)
230  return ES_FAILED;
231  if ((status & MPS_REMOVED) != 0)
232  goto rerun;
233  if (((status & MPS_ASSIGNED) != 0) && y.assigned())
234  return home.ES_SUBSUMED(p);
235  return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
236  }
237 
238  template<class View>
239  ExecStatus
241  return prop_nary_max(home,*this,x,y,PC_FLOAT_BND);
242  }
243 
244 }}}
245 
246 // STATISTICS: float-prop
247 
static ExecStatus post(Home home, ViewArray< View > &x, View y)
Post propagator .
Definition: min-max.hpp:153
Propagator for bounds consistent max operator
Definition: arithmetic.hh:360
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Max(Space &home, bool share, Max &p)
Constructor for cloning p.
Definition: min-max.hpp:104
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:123
bool overlap(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:502
Binary bounds consistent equality propagator.
Definition: rel.hh:70
int ModEvent
Type for modification events.
Definition: core.hpp:142
Base-class for propagators.
Definition: core.hpp:1092
const Gecode::ModEvent ME_FLOAT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:260
Telling has found a new upper bound.
Definition: min-max.hpp:197
Propagation has computed fixpoint.
Definition: core.hpp:545
Computation spaces.
Definition: core.hpp:1748
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: min-max.hpp:185
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: min-max.hpp:115
Base-class for both propagators and branchers.
Definition: core.hpp:696
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
bool same(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether two views are the same.
Definition: view.hpp:643
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
Execution has resulted in failure.
Definition: core.hpp:542
MaxPropStatus
Status of propagation for nary max.
Definition: min-max.hpp:194
Mixed ternary propagator.
Definition: propagator.hpp:247
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
All views are assigned.
Definition: min-max.hpp:195
(n+1)-ary propagator
Definition: propagator.hpp:180
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: min-max.hpp:79
View arrays.
Definition: array.hpp:234
static ExecStatus post(Home home, A x0, B x1, C x2)
Post propagator for .
Definition: min-max.hpp:72
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Less or equal propagator.
Definition: rel.hh:245
static ExecStatus post(Home home, A x0, B x1, C x2)
Post propagator for .
Definition: min-max.hpp:121
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
bool same(const VarImpVar< VarImp > &y) const
Test whether variable is the same as y.
Definition: var.hpp:133
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: min-max.hpp:128
ExecStatus
Definition: core.hpp:540
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: min-max.hpp:66
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:173
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: min-max.hpp:240
NaryMax(Space &home, bool share, NaryMax &p)
Constructor for cloning p.
Definition: min-max.hpp:180
Post propagator for SetVar x
Definition: set.hh:784
Execution is okay.
Definition: core.hpp:544
Propagation has not computed fixpoint.
Definition: core.hpp:543
ExecStatus prop_nary_max(Space &home, Propagator &p, ViewArray< View > &x, View y, PropCond pc)
Definition: min-max.hpp:202
const Gecode::PropCond PC_FLOAT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:292
Gecode toplevel namespace
Bounds consistent n-ary maximum propagator.
Definition: arithmetic.hh:387
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
Propagator for bounds consistent min operator
Definition: arithmetic.hh:331
double FloatNum
Floating point number base type.
Definition: float.hh:110
Min(Space &home, bool share, Min &p)
Constructor for cloning p.
Definition: min-max.hpp:55