int-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>
*
* Copyright:
* Christian Schulte, 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 Linear {
class SupportSet {
private:
Support::BitSetBase bs;
public:
SupportSet(void);
void init(Region& r, unsigned int n);
void support(unsigned int i);
bool supported(unsigned int i) const;
private:
class ResultIter : public ViewValues<IntView> {
protected:
const SupportSet& s;
unsigned int p;
public:
ResultIter(const SupportSet& s0, const IntView& x);
void operator ++(void);
};
public:
ModEvent tell(Space& home, IntView& x) const;
};
template<class Val>
class SupportIter {
protected:
int a;
IntView x;
SupportSet s;
int c;
unsigned int p;
Val l;
Val u;
public:
void init(Region& r, int a, const IntView& x, Val l, Val u);
void support(void);
ModEvent tell(Space& home);
};
template<class Val>
class PosSupportIter : public SupportIter<Val> {
private:
IntVarImpFwd i;
// Using-declarations for dependant names
using SupportIter<Val>::a;
using SupportIter<Val>::x;
using SupportIter<Val>::s;
using SupportIter<Val>::c;
using SupportIter<Val>::p;
using SupportIter<Val>::l;
using SupportIter<Val>::u;
public:
bool reset(Val& d);
bool adjust(Val& d);
};
template<class Val>
class NegSupportIter : public SupportIter<Val> {
private:
IntVarImpBwd i;
// Using-declarations for dependant names
using SupportIter<Val>::a;
using SupportIter<Val>::x;
using SupportIter<Val>::s;
using SupportIter<Val>::c;
using SupportIter<Val>::p;
using SupportIter<Val>::l;
using SupportIter<Val>::u;
public:
bool reset(Val& d);
bool adjust(Val& d);
};
/*
* Support set
*
*/
forceinline
SupportSet::SupportSet(void) {}
forceinline void
SupportSet::init(Region& r, unsigned int n) {
bs.init(r,n);
}
forceinline void
SupportSet::support(unsigned int i) {
bs.set(i);
}
forceinline bool
SupportSet::supported(unsigned int i) const {
return bs.get(i);
}
forceinline
SupportSet::ResultIter::ResultIter(const SupportSet& s0, const IntView& x)
: ViewValues<IntView>(x), s(s0), p(0) {
while (ViewValues<IntView>::operator ()() && s.supported(p)) {
ViewValues<IntView>::operator ++(); ++p;
}
}
forceinline void
SupportSet::ResultIter::operator ++(void) {
do {
ViewValues<IntView>::operator ++(); ++p;
} while (ViewValues<IntView>::operator ()() && s.supported(p));
}
forceinline ModEvent
SupportSet::tell(Space& home, IntView& x) const {
switch (bs.status()) {
case Support::BSS_NONE:
return ME_INT_FAILED;
case Support::BSS_ALL:
return ME_INT_NONE;
case Support::BSS_SOME:
{
ResultIter i(*this,x);
return x.minus_v(home,i);
}
default:
GECODE_NEVER;
}
return ME_INT_NONE;
}
/*
* Base-class for support-based iterator
*
*/
template<class Val>
forceinline void
SupportIter<Val>::init(Region& r,
int a0, const IntView& x0, Val l0, Val u0) {
a=a0; x=x0; l=l0; u=u0;
s.init(r,x.size());
}
template<class Val>
forceinline void
SupportIter<Val>::support(void) {
s.support(p);
}
template<class Val>
forceinline ModEvent
SupportIter<Val>::tell(Space& home) {
return s.tell(home,x);
}
/*
* Support-based iterator for positive view
*
*/
template<class Val>
forceinline bool
PosSupportIter<Val>::reset(Val& d) {
// Way too small, no value can make it big enough
if (d + static_cast<Val>(a)*x.max() < u)
return false;
// Restart iterator and position of values
i.init(x.varimp()); p = 0;
// Skip all ranges which are too small
while (d + static_cast<Val>(a)*i.max() < u) {
p += i.width(); ++i;
}
// There is at least one range left (check of max)
assert(i());
// Initialize current range and adjust value
c = i.min();
// Skip all values which are too small
while (d + static_cast<Val>(a)*c < u) {
p++; c++;
}
// Adjust to new value
d += static_cast<Val>(a) * c;
return true;
}
template<class Val>
forceinline bool
PosSupportIter<Val>::adjust(Val& d) {
// Current value
Val v = static_cast<Val>(a) * c;
// Subtract current value from d
d -= v;
// Move to next position (number of value)
p++;
// Still in the same range
if (c < i.max()) {
// Decrement current values
c += 1; v += a;
} else {
// Go to next range
++i;
if (!i())
return false;
c = i.min(); v = static_cast<Val>(a) * c;
}
// Is d with the current value too large?
if (d + v > l)
return false;
// Update d
d += v;
return true;
}
/*
* Support-based iterator for negative view
*
*/
template<class Val>
forceinline bool
NegSupportIter<Val>::reset(Val& d) {
// Way too small, no value can make it big enough
if (d + static_cast<Val>(a)*x.min() < u)
return false;
// Restart iterator and position of values
i.init(x.varimp()); p = x.size()-1;
// Skip all ranges which are too small
while (d + static_cast<Val>(a)*i.min() < u) {
p -= i.width(); ++i;
}
// There is at least one range left (check of max)
assert(i());
// Initialize current range
c = i.max();
// Skip all values which are too small
while (d + static_cast<Val>(a)*c < u) {
p--; c--;
}
// Adjust to new value
d += static_cast<Val>(a) * c;
return true;
}
template<class Val>
forceinline bool
NegSupportIter<Val>::adjust(Val& d) {
// Current value
Val v = static_cast<Val>(a) * c;
// Subtract current value from d
d -= v;
// Move to next position (number of value)
p--;
// Still in the same range
if (c > i.min()) {
// Decrement current values
c -= 1; v -= a;
} else {
// Go to next range
++i;
if (!i())
return false;
c = i.max(); v = static_cast<Val>(a) * c;
}
// Is d with the current value too large?
if (d + v > l)
return false;
// Update d
d += v;
return true;
}
/*
* The domain consisten equality propagator
*
*/
template<class Val, class View>
forceinline
DomEq<Val,View>::DomEq(Home home,
ViewArray<View >& x, ViewArray<View >& y,
Val c)
: Lin<Val,View,View,PC_INT_DOM>(home,x,y,c) {}
template<class Val, class View>
ExecStatus
DomEq<Val,View>::post(Home home,
ViewArray<View>& x, ViewArray<View>& y,
Val c) {
(void) new (home) DomEq<Val,View>(home,x,y,c);
return ES_OK;
}
template<class Val, class View>
forceinline
DomEq<Val,View>::DomEq(Space& home, DomEq<Val,View>& p)
: Lin<Val,View,View,PC_INT_DOM>(home,p) {}
template<class Val, class View>
Actor*
DomEq<Val,View>::copy(Space& home) {
return new (home) DomEq<Val,View>(home,*this);
}
template<class Val, class View>
PropCost
DomEq<Val,View>::cost(const Space&, const ModEventDelta& med) const {
if (View::me(med) != ME_INT_DOM)
return PropCost::linear(PropCost::LO, x.size()+y.size());
else
return PropCost::crazy(PropCost::HI, x.size()+y.size());
}
template<class Val, class View>
ExecStatus
DomEq<Val,View>::propagate(Space& home, const ModEventDelta& med) {
if (View::me(med) != ME_INT_DOM) {
ExecStatus es = prop_bnd<Val,View,View>(home,med,*this,x,y,c);
GECODE_ES_CHECK(es);
return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
}
// Value of equation for partial assignment
Val d = -c;
int n = x.size();
int m = y.size();
Region r;
// Create support-base iterators
PosSupportIter<Val>* xp = r.alloc<PosSupportIter<Val> >(n);
NegSupportIter<Val>* yp = r.alloc<NegSupportIter<Val> >(m);
// Initialize views for assignments
{
Val l = 0;
Val u = 0;
for (int j=m; j--; ) {
yp[j].init(r,-y[j].scale(),y[j].base(),l,u);
l += y[j].max(); u += y[j].min();
}
for (int i=n; i--; ) {
xp[i].init(r,x[i].scale(),x[i].base(),l,u);
l -= x[i].min(); u -= x[i].max();
}
}
// Collect support information by iterating assignments
{
// Force reset of all iterators in first round
int i = 0;
int j = 0;
next_i:
// Reset all iterators for positive views and update d
while (i<n) {
if (!xp[i].reset(d)) goto prev_i;
i++;
}
next_j:
// Reset all iterators for negative views and update d
while (j<m) {
if (!yp[j].reset(d)) goto prev_j;
j++;
}
// Check whether current assignment is solution
if (d == 0) {
// Record support
for (int is=0; is<n; is++) xp[is].support();
for (int js=0; js<m; js++) yp[js].support();
}
prev_j:
// Try iterating to next assignment: negative views
while (j>0) {
if (yp[j-1].adjust(d)) goto next_j;
j--;
}
prev_i:
// Try iterating to next assignment: positive views
while (i>0) {
if (xp[i-1].adjust(d)) goto next_i;
i--;
}
}
// Tell back new variable domains
bool assigned = true;
for (int i=0; i<n; i++) {
GECODE_ME_CHECK(xp[i].tell(home));
if (!x[i].assigned())
assigned = false;
}
for (int j=0; j<m; j++) {
GECODE_ME_CHECK(yp[j].tell(home));
if (!y[j].assigned())
assigned = false;
}
if (assigned)
return home.ES_SUBSUMED(*this);
return ES_FIX;
}
}}}
// 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::IntVarImpBwd
Backward iterator for ranges of integer variable implementations.
Definition var-imp.hpp:435
Gecode::Int::IntVarImpFwd
Range iterator for ranges of integer variable implementation.
Definition var-imp.hpp:392
Gecode::Int::IntView
Integer view for integer variables.
Definition view.hpp:129
Gecode::Int::IntView::minus_v
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition int.hpp:206
Gecode::Int::Linear::DomEq
Propagator for domain consistent n-ary linear equality
Definition linear.hh:609
Gecode::Int::Linear::DomEq::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition int-dom.hpp:382
Gecode::Int::Linear::DomEq::copy
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition int-dom.hpp:376
Gecode::Int::Linear::DomEq::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int-dom.hpp:391
Gecode::Int::Linear::DomEq::DomEq
DomEq(Space &home, DomEq &p)
Constructor for cloning p.
Gecode::Int::Linear::DomEq::post
static ExecStatus post(Home home, ViewArray< View > &x, ViewArray< View > &y, Val c)
Post propagator for .
Definition int-dom.hpp:362
Gecode::Int::Linear::Lin
Base-class for n-ary linear propagators.
Definition linear.hh:497
Gecode::Int::Linear::Lin< Val, View, View, PC_INT_DOM >::Lin
Lin(Space &home, Lin< Val, View, View, pc > &p)
Definition int-nary.hpp:69
Gecode::Int::Linear::Lin< Val, View, View, PC_INT_DOM >::y
ViewArray< View > y
Definition linear.hh:502
Gecode::Int::Linear::Lin< Val, View, View, PC_INT_DOM >::x
ViewArray< View > x
Definition linear.hh:500
Gecode::Int::Linear::Lin< Val, View, View, PC_INT_DOM >::c
Val c
Definition linear.hh:504
Gecode::Int::Linear::NegSupportIter
Support-based iterator for negative view.
Definition int-dom.hpp:138
Gecode::Int::Linear::NegSupportIter::adjust
bool adjust(Val &d)
Adjust.
Definition int-dom.hpp:321
Gecode::Int::Linear::NegSupportIter::reset
bool reset(Val &d)
Reset iterator to beginning and adjust.
Definition int-dom.hpp:297
Gecode::Int::Linear::PosSupportIter
Support-based iterator for positive view.
Definition int-dom.hpp:113
Gecode::Int::Linear::PosSupportIter::reset
bool reset(Val &d)
Reset iterator to beginning and adjust.
Definition int-dom.hpp:240
Gecode::Int::Linear::PosSupportIter::adjust
bool adjust(Val &d)
Adjust.
Definition int-dom.hpp:264
Gecode::Int::Linear::SupportIter
Base-class for support-based iterator.
Definition int-dom.hpp:82
Gecode::Int::Linear::SupportIter::x
IntView x
Integer view.
Definition int-dom.hpp:87
Gecode::Int::Linear::SupportIter::init
void init(Region &r, int a, const IntView &x, Val l, Val u)
Initialize view.
Definition int-dom.hpp:217
Gecode::Int::Linear::SupportIter::c
int c
Current value.
Definition int-dom.hpp:91
Gecode::Int::Linear::SupportIter::a
int a
Integer coefficient for view.
Definition int-dom.hpp:85
Gecode::Int::Linear::SupportIter::u
Val u
Upper bound information for value.
Definition int-dom.hpp:97
Gecode::Int::Linear::SupportIter::l
Val l
Lower bound information for value.
Definition int-dom.hpp:95
Gecode::Int::Linear::SupportIter::support
void support(void)
Record value at current position as supported.
Definition int-dom.hpp:224
Gecode::Int::Linear::SupportIter::p
unsigned int p
Position of current value.
Definition int-dom.hpp:93
Gecode::Int::Linear::SupportIter::s
SupportSet s
Set of support for values in x.
Definition int-dom.hpp:89
Gecode::Int::Linear::SupportIter::tell
ModEvent tell(Space &home)
Tell back new variable domain according to support found.
Definition int-dom.hpp:229
Gecode::Int::Linear::SupportSet
Set for support information
Definition int-dom.hpp:43
Gecode::Int::Linear::SupportSet::supported
bool supported(unsigned int i) const
Check whether position.
Definition int-dom.hpp:173
Gecode::Int::Linear::SupportSet::tell
ModEvent tell(Space &home, IntView &x) const
Perform tell according to recorded support information on.
Definition int-dom.hpp:193
Gecode::Int::Linear::SupportSet::SupportSet
SupportSet(void)
Default constructor.
Definition int-dom.hpp:163
Gecode::Int::Linear::SupportSet::support
void support(unsigned int i)
Record that there is support at position i.
Definition int-dom.hpp:169
Gecode::Int::Linear::SupportSet::init
void init(Region &r, unsigned int n)
Initialize support set with cardinality n.
Definition int-dom.hpp:165
Gecode::Int::ViewValues
Value iterator for integer views.
Definition view.hpp:94
Gecode::Iter::Ranges::ToValues< ViewRanges< IntView > >::operator++
void operator++(void)
Definition ranges-values.hpp:117
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::crazy
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Definition core.hpp:4769
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::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::BitSetBase
Basic bitset support.
Definition bitset-base.hpp:190
Gecode::Val
Gecode::View
Gecode::ViewArray
View arrays.
Definition array.hpp:253
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_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::Int::Linear
Linear propagators
Gecode::Int::Linear::prop_bnd
ExecStatus prop_bnd(Space &home, ModEventDelta med, Propagator &p, ViewArray< P > &x, ViewArray< N > &y, Val &c)
Definition int-nary.hpp:183
Gecode::Int
Finite domain integers.
Gecode::Int::ME_INT_FAILED
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition var-type.hpp:52
Gecode::Int::PC_INT_DOM
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode::Int::ME_INT_DOM
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
Gecode::Int::ME_INT_NONE
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition var-type.hpp:54
Gecode::Support::BSS_NONE
@ BSS_NONE
No bits set.
Definition bitset-base.hpp:131
Gecode::Support::BSS_ALL
@ BSS_ALL
All bits set.
Definition bitset-base.hpp:132
Gecode::Support::BSS_SOME
@ BSS_SOME
Some but not all bits set.
Definition bitset-base.hpp:133
Gecode
Gecode toplevel namespace
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
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56