Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
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  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 #include <cmath>
37 
38 namespace Gecode { namespace Float { namespace Arithmetic {
39 
40  /*
41  * Bounds consistent min propagator
42  *
43  */
44  template<class A, class B, class C>
46  Min<A,B,C>::Min(Home home, A x0, B x1, C x2)
48 
49  template<class A, class B, class C>
53 
54  template<class A, class B, class C>
57  A x0, B x1, C x2)
58  : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,p,x0,x1,x2) {}
59 
60  template<class A, class B, class C>
61  Actor*
63  return new (home) Min<A,B,C>(home,*this);
64  }
65 
66  template<class A, class B, class C>
68  Min<A,B,C>::post(Home home, A x0, B x1, C x2) {
69  GECODE_ME_CHECK(x2.eq(home,min(x0.domain(),x1.domain())));
70  GECODE_ME_CHECK(x0.gq(home,x2.min()));
71  GECODE_ME_CHECK(x1.gq(home,x2.min()));
72  (void) new (home) Min<A,B,C>(home,x0,x1,x2);
73  return ES_OK;
74  }
75 
76  template<class A, class B, class C>
79  GECODE_ME_CHECK(x2.eq(home,min(x0.domain(),x1.domain())));
80  GECODE_ME_CHECK(x0.gq(home,x2.min()));
81  GECODE_ME_CHECK(x1.gq(home,x2.min()));
82  if (same(x0,x1)) {
83  GECODE_ME_CHECK(x0.lq(home,x2.max()));
84  } else {
85  if (!overlap(x1.val(),x2.val())) GECODE_ME_CHECK(x0.lq(home,x2.max()));
86  if (!overlap(x0.val(),x2.val())) GECODE_ME_CHECK(x1.lq(home,x2.max()));
87  }
88  return (x0.assigned() && x1.assigned()) ? home.ES_SUBSUMED(*this) : ES_FIX;
89  }
90 
91  /*
92  * Bounds consistent max propagator
93  *
94  */
95 
96  template<class A, class B, class C>
98  Max<A,B,C>::Max(Home home, A x0, B x1, C x2)
100 
101  template<class A, class B, class C>
105 
106  template<class A, class B, class C>
109  A x0, B x1, C x2)
110  : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,p,x0,x1,x2) {}
111 
112  template<class A, class B, class C>
113  Actor*
115  return new (home) Max<A,B,C>(home,*this);
116  }
117 
118  template<class A, class B, class C>
119  ExecStatus
120  Max<A,B,C>::post(Home home, A x0, B x1, C x2) {
121  GECODE_ME_CHECK(x2.eq(home,max(x0.domain(),x1.domain())));
122  GECODE_ME_CHECK(x0.lq(home,x2.max()));
123  GECODE_ME_CHECK(x1.lq(home,x2.max()));
124  (void) new (home) Max<A,B,C>(home,x0,x1,x2);
125  return ES_OK;
126  }
127 
128  template<class A, class B, class C>
129  ExecStatus
131  GECODE_ME_CHECK(x2.eq(home,max(x0.domain(),x1.domain())));
132  GECODE_ME_CHECK(x0.lq(home,x2.max()));
133  GECODE_ME_CHECK(x1.lq(home,x2.max()));
134  if (same(x0,x1)) {
135  GECODE_ME_CHECK(x0.gq(home,x2.min()));
136  } else {
137  if (!overlap(x1.val(),x2.val())) GECODE_ME_CHECK(x0.gq(home,x2.min()));
138  if (!overlap(x0.val(),x2.val())) GECODE_ME_CHECK(x1.gq(home,x2.min()));
139  }
140  return (x0.assigned() && x1.assigned()) ? home.ES_SUBSUMED(*this) : ES_FIX;
141  }
142 
143  /*
144  * Nary bounds consistent maximum
145  *
146  */
147 
148  template<class View>
151  : NaryOnePropagator<View,PC_FLOAT_BND>(home,x,y) {}
152 
153  template<class View>
154  ExecStatus
156  assert(x.size() > 0);
157  x.unique();
158  if (x.size() == 1)
159  return Rel::Eq<View,View>::post(home,x[0],y);
160  if (x.size() == 2)
161  return Max<View,View,View>::post(home,x[0],x[1],y);
164  for (int i=x.size(); i--; ) {
165  l = std::max(l,x[i].min());
166  u = std::max(u,x[i].max());
167  }
168  GECODE_ME_CHECK(y.gq(home,l));
169  GECODE_ME_CHECK(y.lq(home,u));
170  if (x.same(y)) {
171  // Check whether y occurs in x
172  for (int i=x.size(); i--; )
173  GECODE_ES_CHECK((Rel::Lq<View>::post(home,x[i],y)));
174  } else {
175  (void) new (home) NaryMax<View>(home,x,y);
176  }
177  return ES_OK;
178  }
179 
180  template<class View>
183  : NaryOnePropagator<View,PC_FLOAT_BND>(home,p) {}
184 
185  template<class View>
186  Actor*
188  if (x.size() == 1)
189  return new (home) Rel::Eq<View,View>(home,*this,x[0],y);
190  if (x.size() == 2)
191  return new (home) Max<View,View,View>(home,*this,x[0],x[1],y);
192  return new (home) NaryMax<View>(home,*this);
193  }
194 
197  MPS_ASSIGNED = 1<<0,
198  MPS_REMOVED = 1<<1,
200  };
201 
202  template<class View>
205  ViewArray<View>& x, View y, PropCond pc) {
206  rerun:
207  assert(x.size() > 0);
208  FloatNum maxmax = x[x.size()-1].max();
209  FloatNum maxmin = x[x.size()-1].min();
210  for (int i = x.size()-1; i--; ) {
211  maxmax = std::max(x[i].max(),maxmax);
212  maxmin = std::max(x[i].min(),maxmin);
213  }
214  GECODE_ME_CHECK(y.lq(home,maxmax));
215  GECODE_ME_CHECK(y.gq(home,maxmin));
216  maxmin = y.min();
217  maxmax = y.max();
218  int status = MPS_ASSIGNED;
219  for (int i = x.size(); i--; ) {
220  ModEvent me = x[i].lq(home,maxmax);
221  if (me == ME_FLOAT_FAILED)
222  return ES_FAILED;
223  if (me_modified(me) && (x[i].max() != maxmax))
224  status |= MPS_NEW_BOUND;
225  if (x[i].max() < maxmin) {
226  x.move_lst(i,home,p,pc);
227  status |= MPS_REMOVED;
228  } else if (!x[i].assigned())
229  status &= ~MPS_ASSIGNED;
230  }
231  if (x.size() == 0)
232  return ES_FAILED;
233  if ((status & MPS_REMOVED) != 0)
234  goto rerun;
235  if (((status & MPS_ASSIGNED) != 0) && y.assigned())
236  return home.ES_SUBSUMED(p);
237  return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
238  }
239 
240  template<class View>
241  ExecStatus
243  return prop_nary_max(home,*this,x,y,PC_FLOAT_BND);
244  }
245 
246 }}}
247 
248 // STATISTICS: float-prop
249 
static ExecStatus post(Home home, ViewArray< View > &x, View y)
Post propagator .
Definition: min-max.hpp:155
Propagator for bounds consistent max operator
Definition: arithmetic.hh:356
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
ViewArray< View > x
Array of views.
Definition: pattern.hpp:175
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3482
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
bool overlap(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:498
Binary bounds consistent equality propagator.
Definition: rel.hh:66
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition: min-max.hpp:114
int ModEvent
Type for modification events.
Definition: core.hpp:62
Base-class for propagators.
Definition: core.hpp:1023
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:199
#define forceinline
Definition: config.hpp:185
Propagation has computed fixpoint.
Definition: core.hpp:476
Computation spaces.
Definition: core.hpp:1701
Base-class for both propagators and branchers.
Definition: core.hpp:627
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
bool same(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether two views are the same.
Definition: view.hpp:676
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Gecode::IntArgs i(4, 1, 2, 3, 4)
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: min-max.hpp:187
Max(Space &home, Max &p)
Constructor for cloning p.
Definition: min-max.hpp:103
Execution has resulted in failure.
Definition: core.hpp:473
MaxPropStatus
Status of propagation for nary max.
Definition: min-max.hpp:196
Mixed ternary propagator.
Definition: pattern.hpp:237
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
All views are assigned.
Definition: min-max.hpp:197
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1036
(n+1)-ary propagator
Definition: pattern.hpp:172
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: min-max.hpp:78
View arrays.
Definition: array.hpp:224
static ExecStatus post(Home home, A x0, B x1, C x2)
Post propagator for .
Definition: min-max.hpp:68
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
NaryMax(Space &home, NaryMax &p)
Constructor for cloning p.
Definition: min-max.hpp:182
void move_lst(int i)
Move view from position size()-1 to position i (truncate array by one)
Definition: array.hpp:1279
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Less or equal propagator.
Definition: rel.hh:241
static ExecStatus post(Home home, A x0, B x1, C x2)
Post propagator for .
Definition: min-max.hpp:120
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:765
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition: min-max.hpp:62
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: min-max.hpp:130
ExecStatus
Definition: core.hpp:471
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: min-max.hpp:242
Post propagator for SetVar x
Definition: set.hh:765
Execution is okay.
Definition: core.hpp:475
Propagation has not computed fixpoint.
Definition: core.hpp:474
void unique(void)
Remove all duplicate views from array (changes element order)
Definition: array.hpp:1489
ExecStatus prop_nary_max(Space &home, Propagator &p, ViewArray< View > &x, View y, PropCond pc)
Definition: min-max.hpp:204
const Gecode::PropCond PC_FLOAT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:292
Gecode toplevel namespace
Min(Space &home, Min &p)
Constructor for cloning p.
Definition: min-max.hpp:51
Bounds consistent n-ary maximum propagator.
Definition: arithmetic.hh:383
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1199
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Home class for posting propagators
Definition: core.hpp:853
Propagator for bounds consistent min operator
Definition: arithmetic.hh:327
double FloatNum
Floating point number base type.
Definition: float.hh:106
bool same(void) const
Test whether array has multiple occurence of the same view.
Definition: array.hpp:1459