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