Generated on Sat Jul 28 2018 17:12:13 for Gecode by doxygen 1.8.14
view.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  * Contributing authors:
7  * Guido Tack <tack@gecode.org>
8  *
9  * Copyright:
10  * Christian Schulte, 2004
11  * Guido Tack, 2004
12  *
13  * Last modified:
14  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
15  * $Revision: 15137 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <algorithm>
43 
44 namespace Gecode { namespace Int { namespace Element {
45 
50  template<class VA, class VC>
51  class RelTestBnd {
52  public:
53  RelTest operator ()(VA,VC);
54  };
59  template<class VA>
61  public:
63  };
64 
69  template<class VA, class VC>
70  class RelTestDom {
71  public:
72  RelTest operator ()(VA,VC);
73  };
78  template<class VA>
80  public:
82  };
83 
84 
85  template<class VA, class VC>
88  return rtest_eq_bnd(x,y);
89  }
90  template<class VA>
93  return rtest_eq_bnd(x,y.val());
94  }
95 
96  template<class VA, class VC>
99  return rtest_eq_dom(x,y);
100  }
101  template<class VA>
104  return rtest_eq_dom(x,y.val());
105  }
106 
107 
108 
109 
110  /*
111  * Base class
112  *
113  */
114 
115  template<class VA, class VB, class VC, PropCond pc_ac>
117  VB y0, VC y1)
118  : Propagator(home), iv(iv0), x0(y0), x1(y1) {
119  x0.subscribe(home,*this,PC_INT_DOM);
120  x1.subscribe(home,*this,pc_ac);
121  iv.subscribe(home,*this,pc_ac);
122  }
123 
124  template<class VA, class VB, class VC, PropCond pc_ac>
126  View<VA,VB,VC,pc_ac>::View(Space& home, bool share, View& p)
127  : Propagator(home,share,p) {
128  x0.update(home,share,p.x0);
129  x1.update(home,share,p.x1);
130  iv.update(home,share,p.iv);
131  }
132 
133  template<class VA, class VB, class VC, PropCond pc_ac>
134  PropCost
136  // This is required for subscribing to variables in the
137  // above constructor, but this is then the only time this
138  // virtual function is ever used!
139  return PropCost::linear(PropCost::LO,iv.size()+2);
140  }
141 
142  template<class VA, class VB, class VC, PropCond pc_ac>
143  void
145  x0.reschedule(home,*this,PC_INT_DOM);
146  x1.reschedule(home,*this,pc_ac);
147  iv.reschedule(home,*this,pc_ac);
148  }
149 
150  template<class VA, class VB, class VC, PropCond pc_ac>
151  forceinline size_t
153  x0.cancel(home,*this,PC_INT_DOM);
154  x1.cancel(home,*this,pc_ac);
155  iv.cancel(home,*this,pc_ac);
156  (void) Propagator::dispose(home);
157  return sizeof(*this);
158  }
159 
160 
161 
162 
167  template<class View>
168  class IterIdxView {
169  private:
170  const IdxView<View> *cur, *end;
171  public:
172  IterIdxView(void);
173  IterIdxView(const IdxView<View>*, const IdxView<View>*);
174  void init(const IdxView<View>*, const IdxView<View>*);
175  bool operator ()(void) const;
176  void operator ++(void);
177  int val(void) const;
178  };
179 
180  template<class View>
183  template<class View>
186  const IdxView<View>* e)
187  : cur(b), end(e) {}
188  template<class View>
189  forceinline void
191  const IdxView<View>* e) {
192  cur=b; end=e;
193  }
194  template<class View>
195  forceinline bool
197  return cur < end;
198  }
199  template<class View>
200  forceinline void
202  cur++;
203  }
204  template<class View>
205  forceinline int
207  return cur->idx;
208  }
209 
210 
211 
212 
213  /*
214  * Generic scanning: does all but computing new domain for result
215  * (which is specific to bounds/domain version)
216  *
217  */
218 
219  template<class VA, class VB, class VC, PropCond pc_ac, class RelTest>
220  ExecStatus
222  VB x0, VC x1, Propagator& p, RelTest rt) {
223  assert(iv.size() > 1);
224  /*
225  * Prunes pairs of index, variable
226  * - checks for idx value removed
227  * - checks for disequal variables
228  *
229  */
230  ViewValues<VB> vx0(x0);
231  int i = 0;
232  int j = 0;
233  while (vx0() && (i < iv.size())) {
234  if (iv[i].idx < vx0.val()) {
235  iv[i].view.cancel(home,p,pc_ac);
236  ++i;
237  } else if (iv[i].idx > vx0.val()) {
238  ++vx0;
239  } else {
240  assert(iv[i].idx == vx0.val());
241  switch (rt(iv[i].view,x1)) {
242  case RT_FALSE:
243  iv[i].view.cancel(home,p,pc_ac);
244  break;
245  case RT_TRUE:
246  case RT_MAYBE:
247  iv[j++] = iv[i];
248  break;
249  default: GECODE_NEVER;
250  }
251  ++vx0; ++i;
252  }
253  }
254  while (i < iv.size())
255  iv[i++].view.cancel(home,p,pc_ac);
256  bool adjust = (j<iv.size());
257  iv.size(j);
258 
259  if (iv.size() == 0)
260  return ES_FAILED;
261 
262  if (iv.size() == 1) {
263  GECODE_ME_CHECK(x0.eq(home,iv[0].idx));
264  } else if (adjust) {
265  IterIdxView<VA> v(&iv[0],&iv[0]+iv.size());
266  GECODE_ME_CHECK(x0.narrow_v(home,v,false));
267  assert(x0.size() == static_cast<unsigned int>(iv.size()));
268  }
269  return ES_OK;
270  }
271 
272 
273 
274 
275  /*
276  * Bounds consistent propagator
277  *
278  */
279 
280  template<class VA, class VB, class VC>
283  IdxViewArray<VA>& iv, VB x0, VC x1)
284  : View<VA,VB,VC,PC_INT_BND>(home,iv,x0,x1) {}
285 
286  template<class VA, class VB, class VC>
287  ExecStatus
289  IdxViewArray<VA>& iv, VB x0, VC x1) {
290  GECODE_ME_CHECK(x0.gq(home,0));
291  GECODE_ME_CHECK(x0.le(home,iv.size()));
292  if (x0.assigned()) {
293  (void) new (home) Rel::EqBnd<VA,VC>(home,iv[x0.val()].view,x1);
294  return ES_OK;
295  } else {
296  assert(iv.size()>1);
297  (void) new (home) ViewBnd<VA,VB,VC>(home,iv,x0,x1);
298  }
299  return ES_OK;
300  }
301 
302 
303  template<class VA, class VB, class VC>
306  : View<VA,VB,VC,PC_INT_BND>(home,share,p) {}
307 
308  template<class VA, class VB, class VC>
309  Actor*
310  ViewBnd<VA,VB,VC>::copy(Space& home, bool share) {
311  return new (home) ViewBnd<VA,VB,VC>(home,share,*this);
312  }
313 
314  template<class VA, class VB, class VC>
315  ExecStatus
317  assert(iv.size() > 1);
320  (home,iv,x0,x1,*this,rt)));
321  if (iv.size() == 1) {
322  ExecStatus es = home.ES_SUBSUMED(*this);
323  (void) new (home) Rel::EqBnd<VA,VC>(home(*this),iv[0].view,x1);
324  return es;
325  }
326  assert(iv.size() > 1);
327  // Compute new result
328  int min = iv[iv.size()-1].view.min();
329  int max = iv[iv.size()-1].view.max();
330  for (int i=iv.size()-1; i--; ) {
331  min = std::min(iv[i].view.min(),min);
332  max = std::max(iv[i].view.max(),max);
333  }
334  ExecStatus es = shared(x0,x1) ? ES_NOFIX : ES_FIX;
335  {
336  ModEvent me = x1.lq(home,max);
337  if (me_failed(me))
338  return ES_FAILED;
339  if (me_modified(me) && (x1.max() != max))
340  es = ES_NOFIX;
341  }
342  {
343  ModEvent me = x1.gq(home,min);
344  if (me_failed(me))
345  return ES_FAILED;
346  if (me_modified(me) && (x1.min() != min))
347  es = ES_NOFIX;
348  }
349  return (x1.assigned() && (min == max)) ?
350  home.ES_SUBSUMED(*this) : es;
351  }
352 
353 
354 
355 
356 
357  /*
358  * Domain consistent propagator
359  *
360  */
361 
362  template<class VA, class VB, class VC>
365  IdxViewArray<VA>& iv, VB x0, VC x1)
366  : View<VA,VB,VC,PC_INT_DOM>(home,iv,x0,x1) {}
367 
368  template<class VA, class VB, class VC>
369  ExecStatus
371  IdxViewArray<VA>& iv, VB x0, VC x1){
372  GECODE_ME_CHECK(x0.gq(home,0));
373  GECODE_ME_CHECK(x0.le(home,iv.size()));
374  if (x0.assigned()) {
375  (void) new (home) Rel::EqDom<VA,VC>(home,iv[x0.val()].view,x1);
376  return ES_OK;
377  } else {
378  assert(iv.size()>1);
379  (void) new (home) ViewDom<VA,VB,VC>(home,iv,x0,x1);
380  }
381  return ES_OK;
382  }
383 
384 
385  template<class VA, class VB, class VC>
388  : View<VA,VB,VC,PC_INT_DOM>(home,share,p) {}
389 
390  template<class VA, class VB, class VC>
391  Actor*
392  ViewDom<VA,VB,VC>::copy(Space& home, bool share) {
393  return new (home) ViewDom<VA,VB,VC>(home,share,*this);
394  }
395 
396 
397  template<class VA, class VB, class VC>
398  PropCost
399  ViewDom<VA,VB,VC>::cost(const Space&, const ModEventDelta& med) const {
400  return PropCost::linear((VA::me(med) != ME_INT_DOM) ?
401  PropCost::LO : PropCost::HI, iv.size()+2);
402  }
403 
404  template<class VA, class VB, class VC>
405  ExecStatus
407  assert(iv.size() > 1);
408  if (VA::me(med) != ME_INT_DOM) {
411  (home,iv,x0,x1,*this,rt)));
412  if (iv.size() == 1) {
413  ExecStatus es = home.ES_SUBSUMED(*this);
414  (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1);
415  return es;
416  }
417  // Compute new result
418  int min = iv[iv.size()-1].view.min();
419  int max = iv[iv.size()-1].view.max();
420  for (int i=iv.size()-1; i--; ) {
421  min = std::min(iv[i].view.min(),min);
422  max = std::max(iv[i].view.max(),max);
423  }
424  GECODE_ME_CHECK(x1.lq(home,max));
425  GECODE_ME_CHECK(x1.gq(home,min));
426  return (x1.assigned() && (min == max)) ?
427  home.ES_SUBSUMED(*this) :
428  home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
429  }
432  (home,iv,x0,x1,*this,rt)));
433  if (iv.size() == 1) {
434  ExecStatus es = home.ES_SUBSUMED(*this);
435  (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1);
436  return es;
437  }
438  assert(iv.size() > 1);
439 
440  if (x1.assigned()) {
441  for (int i = iv.size(); i--; )
442  if (iv[i].view.in(x1.val()))
443  return shared(x0,x1) ? ES_NOFIX : ES_FIX;
444  return ES_FAILED;
445  } else {
446  Region r(home);
447  ViewRanges<VA>* i_view = r.alloc<ViewRanges<VA> >(iv.size());
448  for (int i = iv.size(); i--; )
449  i_view[i].init(iv[i].view);
450  Iter::Ranges::NaryUnion i_val(r, i_view, iv.size());
451  ModEvent me = x1.inter_r(home,i_val);
452  r.free<ViewRanges<VA> >(i_view,iv.size());
453  GECODE_ME_CHECK(me);
454  return (shared(x0,x1) || me_modified(me)) ? ES_NOFIX : ES_FIX;
455  }
456  }
457 
458 }}}
459 
460 // STATISTICS: int-prop
461 
Domain consistent element propagator for array of views.
Definition: element.hh:266
Relation may hold or not.
Definition: view.hpp:1616
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4841
Binary domain consistent equality propagator.
Definition: rel.hh:71
View(Space &home, bool share, View &p)
Constructor for cloning p.
Definition: view.hpp:126
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
RelTest rtest_eq_dom(VX x, VY y)
Test whether views x and y are equal (use full domain information)
Definition: rel-test.hpp:69
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:3627
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
int ModEvent
Type for modification events.
Definition: core.hpp:142
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:45
Base-class for propagators.
Definition: core.hpp:1092
void init(const IdxView< View > *, const IdxView< View > *)
Definition: view.hpp:190
static ExecStatus post(Home home, IdxViewArray< VA > &iv, VB x0, VC x1)
Post propagator for .
Definition: view.hpp:288
Handle to region.
Definition: region.hpp:61
Value iterator for integer views.
Definition: view.hpp:94
Propagation has computed fixpoint.
Definition: core.hpp:545
Computation spaces.
Definition: core.hpp:1748
Base-class for both propagators and branchers.
Definition: core.hpp:696
Range iterator for integer views.
Definition: view.hpp:54
Class for bounds-equality test.
Definition: view.hpp:51
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: view.hpp:392
bool operator()(void) const
Definition: view.hpp:196
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)
static ExecStatus post(Home home, IdxViewArray< VA > &iv, VB x0, VC x1)
Post propagator for .
Definition: view.hpp:370
Execution has resulted in failure.
Definition: core.hpp:542
Relation does not hold.
Definition: view.hpp:1615
RelTest
Result of testing relation.
Definition: view.hpp:1614
void cancel(Space &home, Propagator &p, PropCond pc)
Definition: idx-view.hpp:137
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
Range iterator for union of iterators.
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
Binary bounds consistent equality propagator.
Definition: rel.hh:137
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
RelTest operator()(VA, VC)
Definition: view.hpp:98
Expensive.
Definition: core.hpp:582
Base-class for element propagator for array of views.
Definition: element.hh:207
int size(void) const
Return the current size.
Definition: idx-view.hpp:103
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: view.hpp:310
RelTest rtest_eq_bnd(VX x, VY y)
Test whether views x and y are equal (use bounds information)
Definition: rel-test.hpp:47
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
const int v[7]
Definition: distinct.cpp:263
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Value iterator for indices in index-view map.
Definition: view.hpp:168
ExecStatus scan(Space &home, IdxViewArray< VA > &iv, VB x0, VC x1, Propagator &p, RelTest rt)
Definition: view.hpp:221
Constant integer view.
Definition: view.hpp:804
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view.hpp:316
ViewBnd(Space &home, bool share, ViewBnd &p)
Constructor for cloning p.
Definition: view.hpp:305
Propagation cost.
Definition: core.hpp:554
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
ExecStatus
Definition: core.hpp:540
#define forceinline
Definition: config.hpp:173
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
ViewDom(Space &home, bool share, ViewDom &p)
Constructor for cloning p.
Definition: view.hpp:387
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
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: view.hpp:399
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:702
Gecode toplevel namespace
RelTest operator()(VA, VC)
Definition: view.hpp:87
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view.hpp:406
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
Class for pair of index and view.
Definition: idx-view.hh:52
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
Class for domain-equality test.
Definition: view.hpp:70
Relation does hold.
Definition: view.hpp:1617
Bounds consistent element propagator for array of views.
Definition: element.hh:236
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58