Generated on Sat Feb 7 2015 02:01:17 for Gecode by doxygen 1.8.9.1
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: 2011-05-23 16:48:31 +0200 (Mon, 23 May 2011) $
15  * $Revision: 12018 $
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);
56  SupportAdvisor(Space& home, bool share, SupportAdvisor& a);
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>
72  : Advisor(home,share,a), i(a.i) {
73  }
74 
75  template<class View>
76  forceinline void
78  Advisor::dispose(home,c);
79  }
80 
84  template<class View, class Val,bool iss>
86  public:
88  void init(Space& home, ViewArray<View>& x,Val s, int i, int q);
90  void update(Space& home, bool share, ViewValSupport<View,Val,iss>& vvs, int n0);
92  ExecStatus advise(Space& home,ViewArray<View>& a,Val s,int i,int q, int j,const Delta& d);
94  ExecStatus propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u);
96  bool violated(int j, int q, int l, int u) const;
98  bool retired(void) const;
100  static ViewValSupport* allocate(Space&,int);
101  private:
103  ExecStatus schedule_conclusion(ViewArray<View>& a,Val s,int i);
105  bool conlusion_scheduled(void) const;
107  void retire(void);
109  int values(int j, int q) const;
111  bool shaved(const View& x, Val s, int i) const;
113  bool pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v);
115  ExecStatus conclude(Space& home,ViewArray<View>& a,Val s,int i);
117  bool s_not_possible(ViewArray<View>& a, Val s, int i, int idx) const;
119  bool alternative_not_possible(ViewArray<View>& a,Val s,int i, int idx) const;
121  bool has_potential_violation(void) const;
123  int next_potential_violation(void);
125  void potential_violation(int i);
126  // Sets element idx of cumulative array to v
127  void set(int idx, int v, int q, int n);
129  void potential_violation(int idx, int q, int n);
131  int* y;
133  Violations v;
134  };
135 
136 
137  template<class View, class Val,bool iss>
140  return home.alloc<ViewValSupport<View,Val,iss> >(n);
141  }
142 
143  template<class View, class Val,bool iss>
144  forceinline bool
146  return !v.empty();
147  }
148 
149  template<class View, class Val,bool iss>
150  forceinline int
151  ViewValSupport<View,Val,iss>::next_potential_violation(void) {
152  return static_cast<int>(v.get());
153  }
154 
155  template<class View, class Val,bool iss>
156  forceinline void
157  ViewValSupport<View,Val,iss>::potential_violation(int k) {
158  v.add(static_cast<unsigned int>(k));
159  }
160 
161 
162  template<class View, class Val,bool iss>
163  forceinline bool
165  return NULL == y;
166  }
167 
168  template<class View, class Val,bool iss>
169  forceinline void
171  y = NULL;
172  }
173 
174  template<class View,class Val,bool iss>
175  forceinline bool
176  ViewValSupport<View,Val,iss>::alternative_not_possible
177  (ViewArray<View>& a, Val s, int i, int idx) const {
178  (void) i;
179  return includes(a[idx-1],s) || (iss && (idx-1 == i));
180  }
181 
182  template<class View, class Val,bool iss>
183  forceinline bool
184  ViewValSupport<View,Val,iss>::s_not_possible
185  (ViewArray<View>& a, Val s, int i, int idx) const {
186  (void) i;
187  return excludes(a[idx-1],s) || (!iss && (i == idx-1));
188  }
189 
190 
191  template<class View, class Val,bool iss>
192  forceinline void
194  int i, int q) {
195  y = home.alloc<int>(a.size()+1);
196  v.init(home,static_cast<unsigned int>(a.size()));
197  y[0] = 0;
198  for ( int l=0; l<a.size(); l++ ) {
199  if ( alternative_not_possible(a,s,i,l+1) ) {
200  y[l+1] = y[l] + 1;
201  } else {
202  y[l+1] = y[l];
203  }
204  if ( l+1 >= q ) {
205  potential_violation(l+1-q);
206  }
207  if ( l <= a.size() - q ) {
208  potential_violation(l);
209  }
210 
211  }
212  }
213 
214  template<class View, class Val,bool iss>
215  forceinline void
218  int n0) {
219  y = NULL;
220  if ( !vvs.retired() ) {
221  y = home.alloc<int>(n0);
222  for ( int l=0; l<n0; l++ ) {
223  y[l] = vvs.y[l];
224  }
225  v.update(home,share,vvs.v);
226  // = &home.construct<S>(S::key_compare(),S::allocator_type(home));
227  }
228  }
229 
230  template<class View,class Val,bool iss>
231  forceinline bool
232  ViewValSupport<View,Val,iss>::shaved(const View& x, Val s, int) const {
233  if (iss)
234  return excludes(x,s);
235  else
236  return includes(x,s);
237  }
238 
239  template<class View,class Val,bool iss>
241  ViewValSupport<View,Val,iss>::schedule_conclusion(ViewArray<View>& a, Val s,
242  int i) {
243  if (!retired()) {
244  if ((iss && includes(a[i],s)) || (!iss && excludes(a[i],s)))
245  return ES_FAILED;
246  y[0] = 1;
247  potential_violation(0);
248  }
249 
250  return ES_OK;
251  }
252 
253  template<class View,class Val,bool iss>
254  forceinline bool
255  ViewValSupport<View,Val,iss>::conlusion_scheduled(void) const {
256  return !retired() && y[0] > 0;
257  }
258 
259  template<class View,class Val,bool iss>
260  forceinline int
261  ViewValSupport<View,Val,iss>::values(int j, int q) const {
262  return y[j+q]-y[j];
263  }
264 
265  template<class View,class Val,bool iss>
266  forceinline bool
267  ViewValSupport<View,Val,iss>::violated(int j, int q, int l, int u) const {
268  return values(j,q) < l || values(j,q) > u;
269  }
270 
271  template<class View,class Val,bool iss>
274  Val s, int i) {
275  if ( iss ) {
276  GECODE_ME_CHECK(exclude(home,a[i],s));
277  } else {
278  GECODE_ME_CHECK(include(home,a[i],s));
279  }
280 
281  retire();
282 
283  return ES_OK;
284  }
285 
286  template<class View,class Val,bool iss>
287  forceinline void
288  ViewValSupport<View,Val,iss>::potential_violation(int idx, int q, int n) {
289  if ( idx >= q ) {
290  potential_violation(idx-q);
291  }
292  if ( idx <= n - q - 1) {
293  potential_violation(idx);
294  }
295  }
296 
297  template<class View,class Val,bool iss>
298  forceinline void
299  ViewValSupport<View,Val,iss>::set(int idx, int v, int q, int n) {
300  assert(y[idx]<=v);
301  if ( y[idx] < v ) {
302  y[idx] = v;
303  potential_violation(idx,q,n);
304  }
305  }
306 
307  template<class View,class Val,bool iss>
308  forceinline bool
309  ViewValSupport<View,Val,iss>::pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v) {
310  if ( !retired() ) {
311  int n = a.size() + 1;
312 
313  set(idx,y[idx]+v,q,n);
314 
315  if ( y[idx] > idx ) {
316  return false;
317  }
318 
319  int t = idx;
320 
321  // repair y on the left
322  while ( idx > 0 && ((y[idx]-y[idx-1]>1) || ((y[idx]-y[idx-1]==1 && s_not_possible(a,s,i,idx)))) ) {
323  if ( s_not_possible(a,s,i,idx) ) {
324  set(idx-1,y[idx],q,n);
325  } else {
326  set(idx-1,y[idx]-1,q,n);
327  }
328  if ( y[idx-1]>idx-1 ) {
329  return false;
330  }
331  idx -= 1;
332  }
333 
334  idx = t;
335 
336  // repair y on the right
337  while ( idx < a.size() && ((y[idx]-y[idx+1]>0) || ((y[idx]-y[idx+1]==0) && alternative_not_possible(a,s,i,idx+1))) ) {
338  if ( alternative_not_possible(a,s,i,idx+1) ) {
339  set(idx+1,y[idx]+1,q,n);
340  } else {
341  set(idx+1,y[idx],q,n);
342  }
343  idx += 1;
344  }
345  }
346 
347  return true;
348  }
349 
350  template<class View,class Val,bool iss>
353  Val s,int i,int q, int j,
354  const Delta&) {
355  ExecStatus status = ES_FIX;
356  if (!retired()) {
357  if ((j == i) && shaved(a[j],s,j)) {
358  retire();
359  } else {
360  switch (takes(a[j],s)) {
361  case TS_YES:
362  if (y[j+1]-y[j] == 0) {
363  if (!pushup(a,s,i,q,j+1,1)) {
364  GECODE_ES_CHECK(schedule_conclusion(a,s,i));
365  }
366  }
367  break;
368  case TS_NO:
369  if (y[j+1]-y[j] > 0) {
370  if (!pushup(a,s,i,q,j,y[j+1]-y[j])) {
371  GECODE_ES_CHECK(schedule_conclusion(a,s,i));
372  }
373  }
374  break;
375  case TS_MAYBE:
376  break;
377  default:
378  GECODE_NEVER;
379  }
380 
381  if ( has_potential_violation() )
382  status = ES_NOFIX;
383  }
384  }
385 
386  return status;
387  }
388 
389  template<class View,class Val,bool iss>
391  ViewValSupport<View,Val,iss>::propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u) {
392  if ( !retired() ) {
393  if ( conlusion_scheduled() ) {
394  return conclude(home,a,s,i);
395  }
396 
397  while (has_potential_violation()) {
398  int j = next_potential_violation();
399  if (violated(j,q,l,u)) {
400  int forced_to_s = values(j,q);
401  if (forced_to_s < l) {
402  if (!pushup(a,s,i,q,j+q,l-forced_to_s))
403  return conclude(home,a,s,i);
404  } else {
405  if (!pushup(a,s,i,q,j,forced_to_s-u))
406  return conclude(home,a,s,i);
407  }
408  if (violated(j,q,l,u))
409  return conclude(home,a,s,i);
410  }
411  }
412  }
413  return ES_OK;
414  }
415 
416  template<class View,class Val,bool iss>
418  }
419 
420  template<class View,class Val,bool iss>
422  n = a.n; xs = a.xs;
423  }
424 
425  template<class View,class Val,bool iss>
427  n = x.size();
428  if ( n > 0 ) {
430  for (int i = n; i--; ) {
431  xs[i].init(home,x,s,i,q);
432  }
433  }
434  }
435 
436  template<class View,class Val,bool iss>
438  n = n0;
439  if (n>0) {
441  }
442  }
443 
444  template<class View,class Val,bool iss>
445  forceinline int
447  return n;
448  }
449 
450  template<class View,class Val,bool iss>
453  assert((i >= 0) && (i < size()));
454  return xs[i];
455  }
456 
457  template<class View,class Val,bool iss>
460  assert((i >= 0) && (i < size()));
461  return xs[i];
462  }
463 
464  template<class View,class Val,bool iss>
465  void
467  n = a.size();
468  if (n>0) {
470  for (int i=n; i--; ) {
471  xs[i].update(home,share,a[i],n+1);
472  }
473  }
474  }
475 
476  template<class View,class Val,bool iss>
477  ExecStatus
479  for (int i=n; i--; ) {
480  GECODE_ES_CHECK(xs[i].propagate(home,a,s,i,q,l,u));
481  }
482  return ES_OK;
483  }
484 
485  template<class View,class Val,bool iss>
486  ExecStatus
488  ExecStatus status = ES_FIX;
489  for (int i=n; i--; ) {
490  if ( ES_NOFIX == xs[i].advise(home,a,s,i,q,j,d) )
491  status = ES_NOFIX;
492  }
493  return status;
494  }
495 }}}
496 
497 
498 // STATISTICS: int-prop
499 
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:267
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
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int q, int j, const Delta &d)
Advise.
Definition: view.hpp:487
Definitely not.
Definition: set-op.hpp:42
Maybe or maybe not.
Definition: set-op.hpp:44
Base-class for propagators.
Definition: core.hpp:755
Base-class for advisors.
Definition: core.hpp:926
An array of ViewValSupport data structures.
Definition: sequence.hh:69
Propagation has computed fixpoint.
Definition: core.hpp:528
bool retired(void) const
Check if retired.
Definition: view.hpp:164
Computation spaces.
Definition: core.hpp:1362
Class for view value support structure.
Definition: view.hpp:85
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:193
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:2397
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int q, int l, int u)
Propagate.
Definition: view.hpp:478
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int i, int q, int j, const Delta &d)
Advise.
Definition: view.hpp:352
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:525
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:63
ViewValSupport< View, Val, iss > & operator[](int n)
Access element n.
Definition: view.hpp:452
View arrays.
Definition: array.hpp:234
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int i, int q, int l, int u)
Propagate.
Definition: view.hpp:391
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
void dispose(Space &home, Council< SupportAdvisor > &c)
Dispose advisor.
Definition: view.hpp:77
const int v[7]
Definition: distinct.cpp:207
void values(Home home, const IntVarArgs &x, IntSet y, IntConLevel icl=ICL_DEF)
Post constraint .
Definition: minimodel.hh:1869
void update(Space &home, bool share, ViewValSupport< View, Val, iss > &vvs, int n0)
Update.
Definition: view.hpp:216
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:275
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition: core.hpp:3267
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:523
TakesStatus takes(const View &x, int s)
Return whether view x takes value s.
Definition: set-op.hpp:50
#define forceinline
Definition: config.hpp:132
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
Definitely yes.
Definition: set-op.hpp:43
static ViewValSupport * allocate(Space &, int)
Allocate an instance.
Definition: view.hpp:139
bool excludes(const View &x, int s)
Test whether all values of view x are excluded from s.
Definition: set-op.hpp:93
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
int size(void) const
Return the current size.
Definition: view.hpp:446
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Class for advising the propagator.
Definition: view.hpp:48
ViewValSupportArray(void)
Default constructor.
Definition: view.hpp:417
void update(Space &home, bool share, ViewValSupportArray< View, Val, iss > &x)
Cloning.
Definition: view.hpp:466