38namespace Gecode {
namespace Int {
namespace Sequence {
79 template<
class View,
class Val,
bool iss>
91 bool violated(
int j,
int q,
int l,
int u)
const;
100 bool conlusion_scheduled(
void)
const;
104 int values(
int j,
int q)
const;
106 bool shaved(
const View&
x, Val s,
int i)
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);
122 void set(
int idx,
int v,
int q,
int n);
124 void potential_violation(
int idx,
int q,
int n);
132 template<
class View,
class Val,
bool iss>
138 template<
class View,
class Val,
bool iss>
144 template<
class View,
class Val,
bool iss>
146 ViewValSupport<View,Val,iss>::next_potential_violation(
void) {
147 return static_cast<int>(v.get());
150 template<
class View,
class Val,
bool iss>
152 ViewValSupport<View,Val,iss>::potential_violation(
int k) {
153 v.add(
static_cast<unsigned int>(k));
157 template<
class View,
class Val,
bool iss>
163 template<
class View,
class Val,
bool iss>
169 template<
class View,
class Val,
bool iss>
171 ViewValSupport<View,Val,iss>::alternative_not_possible
174 return includes(a[idx-1],s) || (iss && (idx-1 == i));
177 template<
class View,
class Val,
bool iss>
179 ViewValSupport<View,Val,iss>::s_not_possible
182 return excludes(a[idx-1],s) || (!iss && (i == idx-1));
186 template<
class View,
class Val,
bool iss>
191 v.init(home,
static_cast<unsigned int>(a.
size()));
193 for (
int l=0; l<a.
size(); l++ ) {
194 if ( alternative_not_possible(a,s,i,l+1) ) {
200 potential_violation(l+1-q);
202 if ( l <= a.
size() - q ) {
203 potential_violation(l);
209 template<
class View,
class Val,
bool iss>
217 for (
int l=0; l<n0; l++ ) {
220 v.update(home,vvs.v);
225 template<
class View,
class Val,
bool iss>
234 template<
class View,
class Val,
bool iss>
236 ViewValSupport<View,Val,iss>::schedule_conclusion(
ViewArray<View>& a, Val s,
242 potential_violation(0);
248 template<
class View,
class Val,
bool iss>
250 ViewValSupport<View,Val,iss>::conlusion_scheduled(
void)
const {
251 return !retired() &&
y[0] > 0;
254 template<
class View,
class Val,
bool iss>
256 ViewValSupport<View,Val,iss>::values(
int j,
int q)
const {
260 template<
class View,
class Val,
bool iss>
266 template<
class View,
class Val,
bool iss>
281 template<
class View,
class Val,
bool iss>
283 ViewValSupport<View,Val,iss>::potential_violation(
int idx,
int q,
int n) {
285 potential_violation(idx-q);
287 if ( idx <= n - q - 1) {
288 potential_violation(idx);
292 template<
class View,
class Val,
bool iss>
294 ViewValSupport<View,Val,iss>::set(
int idx,
int v,
int q,
int n) {
298 potential_violation(idx,q,n);
302 template<
class View,
class Val,
bool iss>
304 ViewValSupport<View,Val,iss>::pushup(ViewArray<View>& a,Val s,
int i,
int q,
int idx,
int v) {
306 int n =
a.
size() + 1;
308 set(idx,
y[idx]+v,q,n);
310 if (
y[idx] > idx ) {
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);
321 set(idx-1,
y[idx]-1,q,n);
323 if (
y[idx-1]>idx-1 ) {
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);
336 set(idx+1,
y[idx],q,n);
345 template<
class View,
class Val,
bool iss>
348 Val s,
int i,
int q,
int j,
352 if ((j == i) && shaved(a[j],s,j)) {
355 switch (
takes(a[j],s)) {
357 if (
y[j+1]-
y[j] == 0) {
358 if (!pushup(a,s,i,q,j+1,1)) {
364 if (
y[j+1]-
y[j] > 0) {
365 if (!pushup(a,s,i,q,j,
y[j+1]-
y[j])) {
376 if ( has_potential_violation() )
384 template<
class View,
class Val,
bool iss>
388 if ( conlusion_scheduled() ) {
389 return conclude(home,a,s,i);
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);
400 if (!pushup(a,s,i,q,j,forced_to_s-u))
401 return conclude(home,a,s,i);
403 if (violated(j,q,l,u))
404 return conclude(home,a,s,i);
411 template<
class View,
class Val,
bool iss>
415 template<
class View,
class Val,
bool iss>
420 template<
class View,
class Val,
bool iss>
425 for (
int i = n; i--; ) {
426 xs[i].init(home,
x,s,i,q);
431 template<
class View,
class Val,
bool iss>
439 template<
class View,
class Val,
bool iss>
445 template<
class View,
class Val,
bool iss>
448 assert((i >= 0) && (i < size()));
452 template<
class View,
class Val,
bool iss>
455 assert((i >= 0) && (i < size()));
459 template<
class View,
class Val,
bool iss>
465 for (
int i=n; i--; ) {
466 xs[i].update(home,a[i],n+1);
471 template<
class View,
class Val,
bool iss>
474 for (
int i=n; i--; ) {
480 template<
class View,
class Val,
bool iss>
484 for (
int i=n; i--; ) {
485 if (
ES_NOFIX == xs[i].advise(home,a,s,i,q,j,d) )
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Generic domain change information to be supplied to advisors.
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Class for advising the propagator.
SupportAdvisor(Space &home, Propagator &p, Council< SupportAdvisor > &c, int i0)
Initialize.
void dispose(Space &home, Council< SupportAdvisor > &c)
Dispose advisor.
An array of ViewValSupport data structures.
ViewValSupportArray(void)
Default constructor.
void update(Space &home, ViewValSupportArray< View, Val, iss > &x)
Cloning.
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int q, int j, const Delta &d)
Advise.
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int q, int l, int u)
Propagate.
int size(void) const
Return the current size.
ViewValSupport< View, Val, iss > & operator[](int n)
Access element n.
Class for view value support structure.
static ViewValSupport * allocate(Space &, int)
Allocate an instance.
void update(Space &home, ViewValSupport< View, Val, iss > &vvs, int n0)
Update.
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int i, int q, int l, int u)
Propagate.
bool violated(int j, int q, int l, int u) const
Return true if sequence j has been violated.
void init(Space &home, ViewArray< View > &x, Val s, int i, int q)
Initialize.
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int i, int q, int j, const Delta &d)
Advise.
bool retired(void) const
Check if retired.
Simple bitsets for recording violations.
Base-class for propagators.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
ModEvent exclude(Space &home, View &x, int s)
Prune view x to exclude all values from s.
bool excludes(const View &x, int s)
Test whether all values of view x are excluded from s.
@ TS_MAYBE
Maybe or maybe not.
bool includes(const View &x, int s)
Test whether all values of view x are included in s.
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.
Gecode toplevel namespace
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Post propagator for SetVar SetOpType SetVar y
@ ES_OK
Execution is okay.
@ ES_FIX
Propagation has computed fixpoint.
@ ES_FAILED
Execution has resulted in failure.
@ ES_NOFIX
Propagation has not computed fixpoint.
Post propagator for SetVar x
Gecode::FloatVal a(-8, 5)
#define GECODE_NEVER
Assert that this command is never executed.