Generated on Sat Feb 7 2015 02:01:14 for Gecode by doxygen 1.8.9.1
min-max-channel.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: 2013-02-14 16:29:11 +0100 (Thu, 14 Feb 2013) $ by $Author: schulte $
13  * $Revision: 13292 $
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 namespace Gecode { namespace Float { namespace Arithmetic {
41 
42 #include <cmath>
43  /*
44  * Bounds consistent min operator
45  *
46  */
47  template<class A, class B, class C>
49  Min<A,B,C>::Min(Home home, A x0, B x1, C x2)
51 
52  template<class A, class B, class C>
54  Min<A,B,C>::Min(Space& home, bool share, Min<A,B,C>& p)
56 
57  template<class A, class B, class C>
59  Min<A,B,C>::Min(Space& home, bool share, Propagator& p,
60  A x0, B x1, C x2)
61  : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,share,p,x0,x1,x2) {}
62 
63  template<class A, class B, class C>
64  Actor*
65  Min<A,B,C>::copy(Space& home, bool share) {
66  return new (home) Min<A,B,C>(home,share,*this);
67  }
68 
69  template<class A, class B, class C>
71  Min<A,B,C>::post(Home home, A x0, B x1, C x2) {
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 operator
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>
103  Max<A,B,C>::Max(Space& home, bool share, Max<A,B,C>& p)
105 
106  template<class A, class B, class C>
108  Max<A,B,C>::Max(Space& home, bool share, Propagator& p,
109  A x0, B x1, C x2)
110  : MixTernaryPropagator<A,PC_FLOAT_BND,B,PC_FLOAT_BND,C,PC_FLOAT_BND>(home,share,p,x0,x1,x2) {}
111 
112  template<class A, class B, class C>
113  Actor*
114  Max<A,B,C>::copy(Space& home, bool share) {
115  return new (home) Max<A,B,C>(home,share,*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  (void) new (home) Max<A,B,C>(home,x0,x1,x2);
122  return ES_OK;
123  }
124 
125  template<class A, class B, class C>
126  ExecStatus
128  GECODE_ME_CHECK(x2.eq(home,max(x0.domain(),x1.domain())));
129  GECODE_ME_CHECK(x0.lq(home,x2.max()));
130  GECODE_ME_CHECK(x1.lq(home,x2.max()));
131  if (same(x0,x1)) {
132  GECODE_ME_CHECK(x0.gq(home,x2.min()));
133  } else {
134  if (!overlap(x1.val(),x2.val())) GECODE_ME_CHECK(x0.gq(home,x2.min()));
135  if (!overlap(x0.val(),x2.val())) GECODE_ME_CHECK(x1.gq(home,x2.min()));
136  }
137  return (x0.assigned() && x1.assigned()) ? home.ES_SUBSUMED(*this) : ES_FIX;
138  }
139 
140  /*
141  * Nary bounds consistent maximum
142  *
143  */
144 
145  template<class View>
148  : NaryOnePropagator<View,PC_FLOAT_BND>(home,x,y) {}
149 
150  template<class View>
151  ExecStatus
153  assert(x.size() > 0);
154  x.unique(home);
155  if (x.size() == 1)
156  return Rel::Eq<View,View>::post(home,x[0],y);
157  if (x.size() == 2)
158  return Max<View,View,View>::post(home,x[0],x[1],y);
161  for (int i=x.size(); i--; ) {
162  l = std::max(l,x[i].min());
163  u = std::max(u,x[i].max());
164  }
165  GECODE_ME_CHECK(y.gq(home,l));
166  GECODE_ME_CHECK(y.lq(home,u));
167  if (x.same(home,y)) {
168  // Check whether y occurs in x
169  for (int i=x.size(); i--; )
170  GECODE_ES_CHECK((Rel::Lq<View>::post(home,x[i],y)));
171  } else {
172  (void) new (home) NaryMax<View>(home,x,y);
173  }
174  return ES_OK;
175  }
176 
177  template<class View>
180  : NaryOnePropagator<View,PC_FLOAT_BND>(home,share,p) {}
181 
182  template<class View>
183  Actor*
184  NaryMax<View>::copy(Space& home, bool share) {
185  if (x.size() == 1)
186  return new (home) Rel::Eq<View,View>(home,share,*this,x[0],y);
187  if (x.size() == 2)
188  return new (home) Max<View,View,View>(home,share,*this,x[0],x[1],y);
189  return new (home) NaryMax<View>(home,share,*this);
190  }
191 
194  MPS_ASSIGNED = 1<<0,
195  MPS_REMOVED = 1<<1,
197  };
198 
199  template<class View>
202  ViewArray<View>& x, View y, PropCond pc) {
203  rerun:
204  assert(x.size() > 0);
205  FloatNum maxmax = x[x.size()-1].max();
206  FloatNum maxmin = x[x.size()-1].min();
207  for (int i = x.size()-1; i--; ) {
208  maxmax = std::max(x[i].max(),maxmax);
209  maxmin = std::max(x[i].min(),maxmin);
210  }
211  GECODE_ME_CHECK(y.lq(home,maxmax));
212  GECODE_ME_CHECK(y.gq(home,maxmin));
213  maxmin = y.min();
214  maxmax = y.max();
215  int status = MPS_ASSIGNED;
216  for (int i = x.size(); i--; ) {
217  ModEvent me = x[i].lq(home,maxmax);
218  if (me == ME_FLOAT_FAILED)
219  return ES_FAILED;
220  if (me_modified(me) && (x[i].max() != maxmax))
221  status |= MPS_NEW_BOUND;
222  if (x[i].max() < maxmin) {
223  x.move_lst(i,home,p,pc);
224  status |= MPS_REMOVED;
225  } else if (!x[i].assigned())
226  status &= ~MPS_ASSIGNED;
227  }
228  if (x.size() == 0)
229  return ES_FAILED;
230  if ((status & MPS_REMOVED) != 0)
231  goto rerun;
232  if (((status & MPS_ASSIGNED) != 0) && y.assigned())
233  return home.ES_SUBSUMED(p);
234  return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
235  }
236 
237  template<class View>
238  ExecStatus
240  return prop_nary_max(home,*this,x,y,PC_FLOAT_BND);
241  }
242 
243 
244  /*
245  * Bounds consistent interger part operator
246  *
247  */
248 
249  template<class A, class B>
251  Channel<A,B>::Channel(Home home, A x0, B x1)
252  : MixBinaryPropagator<A,PC_FLOAT_BND,B,Int::PC_INT_BND>(home,x0,x1) {}
253 
254  template<class A, class B>
257  : MixBinaryPropagator<A,PC_FLOAT_BND,B,Int::PC_INT_BND>(home,share,p) {}
258 
259  template<class A, class B>
260  Actor*
261  Channel<A,B>::copy(Space& home, bool share) {
262  return new (home) Channel<A,B>(home,share,*this);
263  }
264 
265  template<class A, class B>
266  ExecStatus
267  Channel<A,B>::post(Home home, A x0, B x1) {
269  Int::Limits::max)));
270  (void) new (home) Channel<A,B>(home,x0,x1);
271  return ES_OK;
272  }
273 
274  template<class A, class B>
275  ExecStatus
277  GECODE_ME_CHECK(x1.gq(home,static_cast<int>(std::ceil(x0.min()))));
278  GECODE_ME_CHECK(x1.lq(home,static_cast<int>(std::floor(x0.max()))));
279  GECODE_ME_CHECK(x0.eq(home,FloatVal(x1.min(),x1.max())));
280  return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
281  }
282 
283 }}}
284 
285 // STATISTICS: float-prop
286 
static ExecStatus post(Home home, ViewArray< View > &x, View y)
Post propagator .
Propagator for bounds consistent max operator
Definition: arithmetic.hh:389
Channel(Space &home, bool share, Channel &p)
Constructor for cloning p.
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Max(Space &home, bool share, Max &p)
Constructor for cloning p.
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
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:146
Base-class for propagators.
Definition: core.hpp:755
const Gecode::ModEvent ME_FLOAT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:260
Telling has found a new upper bound.
Propagation has computed fixpoint.
Definition: core.hpp:528
const int max
Largest allowed integer value.
Definition: int.hh:113
void unique(const Space &home)
Remove all duplicate views from array (changes element order)
Definition: array.hpp:1498
Computation spaces.
Definition: core.hpp:1362
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
const int min
Smallest allowed integer value.
Definition: int.hh:115
Base-class for both propagators and branchers.
Definition: core.hpp:666
Propagator for bounds consistent integer part operator
Definition: arithmetic.hh:441
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
bool same(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether two views are the same.
Definition: view.hpp:603
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 1, 2, 3, 4)
Execution has resulted in failure.
Definition: core.hpp:525
MaxPropStatus
Status of propagation for nary max.
Mixed ternary propagator.
Definition: propagator.hpp:235
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
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:766
(n+1)-ary propagator
Definition: propagator.hpp:172
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
View arrays.
Definition: array.hpp:234
static ExecStatus post(Home home, A x0, B x1, C x2)
Post propagator for .
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
void move_lst(int i)
Move view from position size()-1 to position i (truncate array by one)
Definition: array.hpp:1295
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
Less or equal propagator.
Definition: rel.hh:245
static ExecStatus post(Home home, A x0, B x1, C x2)
Post propagator for .
Float value type.
Definition: float.hh:321
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Mixed binary propagator.
Definition: propagator.hpp:203
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
ExecStatus
Definition: core.hpp:523
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
static ExecStatus post(Home home, A x0, B x1)
Post propagator for .
#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 ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
NaryMax(Space &home, bool share, NaryMax &p)
Constructor for cloning p.
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
ExecStatus prop_nary_max(Space &home, Propagator &p, ViewArray< View > &x, View y, PropCond pc)
const Gecode::PropCond PC_FLOAT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:292
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
Bounds consistent n-ary maximum propagator.
Definition: arithmetic.hh:416
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
Propagator for bounds consistent min operator
Definition: arithmetic.hh:360
double FloatNum
Floating point number base type.
Definition: float.hh:108
Min(Space &home, bool share, Min &p)
Constructor for cloning p.