Go to the documentation of this file.
38 namespace Gecode {
namespace Int {
namespace Sequence {
79 template<
class View,
class Val,
bool iss>
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;
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>
190 y = home.
alloc<
int>(
a.size()+1);
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)) {
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--; ) {
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl)
Post constraint .
bool retired(void) const
Check if retired.
void update(Space &home, ViewValSupportArray< View, Val, iss > &x)
Cloning.
Post propagator for SetVar x
Post propagator for SetVar SetOpType SetVar y
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.
Class for view value support structure.
unsigned int size(I &i)
Size of all ranges of range iterator i.
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int q, int j, const Delta &d)
Advise.
@ TS_MAYBE
Maybe or maybe not.
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.
Simple bitsets for recording violations.
Gecode toplevel namespace
Base-class for propagators.
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Generic domain change information to be supplied to advisors.
int size(void) const
Return the current size.
bool violated(int j, int q, int l, int u) const
Return true if sequence j has been violated.
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int i, int q, int j, const Delta &d)
Advise.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
static ViewValSupport * allocate(Space &, int)
Allocate an instance.
#define GECODE_NEVER
Assert that this command is never executed.
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
void update(Space &home, ViewValSupport< View, Val, iss > &vvs, int n0)
Update.
bool excludes(const View &x, int s)
Test whether all values of view x are excluded from s.
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
@ ES_FIX
Propagation has computed fixpoint.
Class for advising the propagator.
SupportAdvisor(Space &home, Propagator &p, Council< SupportAdvisor > &c, int i0)
Initialize.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
ViewValSupportArray(void)
Default constructor.
ModEvent include(Space &home, View &x, int s)
Prune view x to only include values from s.
void dispose(Space &home, Council< SupportAdvisor > &c)
Dispose advisor.
Gecode::FloatVal c(-8, 8)
TakesStatus takes(const View &x, int s)
Return whether view x takes value s.
int n
Number of negative literals for node type.
@ ES_FAILED
Execution has resulted in failure.
bool includes(const View &x, int s)
Test whether all values of view x are included in s.
@ ES_NOFIX
Propagation has not computed fixpoint.
Gecode::IntArgs i({1, 2, 3, 4})
@ ES_OK
Execution is okay.
int p
Number of positive literals for node type.
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int q, int l, int u)
Propagate.
An array of ViewValSupport data structures.