complement.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>
*
* Contributing authors:
* 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.
*
*/
#include <sstream>
namespace Gecode { namespace Set {
template<class View>
forceinline
ComplementView<View>::ComplementView(void) {}
template<class View>
forceinline
ComplementView<View>::ComplementView(View& y)
: DerivedView<View>(y) {}
template<class View>
forceinline ModEvent
ComplementView<View>::me_negateset(ModEvent me) {
switch(me) {
case ME_SET_LUB : return ME_SET_GLB;
case ME_SET_GLB : return ME_SET_LUB;
case ME_SET_CLUB : return ME_SET_CGLB;
case ME_SET_CGLB : return ME_SET_CLUB;
default: return me;
}
}
template<class View>
forceinline PropCond
ComplementView<View>::pc_negateset(PropCond pc) {
switch(pc) {
case PC_SET_CLUB : return PC_SET_CGLB;
case PC_SET_CGLB : return PC_SET_CLUB;
default: return pc;
}
}
template<class View>
forceinline unsigned int
ComplementView<View>::glbSize(void) const {
return Limits::card - x.lubSize();
}
template<class View>
forceinline unsigned int
ComplementView<View>::lubSize(void) const {
return Limits::card - x.glbSize();
}
template<class View>
forceinline unsigned int
ComplementView<View>::unknownSize(void) const {
return lubSize() - glbSize();
}
template<class View>
forceinline bool
ComplementView<View>::contains(int n) const { return x.notContains(n); }
template<class View>
forceinline bool
ComplementView<View>::notContains(int n) const { return x.contains(n); }
template<class View>
forceinline unsigned int
ComplementView<View>::cardMin(void) const {
return Limits::card - x.cardMax();
}
template<class View>
forceinline unsigned int
ComplementView<View>::cardMax(void) const {
return Limits::card - x.cardMin();
}
template<class View>
forceinline int
ComplementView<View>::lubMin(void) const {
GlbRanges<View> lb(x);
RangesCompl<GlbRanges<View> > lbc(lb);
if (lbc()) {
return lbc.min();
} else {
return BndSet::MIN_OF_EMPTY;
}
}
template<class View>
forceinline int
ComplementView<View>::lubMax(void) const {
GlbRanges<View> lb(x);
RangesCompl<GlbRanges<View> > lbc(lb);
if (lbc()) {
while(lbc()) ++lbc;
return lbc.max();
} else {
return BndSet::MAX_OF_EMPTY;
}
}
template<class View>
forceinline int
ComplementView<View>::glbMin(void) const {
LubRanges<View> ub(x);
RangesCompl<LubRanges<View> > ubc(ub);
if (ubc()) {
return ubc.min();
} else {
return BndSet::MIN_OF_EMPTY;
}
}
template<class View>
forceinline int
ComplementView<View>::glbMax(void) const {
LubRanges<View> ub(x);
RangesCompl<LubRanges<View> > ubc(ub);
if (ubc()) {
while (ubc()) ++ubc;
return ubc.max();
} else {
return BndSet::MAX_OF_EMPTY;
}
}
template<class View>
forceinline ModEvent
ComplementView<View>::cardMin(Space& home, unsigned int c) {
if (c < Limits::card)
return me_negateset(x.cardMax(home, Limits::card - c));
return ME_SET_NONE;
}
template<class View>
forceinline ModEvent
ComplementView<View>::cardMax(Space& home, unsigned int c) {
if (c < Limits::card)
return me_negateset(x.cardMin(home, Limits::card - c));
return ME_SET_NONE;
}
template<class View>
forceinline ModEvent
ComplementView<View>::include(Space& home, int c) {
return me_negateset((x.exclude(home, c)));
}
template<class View>
forceinline ModEvent
ComplementView<View>::exclude(Space& home, int c) {
return me_negateset((x.include(home, c)));
}
template<class View>
forceinline ModEvent
ComplementView<View>::intersect(Space& home, int c) {
Iter::Ranges::Singleton si(c,c);
RangesCompl<Iter::Ranges::Singleton> csi(si);
return me_negateset((x.includeI(home, csi)));
}
template<class View>
forceinline ModEvent
ComplementView<View>::intersect(Space& home, int i, int j) {
Iter::Ranges::Singleton si(i,j);
RangesCompl<Iter::Ranges::Singleton> csi(si);
return me_negateset((x.includeI(home, csi)));
}
template<class View>
forceinline ModEvent
ComplementView<View>::include(Space& home, int j, int k) {
return me_negateset(x.exclude(home,j,k));
}
template<class View>
forceinline ModEvent
ComplementView<View>::exclude(Space& home, int j, int k) {
return me_negateset(x.include(home,j,k));
}
template<class View>
template<class I> ModEvent
ComplementView<View>::excludeI(Space& home,I& iter) {
return me_negateset(x.includeI(home,iter));
}
template<class View>
template<class I> ModEvent
ComplementView<View>::includeI(Space& home,I& iter) {
return me_negateset(x.excludeI(home,iter));
}
template<class View>
template<class I> ModEvent
ComplementView<View>::intersectI(Space& home,I& iter) {
RangesCompl<I> c(iter);
return me_negateset(x.includeI(home,c));
}
template<class View>
forceinline void
ComplementView<View>::subscribe(Space& home, Propagator& p, PropCond pc,
bool schedule) {
x.subscribe(home,p, pc_negateset(pc),schedule);
}
template<class View>
forceinline void
ComplementView<View>::cancel(Space& home, Propagator& p, PropCond pc) {
x.cancel(home,p, pc_negateset(pc));
}
template<class View>
forceinline void
ComplementView<View>::subscribe(Space& home, Advisor& a) {
x.subscribe(home,a);
}
template<class View>
forceinline void
ComplementView<View>::cancel(Space& home, Advisor& a) {
x.cancel(home,a);
}
template<class View>
forceinline void
ComplementView<View>::schedule(Space& home, Propagator& p, ModEvent me) {
return View::schedule(home,p,me_negateset(me));
}
template<class View>
forceinline ModEvent
ComplementView<View>::me(const ModEventDelta& med) {
return me_negateset(View::me(med));
}
template<class View>
forceinline ModEventDelta
ComplementView<View>::med(ModEvent me) {
return me_negateset(View::med(me));
}
/*
* Delta information for advisors
*
*/
template<class View>
forceinline ModEvent
ComplementView<View>::modevent(const Delta& d) {
return me_negateset(View::modevent(d));
}
template<class View>
forceinline int
ComplementView<View>::glbMin(const Delta& d) const {
return x.lubMin(d);
}
template<class View>
forceinline int
ComplementView<View>::glbMax(const Delta& d) const {
return x.lubMax(d);
}
template<class View>
forceinline bool
ComplementView<View>::glbAny(const Delta& d) const {
return x.lubAny(d);
}
template<class View>
forceinline int
ComplementView<View>::lubMin(const Delta& d) const {
return x.glbMin(d);
}
template<class View>
forceinline int
ComplementView<View>::lubMax(const Delta& d) const {
return x.glbMax(d);
}
template<class View>
forceinline bool
ComplementView<View>::lubAny(const Delta& d) const {
return x.glbAny(d);
}
template<class View>
class LubRanges<ComplementView<View> > {
private:
GlbRanges<View> lb;
RangesCompl<GlbRanges<View> > lbc;
public:
LubRanges(void) {}
LubRanges(const ComplementView<View>& x);
void init(const ComplementView<View>& x);
bool operator ()(void) const;
void operator ++(void);
int min(void) const;
int max(void) const;
unsigned int width(void) const;
};
template<class View>
forceinline
LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s)
: lb(s.base()), lbc(lb) {}
template<class View>
forceinline void
LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) {
lb.init(s.base());
lbc.init(lb);
}
template<class View>
forceinline bool
LubRanges<ComplementView<View> >::operator ()(void) const { return lbc(); }
template<class View>
forceinline void
LubRanges<ComplementView<View> >::operator ++(void) { return ++lbc; }
template<class View>
forceinline int
LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
template<class View>
forceinline int
LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
template<class View>
forceinline unsigned int
LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
template<class View>
class LubRanges<ComplementView<ComplementView<View> > > :
public LubRanges<View> {
public:
LubRanges(void) {}
LubRanges(const ComplementView<ComplementView<View> >& x);
void init(const ComplementView<ComplementView<View> >& x);
};
template<class View>
forceinline
LubRanges<ComplementView<ComplementView<View> > >::
LubRanges(const ComplementView<ComplementView<View> >& x) :
LubRanges<View>(x) {}
template<class View>
forceinline void
LubRanges<ComplementView<ComplementView<View> > >::
init(const ComplementView<ComplementView<View> >& x) {
LubRanges<View>::init(x);
}
template<class View>
class GlbRanges<ComplementView<View> > {
private:
LubRanges<View> ub;
RangesCompl<LubRanges<View> > ubc;
public:
GlbRanges(void) {}
GlbRanges(const ComplementView<View> & x);
void init(const ComplementView<View> & x);
bool operator ()(void) const;
void operator ++(void);
int min(void) const;
int max(void) const;
unsigned int width(void) const;
};
template<class View>
forceinline
GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s)
: ub(s.base()), ubc(ub) {}
template<class View>
forceinline void
GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) {
ub.init(s.base());
ubc.init(ub);
}
template<class View>
forceinline bool
GlbRanges<ComplementView<View> >::operator ()(void) const { return ubc(); }
template<class View>
forceinline void
GlbRanges<ComplementView<View> >::operator ++(void) { return ++ubc; }
template<class View>
forceinline int
GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
template<class View>
forceinline int
GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
template<class View>
forceinline unsigned int
GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
template<class View>
class GlbRanges<ComplementView<ComplementView<View> > > :
public GlbRanges<View> {
public:
GlbRanges(void) {}
GlbRanges(const ComplementView<ComplementView<View> >& x);
void init(const ComplementView<ComplementView<View> >& x);
};
template<class View>
forceinline
GlbRanges<ComplementView<ComplementView<View> > >::
GlbRanges(const ComplementView<ComplementView<View> >& x) :
GlbRanges<View>(x) {}
template<class View>
forceinline void
GlbRanges<ComplementView<ComplementView<View> > >::
init(const ComplementView<ComplementView<View> >& x) {
GlbRanges<View>::init(x);
}
template<class Char, class Traits, class View>
std::basic_ostream<Char,Traits>&
operator <<(std::basic_ostream<Char,Traits>& os,
const ComplementView<View>& x) {
std::basic_ostringstream<Char,Traits> s;
s.copyfmt(os); s.width(0);
s << "(" << x.base() << ")^C";
return os << s.str();
}
template<class View>
forceinline bool
operator ==(const ComplementView<View>& x, const ComplementView<View>& y) {
return x.base() == y.base();
}
template<class View>
forceinline bool
operator !=(const ComplementView<View>& x, const ComplementView<View>& y) {
return x.base() != y.base();
}
}}
// STATISTICS: set-var
Gecode::Advisor
Base-class for advisors.
Definition core.hpp:1292
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::DerivedView::base
View base(void) const
Return view from which this view is derived.
Definition view.hpp:605
Gecode::DerivedView::x
View x
View from which this view is derived.
Definition view.hpp:238
Gecode::DerivedView::DerivedView
DerivedView(void)
Default constructor.
Definition view.hpp:584
Gecode::Iter::Ranges::MinMax::min
int min(void) const
Return smallest value of range.
Definition ranges-minmax.hpp:99
Gecode::Iter::Ranges::MinMax::max
int max(void) const
Return largest value of range.
Definition ranges-minmax.hpp:103
Gecode::Iter::Ranges::Singleton
Range iterator for singleton range.
Definition ranges-singleton.hpp:42
Gecode::Propagator
Base-class for propagators.
Definition core.hpp:1064
Gecode::Set::BndSet::MAX_OF_EMPTY
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition var-imp.hpp:110
Gecode::Set::BndSet::MIN_OF_EMPTY
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition var-imp.hpp:112
Gecode::Set::ComplementView
Complement set view.
Definition view.hpp:769
Gecode::Set::ComplementView::glbAny
bool glbAny(const Delta &d) const
Test whether arbitrary values got pruned from glb.
Definition complement.hpp:303
Gecode::Set::ComplementView::me_negateset
static ModEvent me_negateset(ModEvent me)
Negate the modification event me.
Definition complement.hpp:53
Gecode::Set::ComplementView::include
ModEvent include(Space &home, int i, int j)
Update greatest lower bound to include all elements between and including i and j.
Definition complement.hpp:207
Gecode::Set::ComplementView::me
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition complement.hpp:268
Gecode::Set::ComplementView::contains
bool contains(int i) const
Test whether i is in the greatest lower bound.
Definition complement.hpp:93
Gecode::Set::ComplementView::cardMax
unsigned int cardMax(void) const
Return maximum cardinality.
Definition complement.hpp:107
Gecode::Set::ComplementView::lubSize
unsigned int lubSize(void) const
Return the number of elements in the least upper bound.
Definition complement.hpp:81
Gecode::Set::ComplementView::glbMin
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition complement.hpp:138
Gecode::Set::ComplementView::glbMax
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition complement.hpp:150
Gecode::Set::ComplementView::schedule
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition complement.hpp:263
Gecode::Set::ComplementView::lubMax
int lubMax(void) const
Return maximum of the least upper bound.
Definition complement.hpp:125
Gecode::Set::ComplementView::notContains
bool notContains(int i) const
Test whether i is not in the least upper bound.
Definition complement.hpp:97
Gecode::Set::ComplementView::lubMin
int lubMin(void) const
Return minimum of the least upper bound.
Definition complement.hpp:113
Gecode::Set::ComplementView::exclude
ModEvent exclude(Space &home, int i, int j)
Restrict least upper bound to not contain all elements between and including i and j.
Definition complement.hpp:213
Gecode::Set::ComplementView::subscribe
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition complement.hpp:238
Gecode::Set::ComplementView::intersect
ModEvent intersect(Space &home, int i, int j)
Update least upper bound to contain at most all elements between and including i and j.
Definition complement.hpp:199
Gecode::Set::ComplementView::pc_negateset
static PropCond pc_negateset(PropCond pc)
Negate the propagation condition pc.
Definition complement.hpp:65
Gecode::Set::ComplementView::intersectI
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition complement.hpp:231
Gecode::Set::ComplementView::ComplementView
ComplementView(void)
Default constructor.
Definition complement.hpp:44
Gecode::Set::ComplementView::glbSize
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition complement.hpp:75
Gecode::Set::ComplementView::lubAny
bool lubAny(const Delta &d) const
Test whether arbitrary values got pruned from lub.
Definition complement.hpp:321
Gecode::Set::ComplementView::cardMin
unsigned int cardMin(void) const
Return minimum cardinality.
Definition complement.hpp:101
Gecode::Set::ComplementView::cancel
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition complement.hpp:245
Gecode::Set::ComplementView::excludeI
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
Definition complement.hpp:219
Gecode::Set::ComplementView::includeI
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
Definition complement.hpp:225
Gecode::Set::ComplementView::med
static ModEventDelta med(ModEvent)
Translate modification event me to modification event delta for view.
Definition complement.hpp:274
Gecode::Set::ComplementView::unknownSize
unsigned int unknownSize(void) const
Return the number of unknown elements.
Definition complement.hpp:87
Gecode::Set::ComplementView::modevent
static ModEvent modevent(const Delta &d)
Return modification event.
Definition complement.hpp:285
Gecode::Set::GlbRanges< ComplementView< ComplementView< View > > >::GlbRanges
GlbRanges(void)
Default constructor.
Definition complement.hpp:519
Gecode::Set::GlbRanges< ComplementView< View > >::width
unsigned int width(void) const
Return width of ranges (distance between minimum and maximum).
Definition complement.hpp:502
Gecode::Set::GlbRanges< ComplementView< View > >::GlbRanges
GlbRanges(void)
Default constructor.
Definition complement.hpp:446
Gecode::Set::GlbRanges< ComplementView< View > >::init
void init(const ComplementView< View > &x)
Initialize with ranges for view x.
Definition complement.hpp:479
Gecode::Set::GlbRanges
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Gecode::Set::GlbRanges::operator()
bool operator()(void) const
Test whether iterator is still at a range or done.
Gecode::Set::GlbRanges::init
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
Gecode::Set::GlbRanges::min
int min(void) const
Return smallest value of range.
Gecode::Set::GlbRanges::max
int max(void) const
Return largest value of range.
Gecode::Set::GlbRanges::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum).
Gecode::Set::GlbRanges::operator++
void operator++(void)
Move iterator to next range (if possible).
Gecode::Set::GlbRanges::GlbRanges
GlbRanges(void)
Default constructor.
Gecode::Set::LubRanges< ComplementView< ComplementView< View > > >::LubRanges
LubRanges(void)
Default constructor.
Definition complement.hpp:412
Gecode::Set::LubRanges< ComplementView< View > >::init
void init(const ComplementView< View > &x)
Initialize with ranges for view x.
Definition complement.hpp:372
Gecode::Set::LubRanges< ComplementView< View > >::LubRanges
LubRanges(void)
Default constructor.
Definition complement.hpp:339
Gecode::Set::LubRanges< ComplementView< View > >::width
unsigned int width(void) const
Return width of ranges (distance between minimum and maximum).
Definition complement.hpp:395
Gecode::Set::LubRanges
Range iterator for the least upper bound.
Definition var-imp.hpp:317
Gecode::Set::LubRanges::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum).
Gecode::Set::LubRanges::LubRanges
LubRanges(void)
Default constructor.
Gecode::Set::LubRanges::init
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
Gecode::Set::LubRanges::max
int max(void) const
Return largest value of range.
Gecode::Set::LubRanges::operator()
bool operator()(void) const
Test whether iterator is still at a range or done.
Gecode::Set::LubRanges::operator++
void operator++(void)
Move iterator to next range (if possible).
Gecode::Set::LubRanges::min
int min(void) const
Return smallest value of range.
Gecode::Set::RangesCompl
A complement iterator spezialized for the BndSet limits.
Definition var-imp.hpp:293
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::View
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Gecode::Int::operator<<
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const IdxViewArray< View > &x)
Definition idx-view.hpp:167
Gecode::Int::operator==
bool operator==(const CachedView< View > &x, const CachedView< View > &y)
Definition cached.hpp:401
Gecode::Int::operator!=
bool operator!=(const CachedView< View > &x, const CachedView< View > &y)
Definition cached.hpp:406
Gecode::Set::Limits::card
const unsigned int card
Maximum cardinality of an integer set.
Definition set.hh:101
Gecode::Set
Finite integer sets.
Definition var-imp.hpp:137
Gecode::Set::ME_SET_CLUB
const Gecode::ModEvent ME_SET_CLUB
Domain operation has changed the least upper bound and the cardinality.
Definition var-type.hpp:179
Gecode::Set::ME_SET_NONE
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition var-type.hpp:140
Gecode::Set::ME_SET_GLB
const Gecode::ModEvent ME_SET_GLB
Domain operation has changed the greatest lower bound.
Definition var-type.hpp:164
Gecode::Set::ME_SET_CGLB
const Gecode::ModEvent ME_SET_CGLB
Domain operation has changed the greatest lower bound and the cardinality.
Definition var-type.hpp:186
Gecode::Set::PC_SET_CLUB
const Gecode::PropCond PC_SET_CLUB
Propagate when the cardinality or the least upper bound of a view changes.
Definition var-type.hpp:227
Gecode::Set::ME_SET_LUB
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition var-type.hpp:156
Gecode::Set::PC_SET_CGLB
const Gecode::PropCond PC_SET_CGLB
Propagate when the cardinality or the greatest lower bound of a view changes.
Definition var-type.hpp:238
Gecode
Gecode toplevel namespace
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Gecode::PropCond
int PropCond
Type for propagation conditions.
Definition core.hpp:72
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
forceinline
#define forceinline
Definition config.hpp:187