view.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* David Rijsman <David.Rijsman@quintiq.com>
*
* Contributing authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* David Rijsman, 2009
* Christian Schulte, 2009
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
namespace Gecode { namespace Int { namespace Sequence {
template<class View>
class SupportAdvisor : public Advisor {
public:
int i;
SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c,
int i0);
SupportAdvisor(Space& home, SupportAdvisor& a);
void dispose(Space& home, Council<SupportAdvisor>& c);
};
template<class View>
forceinline
SupportAdvisor<View>::SupportAdvisor(Space& home, Propagator& p,
Council<SupportAdvisor>& c,int i0)
: Advisor(home,p,c), i(i0) {
}
template<class View>
forceinline
SupportAdvisor<View>::SupportAdvisor(Space& home, SupportAdvisor& a)
: Advisor(home,a), i(a.i) {
}
template<class View>
forceinline void
SupportAdvisor<View>::dispose(Space& home, Council<SupportAdvisor>& c) {
Advisor::dispose(home,c);
}
template<class View, class Val, bool iss>
class ViewValSupport {
public:
void init(Space& home, ViewArray<View>& x,Val s, int i, int q);
void update(Space& home, ViewValSupport<View,Val,iss>& vvs, int n0);
ExecStatus advise(Space& home,ViewArray<View>& a,Val s,int i,int q, int j,const Delta& d);
ExecStatus propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u);
bool violated(int j, int q, int l, int u) const;
bool retired(void) const;
static ViewValSupport* allocate(Space&,int);
private:
ExecStatus schedule_conclusion(ViewArray<View>& a,Val s,int i);
bool conlusion_scheduled(void) const;
void retire(void);
int values(int j, int q) const;
bool shaved(const View& x, Val s, int i) const;
bool pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v);
ExecStatus conclude(Space& home,ViewArray<View>& a,Val s,int i);
bool s_not_possible(ViewArray<View>& a, Val s, int i, int idx) const;
bool alternative_not_possible(ViewArray<View>& a,Val s,int i, int idx) const;
bool has_potential_violation(void) const;
int next_potential_violation(void);
void potential_violation(int i);
// Sets element idx of cumulative array to v
void set(int idx, int v, int q, int n);
void potential_violation(int idx, int q, int n);
int* y;
Violations v;
};
template<class View, class Val, bool iss>
forceinline ViewValSupport<View,Val,iss>*
ViewValSupport<View,Val,iss>::allocate(Space& home, int n) {
return home.alloc<ViewValSupport<View,Val,iss> >(n);
}
template<class View, class Val, bool iss>
forceinline bool
ViewValSupport<View,Val,iss>::has_potential_violation(void) const {
return !v.empty();
}
template<class View, class Val, bool iss>
forceinline int
ViewValSupport<View,Val,iss>::next_potential_violation(void) {
return static_cast<int>(v.get());
}
template<class View, class Val, bool iss>
forceinline void
ViewValSupport<View,Val,iss>::potential_violation(int k) {
v.add(static_cast<unsigned int>(k));
}
template<class View, class Val, bool iss>
forceinline bool
ViewValSupport<View,Val,iss>::retired(void) const {
return NULL == y;
}
template<class View, class Val, bool iss>
forceinline void
ViewValSupport<View,Val,iss>::retire(void) {
y = NULL;
}
template<class View,class Val, bool iss>
forceinline bool
ViewValSupport<View,Val,iss>::alternative_not_possible
(ViewArray<View>& a, Val s, int i, int idx) const {
(void) i;
return includes(a[idx-1],s) || (iss && (idx-1 == i));
}
template<class View, class Val, bool iss>
forceinline bool
ViewValSupport<View,Val,iss>::s_not_possible
(ViewArray<View>& a, Val s, int i, int idx) const {
(void) i;
return excludes(a[idx-1],s) || (!iss && (i == idx-1));
}
template<class View, class Val, bool iss>
forceinline void
ViewValSupport<View,Val,iss>::init(Space& home, ViewArray<View>& a, Val s,
int i, int q) {
y = home.alloc<int>(a.size()+1);
v.init(home,static_cast<unsigned int>(a.size()));
y[0] = 0;
for ( int l=0; l<a.size(); l++ ) {
if ( alternative_not_possible(a,s,i,l+1) ) {
y[l+1] = y[l] + 1;
} else {
y[l+1] = y[l];
}
if ( l+1 >= q ) {
potential_violation(l+1-q);
}
if ( l <= a.size() - q ) {
potential_violation(l);
}
}
}
template<class View, class Val, bool iss>
forceinline void
ViewValSupport<View,Val,iss>::update(Space& home,
ViewValSupport<View,Val,iss>& vvs,
int n0) {
y = NULL;
if ( !vvs.retired() ) {
y = home.alloc<int>(n0);
for ( int l=0; l<n0; l++ ) {
y[l] = vvs.y[l];
}
v.update(home,vvs.v);
// = &home.construct<S>(S::key_compare(),S::allocator_type(home));
}
}
template<class View,class Val, bool iss>
forceinline bool
ViewValSupport<View,Val,iss>::shaved(const View& x, Val s, int) const {
if (iss)
return excludes(x,s);
else
return includes(x,s);
}
template<class View,class Val, bool iss>
forceinline ExecStatus
ViewValSupport<View,Val,iss>::schedule_conclusion(ViewArray<View>& a, Val s,
int i) {
if (!retired()) {
if ((iss && includes(a[i],s)) || (!iss && excludes(a[i],s)))
return ES_FAILED;
y[0] = 1;
potential_violation(0);
}
return ES_OK;
}
template<class View,class Val, bool iss>
forceinline bool
ViewValSupport<View,Val,iss>::conlusion_scheduled(void) const {
return !retired() && y[0] > 0;
}
template<class View,class Val, bool iss>
forceinline int
ViewValSupport<View,Val,iss>::values(int j, int q) const {
return y[j+q]-y[j];
}
template<class View,class Val,bool iss>
forceinline bool
ViewValSupport<View,Val,iss>::violated(int j, int q, int l, int u) const {
return values(j,q) < l || values(j,q) > u;
}
template<class View,class Val,bool iss>
forceinline ExecStatus
ViewValSupport<View,Val,iss>::conclude(Space& home,ViewArray<View>& a,
Val s, int i) {
if ( iss ) {
GECODE_ME_CHECK(exclude(home,a[i],s));
} else {
GECODE_ME_CHECK(include(home,a[i],s));
}
retire();
return ES_OK;
}
template<class View,class Val,bool iss>
forceinline void
ViewValSupport<View,Val,iss>::potential_violation(int idx, int q, int n) {
if ( idx >= q ) {
potential_violation(idx-q);
}
if ( idx <= n - q - 1) {
potential_violation(idx);
}
}
template<class View,class Val,bool iss>
forceinline void
ViewValSupport<View,Val,iss>::set(int idx, int v, int q, int n) {
assert(y[idx]<=v);
if ( y[idx] < v ) {
y[idx] = v;
potential_violation(idx,q,n);
}
}
template<class View,class Val,bool iss>
forceinline bool
ViewValSupport<View,Val,iss>::pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v) {
if ( !retired() ) {
int n = a.size() + 1;
set(idx,y[idx]+v,q,n);
if ( y[idx] > idx ) {
return false;
}
int t = idx;
// repair y on the left
while ( idx > 0 && ((y[idx]-y[idx-1]>1) || ((y[idx]-y[idx-1]==1 && s_not_possible(a,s,i,idx)))) ) {
if ( s_not_possible(a,s,i,idx) ) {
set(idx-1,y[idx],q,n);
} else {
set(idx-1,y[idx]-1,q,n);
}
if ( y[idx-1]>idx-1 ) {
return false;
}
idx -= 1;
}
idx = t;
// repair y on the right
while ( idx < a.size() && ((y[idx]-y[idx+1]>0) || ((y[idx]-y[idx+1]==0) && alternative_not_possible(a,s,i,idx+1))) ) {
if ( alternative_not_possible(a,s,i,idx+1) ) {
set(idx+1,y[idx]+1,q,n);
} else {
set(idx+1,y[idx],q,n);
}
idx += 1;
}
}
return true;
}
template<class View,class Val,bool iss>
forceinline ExecStatus
ViewValSupport<View,Val,iss>::advise(Space&, ViewArray<View>& a,
Val s,int i,int q, int j,
const Delta&) {
ExecStatus status = ES_FIX;
if (!retired()) {
if ((j == i) && shaved(a[j],s,j)) {
retire();
} else {
switch (takes(a[j],s)) {
case TS_YES:
if (y[j+1]-y[j] == 0) {
if (!pushup(a,s,i,q,j+1,1)) {
GECODE_ES_CHECK(schedule_conclusion(a,s,i));
}
}
break;
case TS_NO:
if (y[j+1]-y[j] > 0) {
if (!pushup(a,s,i,q,j,y[j+1]-y[j])) {
GECODE_ES_CHECK(schedule_conclusion(a,s,i));
}
}
break;
case TS_MAYBE:
break;
default:
GECODE_NEVER;
}
if ( has_potential_violation() )
status = ES_NOFIX;
}
}
return status;
}
template<class View,class Val,bool iss>
forceinline ExecStatus
ViewValSupport<View,Val,iss>::propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u) {
if ( !retired() ) {
if ( conlusion_scheduled() ) {
return conclude(home,a,s,i);
}
while (has_potential_violation()) {
int j = next_potential_violation();
if (violated(j,q,l,u)) {
int forced_to_s = values(j,q);
if (forced_to_s < l) {
if (!pushup(a,s,i,q,j+q,l-forced_to_s))
return conclude(home,a,s,i);
} else {
if (!pushup(a,s,i,q,j,forced_to_s-u))
return conclude(home,a,s,i);
}
if (violated(j,q,l,u))
return conclude(home,a,s,i);
}
}
}
return ES_OK;
}
template<class View,class Val,bool iss>
ViewValSupportArray<View,Val,iss>::ViewValSupportArray(void) : xs(NULL), n(0) {
}
template<class View,class Val,bool iss>
ViewValSupportArray<View,Val,iss>::ViewValSupportArray(const ViewValSupportArray<View,Val,iss>& a) {
n = a.n; xs = a.xs;
}
template<class View,class Val,bool iss>
ViewValSupportArray<View,Val,iss>::ViewValSupportArray(Space& home,ViewArray<View>& x, Val s, int q) : xs(NULL) {
n = x.size();
if ( n > 0 ) {
xs = ViewValSupport<View,Val,iss>::allocate(home,n);
for (int i = n; i--; ) {
xs[i].init(home,x,s,i,q);
}
}
}
template<class View,class Val,bool iss>
ViewValSupportArray<View,Val,iss>::ViewValSupportArray(Space& home, int n0) : xs(NULL) {
n = n0;
if (n>0) {
xs = ViewValSupport<View,Val,iss>::allocate(home,n);
}
}
template<class View,class Val,bool iss>
forceinline int
ViewValSupportArray<View,Val,iss>::size(void) const {
return n;
}
template<class View,class Val,bool iss>
forceinline ViewValSupport<View,Val,iss>&
ViewValSupportArray<View,Val,iss>::operator [](int i) {
assert((i >= 0) && (i < size()));
return xs[i];
}
template<class View,class Val,bool iss>
forceinline const ViewValSupport<View,Val,iss>&
ViewValSupportArray<View,Val,iss>::operator [](int i) const {
assert((i >= 0) && (i < size()));
return xs[i];
}
template<class View,class Val,bool iss>
void
ViewValSupportArray<View,Val,iss>::update(Space& home, ViewValSupportArray<View,Val,iss>& a) {
n = a.size();
if (n>0) {
xs = ViewValSupport<View,Val,iss>::allocate(home,n);
for (int i=n; i--; ) {
xs[i].update(home,a[i],n+1);
}
}
}
template<class View,class Val,bool iss>
ExecStatus
ViewValSupportArray<View,Val,iss>::propagate(Space& home,ViewArray<View>& a,Val s,int q,int l,int u) {
for (int i=n; i--; ) {
GECODE_ES_CHECK(xs[i].propagate(home,a,s,i,q,l,u));
}
return ES_OK;
}
template<class View,class Val,bool iss>
ExecStatus
ViewValSupportArray<View,Val,iss>::advise(Space& home,ViewArray<View>& a,Val s,int q,int j,const Delta& d) {
ExecStatus status = ES_FIX;
for (int i=n; i--; ) {
if ( ES_NOFIX == xs[i].advise(home,a,s,i,q,j,d) )
status = ES_NOFIX;
}
return status;
}
}}}
// STATISTICS: int-prop
Gecode::ActorLink::Space
friend class Space
Definition core.hpp:595
Gecode::ActorLink::Propagator
friend class Propagator
Definition core.hpp:591
Gecode::Advisor::Advisor
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:3831
Gecode::Advisor::dispose
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition core.hpp:3864
Gecode::Advisor::Council
friend class Council
Definition core.hpp:1294
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::FloatVal::size
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
Gecode::Int::Sequence::SupportAdvisor::SupportAdvisor
SupportAdvisor(Space &home, Propagator &p, Council< SupportAdvisor > &c, int i0)
Initialize.
Definition view.hpp:59
Gecode::Int::Sequence::SupportAdvisor::i
int i
Index position.
Definition view.hpp:47
Gecode::Int::Sequence::SupportAdvisor::dispose
void dispose(Space &home, Council< SupportAdvisor > &c)
Dispose advisor.
Definition view.hpp:72
Gecode::Int::Sequence::ViewValSupportArray::ViewValSupportArray
ViewValSupportArray(void)
Default constructor.
Definition view.hpp:412
Gecode::Int::Sequence::ViewValSupportArray::update
void update(Space &home, ViewValSupportArray< View, Val, iss > &x)
Cloning.
Definition view.hpp:461
Gecode::Int::Sequence::ViewValSupportArray::advise
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int q, int j, const Delta &d)
Advise.
Definition view.hpp:482
Gecode::Int::Sequence::ViewValSupportArray::propagate
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int q, int l, int u)
Propagate.
Definition view.hpp:473
Gecode::Int::Sequence::ViewValSupportArray::size
int size(void) const
Return the current size.
Definition view.hpp:441
Gecode::Int::Sequence::ViewValSupportArray::operator[]
ViewValSupport< View, Val, iss > & operator[](int n)
Access element n.
Definition view.hpp:447
Gecode::Int::Sequence::ViewValSupport
Class for view value support structure.
Definition view.hpp:80
Gecode::Int::Sequence::ViewValSupport::allocate
static ViewValSupport * allocate(Space &, int)
Allocate an instance.
Definition view.hpp:134
Gecode::Int::Sequence::ViewValSupport::update
void update(Space &home, ViewValSupport< View, Val, iss > &vvs, int n0)
Update.
Definition view.hpp:211
Gecode::Int::Sequence::ViewValSupport::propagate
ExecStatus propagate(Space &home, ViewArray< View > &a, Val s, int i, int q, int l, int u)
Propagate.
Definition view.hpp:386
Gecode::Int::Sequence::ViewValSupport::violated
bool violated(int j, int q, int l, int u) const
Return true if sequence j has been violated.
Definition view.hpp:262
Gecode::Int::Sequence::ViewValSupport::init
void init(Space &home, ViewArray< View > &x, Val s, int i, int q)
Initialize.
Definition view.hpp:188
Gecode::Int::Sequence::ViewValSupport::advise
ExecStatus advise(Space &home, ViewArray< View > &a, Val s, int i, int q, int j, const Delta &d)
Advise.
Definition view.hpp:347
Gecode::Int::Sequence::ViewValSupport::retired
bool retired(void) const
Check if retired.
Definition view.hpp:159
Gecode::Int::Sequence::Violations
Simple bitsets for recording violations.
Definition violations.hpp:40
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2837
Gecode::Val
Gecode::View
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::ViewArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1156
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
GECODE_ES_CHECK
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
Gecode::Int::Sequence
Sequence propagators
Definition sequence.hh:40
Gecode::Int::Sequence::exclude
ModEvent exclude(Space &home, View &x, int s)
Prune view x to exclude all values from s.
Definition set-op.hpp:137
Gecode::Int::Sequence::excludes
bool excludes(const View &x, int s)
Test whether all values of view x are excluded from s.
Definition set-op.hpp:89
Gecode::Int::Sequence::TS_MAYBE
@ TS_MAYBE
Maybe or maybe not.
Definition set-op.hpp:40
Gecode::Int::Sequence::TS_NO
@ TS_NO
Definitely not.
Definition set-op.hpp:38
Gecode::Int::Sequence::TS_YES
@ TS_YES
Definitely yes.
Definition set-op.hpp:39
Gecode::Int::Sequence::includes
bool includes(const View &x, int s)
Test whether all values of view x are included in s.
Definition set-op.hpp:72
Gecode::Int::Sequence::include
ModEvent include(Space &home, View &x, int s)
Prune view x to only include values from s.
Definition set-op.hpp:123
Gecode::Int::Sequence::takes
TakesStatus takes(const View &x, int s)
Return whether view x takes value s.
Definition set-op.hpp:46
Gecode::Int
Finite domain integers.
Gecode
Gecode toplevel namespace
Gecode::values
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Test::Float::Arithmetic::a
Gecode::FloatVal a(-8, 5)
Test::Int::Distinct::v
const int v[7]
Definition distinct.cpp:259
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56