lq.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, 2011
*
* 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 Rel {
class CharacteristicSets {
protected:
unsigned int xsize;
Support::BitSetBase b;
int* ub;
bool xlm;
bool xum;
bool ylm;
bool yum;
bool get(unsigned int i) const;
void set(unsigned int i, bool j);
class CSIter {
public:
CharacteristicSets* cs;
unsigned int i;
unsigned int xoff;
unsigned int yoff;
void operator++ (void);
CSIter(void);
CSIter(CharacteristicSets& cs0, unsigned int xoff0, unsigned int yoff0);
bool operator() (void) const;
int val(void) const;
};
public:
template<class View0, class View1>
CharacteristicSets(Region& re, View0 x, View1 y);
bool xmin(unsigned int i) const;
bool xmax(unsigned int i) const;
bool ymin(unsigned int i) const;
bool ymax(unsigned int i) const;
void xmin(unsigned int i, bool j);
void xmax(unsigned int i, bool j);
void ymin(unsigned int i, bool j);
void ymax(unsigned int i, bool j);
ModEvent xlq(unsigned int i, bool j);
ModEvent xgq(unsigned int i, bool j);
ModEvent ylq(unsigned int i, bool j);
ModEvent ygq(unsigned int i, bool j);
unsigned int size(void) const;
template<class View0, class View1>
ExecStatus prune(Space& home, View0 x, View1 y);
};
forceinline bool
CharacteristicSets::get(unsigned int i) const {
return b.get(i);
}
forceinline void
CharacteristicSets::set(unsigned int i, bool j) {
if (j)
b.set(i);
else
b.clear(i);
}
forceinline unsigned int
CharacteristicSets::size(void) const {
return xsize;
}
forceinline
CharacteristicSets::CSIter::CSIter(void) {}
forceinline
CharacteristicSets::CSIter::CSIter(CharacteristicSets& cs0,
unsigned int xoff0, unsigned int yoff0)
: cs(&cs0), i(0), xoff(xoff0), yoff(yoff0) {
while ((i < cs->xsize) && !cs->get(xoff+2*i+yoff))
i++;
}
forceinline void
CharacteristicSets::CSIter::operator++ (void) {
i++;
while ((i < cs->xsize) && !cs->get(xoff+2*i+yoff))
i++;
}
forceinline bool
CharacteristicSets::CSIter::operator() (void) const {
return i<cs->xsize;
}
forceinline int
CharacteristicSets::CSIter::val(void) const {
return cs->ub[i];
}
forceinline bool
CharacteristicSets::xmin(unsigned int i) const {
return get(2*i);
}
forceinline bool
CharacteristicSets::xmax(unsigned int i) const {
return get(2*i+1);
}
forceinline bool
CharacteristicSets::ymin(unsigned int i) const {
return get(2*xsize+2*i);
}
forceinline bool
CharacteristicSets::ymax(unsigned int i) const {
return get(2*xsize+2*i+1);
}
forceinline void
CharacteristicSets::xmin(unsigned int i, bool j) {
set(2*i,j);
}
forceinline void
CharacteristicSets::xmax(unsigned int i, bool j) {
set(2*i+1,j);
}
forceinline void
CharacteristicSets::ymin(unsigned int i, bool j) {
set(2*xsize+2*i,j);
}
forceinline void
CharacteristicSets::ymax(unsigned int i, bool j) {
set(2*xsize+2*i+1,j);
}
forceinline ModEvent
CharacteristicSets::xlq(unsigned int i, bool j) {
if (!j) {
if (xmin(i)) return ME_SET_FAILED;
if (xmax(i)) {
xmax(i,false);
xum=true;
}
}
return ME_SET_NONE;
}
forceinline ModEvent
CharacteristicSets::xgq(unsigned int i, bool j) {
if (j) {
if (!xmax(i)) return ME_SET_FAILED;
if (!xmin(i)) {
xmin(i,true);
xlm=true;
}
}
return ME_SET_NONE;
}
forceinline ModEvent
CharacteristicSets::ylq(unsigned int i, bool j) {
if (!j) {
if (ymin(i)) return ME_SET_FAILED;
if (ymax(i)) {
ymax(i,false);
yum=true;
}
}
return ME_SET_NONE;
}
forceinline ModEvent
CharacteristicSets::ygq(unsigned int i, bool j) {
if (j) {
if (!ymax(i)) return ME_SET_FAILED;
if (!ymin(i)) {
ymin(i,true);
ylm=true;
}
}
return ME_SET_NONE;
}
template<class View0, class View1>
forceinline ExecStatus
CharacteristicSets::prune(Space& home, View0 x, View1 y) {
if (xlm) {
CSIter i(*this,0,0);
Iter::Values::ToRanges<CSIter> ir(i);
GECODE_ME_CHECK(x.includeI(home,ir));
}
if (xum) {
CSIter i(*this,0,1);
Iter::Values::ToRanges<CSIter> ir(i);
GECODE_ME_CHECK(x.intersectI(home,ir));
}
if (ylm) {
CSIter i(*this,2*xsize,0);
Iter::Values::ToRanges<CSIter> ir(i);
GECODE_ME_CHECK(y.includeI(home,ir));
}
if (yum) {
CSIter i(*this,2*xsize,1);
Iter::Values::ToRanges<CSIter> ir(i);
GECODE_ME_CHECK(y.intersectI(home,ir));
}
return ES_OK;
}
template<class View0, class View1>
forceinline
CharacteristicSets::CharacteristicSets(Region& re,View0 x, View1 y)
: xlm(false), xum(false), ylm(false), yum(false) {
LubRanges<View0> xlub(x);
LubRanges<View1> ylub(y);
Iter::Ranges::Union<LubRanges<View0>,LubRanges<View1> > xylub(xlub,ylub);
Iter::Ranges::Cache xylubc(re,xylub);
xsize = Iter::Ranges::size(xylubc);
b.init(re,4*xsize);
ub = re.alloc<int>(xsize);
xylubc.reset();
Iter::Ranges::ToValues<Iter::Ranges::Cache> xylubv(xylubc);
LubRanges<View0> xur(x);
GlbRanges<View0> xlr(x);
LubRanges<View1> yur(y);
GlbRanges<View1> ylr(y);
Iter::Ranges::ToValues<LubRanges<View0> > xuv(xur);
Iter::Ranges::ToValues<GlbRanges<View0> > xlv(xlr);
Iter::Ranges::ToValues<LubRanges<View1> > yuv(yur);
Iter::Ranges::ToValues<GlbRanges<View1> > ylv(ylr);
for (unsigned int i=0; xylubv(); ++xylubv, ++i) {
ub[i] = xylubv.val();
if (xlv() && xylubv.val()==xlv.val()) {
b.set(2*i);
++xlv;
}
if (xuv() && xylubv.val()==xuv.val()) {
b.set(2*i+1);
++xuv;
}
if (ylv() && xylubv.val()==ylv.val()) {
b.set(2*xsize+2*i);
++ylv;
}
if (yuv() && xylubv.val()==yuv.val()) {
b.set(2*xsize+2*i+1);
++yuv;
}
}
}
template<class View0, class View1, bool strict>
forceinline
Lq<View0,View1,strict>::Lq(Home home, View0 x, View1 y)
: MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {}
template<class View0, class View1, bool strict>
forceinline
Lq<View0,View1,strict>::Lq(Space& home, Lq& p)
: MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,p) {}
template<class View0, class View1, bool strict>
ExecStatus
Lq<View0,View1,strict>::post(Home home, View0 x, View1 y) {
if (strict)
GECODE_ME_CHECK(y.cardMin(home,1));
if (same(x,y))
return strict ? ES_FAILED : ES_OK;
(void) new (home) Lq(home,x,y);
return ES_OK;
}
template<class View0, class View1, bool strict>
Actor*
Lq<View0,View1,strict>::copy(Space& home) {
return new (home) Lq(home,*this);
}
template<class View0, class View1, bool strict>
ExecStatus
Lq<View0,View1,strict>::propagate(Space& home, const ModEventDelta&) {
if ( (!strict) && x1.cardMax()==0) {
GECODE_ME_CHECK(x0.cardMax(home,0));
}
if (x0.cardMax()==0) {
return home.ES_SUBSUMED(*this);
}
if (x0.glbMin() < x1.lubMin())
return ES_FAILED;
if (x1.glbMin() < x0.lubMin())
return home.ES_SUBSUMED(*this);
bool assigned = x0.assigned() && x1.assigned();
Region re;
CharacteristicSets cs(re,x0,x1);
/*
* State 1
*
*/
unsigned int i=0;
unsigned int firsti=0;
unsigned int n=cs.size();
while ((i<n) && (cs.xmin(i) == cs.ymax(i))) {
// case: =, >=
GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i)));
GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i)));
i++;
}
if (i == n) {// case: $
if (strict) {
return ES_FAILED;
} else {
GECODE_ES_CHECK(cs.prune(home,x0,x1));
return home.ES_SUBSUMED(*this);
}
}
// Possible cases left: <, <=, > (yields failure), ?
GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i)));
GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i)));
if (cs.xmax(i) < cs.ymin(i)) { // case: < (after tell)
GECODE_ES_CHECK(cs.prune(home,x0,x1));
return home.ES_SUBSUMED(*this);
}
firsti=i;
/*
* State 2
* prefix: (?|<=)
*
*/
i++;
while ((i < n) &&
(cs.xmin(i) == cs.ymax(i)) &&
(cs.xmax(i) == cs.ymin(i))) { // case: =
i++;
}
if (i == n) { // case: $
if (strict)
goto rewrite_le;
else
goto rewrite_lq;
}
if (cs.xmax(i) < cs.ymin(i)) // case: <
goto rewrite_lq;
if (cs.xmin(i) > cs.ymax(i)) // case: >
goto rewrite_le;
if (cs.xmax(i) <= cs.ymin(i)) {
// case: <= (invariant: not =, <)
/*
* State 3
* prefix: (?|<=),<=
*
*/
i++;
while ((i < n) && (cs.xmax(i) == cs.ymin(i))) {// case: <=, =
i++;
}
if (i == n) { // case: $
if (strict) {
GECODE_ES_CHECK(cs.prune(home,x0,x1));
return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
} else {
goto rewrite_lq;
}
}
if (cs.xmax(i) < cs.ymin(i)) // case: <
goto rewrite_lq;
GECODE_ES_CHECK(cs.prune(home,x0,x1));
return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
}
if (cs.xmin(i) >= cs.ymax(i)) {
// case: >= (invariant: not =, >)
/*
* State 4
* prefix: (?|<=) >=
*
*/
i++;
while ((i < n) && (cs.xmin(i) == cs.ymax(i))) {
// case: >=, =
i++;
}
if (i == n) { // case: $
if (strict) {
goto rewrite_le;
} else {
GECODE_ES_CHECK(cs.prune(home,x0,x1));
return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
}
}
if (cs.xmin(i) > cs.ymax(i)) // case: >
goto rewrite_le;
GECODE_ES_CHECK(cs.prune(home,x0,x1));
return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
}
GECODE_ES_CHECK(cs.prune(home,x0,x1));
return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
rewrite_le:
GECODE_ME_CHECK(cs.xlq(firsti,false));
GECODE_ME_CHECK(cs.ygq(firsti,true));
GECODE_ES_CHECK(cs.prune(home,x0,x1));
return home.ES_SUBSUMED(*this);
rewrite_lq:
GECODE_ES_CHECK(cs.prune(home,x0,x1));
return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
}
}}}
// STATISTICS: set-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::Rel::Lq::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition lq-le.hpp:71
Gecode::Int::Rel::Lq::post
static ExecStatus post(Home home, V0 x0, V1 x1)
Post propagator .
Definition lq-le.hpp:50
Gecode::Int::Rel::Lq::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition lq-le.hpp:65
Gecode::Int::Rel::Lq::Lq
Lq(Space &home, Lq &p)
Constructor for cloning p.
Definition lq-le.hpp:60
Gecode::Iter::Ranges::Cache
Range iterator cache
Definition ranges-cache.hpp:45
Gecode::Iter::Ranges::RangeListIter::reset
void reset(void)
Reset iterator to start.
Definition ranges-list.hpp:240
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::Iter::Values::ToRanges
Range iterator from value iterator.
Definition values-ranges.hpp:46
Gecode::MixBinaryPropagator< View0, PC_SET_ANY, View1, PC_SET_ANY >::x1
View1 x1
Definition pattern.hpp:209
Gecode::MixBinaryPropagator< View0, PC_SET_ANY, View1, PC_SET_ANY >::MixBinaryPropagator
MixBinaryPropagator(Space &home, MixBinaryPropagator &p)
Definition pattern.hpp:597
Gecode::MixBinaryPropagator< View0, PC_SET_ANY, View1, PC_SET_ANY >::x0
View0 x0
Definition pattern.hpp:207
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Region::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
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::Rel::CharacteristicSets::CSIter
Value iterator for characteristic function.
Definition lq.hpp:61
Gecode::Set::Rel::CharacteristicSets::CSIter::xoff
unsigned int xoff
Offset from start of bitset.
Definition lq.hpp:68
Gecode::Set::Rel::CharacteristicSets::CSIter::CSIter
CSIter(void)
Default constructor.
Definition lq.hpp:142
Gecode::Set::Rel::CharacteristicSets::CSIter::i
unsigned int i
Current position.
Definition lq.hpp:66
Gecode::Set::Rel::CharacteristicSets::CSIter::operator()
bool operator()(void) const
Test if iterator is finished.
Definition lq.hpp:157
Gecode::Set::Rel::CharacteristicSets::CSIter::yoff
unsigned int yoff
Offset for each element (0=lower bound, 1=upper bound).
Definition lq.hpp:70
Gecode::Set::Rel::CharacteristicSets::CSIter::operator++
void operator++(void)
Move iterator to next element.
Definition lq.hpp:151
Gecode::Set::Rel::CharacteristicSets::CSIter::val
int val(void) const
Value of current iterator position.
Definition lq.hpp:161
Gecode::Set::Rel::CharacteristicSets::CSIter::cs
CharacteristicSets * cs
Pointer to the underlying set.
Definition lq.hpp:64
Gecode::Set::Rel::CharacteristicSets
Representation of the characteristic functions of two sets.
Definition lq.hpp:39
Gecode::Set::Rel::CharacteristicSets::yum
bool yum
Whether upper bound of y was updated.
Definition lq.hpp:54
Gecode::Set::Rel::CharacteristicSets::xlq
ModEvent xlq(unsigned int i, bool j)
Update upper bound of to j.
Definition lq.hpp:201
Gecode::Set::Rel::CharacteristicSets::ub
int * ub
Elements in the combined upper bounds.
Definition lq.hpp:46
Gecode::Set::Rel::CharacteristicSets::size
unsigned int size(void) const
Return size of combined upper bounds.
Definition lq.hpp:137
Gecode::Set::Rel::CharacteristicSets::xlm
bool xlm
Whether lower bound of x was updated.
Definition lq.hpp:48
Gecode::Set::Rel::CharacteristicSets::set
void set(unsigned int i, bool j)
Set bit i to value j.
Definition lq.hpp:130
Gecode::Set::Rel::CharacteristicSets::xmin
bool xmin(unsigned int i) const
Return minimum of element i for variable x.
Definition lq.hpp:167
Gecode::Set::Rel::CharacteristicSets::get
bool get(unsigned int i) const
Get bit i.
Definition lq.hpp:126
Gecode::Set::Rel::CharacteristicSets::xmax
bool xmax(unsigned int i) const
Return maximum of element i for variable x.
Definition lq.hpp:171
Gecode::Set::Rel::CharacteristicSets::xum
bool xum
Whether upper bound of x was updated.
Definition lq.hpp:50
Gecode::Set::Rel::CharacteristicSets::ymin
bool ymin(unsigned int i) const
Return minimum of element i for variable y.
Definition lq.hpp:175
Gecode::Set::Rel::CharacteristicSets::xgq
ModEvent xgq(unsigned int i, bool j)
Update lower bound of to j.
Definition lq.hpp:212
Gecode::Set::Rel::CharacteristicSets::xsize
unsigned int xsize
Size of the combined upper bounds.
Definition lq.hpp:42
Gecode::Set::Rel::CharacteristicSets::ylq
ModEvent ylq(unsigned int i, bool j)
Update upper bound of to j.
Definition lq.hpp:223
Gecode::Set::Rel::CharacteristicSets::prune
ExecStatus prune(Space &home, View0 x, View1 y)
Prune x and y using computed bounds.
Definition lq.hpp:247
Gecode::Set::Rel::CharacteristicSets::ylm
bool ylm
Whether lower bound of y was updated.
Definition lq.hpp:52
Gecode::Set::Rel::CharacteristicSets::ygq
ModEvent ygq(unsigned int i, bool j)
Update lower bound of to j.
Definition lq.hpp:234
Gecode::Set::Rel::CharacteristicSets::CharacteristicSets
CharacteristicSets(Region &re, View0 x, View1 y)
Constructor.
Definition lq.hpp:273
Gecode::Set::Rel::CharacteristicSets::ymax
bool ymax(unsigned int i) const
Return maximum of element i for variable y.
Definition lq.hpp:179
Gecode::Set::Rel::CharacteristicSets::b
Support::BitSetBase b
Storage for the characteristic functions.
Definition lq.hpp:44
Gecode::Set::Rel::Lq::Lq
Lq(Space &home, Lq &p)
Constructor for cloning p.
Definition lq.hpp:320
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::BitSetBase
Basic bitset support.
Definition bitset-base.hpp:190
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::Iter::Ranges::size
unsigned int size(I &i)
Size of all ranges of range iterator i.
Definition ranges-operations.hpp:74
Gecode::Set::Rel
Standard set relation propagators.
Definition rel.hh:45
Gecode::Set
Finite integer sets.
Definition var-imp.hpp:137
Gecode::Set::ME_SET_NONE
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition var-type.hpp:140
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::same
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1937
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
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::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
forceinline
#define forceinline
Definition config.hpp:187