42 namespace Gecode {
namespace Int {
namespace Sequence {
84 template<
class View,
class Val,
bool iss>
96 bool violated(
int j,
int q,
int l,
int u)
const;
105 bool conlusion_scheduled(
void)
const;
109 int values(
int j,
int q)
const;
111 bool shaved(
const View& x, Val s,
int i)
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);
127 void set(
int idx,
int v,
int q,
int n);
129 void potential_violation(
int idx,
int q,
int n);
137 template<
class View,
class Val,
bool iss>
143 template<
class View,
class Val,
bool iss>
149 template<
class View,
class Val,
bool iss>
151 ViewValSupport<View,Val,iss>::next_potential_violation(
void) {
152 return static_cast<int>(
v.get());
155 template<
class View,
class Val,
bool iss>
157 ViewValSupport<View,Val,iss>::potential_violation(
int k) {
158 v.add(static_cast<unsigned int>(k));
162 template<
class View,
class Val,
bool iss>
168 template<
class View,
class Val,
bool iss>
174 template<
class View,
class Val,
bool iss>
176 ViewValSupport<View,Val,iss>::alternative_not_possible
179 return includes(a[idx-1],s) || (iss && (idx-1 ==
i));
182 template<
class View,
class Val,
bool iss>
184 ViewValSupport<View,Val,iss>::s_not_possible
187 return excludes(a[idx-1],s) || (!iss && (i == idx-1));
191 template<
class View,
class Val,
bool iss>
196 v.init(home,static_cast<unsigned int>(a.
size()));
198 for (
int l=0;
l<a.
size();
l++ ) {
199 if ( alternative_not_possible(a,s,i,
l+1) ) {
205 potential_violation(
l+1-q);
207 if (
l <= a.
size() - q ) {
208 potential_violation(
l);
214 template<
class View,
class Val,
bool iss>
221 y = home.
alloc<
int>(n0);
222 for (
int l=0;
l<n0;
l++ ) {
225 v.update(home,share,vvs.v);
230 template<
class View,
class Val,
bool iss>
239 template<
class View,
class Val,
bool iss>
241 ViewValSupport<View,Val,iss>::schedule_conclusion(
ViewArray<View>&
a, Val s,
247 potential_violation(0);
253 template<
class View,
class Val,
bool iss>
255 ViewValSupport<View,Val,iss>::conlusion_scheduled(
void)
const {
256 return !retired() && y[0] > 0;
259 template<
class View,
class Val,
bool iss>
265 template<
class View,
class Val,
bool iss>
271 template<
class View,
class Val,
bool iss>
286 template<
class View,
class Val,
bool iss>
288 ViewValSupport<View,Val,iss>::potential_violation(
int idx,
int q,
int n) {
290 potential_violation(idx-q);
292 if ( idx <= n - q - 1) {
293 potential_violation(idx);
297 template<
class View,
class Val,
bool iss>
299 ViewValSupport<View,Val,iss>::set(
int idx,
int v,
int q,
int n) {
303 potential_violation(idx,q,n);
307 template<
class View,
class Val,
bool iss>
309 ViewValSupport<View,Val,iss>::pushup(ViewArray<View>& a,Val s,
int i,
int q,
int idx,
int v) {
311 int n = a.size() + 1;
313 set(idx,y[idx]+v,q,n);
315 if ( y[idx] > idx ) {
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);
326 set(idx-1,y[idx]-1,q,n);
328 if ( y[idx-1]>idx-1 ) {
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);
341 set(idx+1,y[idx],q,n);
350 template<
class View,
class Val,
bool iss>
353 Val s,
int i,
int q,
int j,
357 if ((j == i) && shaved(a[j],s,j)) {
360 switch (
takes(a[j],s)) {
362 if (y[j+1]-y[j] == 0) {
363 if (!pushup(a,s,i,q,j+1,1)) {
369 if (y[j+1]-y[j] > 0) {
370 if (!pushup(a,s,i,q,j,y[j+1]-y[j])) {
381 if ( has_potential_violation() )
389 template<
class View,
class Val,
bool iss>
393 if ( conlusion_scheduled() ) {
394 return conclude(home,a,s,i);
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);
405 if (!pushup(a,s,i,q,j,forced_to_s-u))
406 return conclude(home,a,s,i);
408 if (violated(j,q,l,u))
409 return conclude(home,a,s,i);
416 template<
class View,
class Val,
bool iss>
420 template<
class View,
class Val,
bool iss>
425 template<
class View,
class Val,
bool iss>
430 for (
int i = n; i--; ) {
431 xs[
i].init(home,x,s,i,q);
436 template<
class View,
class Val,
bool iss>
444 template<
class View,
class Val,
bool iss>
450 template<
class View,
class Val,
bool iss>
453 assert((i >= 0) && (i <
size()));
457 template<
class View,
class Val,
bool iss>
460 assert((i >= 0) && (i <
size()));
464 template<
class View,
class Val,
bool iss>
470 for (
int i=n; i--; ) {
471 xs[
i].update(home,share,a[i],n+1);
476 template<
class View,
class Val,
bool iss>
479 for (
int i=n; i--; ) {
485 template<
class View,
class Val,
bool iss>
489 for (
int i=n; i--; ) {
490 if (
ES_NOFIX == xs[i].advise(home,a,s,i,q,j,d) )
bool violated(int j, int q, int l, int u) const
Return true if sequence j has been violated.
bool includes(const View &x, int s)
Test whether all values of view x are included in s.
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int q, int j, const Delta &d)
Advise.
Base-class for propagators.
An array of ViewValSupport data structures.
Propagation has computed fixpoint.
bool retired(void) const
Check if retired.
Class for view value support structure.
ModEvent exclude(Space &home, View &x, int s)
Prune view x to exclude all values from s.
void init(Space &home, ViewArray< View > &x, Val s, int i, int q)
Initialize.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int q, int l, int u)
Propagate.
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int i, int q, int j, const Delta &d)
Advise.
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Simple bitsets for recording violations.
Execution has resulted in failure.
unsigned int size(I &i)
Size of all ranges of range iterator i.
SupportAdvisor(Space &home, Propagator &p, Council< SupportAdvisor > &c, int i0)
Initialize.
ViewValSupport< View, Val, iss > & operator[](int n)
Access element n.
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int i, int q, int l, int u)
Propagate.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
void dispose(Space &home, Council< SupportAdvisor > &c)
Dispose advisor.
void values(Home home, const IntVarArgs &x, IntSet y, IntConLevel icl=ICL_DEF)
Post constraint .
void update(Space &home, bool share, ViewValSupport< View, Val, iss > &vvs, int n0)
Update.
Node * x
Pointer to corresponding Boolean expression node.
Generic domain change information to be supplied to advisors.
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
ModEvent include(Space &home, View &x, int s)
Prune view x to only include values from s.
TakesStatus takes(const View &x, int s)
Return whether view x takes value s.
Propagation has not computed fixpoint.
static ViewValSupport * allocate(Space &, int)
Allocate an instance.
bool excludes(const View &x, int s)
Test whether all values of view x are excluded from s.
int size(void) const
Return size of array (number of elements)
Gecode toplevel namespace
int size(void) const
Return the current size.
#define GECODE_NEVER
Assert that this command is never executed.
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Class for advising the propagator.
ViewValSupportArray(void)
Default constructor.
void update(Space &home, bool share, ViewValSupportArray< View, Val, iss > &x)
Cloning.