bool.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Guido Tack, 2004
*
* 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.
*
*/
#include <gecode/int.hh>
namespace Gecode { namespace Set { namespace Channel {
template<class View>
template<class A>
forceinline
ChannelBool<View>::IndexAdvisor::IndexAdvisor(Space& home,
ChannelBool<View>& p,
Council<A>& c, int index)
: Advisor(home,p,c), idx(index) {
if (idx == -1)
p.y.subscribe(home,*this);
else {
p.x[idx].subscribe(home,*this);
}
}
template<class View>
forceinline
ChannelBool<View>::IndexAdvisor::IndexAdvisor(Space& home, IndexAdvisor& a)
: Advisor(home,a), idx(a.idx) {}
template<class View>
forceinline int
ChannelBool<View>::IndexAdvisor::index(void) const {
return idx;
}
template<class View>
template<class A>
forceinline void
ChannelBool<View>::IndexAdvisor::dispose(Space& home, Council<A>& c) {
ChannelBool<View>& p = static_cast<ChannelBool<View>&>(propagator());
if (idx == -1)
p.y.cancel(home,*this);
else {
p.x[idx].cancel(home,*this);
}
Advisor::dispose(home,c);
}
template<class View>
forceinline
ChannelBool<View>::ChannelBool(Home home,
ViewArray<Gecode::Int::BoolView>& x0,
View y0)
: Super(home,x0,y0), co(home), running(false) {
bool assigned = false;
for (int i=x.size(); i--;) {
if (x[i].zero()) {
assigned = true;
SetDelta d;
zeros.include(home, i, i, d);
} else if (x[i].one()) {
assigned = true;
SetDelta d;
ones.include(home, i, i, d);
} else {
(void) new (home) IndexAdvisor(home,*this,co,i);
}
}
if (assigned)
Gecode::Int::BoolView::schedule(home, *this, Gecode::Int::ME_BOOL_VAL);
View::schedule(home, *this, y.assigned() ? ME_SET_VAL : ME_SET_BB);
if (y.assigned()) {
if (y.glbSize()==static_cast<unsigned int>(y.glbMax()-y.glbMin()+1)) {
new (&delta) SetDelta(y.glbMin(),y.glbMax(),1,0);
} else {
new (&delta) SetDelta(2,0,1,0);
}
}
(void) new (home) IndexAdvisor(home,*this,co,-1);
}
template<class View>
forceinline
ChannelBool<View>::ChannelBool(Space& home, ChannelBool& p)
: Super(home,p), running(false) {
co.update(home, p.co);
}
template<class View>
forceinline ExecStatus
ChannelBool<View>::post(Home home, ViewArray<Gecode::Int::BoolView>& x,
View y) {
GECODE_ME_CHECK(y.intersect(home, 0, x.size()-1));
(void) new (home) ChannelBool(home,x,y);
return ES_OK;
}
template<class View>
PropCost
ChannelBool<View>::cost(const Space&, const ModEventDelta&) const {
return PropCost::quadratic(PropCost::LO, x.size()+1);
}
template<class View>
void
ChannelBool<View>::reschedule(Space& home) {
x.reschedule(home,*this,Gecode::Int::PC_BOOL_VAL);
View::schedule(home, *this, y.assigned() ? ME_SET_VAL : ME_SET_BB);
}
template<class View>
forceinline size_t
ChannelBool<View>::dispose(Space& home) {
co.dispose(home);
(void) Super::dispose(home);
return sizeof(*this);
}
template<class View>
Actor*
ChannelBool<View>::copy(Space& home) {
return new (home) ChannelBool(home,*this);
}
template<class View>
ExecStatus
ChannelBool<View>::propagate(Space& home, const ModEventDelta&) {
running = true;
if (zeros.size() > 0) {
BndSetRanges zi(zeros);
GECODE_ME_CHECK(y.excludeI(home, zi));
zeros.init(home);
}
if (ones.size() > 0) {
BndSetRanges oi(ones);
GECODE_ME_CHECK(y.includeI(home, oi));
ones.init(home);
}
running = false;
if (delta.glbMin() != 1 || delta.glbMax() != 0) {
if (!delta.glbAny()) {
for (int i=delta.glbMin(); i<=delta.glbMax(); i++)
GECODE_ME_CHECK(x[i].one(home));
} else {
GlbRanges<View> glb(y);
for (Iter::Ranges::ToValues<GlbRanges<View> > gv(glb); gv(); ++gv) {
GECODE_ME_CHECK(x[gv.val()].one(home));
}
}
}
if (delta.lubMin() != 1 || delta.lubMax() != 0) {
if (!delta.lubAny()) {
for (int i=delta.lubMin(); i<=delta.lubMax(); i++)
GECODE_ME_CHECK(x[i].zero(home));
} else {
int cur = 0;
for (LubRanges<View> lub(y); lub(); ++lub) {
for (; cur < lub.min(); cur++) {
GECODE_ME_CHECK(x[cur].zero(home));
}
cur = lub.max() + 1;
}
for (; cur < x.size(); cur++) {
GECODE_ME_CHECK(x[cur].zero(home));
}
}
}
new (&delta) SetDelta();
return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
}
template<class View>
ExecStatus
ChannelBool<View>::advise(Space& home, Advisor& _a, const Delta& _d) {
IndexAdvisor& a = static_cast<IndexAdvisor&>(_a);
const SetDelta& d = static_cast<const SetDelta&>(_d);
ModEvent me = View::modevent(d);
int index = a.index();
if ( (running && index == -1 && me != ME_SET_VAL)
|| (index == -1 && me == ME_SET_CARD) ) {
return ES_OK;
}
if (index >= 0) {
if (x[index].zero()) {
SetDelta dummy;
zeros.include(home, index, index, dummy);
} else {
assert(x[index].one());
SetDelta dummy;
ones.include(home, index, index, dummy);
}
return home.ES_NOFIX_DISPOSE( co, a);
}
if ((a.index() == -1) && Rel::testSetEventLB(me)) {
if (d.glbAny()) {
new (&delta)
SetDelta(2,0, delta.lubMin(), delta.lubMax());
} else {
if (delta.glbMin() == 1 && delta.glbMax() == 0) {
new (&delta)
SetDelta(d.glbMin(), d.glbMax(),
delta.lubMin(), delta.lubMax());
} else {
if (delta.glbMin() != 2 || delta.glbMax() != 0) {
if ((delta.glbMin() <= d.glbMin() && delta.glbMax() >= d.glbMin())
||
(delta.glbMin() <= d.glbMax() && delta.glbMax() >= d.glbMax())
) {
new (&delta)
SetDelta(std::min(delta.glbMin(), d.glbMin()),
std::max(delta.glbMax(), d.glbMax()),
delta.lubMin(), delta.lubMax());
} else {
new (&delta)
SetDelta(2, 0, delta.lubMin(), delta.lubMax());
}
}
}
}
}
if ((a.index() == -1) && Rel::testSetEventUB(me)) {
if (d.lubAny()) {
new (&delta)
SetDelta(delta.glbMin(), delta.glbMax(), 2,0);
} else {
if (delta.lubMin() == 1 && delta.lubMax() == 0) {
new (&delta)
SetDelta(delta.glbMin(), delta.glbMax(),
d.lubMin(), d.lubMax());
} else {
if (delta.lubMin() != 2 || delta.lubMax() != 0) {
if ((delta.lubMin() <= d.lubMin() && delta.lubMax() >= d.lubMin())
||
(delta.lubMin() <= d.lubMax() && delta.lubMax() >= d.lubMax())
) {
new (&delta)
SetDelta(delta.lubMin(), delta.lubMax(),
std::min(delta.lubMin(), d.lubMin()),
std::max(delta.lubMax(), d.lubMax())
);
} else {
new (&delta)
SetDelta(delta.glbMin(), delta.glbMax(), 2, 0);
}
}
}
}
}
if (y.assigned())
return home.ES_NOFIX_DISPOSE( co, a);
else
return ES_NOFIX;
}
}}}
// STATISTICS: set-prop
Gecode::ActorLink::Space
friend class Space
Definition core.hpp:595
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
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::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Iter::Ranges::ToValues
Value iterator from range iterator.
Definition ranges-values.hpp:42
Gecode::MixNaryOnePropagator< Gecode::Int::BoolView, Gecode::Int::PC_BOOL_VAL, View, PC_GEN_NONE >::dispose
virtual size_t dispose(Space &home)
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::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::Advisor
friend class Advisor
Definition core.hpp:1068
Gecode::Set::BndSetRanges
Range iterator for integer sets.
Definition var-imp.hpp:185
Gecode::Set::Channel::ChannelBool::IndexAdvisor
Advisor storing a single index
Definition channel.hh:166
Gecode::Set::Channel::ChannelBool::IndexAdvisor::IndexAdvisor
IndexAdvisor(Space &home, ChannelBool< View > &p, Council< A > &c, int index)
Constructor for creation.
Definition bool.hpp:41
Gecode::Set::Channel::ChannelBool::IndexAdvisor::index
int index(void) const
Access index.
Definition bool.hpp:59
Gecode::Set::Channel::ChannelBool::IndexAdvisor::idx
int idx
The single index.
Definition channel.hh:169
Gecode::Set::Channel::ChannelBool::IndexAdvisor::dispose
void dispose(Space &home, Council< A > &c)
Delete advisor.
Definition bool.hpp:66
Gecode::Set::Channel::ChannelBool::zeros
GLBndSet zeros
Accumulated zero Booleans.
Definition channel.hh:189
Gecode::Set::Channel::ChannelBool::ChannelBool
ChannelBool(Space &home, ChannelBool &p)
Constructor for cloning p.
Definition bool.hpp:111
Gecode::Set::Channel::ChannelBool::advise
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition bool.hpp:204
Gecode::Set::Channel::ChannelBool::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition bool.hpp:133
Gecode::Set::Channel::ChannelBool::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition bool.hpp:140
Gecode::Set::Channel::ChannelBool::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition bool.hpp:154
Gecode::Set::Channel::ChannelBool::y
View y
Single view.
Definition pattern.hpp:277
Gecode::Set::Channel::ChannelBool::co
Council< IndexAdvisor > co
Council for managing advisors.
Definition channel.hh:185
Gecode::Set::Channel::ChannelBool::delta
SetDelta delta
Accumulated delta information.
Definition channel.hh:187
Gecode::Set::Channel::ChannelBool::ones
GLBndSet ones
Accumulated one Booleans.
Definition channel.hh:191
Gecode::Set::Channel::ChannelBool::running
bool running
Flag whether propagation is currently running.
Definition channel.hh:193
Gecode::Set::Channel::ChannelBool::Super
MixNaryOnePropagator< Gecode::Int::BoolView, Gecode::Int::PC_BOOL_VAL, View, PC_GEN_NONE > Super
Definition channel.hh:155
Gecode::Set::Channel::ChannelBool::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition bool.hpp:148
Gecode::Set::Channel::ChannelBool::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as PC_QUADRATIC_LO).
Definition bool.hpp:127
Gecode::Set::Channel::ChannelBool::post
static ExecStatus post(Home home, ViewArray< Gecode::Int::BoolView > &x, View y)
Post propagator for .
Definition bool.hpp:118
Gecode::Set::Channel::ChannelBool::x
ViewArray< Gecode::Int::BoolView > x
Array of views.
Definition pattern.hpp:275
Gecode::Set::GlbRanges
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Gecode::Set::LubRanges
Range iterator for the least upper bound.
Definition var-imp.hpp:317
Gecode::Set::SetDelta
Finite set delta information for advisors.
Definition var-imp.hpp:52
Gecode::View
Gecode::VarImpView< BoolVar >::schedule
static void schedule(Space &home, Propagator &p, ModEvent me)
Definition view.hpp:547
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::ViewArray::cancel
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition array.hpp:1349
int.hh
Gecode::Space::ES_NOFIX_DISPOSE
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition core.hpp:3887
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::Int::ME_BOOL_VAL
const Gecode::ModEvent ME_BOOL_VAL
Domain operation has resulted in a value (assigned variable).
Definition var-type.hpp:116
Gecode::Int::PC_BOOL_VAL
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value).
Definition var-type.hpp:126
Gecode::Set::Channel
Channeling propagators for set variables.
Definition channel.hh:43
Gecode::Set::Rel::testSetEventLB
bool testSetEventLB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition common.hpp:83
Gecode::Set::Rel::testSetEventUB
bool testSetEventUB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition common.hpp:87
Gecode::Set
Finite integer sets.
Definition var-imp.hpp:137
Gecode::Set::ME_SET_VAL
const Gecode::ModEvent ME_SET_VAL
Domain operation has resulted in a value (assigned variable).
Definition var-type.hpp:142
Gecode::Set::ME_SET_CARD
const Gecode::ModEvent ME_SET_CARD
Domain operation has changed the variable cardinality.
Definition var-type.hpp:148
Gecode::Set::ME_SET_BB
const Gecode::ModEvent ME_SET_BB
Domain operation has changed both greatest lower and least upper bound.
Definition var-type.hpp:172
Gecode
Gecode toplevel namespace
Gecode::propagator
TFE propagator(PropagatorGroup g)
Only propagators (but not post functions) from g are considered.
Definition filter.cpp:131
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_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
forceinline
#define forceinline
Definition config.hpp:187