unionConst.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>
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Guido Tack, 2004,2006,2007
* Christian Schulte, 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.
*
*/
namespace Gecode { namespace Set { namespace Element {
template<class SView, class RView>
forceinline
ElementUnionConst<SView,RView>::
ElementUnionConst(Home home, SView y0,
const IntSetArgs& iv0,
RView y1)
: Propagator(home), x0(y0), n_iv(iv0.size()), x1(y1) {
home.notice(*this,AP_DISPOSE);
x0.subscribe(home,*this, PC_SET_ANY);
x1.subscribe(home,*this, PC_SET_ANY);
iv=static_cast<Space&>(home).alloc<IntSet>(n_iv);
for (unsigned int i=iv0.size(); i--;)
iv[i]=iv0[i];
}
template<class SView, class RView>
forceinline
ElementUnionConst<SView,RView>::
ElementUnionConst(Space& home, ElementUnionConst<SView,RView>& p)
: Propagator(home,p), n_iv(p.n_iv) {
x0.update(home,p.x0);
x1.update(home,p.x1);
iv=home.alloc<IntSet>(n_iv);
for (unsigned int i=n_iv; i--;)
iv[i]=p.iv[i];
}
template<class SView, class RView>
PropCost
ElementUnionConst<SView,RView>::cost(const Space&, const ModEventDelta&) const {
return PropCost::linear(PropCost::HI, n_iv+2);
}
template<class SView, class RView>
void
ElementUnionConst<SView,RView>::reschedule(Space& home) {
x0.reschedule(home,*this, PC_SET_ANY);
x1.reschedule(home,*this, PC_SET_ANY);
}
template<class SView, class RView>
forceinline size_t
ElementUnionConst<SView,RView>::dispose(Space& home) {
home.ignore(*this,AP_DISPOSE);
if (!home.failed()) {
x0.cancel(home,*this, PC_SET_ANY);
x1.cancel(home,*this, PC_SET_ANY);
}
for (unsigned int i=n_iv; i--;)
iv[i].~IntSet();
(void) Propagator::dispose(home);
return sizeof(*this);
}
template<class SView, class RView>
ExecStatus
ElementUnionConst<SView,RView>::
post(Home home, SView x0, const IntSetArgs& xs,
RView x1) {
int n = xs.size();
// s2 \subseteq {1,...,n}
Iter::Ranges::Singleton s(0, n-1);
GECODE_ME_CHECK(x1.intersectI(home,s));
(void) new (home)
ElementUnionConst<SView,RView>(home,x0,xs,x1);
return ES_OK;
}
template<class SView, class RView>
Actor*
ElementUnionConst<SView,RView>::copy(Space& home) {
return new (home) ElementUnionConst<SView,RView>(home,*this);
}
template<class SView, class RView>
ExecStatus
ElementUnionConst<SView,RView>::propagate(Space& home, const ModEventDelta&) {
Region r;
bool* stillSelected = r.alloc<bool>(n_iv);
bool loopVar;
do {
loopVar = false;
for (int i=n_iv; i--;)
stillSelected[i] = false;
// Cache the upper bound iterator, as we have to
// modify the upper bound while iterating
LubRanges<RView> x1ub(x1);
Iter::Ranges::Cache x1ubc(r,x1ub);
Iter::Ranges::ToValues<Iter::Ranges::Cache>
vx1ub(x1ubc);
GlbRanges<RView> x1lb(x1);
Iter::Ranges::Cache x1lbc(r,x1lb);
Iter::Ranges::ToValues<Iter::Ranges::Cache>
vx1(x1lbc);
// In the first iteration, compute in before[i] the union
// of all the upper bounds of the x_i. At the same time,
// exclude inconsistent x_i from x1.
GLBndSet sofarBefore(home);
LUBndSet selectedInter(home, IntSet (Limits::min,
Limits::max));
GLBndSet* before =
static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n_iv));
unsigned int maxCard = 0;
unsigned int minCard = Limits::card;
while (vx1ub()) {
int i = vx1ub.val();
IntSetRanges candCardR(iv[i]);
unsigned int candidateCard = Iter::Ranges::size(candCardR);
IntSetRanges candlb(iv[i]);
LubRanges<SView> x0ub(x0);
Iter::Ranges::Diff<IntSetRanges,
LubRanges<SView> > diff(candlb, x0ub);
bool selectSingleInconsistent = false;
if (x1.cardMax() <= 1) {
GlbRanges<SView> x0lb(x0);
IntSetRanges candub(iv[i]);
Iter::Ranges::Diff<GlbRanges<SView>,
IntSetRanges > diff2(x0lb, candub);
selectSingleInconsistent = diff2() || candidateCard < x0.cardMin();
}
// exclude inconsistent x_i
// an x_i is inconsistent if
// * at most one x_i can be selected and there are
// elements in x_0 that can't be in x_i
// (selectSingleInconsistent)
// * its min cardinality is greater than maxCard of x0
// * inter is not empty (there are elements in x_i
// that can't be in x_0)
if (selectSingleInconsistent ||
candidateCard > x0.cardMax() ||
diff()) {
ModEvent me = (x1.exclude(home,i));
loopVar |= me_modified(me);
GECODE_ME_CHECK(me);
} else {
stillSelected[i] = true;
// if x_i is consistent, check whether we know
// that its index is in x1
if (vx1() && vx1.val()==i) {
// x0 >= candidate, candidate <= x0
// GlbRanges<SView> candlb(candidate);
IntSetRanges candlb(iv[i]);
ModEvent me = x0.includeI(home,candlb);
loopVar |= me_modified(me);
GECODE_ME_CHECK(me);
++vx1;
}
new (&before[i]) GLBndSet(home);
before[i].update(home,sofarBefore);
IntSetRanges cub(iv[i]);
sofarBefore.includeI(home,cub);
IntSetRanges clb(iv[i]);
selectedInter.intersectI(home,clb);
maxCard = std::max(maxCard, candidateCard);
minCard = std::min(minCard, candidateCard);
}
++vx1ub;
}
if (x1.cardMax()==0) {
// Selector is empty, hence the result must be empty
{
GECODE_ME_CHECK(x0.cardMax(home,0));
}
for (int i=n_iv; i--;)
if (stillSelected[i])
before[i].dispose(home);
selectedInter.dispose(home);
sofarBefore.dispose(home);
return home.ES_SUBSUMED(*this);
}
if (x1.cardMin() > 0) {
// Selector is not empty, hence the intersection of the
// possibly selected lower bounds is contained in x0
BndSetRanges si(selectedInter);
ModEvent me = x0.includeI(home, si);
loopVar |= me_modified(me);
GECODE_ME_CHECK(me);
me = x0.cardMin(home, minCard);
loopVar |= me_modified(me);
GECODE_ME_CHECK(me);
}
selectedInter.dispose(home);
if (x1.cardMax() <= 1) {
ModEvent me = x0.cardMax(home, maxCard);
loopVar |= me_modified(me);
GECODE_ME_CHECK(me);
}
{
// x0 <= sofarBefore
BndSetRanges sfB(sofarBefore);
ModEvent me = x0.intersectI(home,sfB);
loopVar |= me_modified(me);
GECODE_ME_CHECK(me);
}
sofarBefore.dispose(home);
GLBndSet sofarAfter(home);
// In the second iteration, this time backwards, compute
// sofarAfter as the union of all lub(x_j) with j>i
for (int i=n_iv; i--;) {
if (!stillSelected[i])
continue;
BndSetRanges b(before[i]);
BndSetRanges s(sofarAfter);
GlbRanges<SView> x0lb(x0);
Iter::Ranges::Union<BndSetRanges, BndSetRanges> inter(b,s);
Iter::Ranges::Diff<GlbRanges<SView>,
Iter::Ranges::Union<BndSetRanges,BndSetRanges> > diff(x0lb, inter);
if (diff()) {
ModEvent me = (x1.include(home,i));
loopVar |= me_modified(me);
GECODE_ME_CHECK(me);
// candidate != extra
IntSetRanges ivi(iv[i]);
if (!Iter::Ranges::subset(diff, ivi))
GECODE_ME_CHECK(ME_SET_FAILED);
}
IntSetRanges iviub(iv[i]);
sofarAfter.includeI(home,iviub);
before[i].dispose(home);
}
sofarAfter.dispose(home);
} while (loopVar);
if (x1.assigned()) {
assert(x0.assigned());
return home.ES_SUBSUMED(*this);
}
return ES_FIX;
}
}}}
// STATISTICS: set-prop
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::Actor::dispose
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1607
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Home::notice
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3219
Gecode::IntSetRanges
Range iterator for integer sets.
Definition int.hh:292
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::Iter::Ranges::Cache
Range iterator cache
Definition ranges-cache.hpp:45
Gecode::Iter::Ranges::Diff
Range iterator for computing set difference.
Definition ranges-diff.hpp:43
Gecode::Iter::Ranges::Singleton
Range iterator for singleton range.
Definition ranges-singleton.hpp:42
Gecode::Iter::Ranges::ToValues
Value iterator from range iterator.
Definition ranges-values.hpp:42
Gecode::Iter::Ranges::ToValues::val
int val(void) const
Return current value.
Definition ranges-values.hpp:129
Gecode::Iter::Ranges::Union
Range iterator for computing union (binary).
Definition ranges-union.hpp:44
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::linear
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
Gecode::PropCost::HI
@ HI
Expensive.
Definition core.hpp:514
Gecode::Propagator::size
size_t size
The size of the propagator (used during subsumption).
Definition core.hpp:1077
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Set::BndSetRanges
Range iterator for integer sets.
Definition var-imp.hpp:185
Gecode::Set::BndSet::update
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition integerset.hpp:140
Gecode::Set::BndSet::dispose
void dispose(Space &home)
Free memory used by this set.
Definition integerset.hpp:60
Gecode::Set::Element::ElementUnionConst::n_iv
int n_iv
Definition element.hh:161
Gecode::Set::Element::ElementUnionConst::ElementUnionConst
ElementUnionConst(Space &home, ElementUnionConst &p)
Constructor for cloning p.
Definition unionConst.hpp:56
Gecode::Set::Element::ElementUnionConst::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition unionConst.hpp:73
Gecode::Set::Element::ElementUnionConst::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition unionConst.hpp:80
Gecode::Set::Element::ElementUnionConst::x1
RView x1
Definition element.hh:162
Gecode::Set::Element::ElementUnionConst::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition unionConst.hpp:109
Gecode::Set::Element::ElementUnionConst::iv
IntSet * iv
Definition element.hh:160
Gecode::Set::Element::ElementUnionConst::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition unionConst.hpp:115
Gecode::Set::Element::ElementUnionConst::x0
SView x0
Definition element.hh:159
Gecode::Set::Element::ElementUnionConst::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition unionConst.hpp:67
Gecode::Set::GLBndSet
Growing sets of integers.
Definition var-imp.hpp:205
Gecode::Set::GLBndSet::includeI
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition integerset.hpp:296
Gecode::Set::GlbRanges
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Gecode::Set::LUBndSet
Shrinking sets of integers.
Definition var-imp.hpp:243
Gecode::Set::LUBndSet::intersectI
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition integerset.hpp:370
Gecode::Set::LubRanges
Range iterator for the least upper bound.
Definition var-imp.hpp:317
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::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::Space::ignore
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4074
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Gecode::Space::failed
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4044
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Gecode::me_modified
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
Gecode::AP_DISPOSE
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
Gecode::Iter::Ranges::subset
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
Definition ranges-operations.hpp:97
Gecode::Iter::Ranges::size
unsigned int size(I &i)
Size of all ranges of range iterator i.
Definition ranges-operations.hpp:74
Gecode::Set::Element
Set element propagators
Definition element.hh:64
Gecode::Set::Limits::min
const int min
Smallest allowed integer in integer set.
Definition set.hh:99
Gecode::Set::Limits::card
const unsigned int card
Maximum cardinality of an integer set.
Definition set.hh:101
Gecode::Set::Limits::max
const int max
Largest allowed integer in integer set.
Definition set.hh:97
Gecode::Set
Finite integer sets.
Definition var-imp.hpp:137
Gecode::Set::PC_SET_ANY
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition var-type.hpp:248
Gecode::Set::ME_SET_FAILED
const Gecode::ModEvent ME_SET_FAILED
Domain operation has resulted in failure.
Definition var-type.hpp:138
Gecode
Gecode toplevel namespace
Gecode::IntSetArgs
ArgArray< IntSet > IntSetArgs
Passing set arguments.
Definition int.hh:619
Gecode::inter
SetExpr inter(const SetVarArgs &)
Intersection of set variables.
Definition set-expr.cpp:696
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::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
forceinline
#define forceinline
Definition config.hpp:187