link-multi.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2007
*
* 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/channel.hh>
namespace Gecode { namespace Int { namespace Channel {
class BoolIter {
private:
const ViewArray<BoolView>& x;
const int o;
int i;
public:
BoolIter(const ViewArray<BoolView>& x0, int o0);
bool operator ()(void) const;
int val(void) const;
void operator ++(void);
};
forceinline
BoolIter::BoolIter(const ViewArray<BoolView>& x0, int o0) :
x(x0), o(o0), i(0) {
while ((i<x.size()) && !x[i].zero())
i++;
}
forceinline bool
BoolIter::operator ()(void) const {
return i<x.size();
}
forceinline int
BoolIter::val(void) const {
assert(x[i].zero());
return i+o;
}
forceinline void
BoolIter::operator ++(void) {
do {
i++;
} while ((i<x.size()) && !x[i].zero());
}
Actor*
LinkMulti::copy(Space& home) {
return new (home) LinkMulti(home,*this);
}
forceinline size_t
LinkMulti::dispose(Space& home) {
Advisors<Advisor> as(c);
x.cancel(home,as.advisor());
c.dispose(home);
(void) MixNaryOnePropagator<BoolView,PC_BOOL_NONE,IntView,PC_INT_DOM>
::dispose(home);
return sizeof(*this);
}
PropCost
LinkMulti::cost(const Space&, const ModEventDelta& med) const {
if ((status == S_ONE) || (IntView::me(med) == ME_INT_VAL))
return PropCost::unary(PropCost::LO);
else
return PropCost::linear(PropCost::LO, x.size());
}
void
LinkMulti::reschedule(Space& home) {
if (status == S_ONE)
BoolView::schedule(home,*this,ME_BOOL_VAL);
y.reschedule(home,*this,PC_INT_DOM);
}
ExecStatus
LinkMulti::advise(Space&, Advisor&, const Delta& d) {
if (status == S_RUN)
return ES_FIX;
// Detect a one
if (BoolView::one(d))
status = S_ONE;
return ES_NOFIX;
}
ExecStatus
LinkMulti::propagate(Space& home, const ModEventDelta& med) {
int n = x.size();
// Always maintain the invariant that y lies inside the x-array
assert((y.min()-o >= 0) && (y.max()-o < n));
if (y.assigned()) {
status = S_RUN;
int j=y.val()-o;
GECODE_ME_CHECK(x[j].one(home));
for (int i=0; i<j; i++)
GECODE_ME_CHECK(x[i].zero(home));
for (int i=j+1; i<n; i++)
GECODE_ME_CHECK(x[i].zero(home));
return home.ES_SUBSUMED(*this);
}
// Check whether there is a one
if (status == S_ONE) {
status = S_RUN;
for (int i=0; true; i++)
if (x[i].one()) {
for (int j=0; j<i; j++)
GECODE_ME_CHECK(x[j].zero(home));
for (int j=i+1; j<n; j++)
GECODE_ME_CHECK(x[j].zero(home));
GECODE_ME_CHECK(y.eq(home,i+o));
return home.ES_SUBSUMED(*this);
}
GECODE_NEVER;
}
status = S_RUN;
redo:
// Assign all Boolean views to zero that are outside bounds
{
int min=y.min()-o;
for (int i=0; i<min; i++)
GECODE_ME_CHECK(x[i].zero(home));
x.drop_fst(min); o += min; n = x.size();
int max=y.max()-o;
for (int i=max+1; i<n; i++)
GECODE_ME_CHECK(x[i].zero(home));
x.drop_lst(max); n = x.size();
}
{
// Remove zeros on the left
int i=0;
while ((i < n) && x[i].zero()) i++;
if (i >= n)
return ES_FAILED;
x.drop_fst(i); o += i; n = x.size();
}
{
// Remove zeros on the right
int i=n-1;
while ((i >= 0) && x[i].zero()) i--;
assert(i >= 0);
x.drop_lst(i); n = x.size();
}
assert(n >= 1);
// Is there only one left?
if (n == 1) {
GECODE_ME_CHECK(x[0].one(home));
GECODE_ME_CHECK(y.eq(home,o));
return home.ES_SUBSUMED(*this);
}
// Update bounds
GECODE_ME_CHECK(y.gq(home,o));
GECODE_ME_CHECK(y.lq(home,o+n-1));
if ((y.min() > o) || (y.max() < o+n-1))
goto redo;
assert((n >= 2) && x[0].none() && x[n-1].none());
assert((y.min()-o == 0) && (y.max()-o == n-1));
// Propagate from y to Boolean views
if ((IntView::me(med) == ME_INT_BND) || (IntView::me(med) == ME_INT_DOM)) {
ViewValues<IntView> v(y);
int i=0;
do {
int j = v.val()-o;
if (i < j) {
GECODE_ME_CHECK(x[i].zero(home));
++i;
} else if (i > j) {
++v;
} else {
assert(i == j);
++i; ++v;
}
} while (v() && (i < n));
}
// Propagate from Boolean views to y
if (BoolView::me(med) == ME_BOOL_VAL) {
BoolIter bv(x,o);
GECODE_ME_CHECK(y.minus_v(home,bv,false));
}
status = S_NONE;
return ES_FIX;
}
}}}
// STATISTICS: int-prop
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::Advisors
Class to iterate over advisors of a council.
Definition core.hpp:1266
Gecode::Advisors::advisor
A & advisor(void) const
Return advisor.
Definition core.hpp:4010
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::Int::BoolView::one
bool one(void) const
Test whether view is assigned to be one.
Definition bool.hpp:224
Gecode::Int::Channel::BoolIter
Iterates the values to be removed as defined by an array of Boolean views.
Definition link-multi.cpp:39
Gecode::Int::Channel::BoolIter::BoolIter
BoolIter(const ViewArray< BoolView > &x0, int o0)
Initialize iterator.
Definition link-multi.cpp:59
Gecode::Int::Channel::BoolIter::val
int val(void) const
Return value.
Definition link-multi.cpp:69
Gecode::Int::Channel::BoolIter::operator()
bool operator()(void) const
Test whether further values available.
Definition link-multi.cpp:65
Gecode::Int::Channel::BoolIter::operator++
void operator++(void)
Move to the next value.
Definition link-multi.cpp:74
Gecode::Int::Channel::LinkMulti::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (low unary if y is assigned, low linear otherwise).
Definition link-multi.cpp:97
Gecode::Int::Channel::LinkMulti::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition link-multi.cpp:122
Gecode::Int::Channel::LinkMulti::advise
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition link-multi.cpp:112
Gecode::Int::Channel::LinkMulti::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition link-multi.cpp:82
Gecode::Int::Channel::LinkMulti::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition link-multi.cpp:87
Gecode::Int::Channel::LinkMulti::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition link-multi.cpp:105
Gecode::Int::ViewValues
Value iterator for integer views.
Definition view.hpp:94
Gecode::MixNaryOnePropagator< BoolView, PC_BOOL_NONE, IntView, PC_INT_DOM >::MixNaryOnePropagator
MixNaryOnePropagator(Space &home, MixNaryOnePropagator &p)
Definition pattern.hpp:733
Gecode::MixNaryOnePropagator< BoolView, PC_BOOL_NONE, IntView, PC_INT_DOM >::x
ViewArray< BoolView > x
Definition pattern.hpp:275
Gecode::MixNaryOnePropagator< BoolView, PC_BOOL_NONE, IntView, PC_INT_DOM >::y
IntView y
Definition pattern.hpp:277
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::unary
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition core.hpp:4813
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::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::Propagator::med
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1075
Gecode::VarImpView< IntVar >::me
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
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::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
channel.hh
Gecode::Int::Channel
Channel propagators
Gecode::Int
Finite domain integers.
Gecode::Int::ME_INT_BND
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition var-type.hpp:65
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_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_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
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56