dom.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Contributing authors:
* Mikael Lagerkvist <lagerkvist@gecode.org>
*
* Copyright:
* Christian Schulte, 2006
* Mikael Lagerkvist, 2006
*
* 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 Channel {
template<class View, class Offset>
class DomInfo {
public:
View view;
unsigned int size;
int min;
int max;
void init(View x, int n);
void update(Space& home, DomInfo<View,Offset>& vcb);
bool doval(void) const;
bool dodom(void) const;
void assigned(void);
void removed(int i);
void done(Offset& o);
};
template<class View, class Offset>
forceinline void
DomInfo<View,Offset>::init(View x, int n) {
view = x;
size = static_cast<unsigned int>(n);
min = 0;
max = n-1;
}
template<class View, class Offset>
forceinline void
DomInfo<View,Offset>::update(Space& home, DomInfo<View,Offset>& di) {
view.update(home,di.view);
size = di.size;
min = di.min;
max = di.max;
}
template<class View, class Offset>
forceinline bool
DomInfo<View,Offset>::doval(void) const {
return (size != 1) && view.assigned();
}
template<class View, class Offset>
forceinline bool
DomInfo<View,Offset>::dodom(void) const {
return size != view.size();
}
template<class View, class Offset>
forceinline void
DomInfo<View,Offset>::assigned(void) {
size = 1;
}
template<class View, class Offset>
forceinline void
DomInfo<View,Offset>::removed(int i) {
size--;
if (i == min)
min++;
else if (i == max)
max--;
}
template<class View, class Offset>
forceinline void
DomInfo<View,Offset>::done(Offset& o) {
size = view.size();
min = o(view).min();
max = o(view).max();
}
// Propagate domain information from x to y
template<class View, class Offset>
ExecStatus
prop_dom(Space& home, int n, DomInfo<View,Offset>* x, Offset& ox,
DomInfo<View,Offset>* y, Offset& oy, ProcessStack& ya) {
for (int i=0; i<n; i++)
// Only views with not yet propagated missing values
if (x[i].dodom()) {
// Iterate the values in the complement of x[i]
ViewRanges<typename Offset::ViewType>
xir(ox(x[i].view));
Iter::Ranges::ComplVal<ViewRanges<typename Offset::ViewType> >
xirc(x[i].min,x[i].max,xir);
Iter::Ranges::ToValues<Iter::Ranges::ComplVal<
ViewRanges<typename Offset::ViewType> > > jv(xirc);
while (jv()) {
// j is not in the domain of x[i], so prune i from y[j]
int j = jv.val();
ModEvent me = oy(y[j].view).nq(home,i);
if (me_failed(me))
return ES_FAILED;
if (me_modified(me)) {
if (me == ME_INT_VAL) {
// Record that y[j] has been assigned and must be propagated
ya.push(j);
} else {
// Obvious as x[i] is different from j
y[j].removed(i);
}
}
++jv;
}
// Update which values have been propagated and what are the new bounds
x[i].done(ox);
}
return ES_OK;
}
/*
* The actual propagator
*
*/
template<class View, class Offset, bool shared>
forceinline
Dom<View,Offset,shared>::Dom(Home home, int n, DomInfo<View,Offset>* xy,
Offset& ox, Offset& oy)
: Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,n,xy,ox,oy) {}
template<class View, class Offset, bool shared>
forceinline
Dom<View,Offset,shared>::Dom(Space& home, Dom<View,Offset,shared>& p)
: Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,p) {}
template<class View, class Offset, bool shared>
Actor*
Dom<View,Offset,shared>::copy(Space& home) {
return new (home) Dom<View,Offset,shared>(home,*this);
}
template<class View, class Offset, bool shared>
PropCost
Dom<View,Offset,shared>::cost(const Space&,
const ModEventDelta& med) const {
if (View::me(med) == ME_INT_VAL)
return PropCost::quadratic(PropCost::LO, 2*n);
else
return PropCost::quadratic(PropCost::HI, 2*n);
}
template<class View, class Offset, bool shared>
ExecStatus
Dom<View,Offset,shared>::propagate(Space& home, const ModEventDelta& med) {
// MSVC in non-permissive mode needs this, no idea why...
const int n = this->n;
Region r;
ProcessStack xa(r,n);
ProcessStack ya(r,n);
DomInfo<View,Offset>* x = xy;
DomInfo<View,Offset>* y = xy+n;
if (View::me(med) == ME_INT_VAL) {
// Scan x and y for assigned but not yet propagated views
for (int i=0; i<n; i++) {
if (x[i].doval()) xa.push(i);
if (y[i].doval()) ya.push(i);
}
if (shared) {
do {
// Propagate assigned views for x
GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
(home,n,x,ox,y,oy,n_na,xa,ya)));
// Propagate assigned views for y
GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
(home,n,y,oy,x,ox,n_na,ya,xa)));
assert(ya.empty());
} while (!xa.empty() || !ya.empty());
return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
} else {
do {
// Propagate assigned views for x
GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
(home,n,x,ox,y,oy,n_na,xa,ya)));
// Propagate assigned views for y
GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
(home,n,y,oy,x,ox,n_na,ya,xa)));
assert(ya.empty());
} while (!xa.empty());
return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
}
}
// Process changed views for y
// This propagates from y to x and possibly records xs that
// got assigned
GECODE_ES_CHECK(prop_dom(home,n,y,oy,x,ox,xa));
// Process assigned views for x
GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
(home,n,x,ox,y,oy,n_na,xa,ya)));
// Perform domain consistent propagation for distinct on the x views
if (dc.available()) {
GECODE_ES_CHECK(dc.sync());
} else {
ViewArray<View> xv(r,n);
for (int i=0; i<n; i++)
xv[i] = x[i].view;
GECODE_ES_CHECK(dc.init(home,xv));
}
bool assigned;
GECODE_ES_CHECK(dc.propagate(home,assigned));
if (assigned) {
// This has assigned some more views in x which goes unnoticed
// (that is, not recorded in xa). This must be checked and propagated
// to the y views, however the distinctness on x is already
// propagated.
for (int i=0; i<n; i++)
if (x[i].doval()) {
int j = ox(x[i].view).val();
// Assign the y variable to i (or test if already assigned!)
ModEvent me = oy(y[j].view).eq(home,i);
if (me_failed(me))
return ES_FAILED;
if (me_modified(me)) {
// Record that y[j] has been assigned and must be propagated
assert(me == ME_INT_VAL);
// Otherwise the modification event would not be ME_INT_VAL
ya.push(j);
}
x[i].assigned(); n_na--;
}
}
// Process changed views for x
// This propagates from x to y and possibly records ys that
// got assigned
GECODE_ES_CHECK(prop_dom(home,n,x,ox,y,oy,ya));
// Process assigned view again (some might have been found above)
while (!xa.empty() || !ya.empty()) {
// Process assigned views for x
GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
(home,n,x,ox,y,oy,n_na,xa,ya)));
// Process assigned views for y
GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
(home,n,y,oy,x,ox,n_na,ya,xa)));
};
if (shared) {
for (int i=0; i<2*n; i++)
if (!xy[i].view.assigned())
return ES_NOFIX;
return home.ES_SUBSUMED(*this);
} else {
return (n_na == 0) ? home.ES_SUBSUMED(*this) : ES_FIX;
}
}
template<class View, class Offset, bool shared>
ExecStatus
Dom<View,Offset,shared>::post(Home home, int n, DomInfo<View,Offset>* xy,
Offset& ox, Offset& oy) {
assert(n > 0);
if (n == 1) {
GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
return ES_OK;
}
for (int i=0; i<n; i++) {
GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
}
(void) new (home) Dom<View,Offset,shared>(home,n,xy,ox,oy);
return ES_OK;
}
}}}
// STATISTICS: int-prop
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::Channel::Base
Base-class for channel propagators.
Definition channel.hh:55
Gecode::Int::Channel::Base< DomInfo< View, Offset >, Offset, PC_INT_DOM >::Base
Base(Space &home, Base< DomInfo< View, Offset >, Offset, pc > &p)
Definition base.hpp:47
Gecode::Int::Channel::Base< DomInfo< View, Offset >, Offset, PC_INT_DOM >::oy
Offset oy
Definition channel.hh:64
Gecode::Int::Channel::Base< DomInfo< View, Offset >, Offset, PC_INT_DOM >::n
int n
Definition channel.hh:58
Gecode::Int::Channel::Base< DomInfo< View, Offset >, Offset, PC_INT_DOM >::ox
Offset ox
Definition channel.hh:62
Gecode::Int::Channel::Base< DomInfo< View, Offset >, Offset, PC_INT_DOM >::n_na
int n_na
Definition channel.hh:60
Gecode::Int::Channel::Base< DomInfo< View, Offset >, Offset, PC_INT_DOM >::xy
DomInfo< View, Offset > * xy
Definition channel.hh:66
Gecode::Int::Channel::DomInfo
Combine view with information for domain propagation.
Definition dom.hpp:45
Gecode::Int::Channel::DomInfo::view
View view
The view.
Definition dom.hpp:48
Gecode::Int::Channel::DomInfo::update
void update(Space &home, DomInfo< View, Offset > &vcb)
Update during cloning.
Definition dom.hpp:82
Gecode::Int::Channel::DomInfo::size
unsigned int size
Last propagated size.
Definition dom.hpp:50
Gecode::Int::Channel::DomInfo::removed
void removed(int i)
Record that one value got removed.
Definition dom.hpp:109
Gecode::Int::Channel::DomInfo::assigned
void assigned(void)
Record that view got assigned.
Definition dom.hpp:103
Gecode::Int::Channel::DomInfo::done
void done(Offset &o)
Update the size and bounds information after pruning.
Definition dom.hpp:119
Gecode::Int::Channel::DomInfo::min
int min
Last propagated minimum.
Definition dom.hpp:52
Gecode::Int::Channel::DomInfo::doval
bool doval(void) const
Check whether propagation for assignment is to be done.
Definition dom.hpp:91
Gecode::Int::Channel::DomInfo::init
void init(View x, int n)
Initialize.
Definition dom.hpp:73
Gecode::Int::Channel::DomInfo::dodom
bool dodom(void) const
Check whether propagation for domain is to be done.
Definition dom.hpp:97
Gecode::Int::Channel::DomInfo::max
int max
Last propagated maximum.
Definition dom.hpp:54
Gecode::Int::Channel::Dom
Domain consistent channel propagator.
Definition channel.hh:134
Gecode::Int::Channel::Dom::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition dom.hpp:196
Gecode::Int::Channel::Dom::post
static ExecStatus post(Home home, int n, DomInfo< View, Offset > *xy, Offset &ox, Offset &oy)
Post propagator for channeling on xy.
Definition dom.hpp:307
Gecode::Int::Channel::Dom::Dom
Dom(Space &home, Dom &p)
Constructor for cloning p.
Gecode::Int::Channel::Dom::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition dom.hpp:180
Gecode::Int::Channel::Dom::dc
Distinct::DomCtrl< View > dc
Propagation controller for propagating distinct.
Definition channel.hh:142
Gecode::Int::Channel::Dom::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition dom.hpp:186
Gecode::Int::Offset
Converter with fixed offset.
Definition view.hpp:650
Gecode::Int::ViewRanges
Range iterator for integer views.
Definition view.hpp:54
Gecode::Iter::Ranges::ComplVal
Range iterator for computing the complement (described by values).
Definition ranges-compl.hpp:85
Gecode::Iter::Ranges::ToValues
Value iterator from range iterator.
Definition ranges-values.hpp:42
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::quadratic
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4787
Gecode::PropCost::LO
@ LO
Cheap.
Definition core.hpp:513
Gecode::PropCost::HI
@ HI
Expensive.
Definition core.hpp:514
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::med
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1075
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::StaticStack::push
void push(const T &x)
Push element x on top of stack.
Definition static-stack.hpp:137
Gecode::Support::StaticStack::empty
bool empty(void) const
Test whether stack is empty.
Definition static-stack.hpp:98
Gecode::View
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::Space::ES_NOFIX_PARTIAL
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition core.hpp:3576
Gecode::Space::ES_FIX_PARTIAL
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition core.hpp:3569
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Gecode::me_failed
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
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::me_modified
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
Gecode::Int::Channel
Channel propagators
Gecode::Int::Channel::prop_val
ExecStatus prop_val(Space &home, int n, Info *x, Offset &ox, Info *y, Offset &oy, int &n_na, ProcessStack &xa, ProcessStack &ya)
Definition val.hpp:169
Gecode::Int::Channel::ProcessStack
Support::StaticStack< int, Region > ProcessStack
Processing stack.
Definition channel.hh:48
Gecode::Int::Channel::prop_dom
ExecStatus prop_dom(Space &home, int n, DomInfo< View, Offset > *x, Offset &ox, DomInfo< View, Offset > *y, Offset &oy, ProcessStack &ya)
Definition dom.hpp:128
Gecode::Int
Finite domain integers.
Gecode::Int::PC_INT_DOM
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode::Int::ME_INT_VAL
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable).
Definition var-type.hpp:56
Gecode::Int::ME_INT_DOM
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
Gecode
Gecode toplevel namespace
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
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
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Gecode::shared
bool shared(ViewArray< ViewX > x, ViewArray< ViewY > y)
Definition array.hpp:1466
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
forceinline
#define forceinline
Definition config.hpp:187