disjoint.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
* 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
ElementDisjoint<SView,RView>::ElementDisjoint(Home home,
IdxViewArray& iv0,
RView y1)
: Propagator(home), iv(iv0), x1(y1) {
x1.subscribe(home,*this, PC_SET_ANY);
iv.subscribe(home,*this, PC_SET_ANY);
}
template<class SView, class RView>
forceinline
ElementDisjoint<SView,RView>::ElementDisjoint(Space& home,
ElementDisjoint& p)
: Propagator(home,p) {
x1.update(home,p.x1);
iv.update(home,p.iv);
}
template<class SView, class RView>
forceinline ExecStatus
ElementDisjoint<SView,RView>::post(Home home, IdxViewArray& xs,
RView x1) {
int n = xs.size();
// s2 \subseteq {0,...,n-1}
Iter::Ranges::Singleton s(0, n-1);
GECODE_ME_CHECK(x1.intersectI(home,s));
(void) new (home)
ElementDisjoint(home,xs,x1);
return ES_OK;
}
template<class SView, class RView>
PropCost
ElementDisjoint<SView,RView>::cost(const Space&, const ModEventDelta&) const {
return PropCost::quadratic(PropCost::LO, iv.size()+2);
}
template<class SView, class RView>
void
ElementDisjoint<SView,RView>::reschedule(Space& home) {
x1.reschedule(home,*this, PC_SET_ANY);
iv.reschedule(home,*this, PC_SET_ANY);
}
template<class SView, class RView>
forceinline size_t
ElementDisjoint<SView,RView>::dispose(Space& home) {
x1.cancel(home,*this, PC_SET_ANY);
iv.cancel(home,*this,PC_SET_ANY);
(void) Propagator::dispose(home);
return sizeof(*this);
}
template<class SView, class RView>
Actor*
ElementDisjoint<SView,RView>::copy(Space& home) {
return new (home) ElementDisjoint(home,*this);
}
template<class SView, class RView>
ExecStatus
ElementDisjoint<SView,RView>::propagate(Space& home, const ModEventDelta&) {
int n = iv.size();
Region r;
bool fix_flag = false;
do {
fix_flag = false;
// Compute union of all selected elements' lower bounds
GlbRanges<RView> x1lb(x1);
Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb);
GLBndSet unionOfSelected(home);
for(int i=0; vx1lb(); ++vx1lb) {
while (iv[i].idx < vx1lb.val()) i++;
GlbRanges<SView> clb(iv[i].view);
unionOfSelected.includeI(home,clb);
}
{
LubRanges<RView> x1ub(x1);
Iter::Ranges::ToValues<LubRanges<RView> > vx1ub(x1ub);
int i=0;
int j=0;
// Cancel all elements that are no longer in the upper bound
while (vx1ub()) {
if (iv[i].idx < vx1ub.val()) {
iv[i].view.cancel(home,*this, PC_SET_ANY);
i++;
continue;
}
iv[j] = iv[i];
++vx1ub;
++i; ++j;
}
// cancel the variables with index greater than
// max of lub(x1)
for (int k=i; k<n; k++) {
iv[k].view.cancel(home,*this, PC_SET_ANY);
}
n = j;
iv.size(n);
}
{
UnknownRanges<RView> x1u(x1);
Iter::Ranges::Cache x1uc(r,x1u);
Iter::Ranges::ToValues<Iter::Ranges::Cache>
vx1u(x1uc);
int i=0;
int j=0;
while (vx1u()) {
while (iv[i].idx < vx1u.val()) {
iv[j] = iv[i];
i++; j++;
}
assert(iv[i].idx == vx1u.val());
SView candidate = iv[i].view;
int candidateInd = iv[i].idx;
GlbRanges<SView> clb(candidate);
BndSetRanges uos(unionOfSelected);
Iter::Ranges::Inter<GlbRanges<SView>, BndSetRanges>
inter(clb, uos);
if (inter()) {
ModEvent me = x1.exclude(home,candidateInd);
fix_flag |= me_modified(me);
GECODE_ME_CHECK(me);
candidate.cancel(home,*this, PC_SET_ANY);
++i;
++vx1u;
continue;
}
iv[j] = iv[i];
++vx1u;
++i; ++j;
}
unionOfSelected.dispose(home);
// copy remaining variables
for (int k=i; k<n; k++) {
iv[j] = iv[k];
j++;
}
n = j;
iv.size(n);
}
if (x1.cardMax()==0) {
// Selector is empty, we're done
return home.ES_SUBSUMED(*this);
}
{
// remove all elements in a selected variable from
// all other selected variables
GlbRanges<RView> x1lb(x1);
Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb);
int i=0;
for (; vx1lb(); ++vx1lb) {
while (iv[i].idx < vx1lb.val()) i++;
assert(iv[i].idx==vx1lb.val());
GlbRanges<RView> x1lb2(x1);
Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb2(x1lb2);
for (int j=0; vx1lb2(); ++vx1lb2) {
while (iv[j].idx < vx1lb2.val()) j++;
assert(iv[j].idx==vx1lb2.val());
if (iv[i].idx!=iv[j].idx) {
GlbRanges<SView> xilb(iv[i].view);
ModEvent me = iv[j].view.excludeI(home,xilb);
fix_flag |= me_modified(me);
GECODE_ME_CHECK(me);
}
}
}
}
// remove all elements from the selector that overlap
// with all other possibly selected elements, if
// at least two more elements need to be selected
if (x1.cardMin()-x1.glbSize() > 1) {
UnknownRanges<RView> x1u(x1);
Iter::Ranges::Cache x1uc(r,x1u);
Iter::Ranges::ToValues<Iter::Ranges::Cache>
vx1u(x1uc);
for (; vx1u() && x1.cardMin()-x1.glbSize() > 1; ++vx1u) {
int i = 0;
while (iv[i].idx < vx1u.val()) i++;
assert(iv[i].idx == vx1u.val());
bool flag=true;
UnknownRanges<RView> x1u2(x1);
Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2);
for (; vx1u2(); ++vx1u2) {
int j = 0;
while (iv[j].idx < vx1u2.val()) j++;
assert(iv[j].idx == vx1u2.val());
if (iv[i].idx!=iv[j].idx) {
GlbRanges<SView> xjlb(iv[j].view);
GlbRanges<SView> xilb(iv[i].view);
Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> >
inter(xjlb, xilb);
if (!inter()) {
flag = false;
goto here;
}
}
}
here:
if (flag) {
ModEvent me = x1.exclude(home,iv[i].idx);
fix_flag |= me_modified(me);
GECODE_ME_CHECK(me);
}
}
}
// if exactly two more elements need to be selected
// and there is a possible element i such that all other pairs of
// elements overlap, select i
UnknownRanges<RView> x1u(x1);
Iter::Ranges::Cache x1uc(r,x1u);
Iter::Ranges::ToValues<Iter::Ranges::Cache>
vx1u(x1uc);
for (; x1.cardMin()-x1.glbSize() == 2 && vx1u(); ++vx1u) {
int i = 0;
while (iv[i].idx < vx1u.val()) i++;
assert (iv[i].idx == vx1u.val());
bool flag=true;
UnknownRanges<RView> x1u2(x1);
Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2);
for (; vx1u2(); ++vx1u2) {
int j = 0;
while (iv[j].idx < vx1u2.val()) j++;
assert (iv[j].idx == vx1u2.val());
if (iv[i].idx!=iv[j].idx) {
UnknownRanges<RView> x1u3(x1);
Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u3(x1u3);
for (; vx1u3(); ++vx1u3) {
int k = 0;
while (iv[k].idx < vx1u3.val()) k++;
assert (iv[k].idx == vx1u3.val());
if (iv[j].idx!=iv[k].idx && iv[i].idx!=iv[k].idx) {
GlbRanges<SView> xjlb(iv[j].view);
GlbRanges<SView> xilb(iv[k].view);
Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> >
inter(xjlb, xilb);
if (!inter()) {
flag = false;
goto here2;
}
}
}
}
}
here2:
if (flag) {
ModEvent me = x1.include(home,iv[i].idx);
fix_flag |= me_modified(me);
GECODE_ME_CHECK(me);
}
}
} while (fix_flag);
for (int i=iv.size(); i--;)
if (!iv[i].view.assigned())
return ES_FIX;
if (!x1.assigned())
return ES_FIX;
return home.ES_SUBSUMED(*this);
}
}}}
// 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::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::IdxViewArray::size
int size(void) const
Return the current size.
Definition idx-view.hpp:105
Gecode::Iter::Ranges::Cache
Range iterator cache
Definition ranges-cache.hpp:45
Gecode::Iter::Ranges::Inter
Range iterator for computing intersection (binary).
Definition ranges-inter.hpp:44
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::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::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::dispose
void dispose(Space &home)
Free memory used by this set.
Definition integerset.hpp:60
Gecode::Set::Element::ElementDisjoint::x1
RView x1
Definition element.hh:199
Gecode::Set::Element::ElementDisjoint::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition disjoint.hpp:74
Gecode::Set::Element::ElementDisjoint::IdxViewArray
Gecode::Int::IdxViewArray< SView > IdxViewArray
Definition element.hh:196
Gecode::Set::Element::ElementDisjoint::ElementDisjoint
ElementDisjoint(Space &home, ElementDisjoint &p)
Constructor for cloning p.
Definition disjoint.hpp:51
Gecode::Set::Element::ElementDisjoint::post
static ExecStatus post(Home home, IdxViewArray &x, RView y)
Post propagator for .
Definition disjoint.hpp:60
Gecode::Set::Element::ElementDisjoint::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition disjoint.hpp:96
Gecode::Set::Element::ElementDisjoint::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition disjoint.hpp:80
Gecode::Set::Element::ElementDisjoint::iv
IdxViewArray iv
Definition element.hh:198
Gecode::Set::Element::ElementDisjoint::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition disjoint.hpp:87
Gecode::Set::Element::ElementDisjoint::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition disjoint.hpp:102
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::LubRanges
Range iterator for the least upper bound.
Definition var-imp.hpp:317
Gecode::Set::UnknownRanges
Range iterator for the unknown set.
Definition var-imp.hpp:402
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_modified
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
Gecode::Set::Element
Set element propagators
Definition element.hh:64
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
Gecode toplevel namespace
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