Generated on Sat Oct 20 2018 12:43:45 for Gecode by doxygen 1.8.13
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  * David Rijsman <David.Rijsman@quintiq.com>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * David Rijsman, 2009
11  * Christian Schulte, 2009
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 namespace Gecode { namespace Int { namespace Sequence {
39 
43  template<class View>
44  class SupportAdvisor : public Advisor {
45  public:
47  int i;
50  int i0);
54  void dispose(Space& home, Council<SupportAdvisor>& c);
55  };
56 
57  template<class View>
60  Council<SupportAdvisor>& c,int i0)
61  : Advisor(home,p,c), i(i0) {
62  }
63 
64  template<class View>
67  : Advisor(home,a), i(a.i) {
68  }
69 
70  template<class View>
71  forceinline void
73  Advisor::dispose(home,c);
74  }
75 
79  template<class View, class Val, bool iss>
81  public:
83  void init(Space& home, ViewArray<View>& x,Val s, int i, int q);
85  void update(Space& home, ViewValSupport<View,Val,iss>& vvs, int n0);
87  ExecStatus advise(Space& home,ViewArray<View>& a,Val s,int i,int q, int j,const Delta& d);
89  ExecStatus propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u);
91  bool violated(int j, int q, int l, int u) const;
93  bool retired(void) const;
95  static ViewValSupport* allocate(Space&,int);
96  private:
98  ExecStatus schedule_conclusion(ViewArray<View>& a,Val s,int i);
100  bool conlusion_scheduled(void) const;
102  void retire(void);
104  int values(int j, int q) const;
106  bool shaved(const View& x, Val s, int i) const;
108  bool pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v);
110  ExecStatus conclude(Space& home,ViewArray<View>& a,Val s,int i);
112  bool s_not_possible(ViewArray<View>& a, Val s, int i, int idx) const;
114  bool alternative_not_possible(ViewArray<View>& a,Val s,int i, int idx) const;
116  bool has_potential_violation(void) const;
118  int next_potential_violation(void);
120  void potential_violation(int i);
121  // Sets element idx of cumulative array to v
122  void set(int idx, int v, int q, int n);
124  void potential_violation(int idx, int q, int n);
126  int* y;
128  Violations v;
129  };
130 
131 
132  template<class View, class Val, bool iss>
135  return home.alloc<ViewValSupport<View,Val,iss> >(n);
136  }
137 
138  template<class View, class Val, bool iss>
139  forceinline bool
141  return !v.empty();
142  }
143 
144  template<class View, class Val, bool iss>
145  forceinline int
147  return static_cast<int>(v.get());
148  }
149 
150  template<class View, class Val, bool iss>
151  forceinline void
153  v.add(static_cast<unsigned int>(k));
154  }
155 
156 
157  template<class View, class Val, bool iss>
158  forceinline bool
160  return NULL == y;
161  }
162 
163  template<class View, class Val, bool iss>
164  forceinline void
166  y = NULL;
167  }
168 
169  template<class View,class Val, bool iss>
170  forceinline bool
172  (ViewArray<View>& a, Val s, int i, int idx) const {
173  (void) i;
174  return includes(a[idx-1],s) || (iss && (idx-1 == i));
175  }
176 
177  template<class View, class Val, bool iss>
178  forceinline bool
180  (ViewArray<View>& a, Val s, int i, int idx) const {
181  (void) i;
182  return excludes(a[idx-1],s) || (!iss && (i == idx-1));
183  }
184 
185 
186  template<class View, class Val, bool iss>
187  forceinline void
189  int i, int q) {
190  y = home.alloc<int>(a.size()+1);
191  v.init(home,static_cast<unsigned int>(a.size()));
192  y[0] = 0;
193  for ( int l=0; l<a.size(); l++ ) {
194  if ( alternative_not_possible(a,s,i,l+1) ) {
195  y[l+1] = y[l] + 1;
196  } else {
197  y[l+1] = y[l];
198  }
199  if ( l+1 >= q ) {
200  potential_violation(l+1-q);
201  }
202  if ( l <= a.size() - q ) {
203  potential_violation(l);
204  }
205 
206  }
207  }
208 
209  template<class View, class Val, bool iss>
210  forceinline void
213  int n0) {
214  y = NULL;
215  if ( !vvs.retired() ) {
216  y = home.alloc<int>(n0);
217  for ( int l=0; l<n0; l++ ) {
218  y[l] = vvs.y[l];
219  }
220  v.update(home,vvs.v);
221  // = &home.construct<S>(S::key_compare(),S::allocator_type(home));
222  }
223  }
224 
225  template<class View,class Val, bool iss>
226  forceinline bool
227  ViewValSupport<View,Val,iss>::shaved(const View& x, Val s, int) const {
228  if (iss)
229  return excludes(x,s);
230  else
231  return includes(x,s);
232  }
233 
234  template<class View,class Val, bool iss>
237  int i) {
238  if (!retired()) {
239  if ((iss && includes(a[i],s)) || (!iss && excludes(a[i],s)))
240  return ES_FAILED;
241  y[0] = 1;
242  potential_violation(0);
243  }
244 
245  return ES_OK;
246  }
247 
248  template<class View,class Val, bool iss>
249  forceinline bool
251  return !retired() && y[0] > 0;
252  }
253 
254  template<class View,class Val, bool iss>
255  forceinline int
256  ViewValSupport<View,Val,iss>::values(int j, int q) const {
257  return y[j+q]-y[j];
258  }
259 
260  template<class View,class Val,bool iss>
261  forceinline bool
262  ViewValSupport<View,Val,iss>::violated(int j, int q, int l, int u) const {
263  return values(j,q) < l || values(j,q) > u;
264  }
265 
266  template<class View,class Val,bool iss>
269  Val s, int i) {
270  if ( iss ) {
271  GECODE_ME_CHECK(exclude(home,a[i],s));
272  } else {
273  GECODE_ME_CHECK(include(home,a[i],s));
274  }
275 
276  retire();
277 
278  return ES_OK;
279  }
280 
281  template<class View,class Val,bool iss>
282  forceinline void
284  if ( idx >= q ) {
285  potential_violation(idx-q);
286  }
287  if ( idx <= n - q - 1) {
288  potential_violation(idx);
289  }
290  }
291 
292  template<class View,class Val,bool iss>
293  forceinline void
294  ViewValSupport<View,Val,iss>::set(int idx, int v, int q, int n) {
295  assert(y[idx]<=v);
296  if ( y[idx] < v ) {
297  y[idx] = v;
298  potential_violation(idx,q,n);
299  }
300  }
301 
302  template<class View,class Val,bool iss>
303  forceinline bool
304  ViewValSupport<View,Val,iss>::pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v) {
305  if ( !retired() ) {
306  int n = a.size() + 1;
307 
308  set(idx,y[idx]+v,q,n);
309 
310  if ( y[idx] > idx ) {
311  return false;
312  }
313 
314  int t = idx;
315 
316  // repair y on the left
317  while ( idx > 0 && ((y[idx]-y[idx-1]>1) || ((y[idx]-y[idx-1]==1 && s_not_possible(a,s,i,idx)))) ) {
318  if ( s_not_possible(a,s,i,idx) ) {
319  set(idx-1,y[idx],q,n);
320  } else {
321  set(idx-1,y[idx]-1,q,n);
322  }
323  if ( y[idx-1]>idx-1 ) {
324  return false;
325  }
326  idx -= 1;
327  }
328 
329  idx = t;
330 
331  // repair y on the right
332  while ( idx < a.size() && ((y[idx]-y[idx+1]>0) || ((y[idx]-y[idx+1]==0) && alternative_not_possible(a,s,i,idx+1))) ) {
333  if ( alternative_not_possible(a,s,i,idx+1) ) {
334  set(idx+1,y[idx]+1,q,n);
335  } else {
336  set(idx+1,y[idx],q,n);
337  }
338  idx += 1;
339  }
340  }
341 
342  return true;
343  }
344 
345  template<class View,class Val,bool iss>
348  Val s,int i,int q, int j,
349  const Delta&) {
350  ExecStatus status = ES_FIX;
351  if (!retired()) {
352  if ((j == i) && shaved(a[j],s,j)) {
353  retire();
354  } else {
355  switch (takes(a[j],s)) {
356  case TS_YES:
357  if (y[j+1]-y[j] == 0) {
358  if (!pushup(a,s,i,q,j+1,1)) {
359  GECODE_ES_CHECK(schedule_conclusion(a,s,i));
360  }
361  }
362  break;
363  case TS_NO:
364  if (y[j+1]-y[j] > 0) {
365  if (!pushup(a,s,i,q,j,y[j+1]-y[j])) {
366  GECODE_ES_CHECK(schedule_conclusion(a,s,i));
367  }
368  }
369  break;
370  case TS_MAYBE:
371  break;
372  default:
373  GECODE_NEVER;
374  }
375 
376  if ( has_potential_violation() )
377  status = ES_NOFIX;
378  }
379  }
380 
381  return status;
382  }
383 
384  template<class View,class Val,bool iss>
386  ViewValSupport<View,Val,iss>::propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u) {
387  if ( !retired() ) {
388  if ( conlusion_scheduled() ) {
389  return conclude(home,a,s,i);
390  }
391 
392  while (has_potential_violation()) {
393  int j = next_potential_violation();
394  if (violated(j,q,l,u)) {
395  int forced_to_s = values(j,q);
396  if (forced_to_s < l) {
397  if (!pushup(a,s,i,q,j+q,l-forced_to_s))
398  return conclude(home,a,s,i);
399  } else {
400  if (!pushup(a,s,i,q,j,forced_to_s-u))
401  return conclude(home,a,s,i);
402  }
403  if (violated(j,q,l,u))
404  return conclude(home,a,s,i);
405  }
406  }
407  }
408  return ES_OK;
409  }
410 
411  template<class View,class Val,bool iss>
413  }
414 
415  template<class View,class Val,bool iss>
417  n = a.n; xs = a.xs;
418  }
419 
420  template<class View,class Val,bool iss>
422  n = x.size();
423  if ( n > 0 ) {
425  for (int i = n; i--; ) {
426  xs[i].init(home,x,s,i,q);
427  }
428  }
429  }
430 
431  template<class View,class Val,bool iss>
433  n = n0;
434  if (n>0) {
436  }
437  }
438 
439  template<class View,class Val,bool iss>
440  forceinline int
442  return n;
443  }
444 
445  template<class View,class Val,bool iss>
448  assert((i >= 0) && (i < size()));
449  return xs[i];
450  }
451 
452  template<class View,class Val,bool iss>
455  assert((i >= 0) && (i < size()));
456  return xs[i];
457  }
458 
459  template<class View,class Val,bool iss>
460  void
462  n = a.size();
463  if (n>0) {
465  for (int i=n; i--; ) {
466  xs[i].update(home,a[i],n+1);
467  }
468  }
469  }
470 
471  template<class View,class Val,bool iss>
472  ExecStatus
474  for (int i=n; i--; ) {
475  GECODE_ES_CHECK(xs[i].propagate(home,a,s,i,q,l,u));
476  }
477  return ES_OK;
478  }
479 
480  template<class View,class Val,bool iss>
481  ExecStatus
483  ExecStatus status = ES_FIX;
484  for (int i=n; i--; ) {
485  if ( ES_NOFIX == xs[i].advise(home,a,s,i,q,j,d) )
486  status = ES_NOFIX;
487  }
488  return status;
489  }
490 }}}
491 
492 
493 // STATISTICS: int-prop
494 
Council of advisors
Definition: core.hpp:154
NodeType t
Type of node.
Definition: bool-expr.cpp:230
bool violated(int j, int q, int l, int u) const
Return true if sequence j has been violated.
Definition: view.hpp:262
bool includes(const View &x, int s)
Test whether all values of view x are included in s.
Definition: set-op.hpp:72
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
Definitely not.
Definition: set-op.hpp:38
void update(Space &home, ViewValSupport< View, Val, iss > &vvs, int n0)
Update.
Definition: view.hpp:211
Maybe or maybe not.
Definition: set-op.hpp:40
Base-class for propagators.
Definition: core.hpp:1023
Base-class for advisors.
Definition: core.hpp:1251
An array of ViewValSupport data structures.
Definition: sequence.hh:65
#define forceinline
Definition: config.hpp:185
Propagation has computed fixpoint.
Definition: core.hpp:476
Computation spaces.
Definition: core.hpp:1701
Class for view value support structure.
Definition: view.hpp:80
ModEvent exclude(Space &home, View &x, int s)
Prune view x to exclude all values from s.
Definition: set-op.hpp:137
void init(Space &home, ViewArray< View > &x, Val s, int i, int q)
Initialize.
Definition: view.hpp:188
Gecode::IntSet d(v, 7)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2794
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int i, int q, int j, const Delta &d)
Advise.
Definition: view.hpp:347
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Simple bitsets for recording violations.
Definition: violations.hpp:40
Gecode::IntArgs i({1, 2, 3, 4})
Execution has resulted in failure.
Definition: core.hpp:473
unsigned int size(I &i)
Size of all ranges of range iterator i.
SupportAdvisor(Space &home, Propagator &p, Council< SupportAdvisor > &c, int i0)
Initialize.
Definition: view.hpp:59
View arrays.
Definition: array.hpp:235
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int i, int q, int l, int u)
Propagate.
Definition: view.hpp:386
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
union Gecode::@593::NNF::@62 u
Union depending on nodetype t.
void dispose(Space &home, Council< SupportAdvisor > &c)
Dispose advisor.
Definition: view.hpp:72
const int v[7]
Definition: distinct.cpp:259
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Generic domain change information to be supplied to advisors.
Definition: core.hpp:203
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition: core.hpp:3791
ModEvent include(Space &home, View &x, int s)
Prune view x to only include values from s.
Definition: set-op.hpp:123
ExecStatus
Definition: core.hpp:471
TakesStatus takes(const View &x, int s)
Return whether view x takes value s.
Definition: set-op.hpp:46
bool retired(void) const
Check if retired.
Definition: view.hpp:159
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition: minimodel.hh:1993
Post propagator for SetVar x
Definition: set.hh:767
Execution is okay.
Definition: core.hpp:475
Propagation has not computed fixpoint.
Definition: core.hpp:474
Definitely yes.
Definition: set-op.hpp:39
static ViewValSupport * allocate(Space &, int)
Allocate an instance.
Definition: view.hpp:134
bool excludes(const View &x, int s)
Test whether all values of view x are excluded from s.
Definition: set-op.hpp:89
Gecode toplevel namespace
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1138
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
void update(IntSet &y, Space &home, IntSet &py)
Definition: rel.hpp:103
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
Class for advising the propagator.
Definition: view.hpp:44
ViewValSupportArray(void)
Default constructor.
Definition: view.hpp:412
int size(void) const
Return the current size.
Definition: view.hpp:441