view.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
*
* Contributing authors:
* Christian Schulte <schulte@gecode.org>
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Patrick Pekczynski, 2004
* Christian Schulte, 2009
* Guido Tack, 2009
*
* This file is part of Gecode, the generic constrain
* 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 GCC {
template<class T>
forceinline bool
lookupValue(T& a, int v, int& i) {
int l = 0;
int r = a.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (v == a[m].card()) {
i=m; return true;
} else if (l == r) {
return false;
} else if (v < a[m].card()) {
r=m-1;
} else {
l=m+1;
}
}
return false;
}
class CardConst {
private:
int _min;
int _max;
int _card;
int _counter;
public:
static const bool propagate = false;
CardConst(void);
void init(Space& home, int min, int max, int c);
int min(void) const;
int max(void) const;
int card(void) const;
int counter(void) const;
bool assigned(void) const;
void counter(int n);
ModEvent inc(void);
ModEvent lq(Space& home, int n);
ModEvent gq(Space& home, int n);
ModEvent eq(Space& home, int n);
void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
void cancel(Space& home, Propagator& p, PropCond pc);
void reschedule(Space& home, Propagator& p, PropCond pc);
void update(Space& home, CardConst& x);
IntView base(void) const;
};
class CardView : public DerivedView<IntView> {
protected:
using DerivedView<IntView>::x;
int _card;
int _counter;
public:
static const bool propagate = true;
CardView(void);
void init(const IntView& y, int c);
void init(Space& home, const IntSet& s, int c);
int min(void) const;
int max(void) const;
unsigned int size(void) const;
int counter(void) const;
int card(void) const;
void counter(int n);
ModEvent inc(void);
ModEvent lq(Space& home, int n);
ModEvent gq(Space& home, int n);
ModEvent eq(Space& home, int n);
template<class I>
ModEvent narrow_v(Space& home, I& i, bool depends=true);
template<class I>
ModEvent inter_v(Space& home, I& i, bool depends=true);
template<class I>
ModEvent minus_v(Space& home, I& i, bool depends=true);
void update(Space& home, CardView& x);
};
/*
* Constant cardinality view
*
*/
forceinline
CardConst::CardConst(void) {}
forceinline void
CardConst::init(Space&, int min, int max, int c) {
_min = min; _max=max; _card = c; _counter = 0;
}
forceinline int
CardConst::min(void) const {
return _min;
}
forceinline int
CardConst::max(void) const {
return _max;
}
forceinline int
CardConst::card(void) const {
return _card;
}
forceinline int
CardConst::counter(void) const {
return _counter;
}
forceinline bool
CardConst::assigned(void) const {
return _min==_max;
}
forceinline void
CardConst::counter(int n) {
_counter = n;
}
forceinline ModEvent
CardConst::inc(void) {
if (++_counter > _max)
return ME_INT_FAILED;
return ME_INT_NONE;
}
forceinline ModEvent
CardConst::lq(Space&, int n) {
if (_min > n)
return ME_INT_FAILED;
return ME_INT_NONE;
}
forceinline ModEvent
CardConst::gq(Space&, int n) {
if (_max < n)
return ME_INT_FAILED;
return ME_INT_NONE;
}
forceinline ModEvent
CardConst::eq(Space&, int n) {
if ((_min > n) || (_max < n))
return ME_INT_FAILED;
return ME_INT_NONE;
}
forceinline void
CardConst::subscribe(Space&, Propagator&, PropCond, bool) {}
forceinline void
CardConst::cancel(Space&, Propagator&, PropCond) {}
forceinline void
CardConst::reschedule(Space&, Propagator&, PropCond) {}
forceinline void
CardConst::update(Space&, CardConst& x) {
_min=x._min; _max=x._max; _card=x._card; _counter=x._counter;
}
forceinline IntView
CardConst::base(void) const {
GECODE_NEVER;
return IntView();
}
/*
* Cardinality integer view
*
*/
forceinline
CardView::CardView(void) {}
forceinline void
CardView::init(const IntView& y, int c) {
x = y; _card = c; _counter = 0;
}
forceinline void
CardView::init(Space& home, const IntSet& s, int c) {
x = IntVar(home,s); _card = c; _counter = 0;
}
forceinline int
CardView::counter(void) const {
return _counter;
}
forceinline int
CardView::card(void) const {
return _card;
}
forceinline int
CardView::min(void) const {
return x.min();
}
forceinline int
CardView::max(void) const {
return x.max();
}
forceinline unsigned int
CardView::size(void) const {
return x.size();
}
forceinline void
CardView::counter(int n) {
_counter = n;
}
forceinline ModEvent
CardView::inc(void) {
if (++_counter > this->max())
return ME_INT_FAILED;
return ME_GEN_NONE;
}
forceinline ModEvent
CardView::lq(Space& home, int n) {
return x.lq(home,n);
}
forceinline ModEvent
CardView::gq(Space& home, int n) {
return x.gq(home,n);
}
forceinline ModEvent
CardView::eq(Space& home, int n) {
return x.eq(home,n);
}
template<class I>
forceinline ModEvent
CardView::narrow_v(Space& home, I& i, bool depends) {
return x.narrow_v(home,i,depends);
}
template<class I>
forceinline ModEvent
CardView::inter_v(Space& home, I& i, bool depends) {
return x.inter_v(home,i,depends);
}
template<class I>
forceinline ModEvent
CardView::minus_v(Space& home, I& i, bool depends) {
return x.minus_v(home,i,depends);
}
forceinline void
CardView::update(Space& home, CardView& y) {
x.update(home,y.x);
_card = y._card; _counter = y._counter;
}
}
template<>
class ViewRanges<GCC::CardView>
: public Gecode::Int::ViewRanges<IntView> {
public:
ViewRanges(void);
ViewRanges(const GCC::CardView& x);
void init(const GCC::CardView& x);
};
forceinline
ViewRanges<GCC::CardView>::ViewRanges(void) :
Gecode::Int::ViewRanges<IntView>() {}
forceinline
ViewRanges<GCC::CardView>::ViewRanges (const GCC::CardView& x)
: Gecode::Int::ViewRanges<IntView>(x.base()) {}
forceinline void
ViewRanges<GCC::CardView>::init(const GCC::CardView& x) {
Gecode::Int::ViewRanges<IntView> xi(x.base());
}
}}
// STATISTICS: int-prop
Gecode::DerivedView::base
View base(void) const
Return view from which this view is derived.
Definition view.hpp:605
Gecode::DerivedView< IntView >::x
IntView x
Definition view.hpp:238
Gecode::DerivedView< IntView >::DerivedView
DerivedView(void)
Definition view.hpp:584
Gecode::FloatVal::size
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::Int::GCC::CardConst::subscribe
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Cancel subscription of propagator p with propagation condition pc to view.
Definition view.hpp:273
Gecode::Int::GCC::CardConst::eq
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition view.hpp:266
Gecode::Int::GCC::CardConst::cancel
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition view.hpp:275
Gecode::Int::GCC::CardConst::card
int card(void) const
Return cardinality.
Definition view.hpp:230
Gecode::Int::GCC::CardConst::inc
ModEvent inc(void)
Increment counter.
Definition view.hpp:248
Gecode::Int::GCC::CardConst::min
int min(void) const
Return minimum of domain.
Definition view.hpp:222
Gecode::Int::GCC::CardConst::propagate
static const bool propagate
This view does not require propagation.
Definition view.hpp:77
Gecode::Int::GCC::CardConst::counter
int counter(void) const
Return the number of times the value occurs.
Definition view.hpp:234
Gecode::Int::GCC::CardConst::init
void init(Space &home, int min, int max, int c)
Initialize with min, max, and cardinality c.
Definition view.hpp:217
Gecode::Int::GCC::CardConst::gq
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition view.hpp:260
Gecode::Int::GCC::CardConst::max
int max(void) const
Return maximum of domain.
Definition view.hpp:226
Gecode::Int::GCC::CardConst::update
void update(Space &home, CardConst &x)
Definition view.hpp:280
Gecode::Int::GCC::CardConst::assigned
bool assigned(void) const
Definition view.hpp:238
Gecode::Int::GCC::CardConst::CardConst
CardConst(void)
Default constructor.
Definition view.hpp:215
Gecode::Int::GCC::CardConst::reschedule
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition view.hpp:277
Gecode::Int::GCC::CardConst::lq
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition view.hpp:254
Gecode::Int::GCC::CardConst::base
IntView base(void) const
Return used IntView (cannot be used).
Definition view.hpp:285
Gecode::Int::GCC::CardView
Cardinality integer view.
Definition view.hpp:140
Gecode::Int::GCC::CardView::eq
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition view.hpp:347
Gecode::Int::GCC::CardView::minus_v
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition view.hpp:363
Gecode::Int::GCC::CardView::card
int card(void) const
Return cardinality.
Definition view.hpp:312
Gecode::Int::GCC::CardView::_counter
int _counter
Counter.
Definition view.hpp:146
Gecode::Int::GCC::CardView::counter
int counter(void) const
Return the number of times the value occurs.
Definition view.hpp:308
Gecode::Int::GCC::CardView::size
unsigned int size(void) const
Return size (cardinality) of domain.
Definition view.hpp:324
Gecode::Int::GCC::CardView::init
void init(const IntView &y, int c)
Initialize with integer view y and value c.
Definition view.hpp:299
Gecode::Int::GCC::CardView::min
int min(void) const
Return minimum of domain.
Definition view.hpp:316
Gecode::Int::GCC::CardView::inter_v
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition view.hpp:358
Gecode::Int::GCC::CardView::update
void update(Space &home, CardView &x)
Definition view.hpp:368
Gecode::Int::GCC::CardView::_card
int _card
Cardinality.
Definition view.hpp:144
Gecode::Int::GCC::CardView::lq
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition view.hpp:339
Gecode::Int::GCC::CardView::gq
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition view.hpp:343
Gecode::Int::GCC::CardView::CardView
CardView(void)
Default constructor.
Definition view.hpp:297
Gecode::Int::GCC::CardView::propagate
static const bool propagate
This view does require propagation.
Definition view.hpp:149
Gecode::Int::GCC::CardView::max
int max(void) const
Return maximum of domain.
Definition view.hpp:320
Gecode::Int::GCC::CardView::inc
ModEvent inc(void)
Increment counter.
Definition view.hpp:333
Gecode::Int::GCC::CardView::narrow_v
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition view.hpp:353
Gecode::Int::IntView
Integer view for integer variables.
Definition view.hpp:129
Gecode::Int::ViewRanges< GCC::CardView >::ViewRanges
ViewRanges(void)
Initialize with ranges for view x.
Definition view.hpp:395
Gecode::Int::ViewRanges
Range iterator for integer views.
Definition view.hpp:54
Gecode::Int::ViewRanges::init
void init(const View &x)
Initialize with ranges for view x.
Gecode::Int::ViewRanges::ViewRanges
ViewRanges(void)
Default constructor.
Gecode::Propagator
Base-class for propagators.
Definition core.hpp:1064
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Int::GCC
Global cardinality propagators (Counting).
Gecode::Int::GCC::lookupValue
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition view.hpp:45
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::ME_INT_NONE
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition var-type.hpp:54
Gecode
Gecode toplevel namespace
Gecode::ME_GEN_NONE
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition core.hpp:67
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
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56