Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
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  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <algorithm>
39 
40 namespace Gecode { namespace Int { namespace Element {
41 
46  template<class VA, class VC>
47  class RelTestBnd {
48  public:
49  RelTest operator ()(VA,VC);
50  };
55  template<class VA>
57  public:
59  };
60 
65  template<class VA, class VC>
66  class RelTestDom {
67  public:
68  RelTest operator ()(VA,VC);
69  };
74  template<class VA>
76  public:
78  };
79 
80 
81  template<class VA, class VC>
84  return rtest_eq_bnd(x,y);
85  }
86  template<class VA>
89  return rtest_eq_bnd(x,y.val());
90  }
91 
92  template<class VA, class VC>
95  return rtest_eq_dom(x,y);
96  }
97  template<class VA>
100  return rtest_eq_dom(x,y.val());
101  }
102 
103 
104 
105 
106  /*
107  * Base class
108  *
109  */
110 
111  template<class VA, class VB, class VC, PropCond pc_ac>
113  VB y0, VC y1)
114  : Propagator(home), iv(iv0), x0(y0), x1(y1) {
115  x0.subscribe(home,*this,PC_INT_DOM);
116  x1.subscribe(home,*this,pc_ac);
117  iv.subscribe(home,*this,pc_ac);
118  }
119 
120  template<class VA, class VB, class VC, PropCond pc_ac>
123  : Propagator(home,p) {
124  x0.update(home,p.x0);
125  x1.update(home,p.x1);
126  iv.update(home,p.iv);
127  }
128 
129  template<class VA, class VB, class VC, PropCond pc_ac>
130  PropCost
132  // This is required for subscribing to variables in the
133  // above constructor, but this is then the only time this
134  // virtual function is ever used!
135  return PropCost::linear(PropCost::LO,iv.size()+2);
136  }
137 
138  template<class VA, class VB, class VC, PropCond pc_ac>
139  void
141  x0.reschedule(home,*this,PC_INT_DOM);
142  x1.reschedule(home,*this,pc_ac);
143  iv.reschedule(home,*this,pc_ac);
144  }
145 
146  template<class VA, class VB, class VC, PropCond pc_ac>
147  forceinline size_t
149  x0.cancel(home,*this,PC_INT_DOM);
150  x1.cancel(home,*this,pc_ac);
151  iv.cancel(home,*this,pc_ac);
152  (void) Propagator::dispose(home);
153  return sizeof(*this);
154  }
155 
156 
157 
158 
163  template<class View>
164  class IterIdxView {
165  private:
166  const IdxView<View> *cur, *end;
167  public:
168  IterIdxView(void);
169  IterIdxView(const IdxView<View>*, const IdxView<View>*);
170  void init(const IdxView<View>*, const IdxView<View>*);
171  bool operator ()(void) const;
172  void operator ++(void);
173  int val(void) const;
174  };
175 
176  template<class View>
179  template<class View>
182  const IdxView<View>* e)
183  : cur(b), end(e) {}
184  template<class View>
185  forceinline void
187  const IdxView<View>* e) {
188  cur=b; end=e;
189  }
190  template<class View>
191  forceinline bool
193  return cur < end;
194  }
195  template<class View>
196  forceinline void
198  cur++;
199  }
200  template<class View>
201  forceinline int
203  return cur->idx;
204  }
205 
206 
207 
208 
209  /*
210  * Generic scanning: does all but computing new domain for result
211  * (which is specific to bounds/domain version)
212  *
213  */
214 
215  template<class VA, class VB, class VC, PropCond pc_ac, class RelTest>
216  ExecStatus
218  VB x0, VC x1, Propagator& p, RelTest rt) {
219  assert(iv.size() > 1);
220  /*
221  * Prunes pairs of index, variable
222  * - checks for idx value removed
223  * - checks for disequal variables
224  *
225  */
226  ViewValues<VB> vx0(x0);
227  int i = 0;
228  int j = 0;
229  while (vx0() && (i < iv.size())) {
230  if (iv[i].idx < vx0.val()) {
231  iv[i].view.cancel(home,p,pc_ac);
232  ++i;
233  } else if (iv[i].idx > vx0.val()) {
234  ++vx0;
235  } else {
236  assert(iv[i].idx == vx0.val());
237  switch (rt(iv[i].view,x1)) {
238  case RT_FALSE:
239  iv[i].view.cancel(home,p,pc_ac);
240  break;
241  case RT_TRUE:
242  case RT_MAYBE:
243  iv[j++] = iv[i];
244  break;
245  default: GECODE_NEVER;
246  }
247  ++vx0; ++i;
248  }
249  }
250  while (i < iv.size())
251  iv[i++].view.cancel(home,p,pc_ac);
252  bool adjust = (j<iv.size());
253  iv.size(j);
254 
255  if (iv.size() == 0)
256  return ES_FAILED;
257 
258  if (iv.size() == 1) {
259  GECODE_ME_CHECK(x0.eq(home,iv[0].idx));
260  } else if (adjust) {
261  IterIdxView<VA> v(&iv[0],&iv[0]+iv.size());
262  GECODE_ME_CHECK(x0.narrow_v(home,v,false));
263  assert(x0.size() == static_cast<unsigned int>(iv.size()));
264  }
265  return ES_OK;
266  }
267 
268 
269 
270 
271  /*
272  * Bounds consistent propagator
273  *
274  */
275 
276  template<class VA, class VB, class VC>
279  IdxViewArray<VA>& iv, VB x0, VC x1)
280  : View<VA,VB,VC,PC_INT_BND>(home,iv,x0,x1) {}
281 
282  template<class VA, class VB, class VC>
283  ExecStatus
285  IdxViewArray<VA>& iv, VB x0, VC x1) {
286  GECODE_ME_CHECK(x0.gq(home,0));
287  GECODE_ME_CHECK(x0.le(home,iv.size()));
288  if (x0.assigned()) {
289  (void) new (home) Rel::EqBnd<VA,VC>(home,iv[x0.val()].view,x1);
290  return ES_OK;
291  } else {
292  assert(iv.size()>1);
293  (void) new (home) ViewBnd<VA,VB,VC>(home,iv,x0,x1);
294  }
295  return ES_OK;
296  }
297 
298 
299  template<class VA, class VB, class VC>
302  : View<VA,VB,VC,PC_INT_BND>(home,p) {}
303 
304  template<class VA, class VB, class VC>
305  Actor*
307  return new (home) ViewBnd<VA,VB,VC>(home,*this);
308  }
309 
310  template<class VA, class VB, class VC>
311  ExecStatus
313  assert(iv.size() > 1);
316  (home,iv,x0,x1,*this,rt)));
317  if (iv.size() == 1) {
318  ExecStatus es = home.ES_SUBSUMED(*this);
319  (void) new (home) Rel::EqBnd<VA,VC>(home(*this),iv[0].view,x1);
320  return es;
321  }
322  assert(iv.size() > 1);
323  // Compute new result
324  int min = iv[0].view.min();
325  int max = iv[0].view.max();
326  for (int i=1; i<iv.size(); i++) {
327  min = std::min(iv[i].view.min(),min);
328  max = std::max(iv[i].view.max(),max);
329  }
330  ExecStatus es = shared(x0,x1) ? ES_NOFIX : ES_FIX;
331  {
332  ModEvent me = x1.lq(home,max);
333  if (me_failed(me))
334  return ES_FAILED;
335  if (me_modified(me) && (x1.max() != max))
336  es = ES_NOFIX;
337  }
338  {
339  ModEvent me = x1.gq(home,min);
340  if (me_failed(me))
341  return ES_FAILED;
342  if (me_modified(me) && (x1.min() != min))
343  es = ES_NOFIX;
344  }
345  return (x1.assigned() && (min == max)) ?
346  home.ES_SUBSUMED(*this) : es;
347  }
348 
349 
350 
351 
352 
353  /*
354  * Domain consistent propagator
355  *
356  */
357 
358  template<class VA, class VB, class VC>
361  IdxViewArray<VA>& iv, VB x0, VC x1)
362  : View<VA,VB,VC,PC_INT_DOM>(home,iv,x0,x1) {}
363 
364  template<class VA, class VB, class VC>
365  ExecStatus
367  IdxViewArray<VA>& iv, VB x0, VC x1){
368  GECODE_ME_CHECK(x0.gq(home,0));
369  GECODE_ME_CHECK(x0.le(home,iv.size()));
370  if (x0.assigned()) {
371  (void) new (home) Rel::EqDom<VA,VC>(home,iv[x0.val()].view,x1);
372  return ES_OK;
373  } else {
374  assert(iv.size()>1);
375  (void) new (home) ViewDom<VA,VB,VC>(home,iv,x0,x1);
376  }
377  return ES_OK;
378  }
379 
380 
381  template<class VA, class VB, class VC>
384  : View<VA,VB,VC,PC_INT_DOM>(home,p) {}
385 
386  template<class VA, class VB, class VC>
387  Actor*
389  return new (home) ViewDom<VA,VB,VC>(home,*this);
390  }
391 
392 
393  template<class VA, class VB, class VC>
394  PropCost
395  ViewDom<VA,VB,VC>::cost(const Space&, const ModEventDelta& med) const {
396  return PropCost::linear((VA::me(med) != ME_INT_DOM) ?
397  PropCost::LO : PropCost::HI, iv.size()+2);
398  }
399 
400  template<class VA, class VB, class VC>
401  ExecStatus
403  assert(iv.size() > 1);
404  if (VA::me(med) != ME_INT_DOM) {
407  (home,iv,x0,x1,*this,rt)));
408  if (iv.size() == 1) {
409  ExecStatus es = home.ES_SUBSUMED(*this);
410  (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1);
411  return es;
412  }
413  // Compute new result
414  int min = iv[0].view.min();
415  int max = iv[0].view.max();
416  for (int i=1; i<iv.size(); i++) {
417  min = std::min(iv[i].view.min(),min);
418  max = std::max(iv[i].view.max(),max);
419  }
420  GECODE_ME_CHECK(x1.lq(home,max));
421  GECODE_ME_CHECK(x1.gq(home,min));
422  return (x1.assigned() && (min == max)) ?
423  home.ES_SUBSUMED(*this) :
424  home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
425  }
428  (home,iv,x0,x1,*this,rt)));
429  if (iv.size() == 1) {
430  ExecStatus es = home.ES_SUBSUMED(*this);
431  (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1);
432  return es;
433  }
434  assert(iv.size() > 1);
435 
436  if (x1.assigned()) {
437  for (int i=0; i<iv.size(); i++)
438  if (iv[i].view.in(x1.val()))
439  return shared(x0,x1) ? ES_NOFIX : ES_FIX;
440  return ES_FAILED;
441  } else {
442  Region r;
443  ViewRanges<VA>* i_view = r.alloc<ViewRanges<VA> >(iv.size());
444  for (int i=0; i<iv.size(); i++)
445  i_view[i].init(iv[i].view);
446  Iter::Ranges::NaryUnion i_val(r, i_view, iv.size());
447  ModEvent me = x1.inter_r(home,i_val);
448  r.free<ViewRanges<VA> >(i_view,iv.size());
449  GECODE_ME_CHECK(me);
450  return (shared(x0,x1) || me_modified(me)) ? ES_NOFIX : ES_FIX;
451  }
452  }
453 
454 }}}
455 
456 // STATISTICS: int-prop
457 
ViewBnd(Space &home, ViewBnd &p)
Constructor for cloning p.
Definition: view.hpp:301
Post propagator for SetVar x
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Constant integer view.
Definition: view.hpp:851
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
VB x0
View for index.
Definition: element.hh:208
Base-class for element propagator for array of views.
Definition: element.hh:203
RelTest rtest_eq_bnd(VX x, VY y)
Test whether views x and y are equal (use bounds information)
Definition: rel-test.hpp:43
static ExecStatus post(Home home, IdxViewArray< VA > &iv, VB x0, VC x1)
Post propagator for .
Definition: view.hpp:284
void update(Space &home, IdxViewArray< View > &x)
Cloning.
Definition: idx-view.hpp:153
IterIdxView(void)
Definition: view.hpp:178
View(Space &home, View &p)
Constructor for cloning p.
Definition: view.hpp:122
@ LO
Cheap.
Definition: core.hpp:513
Value iterator for integer views.
Definition: view.hpp:94
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
bool operator()(void) const
Definition: view.hpp:192
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
Base-class for both propagators and branchers.
Definition: core.hpp:628
@ RT_TRUE
Relation does hold.
Definition: view.hpp:1737
VC x1
View for result.
Definition: element.hh:210
virtual Actor * copy(Space &home)
Perform copying during cloning.
Definition: view.hpp:388
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
@ RT_MAYBE
Relation may hold or not.
Definition: view.hpp:1736
Range iterator for integer views.
Definition: view.hpp:54
void cancel(Space &home, Propagator &p, PropCond pc)
Definition: idx-view.hpp:139
Binary domain consistent equality propagator.
Definition: rel.hh:68
RelTest rtest_eq_dom(VX x, VY y)
Test whether views x and y are equal (use full domain information)
Definition: rel-test.hpp:65
@ RT_FALSE
Relation does not hold.
Definition: view.hpp:1735
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
Bounds consistent element propagator for array of views.
Definition: element.hh:232
Home class for posting propagators
Definition: core.hpp:856
static ExecStatus post(Home home, IdxViewArray< VA > &iv, VB x0, VC x1)
Post propagator for .
Definition: view.hpp:366
Handle to region.
Definition: region.hpp:55
virtual Actor * copy(Space &home)
Perform copying during cloning.
Definition: view.hpp:306
Class for domain-equality test.
Definition: view.hpp:66
Domain consistent element propagator for array of views.
Definition: element.hh:262
ExecStatus scan(Space &home, IdxViewArray< VA > &iv, VB x0, VC x1, Propagator &p, RelTest rt)
Definition: view.hpp:217
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Range iterator for union of iterators.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
int size(void) const
Return the current size.
Definition: idx-view.hpp:105
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
int ModEvent
Type for modification events.
Definition: core.hpp:62
Propagation cost.
Definition: core.hpp:486
const int v[7]
Definition: distinct.cpp:259
Value iterator for indices in index-view map.
Definition: view.hpp:164
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: view.hpp:131
RelTest operator()(VA, VC)
Definition: view.hpp:94
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view.hpp:312
virtual void reschedule(Space &home)
Schedule function.
Definition: view.hpp:140
bool shared(ViewArray< ViewX > x, ViewArray< ViewY > y)
Definition: array.hpp:1466
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition: idx-view.hpp:131
RelTest operator()(VA, VC)
Definition: view.hpp:83
Binary bounds consistent equality propagator.
Definition: rel.hh:134
#define forceinline
Definition: config.hpp:192
ViewDom(Space &home, ViewDom &p)
Constructor for cloning p.
Definition: view.hpp:383
RelTest
Result of testing relation.
Definition: view.hpp:1734
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view.hpp:402
IdxViewArray< VA > iv
Current index-view map.
Definition: element.hh:206
Class for pair of index and view.
Definition: idx-view.hh:48
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: view.hpp:148
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
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 PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: view.hpp:395
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
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
void init(const IdxView< View > *, const IdxView< View > *)
Definition: view.hpp:186
Gecode::IntArgs i({1, 2, 3, 4})
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
@ ES_OK
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int val(void) const
Definition: view.hpp:202
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
void operator++(void)
Definition: view.hpp:197
Class for bounds-equality test.
Definition: view.hpp:47
ExecStatus
Definition: core.hpp:472